CPU 스케줄링

1. CPU and I/O Bursts in Program Execution

2. CPU-burst Time의 분포

CPU로 기계어를 실행하는 단계

image

CPU 스케줄링의 필요성

• 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요

  • Interactive job에게 적절한 response 제공 요망

  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

• I/O bound job가 CPU를 빨리 얻을 수 있도록 함

  • CPU를 먼저 주어야 빨리빨리 CPU를 쓰고 나가기 때문

  • 사람과 Interaction하기 때문에 빠른 응답성 제공 필요

  • 쓰고나서 바로 I/O 작업이 이루어지는데, CPU를 못 주고 있으면 CPU도 못 얻을 뿐만 아니라 I/O 도 못할 것이기 때문

3. Process의 특성 분류

(1) CPU-bound process

• CPU를 길게 쓰고, I/O를 짧게 쓰는 작업

• 사람과 Interaction을 많이 하는 경우 (계산 위주의 job 등)

• few & very long CPU bursts

(2) I/O-bound process

• CPU를 짧게 쓰고, I/O를 길게 쓰는 작업

• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 경우 (과학적 연산 등)

• many & short CPU bursts

4. CPU Scheduler & Dispatcher

소프트웨어이며, CPU 스케줄링을 하는 운영체제 안에 있는 코드

(1) CPU 스케줄러

• Ready 상태의 프로세스 중에서 이번에 CPU를 어떤 프로세스에게 줄지 고르는 역할

(2) Dispatcher

• CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김

• 즉, 결정된 프로세스에게 실제로 CPU를 넘기는 역할

• 운영체제의 일부이며 이 과정을 context switch라고 함

(3) CPU 스케줄링이 필요한 경우

프로세스에게 아래와 같은 상태 변화가 있는 경우

1. Running → Blocked (e.g. I/O 요청하는 시스템 콜)

2. Running → Ready (e.g. 할당시간만료로 timer interrupt)

3. Blocked → Ready (e.g. I/O 완료 후 인터럽트)

4. Terminate

• 1, 4 에서의 스케줄링은 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)

• 그 외 다른 스케줄링은 preemptive (= 정책상 다른 것들도 번갈아 CPU 사용해야 하기에 강제로 빼앗음)

5. Scheduling Criteria

• Performance Index (= Performance Measure, 성능 척도)

• 중국집 주방장에 비유하면 이해하기 쉬움

(1) CPU Utilization (이용률)

• keep the CPU as busy as possible

• CPU를 놀게 하지 않고 이용률은 높을수록 좋음

(2) Throughput (처리량)

• number of processes that complete their execution per time unit

• 처리량은 많을수록 좋음

• e.g. 중국집 셰프가 많은 요리를 처리하면 할수록 좋음

(3) Turnaround Time (소요 시간, 반환 시간)

• amount of time to execute a particular process

• CPU burst를 하고 나서, I/O burst를 하러 나가기까지 전체 시간

• Ready Queue에서 CPU를 기다린 시간 + 실제로 CPU를 사용한 시간

• e.g. 밥먹은 시간 + 대기시간 다 합친 시간

(4) Waiting Time (대기 시간)

• amount of time a process has been waiting in the ready queue

• 처음으로 기다리는 시간이 아닌, CPU를 쓰러 와서 기다린 전체 시간의 합

• e.g. 중국집에서 웨이팅한 시간.. 단무지 → 짜장면 → 탕수육 → 디저트 각각 나오는 시간의 합

(5) Response Time (응답 시간)

• amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

• CPU를 쓰러 들어와 최초로 CPU를 얻기까지 걸린 시간

• 주의할 것은 프로세스가 처음으로 시작해서 처음 CPU를 얻은 시간이 아님. 즉, CPU를 쓰러 들어오는 여러 번의 burst 중, CPU burst를 들어와 최초로 CPU를 얻기까지 걸린 시간이라 보면 됨

• e.g. 중국집에서 최초로 단무지를 받기까지 걸리는 시간

6. Scheduling Algorithms

(1) FCFS(First-Come First-Served)

Much better than previous case

예시

fcfs-example-1

fcfs-example-2

특징

• 두 케이스 다 선착순으로 처리했으니 별 차이가 없는 것 같지만, 평균을 내보면 굉장히 많이 줄어들었음

• 왜? 앞에 CPU 사용 시간이 긴 프로세스가 들어와버리면 전체 프로세스의 기다리는 시간이 길어지기 때문 → 호위 효과

Convoy effect (호위 효과)

• short process behind long process

• 오래 걸리는 프로세스가 먼저 도착해 CPU를 오래 쓰는 탓에, 짧게 걸리는 프로세스가 오래 걸리게 되는 것

(2) SJF (Shortest-Job-First)

예시

sjf-example-1

sjf-example-2

특징

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄링

• 대기 시간 측면에서 보자면 가장 최적의 방법. 이보다 평균 대기시간을 더 짧게 할 수는 없음

SJF is optional

• 평균 대기시간이 짧고 minimum average waiting time을 보장함

• Preemptive한 SJF == SRTF(Shortest-Remaining-Time-First)라고도 부름

• 대기 시간 측면에서 최적인 방법

High Priority를 가진 process에게 CPU 할당

• SJF는 일종의 Priority Scheduling

• Priority = predicated next CPU burst time

Two schemes

• Nonpreemptive

  • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음

  • 갑자기 더 짧은 프로세스가 등장하더라도 이미 CPU를 주었으면 해당 프로세스가 다 쓸 때까지 빼앗지 않음

• Preemptive

  • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로젝트가 도착하면 CPU를 빼앗김

  • Nonpreemptive 보다 더 최적화된 방법

(3) SJF의 단점

starvation 발생

• SJF는 너무 효율성만 생각하다보니, 짧은 프로세스에게 우선권을 주기 때문

• queue가 계속 쌓이면 long job은 영원히 CPU를 얻지 못할 수도 있음

다음 CPU Burst Time의 예측

• 누가 짧게 쓰고 누가 길게 쓰는지 알려주지 않음

• CPU queue에 들어올 때 미리 알 수 없기 때문

• 즉, 프로그램이라는 게 순차적으로 진행되기보단 if문 등 그때그때 상황이 다르기 때문

• 그렇다면 다음번 CPU burst time을 어떻게 알 수 있을까?

• CPU burst를 알 수 없다면 과거의 CPU burst time을 기반으로 추정은 가능

7. Priority Scheduling

A priority number (integer) is associated with each process

특징

• highest priority(smallest integer)를 가진 프로세스에게 CPU 할당

• preemptive: 우선순위가 더 높으면 빼앗아서 줌

• nonpreemptive: 빼앗지 않고 기다림

• SJF는 일종의 priority scheduling

문제점

• Starvation: low priority processes may never execute

해결책

• Aging: as time progresses increase the priority of the process

• 경로우대 같은 개념

8. Round Robin

특징

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐

• 할당 시간이 지나면 프로세스는 선점(preempted) 당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다

• n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

• 즉, 어떠한 프로세스도 (n-1) q time unit 이상 기다리지 않는다.

Performance

• 할당 시간이 너무 길면 → FCFS

• 할당 시간이 너무 짧으면 → context switch가 너무 빈번하게 일어남

9. Multilevel Queue

Ready queue를 여러 개로 분할

image

(1) Ready queue를 여러 개로 분할

• foreground: interactive

• background: batch - no human interaction

(2) 각 queue는 독립적인 스케줄링 알고리즘을 가짐

• foreground: Round Robin

• background: FCFS (긴 프로세스 하나가 context switch 없이 쭉 실행)

• Queue에 대한 스케줄링이 필요 (각 queue 마다 wait을 주는 것)

(3) Fixed priority scheduling

• serve all from foreground then from background

• starvation의 가능성이 있음

(4) Time slice

• 각 queue에 CPU time을 적절한 비율로 할당

• e.g. 80% to foreground in RR, 20% to background in FCFS

• foreground에 우선순위를 주는데 무조건 주는건 아니고, 각 큐마다 시간의 weight를 주는 것

10. Multilevel Feedback Queue

image

(1) 특징

• 줄 간의 이동이 가능

• 한번 정해진 queue는 바뀌지 않음

• Process가 다른 queue로 이동 가능

• 상위 queue가 우선순위가 높다

• 상위 queue가 비어야 하위 queue가 채워짐

• aging을 이와 같은 방식으로 구현 가능

(2) Multilevel Feedback Queue Scheduler를 정의하는 파라미터들

• Queue의 수

• 각 queue의 scheduling algorithm

• 프로세스를 상위 queue로 보내는 기준

• 프로세스를 하위 queue로 보내는 기준

• 프로세스가 CPU 서비스를 받으려 할 때 들어갈 queue를 결정하는 기준

11. Example of Multilevel Feedback Queue

(1) Three queues

• Q0 - time quantum 8 milliseconds

• Q1 - time quantum 16 milliseconds

• Q2 - FCFS

(2) Scheduling

• new job이 queue Q0로 들어감

• 8ms 동안 다 끝내지 못했으면 queue Q1으로 내려감

• Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨

• 16ms 안에 끝내지 못한 경우 queue Q2로 쫓겨남

12. Multiple-Processor Scheduling

CPU가 여러 개인 경우, 스케줄링은 더욱 복잡해짐

(1) Homogeneous processor인 경우

• Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음

• 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐

(2) Load Sharing

• 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

• 별개의 queue를 두는 방법 vs. 공동의 queue를 사용하는 방법

(3) Symmetric Multiprocessing (SMP)

• 각 프로세서가 각자 알아서 스케줄링 결정

(4) Asymmetric Multiprocessing

• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

13. 특수한 경우의 CPU 스케줄링

(1) Load Balancing

• 기본적으로 CPU가 여러 개 있는 경우는 Load Balancing

• 여러 CPU가 밸런스 있게 골고루 일하게 하는 것이 중요

• 그렇지 않으면 전체 성능이 떨어짐

(2) SMP (Symmetric Multiprocessing)

• 하나의 대장 CPU가 있는게 아니라 여러 CPU들이 대등함

• 따라서 각 프로세서가 각자 알아서 스케줄링을 결정

(3) ASMP (Asymmetric Multiprocessing)

• SMP의 비효율적인 측면을 보완하는 방법

• 한 개의 CPU가 대장 CPU가 되어 데이터의 접근과 공유를 책임지고, 나머지 CPU는 거기에 따름

14. Real-Time Scheduling

(1) Hard real-time systems

• 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함

• 이를 위해 각 프로세스들의 CPU 도착 시간을 미리 알고 스케줄링해 시스템이 따라가도록 하기도 함 → Offline Scheduling

• 각 작업들의 load가 얼마인지 고려해서 CPU를 남겨두어야 함

(2) Soft real-time computing

• 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

• 데드라인을 보장해주면 좋지만 비용이 비싸서 일반 프로세스와 섞어 사용

• e.g. 동영상이 끊기지 않도록 동영상 재생 프로세스가 먼저 CPU를 얻을 수 있도록 priority를 높임

15. Thread Scheduling

(1) Thread

• 프로세스 내에서 실행되는 가장 작은 실행 단위

• 각 스레드는 동일한 하나의 프로세스 안에서 실행 중인 다른 프로세스와 메모리 및 자원을 공유

• 이러한 구조는 프로세스 간의 통신을 용이하게 하고, 자원의 효율적 사용을 가능하게 함

(2) Local Scheduling

• 운영체제는 스레드의 존재를 모르고, 사용자 프로세스 본인이 내부에 스레드를 여러 개 두기에 운영체제는 어느 프로그램에 CPU를 주겠다는 의사결정을 하지 못함

• 대신, 사용자 수준의 스레드 라이브러리(User level thread)가 스레드 간의 스케줄링을 담당

• 이 스레드는 사용자 수준에서 관리되기에 커널의 개입 없이 빠르게 스위치할 수 있지만, 한 스레드가 block 되면 전체 프로세스가 block 될 수 있음

(3) Global Scheduling

• 글로벌 스케줄링은 커널 수준에서 이루어지며, 여기서는 운영체제가 스레드의 존재를 알 수 있으며, 커널의 스케줄러가 어떤 스레드를 실행할지 결정

• 이는 각 스레드가 별도의 커널 객체로 관리되기에 가능

• 즉, 커널의 단기 스케줄러가 어떤 thread를 스케줄링할지 결정

• 이 방식은 멀티 프로세서 시스템에서 효율적이지만, 사용자 수준 스레드보다 context switch에 더 많은 비용이 들 수 있음

(4) Global Scheduling이 멀티 프로세서 시스템에서 효율적인 이유

멀티 프로세서 시스템에서는 여러 CPU 코어가 동시에 작동하며, 이 환경에서 글로벌 스케줄링은 아래의 이점을 제공

a. 자원 분배의 유연성

글로벌 스케줄링에서는 커널이 모든 스레드를 인식하고 관리한다. 이는 시스템 전체의 스레드를 다양한 프로세서 코어에 할당하는 유연성을 제공한다. 따라서, 작업 부하를 여러 코어에 균등하게 분산시켜 시스템의 전반적인 성능을 극대화할 수 있다.

b. 효율적인 로드 밸런싱

멀티 프로세서 시스템에서는 각 프로세서의 부하를 모니터링하고, 스레드를 다른 프로세서로 이동시켜 부하를 균등하게 분산시킬 수 있다. 이는 로드 밸런싱을 통해 시스템의 효율성을 높이는 데 중요한 역할을 한다.

c. 병렬 처리의 최적화

멀티 프로세서 시스템에서는 여러 스레드가 동시에 실행될 수 있다. 글로벌 스케줄링을 통해 이러한 병렬 처리를 최적화할 수 있으며, 이는 특히 병렬 계산이 많은 작업에서 중요하다.

d. 데드락 및 기아 상태 관리

멀티 프로세서 환경에서 데드락(Deadlock) 및 기아(Starvation) 상태는 프로세스 및 스레드 관리의 복잡성을 증가시킨다. 글로벌 스케줄링은 이러한 문제를 관리하고 해결하는 데 필요한 전반적인 관점을 제공한다.

e. 동기화와 일관성 유지

멀티 프로세서 환경에서 데이터와 자원의 동기화는 중요한 과제이다. 글로벌 스케줄링을 통해 데이터의 일관성을 유지하고, 자원 접근 시 발생할 수 있는 충돌을 효과적으로 관리할 수 있다.

16. Algorithm Evaluation

어떤 CPU 스케줄링 알고리즘이 좋은지 평가하는 척도

(1) Queueing models

• 확률분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

• 서버가 요청을 처리하는데에 요청이 queue에 쌓여있으면 서버가 처리, 못하면 queue에 남아있음

• CPU를 쓰고자 하는 요청들이 queue에 도착하는데, 얼마나 빠른 빈도로 도착하는지 → 이 도착률이 확률 분포로 주어짐

• CPU의 성능 or 역량을 ‘처리율’ 이라고 함

• 복잡한 수식을 계산하고 나면 Throughput(처리량), Waiting Time(대기 시간)이 도출됨

(2) Implementaion and Measurement

• 실제 시스템에 알고리즘을 구현하며 실제 작업(workload)에 대해 성능을 측정하며 비교

(3) Simulation

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

• trace란, Input이 되는 data를 말하며 실제 시스템에서 돌아가는 프로그램의 패턴과 유사하거나 대변할 수 있을 정도로 신빙성이 있어야 함