Process Scheduler
Basic Concept of CPU scheduling
-
CPU의 사용률을 극대화하고, 프로세스는 빠르게 스위칭하며 time sharing한다.
-
CPU burst와 I/O burst
- CPU burst: CPU에서 연산하는 시간
- I/O burst: I/O 요청을 기다리는 시간
- 프로세스 실행은 CPU burst와 I/O burst의 반복으로 이루어져 있다.
- 주로 CPU burst가 메인이다.
CPU Scheduler
-
CPU 스케줄러는 실행 준비가 된 메모리의 프로세스 중 하나를 선택하고, CPU를 할당한다.
-
CPU 스케줄링 결정은 프로세스가 진행될 때 수행된다.
- running -> waiting: I/O burst로 전환. 더 이상 CPU에서 일할 수 없으므로 다른 프로세스로 교체되는 경우
- running -> ready: OS가 강제적으로 끌어내린 경우이다. 정기적으로 발생할 수 있다.
- waiting -> ready: I/O request가 완료되어 interrupt 발생
- terminates
-> 1번과 4번은 non-preemptive, 2번과 3번은 preemptive이다.
-
CPU Scheduler는 시스템 디자인 규율에 따라 디자인된다.
- Policy와 mechanism으로 나누어진다.
- Policy: 어떤 프로세스를 선택할지 결정
- mechanism: 기계적으로 스케줄링하는 과정
Dispatcher
-
프로세스를 실행하는 OS의 가장 안쪽 부분.
-
유저 프로그램과 유저 프로그램이 수행되는 중간에 개입하여 CPU를 넘겨 주는 역할을 수행한다.
-
CPU 스케쥴러에 의해 선택된 프로세스에 CPU 관리 권한을 넘겨 준다.
-
dispatcher는 어떻게 관리되는가?
- CPU는 동시에 하나만 수행할 수 있다. dispatcher도 CPU를 차지한다.
- 따라서 User processes가 실행 중인 경우에는 dispatcher는 실행 상태가 아니다.
-
dispatcher가 관리 권한을 되찾는 방법
Non-preemptive way:
프로세스가 dispatcher를 불러줄 것이라고 신뢰하는 방법. 프로세스가 자발적으로 CPU를 양보해 줄 때까지 기다린다.Preemptive way:
일정한 때에 dispatcher에게로 권한이 넘어간다. -> Timer 하드웨어와 interrupt를 이용하여, 운영체제가 강제로 프로세스로부터 CPU를 빼앗아 넘긴다.-
제어권이 OS에게 있는 경우
- Traps and Faults: 프로세스 내부에서 이벤트 발생
- interrupts: CPU 외부에서 이벤트 발생
-
Scheduling Policy
-
Dispatcher가 제어하게 되면, 어떻게 다음 프로세스를 결정하는가?
-
Possibility 1: 프로세스 테이블에서 제일 처음에 실행 가능한 프로세스를 찾는다.
- 검색하는데 시간이 많이 소요되며, 결과가 모호할 수 있다.
-
Possibility 2: 실행 가능한 프로세스를 ready queue에 linked list 형태로 연결한다.
- dispatcher가 queue의 head에서 가져온다.
- 실행 가능한 프로세스는 queue의 제일 뒤에 삽입된다.
-
Possibility 3: 프로세스에 우선순위를 부여한다.
- queue는 우선순위대로 정렬된다.
-
누가 우선순위를 결정하는가?
=> Scheduler
- 왜 Dispatcher가 우선순위를 결정하지 않을까?
=> Policy와 mechanism의 분리를 위해서.
Scheduling Policies
Scheduling Criteria
-
CPU utilizaiton: CPU 사용률을 최대로, CPU가 최대한 일을 하는가?
-
Throughput: 주어진 시간 동안 얼마나 더 많은 프로세스가 일을 마치는가?
- CPU utilization과 Throughput은 연관은 있으나 항상 비례하는 관계는 아니다.
-
Turnaround time, Execution time: 일을 시작하고 끝내기까지 얼마나 걸리는가?
-
Waiting time: 각 프로세스가 얼마나 ready queue에서 대기하는가?
-
Response time: 응답시간. 예를 들어 I/O로 인해 output이 나오기까지 걸리는 시간
Scheduling Algorithms
- CPU scheduler가 사용하는 알고리즘
- scheduling disciplines: FIFO, SJF, RR, MLFQ 등
First-Come, First-Served (FCFS)
- 처음으로 들어온 것이 종료될 때까지 실행한다.
- 다른 프로세스가 대기하는 동안 한 프로세스만이 CPU를 사용할 수 있다.
- ready queue로 들어갈 때는 제일 뒤로 들어간다.
- Problem: 매우 큰 크기의 하나의 프로세스가 CPU를 독점할 수 있다.
- Solution: time slice를 이용해 일정한 시간이 지나면 context switching 해 주도록 한다.
FCFS Example
| Process | CPU Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
-
프로세스의 도착 순서가 P1 -> P2 -> P3일 때
- Waiting Time: P1 = 0, P2 = 24, P3 = 27
- Average waiting time = 17
- P1이 24 time이 걸림으로 인해, P2와 P3의 대기시간이 길어졌다.
-
프로세스의 도착 순서가 P2 -> P3 -> P1일 때
- Waiting Time: P1 = 6, P2 = 0, P3 = 3
- Average waiting time = 3
Convoy effect란, 하나의 긴 프로세스로 인해 다른 여러 프로세스가 기다리게 되는 현상을 말한다.
Shortest Job First (SJF)
-
프로세스의 시간이 가장 짧은 것부터 수행한다.
-
SJF is Optimal - 가장 작은 Average waiting time이 나온다. SJF 방법은 가장 최적하다.
- 그러나 다음 CPU의 CPU burst를 예측하기란, 상당히 어려우므로 실제로 구현하기는 어렵다.
=> SJF를 이상값 (ideal)으로 두고, 이 결과에 근접할수록 좋은 알고리즘이라고 본다.
- 그러나 다음 CPU의 CPU burst를 예측하기란, 상당히 어려우므로 실제로 구현하기는 어렵다.
-
SJF의 두 가지 종류
- Non-preemptive: CPU가 프로세스에 할당되면, 현재 CPU burst가 끝나기 전까지 새로운 프로세스를 쓸 수 없다.
- Preemptive: 새로운 프로세스가 현재 실행 중인 프로세스의 남은 CPU burst보다 짧으면 새로운 프로세스 먼저 처리한다.
SJF Example
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
-
SJF non-preemptive
- P1이 먼저 도착하므로 P1 먼저 실행 → non-preemptive는 한 번 실행한 것은 끝내야 하므로 7까지 진행 → Queue에 있는 것 중, 가장 Burst Time이 짧은 P3 → P2 → P4
- Waiting Time P1 = 0, P2 = 6, P3 = 3, P4 = 7
- Average waiting time = 4
-
SJF preemptive
- P1 실행 중, 남은 P1의 burst time보다 짧은 P2가 들어옴 → P2 실행 → P2 실행 중, 남은 P2 time 보다 짧은 P3 → P4 들어왔지만, 남은 P2가 더 짧으므로 P2 실행 → P4 → 남은 P1
- Waiting Time P1 = 9, P2 = 1, P3 = 0, P4 = 2
- Average waiting time = 3
- Context switching이 non-preemptive보다 더 많이 일어난다. (그러나 짧게 소요)
- context switching 포함 Average waiting time = (9 + 5a) + (1 + 3a) + (0 + a) + (2 + 3a) / 4 = 3 + 10a
Round Robin (RR)
- FCFS 방식 + Time slice -> time quantum q를 사용한다. (보통 10-100 ms)
- 정해진 시간 q가 지나면, ready queue의 제일 뒤로 간다.
- Timer interrupt는 q마다 발생하여 다음 프로세스로 넘어가도록 한다.
q가 너무 크면 -> FCFS에서 개선되지 않는다.
q가 너무 작으면 -> context switch overhead
RR Example
| Process | CPU Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
- q = 4
- 0 - 4: P1 진행 후, 4만큼 지났으므로 context switching
- 4 - 7: P2 실행 → 다음 프로세스 (timer interrupt가 아님. q 시간 내 CPU burst 종료)
- 7 - 10: P3
- 10 - 30: 남은 P1 실행, q에 시간에 맞춰 무의미한 context switching은 계속됨
- waiting time: P1 = 6, P2 = 4, P3 = 7
- Average waiting time = 5.66
- SJF 보다 turnaround는 높지만, response는 더 좋다.
- q는 context 전환 시간에 비해 커야 한다.
Round Robin - Bad example
-
모든 프로세스가 비슷한 burst time을 가진 경우
-
quantum time이 너무 긴 경우
Priority Scheduling
- 각각의 프로세스에 우선순위를 부여하는 방식.
- 높은 우선순위를 가진 프로세스에게 낮은 숫자를 부여한다.
- Preemptive와 non-preemptive 방식 존재
- SJF의 우선 순위는? -> 다음 CPU burst가 빠른 기준
- Problem - Starvation: 너무 낮은 우선순위의 프로세스는 계속 실행되지 못하는 상황 발생
- Solution - Aging: 시간이 지날수록 우선순위를 올려 준다.
우선순위 스케줄링은 오로지 빠른 average waiting time만을 위한 것이 아닌, 이용자가 우선으로 생각하는 것부터 처리하기 위한 방법이다. 따라서 priority를 얼마나 세분화하고, 정확하게 잘 부여하는가가 중요한 문제이다.
Multilevel Queue (MQ)
- 큐를 여러 개로 나누는 방식
- Example
- foreground (interactive) - 클라이언트와의 상호작용이 중요한 프로세스들이 모인 큐. 우선순위 높음
- background (batch) - low에서 실행되기만 하면 되는 프로세스들이 모인 큐. 우선순위가 낮음
- Example
- 한 번 어떤 큐로 들어간 프로세스는 다른 큐로 이동할 수 없다.
- 각각의 큐는 스케줄링 알고리즘을 가지고 있다.
- 큐 간의 스케줄링도 요구된다.
Multilevel Feedback Queue (MFQ)
- 이전의 결과에 Feedback을 받는 queue.
- MQ에서 더 발전된 방식으로, 특정적으로 정해진 방법이 없다. -> 여러가지 형태의 구현이 가능하다.
- 프로세스는 상황에 따라 큐를 이동할 수 있다.
MFQ Example
- Two process
- P1: Run for 1ms then wait for I/O for 10ms
- P2: No waiting, run continuously
- P1과 P2가 번갈아가면서 계속 들어온다.
- P1: runs 1ms → blocks for I/O request
- P2: runs 1ms → time slice
- P1: I/O waiting / P2: Q1로 들어간 후 runs 2ms → time slice
- P1: I/O waiting / P2: Q2로 들어간 후 runs 4ms → time slice
- P1: I/O waiting / P2: Q3로 들어간 후 runs 3ms → preempted (P1의 I/O waiting 끝)
- P1: runs 1ms → blocks for I/O request
- P2: runs 5ms (Q3에서 돌다가 남은 5ms)
Thread Scheduling
- 스레드가 지원되는 경우 프로세스가 아닌 스레드가 스케줄링된다.
- Process-contention scope (PCS)
- user와 kernel 매핑 시 스케줄링
- 하나의 프로세스에서 스레드 간의 경쟁
- Many-to-one과 many-to-many 모델, 스레드 라이브러리는 실행할 user-level 스레드가 kernel-level 스레드에서 실행되도록 스케줄링한다.
- 일반적으로 프로그래머가 우선순위를 정한 것을 통해 수행된다.
- System-contention scope (SCS)
- kernel-CPU 매핑 시 스케줄링
- 시스템의 모든 스레드 간의 경쟁
- 커널 레벨 스레드는 사용가능한 CPU에서 스케줄링된다.
