Process Priority

우선순위가 높은 프로세스 : CPU 먼저 & 더 오래 차지함

• 우선순위 : Kernel process > User process

 

 

 

 

 

• CPU burst : running 상태에서 CPU를 집중적으로 쓰는 시간
• I/O burst : waiting 상태에서 I/O를 집중적으로 하는 시간

 

 

 

 

CPU bound process : CPU burst > I/O burst 인 프로세스

 

 

I/O bound process : I/O burst > CPU burst 인 프로세스

 

 

I/O bound process > CPU bound process 우선 순위일 때 시스템의 효율성이 향상됨

이유 : I/O 할 때 CPU bound process가 CPU에 바로 접근 가능하기 때문 (Context Switching 비용 절감)

 

 

 

 

 

 

---

 

 

• Ready Queue : `우선 순위에 따라 다중 큐`로 구성
• Waiting Queue : `입출력 장치 종류에 따라 다중 큐`로 구성

 

 

---

 

 

• Long-term scheduling : 실행 가능한 프로세스 수 결정 
• Middle-term scheduling : 이미 활성화된 프로세스 수 결정
• Short-term scheduling : 일반적인 CPU 스케줄링을 의미

 

 

 

 

 

 

 

 

 

구분	비선점형 스케줄링	선점형 스케줄링
방식	실행 중인 프로세스로부터 CPU를 뺏을 수 없음	실행 중인 프로세스의 CPU를 빼앗아 다른 프로세스를 실행 가능 RR 스케줄링
장점	드문 문맥 교환(context switch)로 인해 오버헤드 작음	빠른응답시간 을 요구하는 시스템에 적합
단점	거의 사용되지 않음	Time slice가 작으면 잦은 문맥 교환로 인 한 오버헤드가 큼
사용	일괄 작업 시스템	시분할 시스템
알고리즘	FCFS, SJF, HRN	RR, SRT, MLQ, MLFQ

 

 

 

 

스케줄링 알고리즘 선택 기준

1. CPU 사용률 (CPU utilization)
2. 처리량 (throughput)
3. 대기 시간 (waiting time)
4. 응답 시간 (response time)
5. 반환 시간(turnaround time)

 

 

 

 

 

---

 비선점 : FCFS (First Come First Served)

 

단점 : convoy effect 발생

 → 순차 진행되므로 앞에서 큰 프로세스 실행하는 동안 뒤의 프로세스는 밀림

 

 

 

 

 

 

---

비선점 : SJF (Shortest Job First)

 

단점 : starvation 발생

 → 우선순위가 높은 프로세스가 먼저 실행되면 우선 순위가 낮은 프로세스는 실행이 계속 지연

 

 

 

 

 

---

비선점 : HRN (Highest Response Ratio Next)

 

 

우선순위 : (대기 시간 + 실행 시간) / 실행시간

값이 클수록 우선순위 높음

 

단점 : starvation 발생

 → SJF 보다 완화되었지만 여전히 starvation 발생

 

 

 

 

 

---

선점 : RR (Round Robin)

 

 

Time Slice 이용 (시분할 시스템 적용한 FCFS)

 

 

• Time slice 큰 경우 : FCFS와 같아짐
• Time slice 작은 경우 : 잦은 context switching으로 오버헤드 커짐

 

 

 

 

 

---

선점 : SRT (Shortest Remaining Time)

 

 

RR 선점형 방식으로 진행되지만 준비 큐에 남은 실행시간이 짧은 프로세스에게 높은 우선순위 부여

 

 

 

단점 : starvation 발생

 

 

 

 

 

---

선점 : MLQ (Multilevel Queue)

 

 

우선순위에 따라 여러 준비 큐(Ready Queue) 사용 - 고정 우선순위 방식

각 Queue는 RR 스케줄링 이용

 

 

 

 

단점 : starvation 발생

 

 

 

MLQ

 

 

 

 

 

---

선점 : MLFQ (Multilevel Feedback Queue)

 

 

우선순위에 따라 여러 준비 큐(Ready Queue) 사용 - 변동  우선순위 방식

각 Queue는 RR 스케줄링 이용

 

 

변동 우선순위 방식

time slice동안 실행 후 작업이 완료되지 않으면 우선순위가 낮아짐 

→ 우선순위가 하나 낮은 큐의 끝으로 이동 (starvation 완화)

 

 

 

 

 

 

MLFQ