[OS] CPU Scheduling

 

- Multi-programming의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 process를 가지게 하는 것

- 하나의 process가 대기해야 할 때마다, 다른 process가 CPU 사용을 양도받을 수 있음

- CPU-I/O Burst Cycle: CPU 실행과 I/O 대기의 cycle로 구성

- Ready queue에서 나온 process가 CPU dispatch 되는데, ready queue는 반드시 FIFO인 것이 아님

→ CPU Scheduling Algorithm

 

- CPU scheduling decision이 일어나는 경우

    (1) Process state: running → waiting

    (2) Process state: running → ready

    (3) Process state: waiting → ready

    (4) Process terminate

    - (1), (4)의 경우 scheduling 면에서 선택의 여지가 없음 (실행을 위해 새 process 반드시 선택되어야 함) → Nonpreemtive (비선점)

    - (2), (3)의 경우 선택의 여지가 있음 → Preemptive (선점)

 

- Nonpreemptive: CPU가 한 process에 할당되면 process가 종료되거나 waiting 상태로 전환해 CPU 방출할 때까지 CPU 점유

- Preemptive: 한 process가 다른 process 대신 CPU 차지 가능

 

- Preemptive Scheduler

    - 공유 자료 접근하는 경우 비용 발생

    - 한 process가 자료 갱신하는 동안 다른 process가 실행 가능해진 경우 → 데이터 일관성 깨짐

 

- Deadlock

    - UNIX에서는 context switching 하기 전 system call의 완료 또는 I/O block을 기다림

      (kernel 자료구조가 비일관적인 상태에 있는 동안에는 해당 process 선점 못하도록 함)

 

- Scheduling criteria

    - CPU utilization, Throughput, Turnaround time, Waiting time, Response time

 

 

1. FCFS Scheduling (First-Come, First-Served)

- 선입선출 스케줄링 알고리즘

- CPU를 먼저 요청하는 process가 CPU를 먼저 할당받음

- Nonpreemptive → CPU가 한 process에 할당되면 CPU를 방출할 때까지 점유함

- 장점: FIFO queue로 쉽게 관리할 수 있음

- 단점: 평균 대기 시간이 대단히 길어질 수 있음

- Convoy effect(호위 효과): 다른 process들이 하나의 긴 process가 CPU를 양도하기를 기다리는 것

 

 

2. SJF Scheduling (Shortest-Job-First)

- shortest-next-CPU-burst 알고리즘

- 각 process에 다음 CPU의 burst 길이를 연관시킴

- 주어진 process 집합에 대해 최소의 평균 대기 시간을 가짐

- 다음 CPU의 burst 길이 파악하는 것이 어려움 (예측값 사용)

- 다음 추정 burst = ɑ * 현재 burst + (1 - ɑ) * 현재 추정 burst (0 ≤ ɑ ≤ 1, 일반적으로 1/2로 설정)

- Preemptive / Nonpreemptive 모두 가능

- Preemptive 버전 = shortest-remaining-time-first

 

 

3. Priority Scheduling

- 우선순위대로 CPU 할당함

- Preemptive / Nonpreeptive 모두 가능

- Preemptive → 새로 도착한 process의 우선순위가 현재 실행되는 process의 우선순위보다 높다면 CPU 선점

- Nonpreemptive → 새로 도착한 process는 단순히 ready queue의 head에 들어감

- 높은 우선순위 process가 꾸준히 들어와 낮은 우선순위 process가 무한히 대기 = starvation (기아 상태) → aging 사용

 

 

4. Round Robin Scheduling

- 시분할 시스템을 위해 설계됨

- Ready queue (원형 큐) 돌면서 한 번에 한 process에게 정해진 time quantum 동안 CPU 할당

- CPU scheduler는 맨앞 process를 선택해 time quantum 이후 interrupt 걸도록 timer 설정한 후, CPU에 dispatch함

- Ready queue에 n개 process 있고 time quantum이 q이면, 각 process는 (n - 1) * q 이상 대기하지 않음

- CPU burst < time quantum: process가 CPU 자발적으로 방출, 다음 process 시작 (Preemptive)

- CPU burst > time quantum: timer가 끝나고 interrupt 발생, context switch 일어나고 process는 ready queue의 tail에 들어감

- Time quantum 너무 큰 경우: FCFS와 똑같아짐

- Time quantum 너무 작은 경우: context switch 너무 자주 일어남, CPU 시간의 대부분을 context switch 하는 데에만 쓰일 수 있음

- Time qunatum을 적절히 설정하는 것이 좋음 (높게 설정한다고 해서 무조건 총 처리시간 줄어드는 것 아님)

 

 

5. Multilevel Queue Scheduling

- System process > Interactive process > Interactive editing process > Batch process > Student process

- Forground process (interactive 대화형) > Background process (batch 일괄처리)

- Foreground - RR 알고리즘 / Background - FCFS 알고리즘

- Queue들 사이에도 scheduling 반드시 있어야 하며, 일반적으로 고정된 우선순위의 preemptive scheduling으로 구현됨

→ background process가 무한히 기다리는 starvation 발생할 수 있음

- 예를 들어, 전체 CPU time에서 Foreground는 80%만큼, Background는 20%만큼 주는 방법이 있음

 

 

6. Multilevel Feedback Queue Scheduling

- Multilevel Queue Scheduling과 달리 process가 queue 사이에서 이동할 수 있음 (overhead는 있으나 융통성 있음)

- 어떤 process가 CPU 시간 너무 많이 사용하면 낮은 우선순위 queue로 이동, 반대로 너무 오래 기다리면 높은 우선순위 queue로 이동 (aging)

- Parameter: queue 개수, 각 queue의 scheduling 알고리즘, 높은/낮은 우선순위 queue로 이동하는 시기, process가 들어갈 queue 고르는 법

 

 

7. Thread Scheduling (Pthread Scheduling)

- Thread 개념을 도입하며 user level thread와 kernel level thread를 구분하였음 (https://serinyoon.tistory.com/69)

- Thread scheduling에서 schedule 되는 대상은 process가 아닌 kernel level thread

- 우선순위는 개발자에 의해 설정됨

 

 

8. Multiple-Processor Scheduling

- 여태까지의 scheduling 알고리즘은 single-processor에서 CPU를 schedule 하기 위한 알고리즘이었음

- Multiple-processor에서 여러 CPU 사용이 가능하다면 load sharing이 가능해짐 (but, 더 복잡함)

- Processor들의 기능이 동일한 경우만을 다룸 (Homogeneous processors)

 

- Asymmetric(비대칭) multiprocessing: 하나의 processor만 system data structure에 접근 (data sharing 필요성 배제)

- Symmetric(대칭) multiprocessing (SMP):

    - 각 processor가 독자적으로 scheduling 함

    - 모든 process는 공동의 ready queue에 있거나, 각 processor만의 ready queue에 있음

    - 각 processor의 scheduler가 ready queue 검사하여 실행할 processor 선택

    - 서로 다른 processor가 같은 process 선택하지 않도록 해야 함

    - 최근엔 소켓당 CPU 수가 많아 SMP 대신 NUMA 아키텍처 많이 사용

 

- Process Affinity(친화성): SMP 시스템에서 다른 processor로의 이주를 피하고 한 processor에서 process 실행하고자 하는 것

    - Soft Affinity: OS가 동일한 processor에서 process 실행시키고자 하는 정책은 가지고 있으나 보장하진 않는 경우

    - Hard Affinity: Process가 자신이 실행될 processor 집합 명시할 수 있는 경우

 

- Load Balancing: SMP에서는 load를 모든 processor에 균등하게 배분하는 것이 중요함

    - Push Migration: 각 processor의 load 확인하고, task를 overloaded CPU에서 다른 CPU로 옮김

    - Pull Migration: 바쁜 processor를 기다리고 있는 process를 쉬고 있는 processor가 가져와 실행

 

- Multicore Processor (Multithreaded Multicore System)

    - Memory stall: processor가 memory에 접근할 때 데이터가 사용 가능해질 때까지 기다리며 많은 시간이 소요됨

    - 각 processor가 2개 이상의 thread를 사용하여 한 thread가 memory를 기다리며 멈추면 core가 다른 thread로 전환