[운영체제] CPU 스케줄링 CPU Scheduling

CPU and I/O Bursts in Program Execution

load store, add store, read from file 등 CPU만 연속적으로 사용하는 단계(CPU burst)와 I/O를 하는 단계(I/O burst)가 번갈아가며 실행된다.

주로 사람이 interaction을 하는 프로그램이 이 cpu burst와 i/o burst가 자주 바뀌는 프로그램이다.

하지만 쭉 계산만 한다거나 사람의 interaction이 그다지 필요 없는 프로그램은 cpu burst가 많이 나오는 프로그램이다.

CPU Scheduling에서의 issue

1. 누구에게 CPU를 줄 것인가
2. 중간에 CPU를 뺏어올 수 있도록 할 것인가

CPU-burst Time 의 분포

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

• Interactive job에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
• I/O bound job 은 사람과 소통하기 때문에 너무 많이 기다리게 되면 사람이 답답하여 CPU 스케줄링을 적절히 해야 한다(효율성)

프로세스의 특성 분류

프로세스는 그 특성에 따라 다음 두 가지로 나눔

• I/O-bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 JOB
  • many short CPU bursts
• CPU-bound process
  • 계산 위주의 job
  • few very long CPU bursts

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher

• CPU의 제어권을 CPU scheduler 에 의해 선택된 프로세스에게 넘긴다.(실제로 CPU를 주는 과정)
• 이 과정을 context switch(문맥 교환) 이라고 한다

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

1. Running → Blocked (예:  I/O 요청하는 시스템 콜)
   • 오래걸리는 작업이 있는 경우
2. Running → Ready (예: 할당 시간 만료로 timer interrupt)
   • 이 아이에게 무한정 CPU를 줄 수 없어 timer interrupt등으로 CPU를 빼앗는 과정
3. Blocked → Ready (예: I/O 완료 후 인터럽트)
   • 다시 CPU를 얻을 수 있는 상태로 만들어줌
   • I/O가 끝났다고 바로 CPU를 바로 줄 수도/그렇지 않을 수도 있다.
     • 예를 들어 우선순위 스케줄링의 경우 I/O작업이 끝나면 CPU를 바로 넘겨줌
4. Terminate

• 1, 4 에서의 스케줄링은 비선점형 nonpreemptive (= 강제로 빼앗지 않고 자진 반납)
• All other scheduling is 선점형 preemptive (= 강제로 빼앗음), 2, 3번이 여기에 해당

Scheduling Algorithms

• FCFS(First-Come First-Serve)
• SJF(Shortest-Job-First)
• SRTF(Shortest-Remaining-Time-First)
• Priority Scheduling
• RR(Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

Scheduling Criteria

CPU Scheduling의 어떤 알고리즘이 좋은 것인가의 성능 척도 → Performance Index = Performance Measure

이러한 성능 척도도 크게 2가지로 나눌 수 있다.

 

CPU 입장에서의 성능 척도: 최대한 일을 많이 시키면 좋음

• CPU utilization (이용률)
  • 전체 CPU에서 CPU가 일한 시간의 비율
  • keep the CPU as busy as possible
• Throughput (처리량, 산출량)
  • 주어진 시간 동안 몇 개의 일을 처리했느냐
  • # of processes that complete their execution per time unit

프로그램 입장에서의 성능 척도: 내가 CPU를 빨리 얻어서 빨리 끝내는 것이 좋음

• Turnaround time (소요시간, 변환시간)
  • CPU를 사용하려 들어와서 다 사용하고 나갈 때까지 걸리는 시간 (기다린 시간 + 다 쓴 시간)
  • amount of time to execute a particular process
•  Waiting time (대기 시간)
  • CPU를 쓰려고 ready queue에서 기다린 시간 
  • amount of time a process has been waiting int the ready queue
• Response time (응답 시간)
  • 들어와서 처음으로 CPU를 사용할 때까지 기다리는 시간 
  • amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
  • time sharing 환경에서는 처음으로 CPU를 얻는 시간이 사용자 환경에서 중요하기 때문에 존재

FCFS( First-Come First-Served)

• 먼저 온 프로그램에게 CPU를 넘김
• 비선점형 스케줄링
• 앞에 시간이 엄청 긴 프로세스가 있으면 뒤에 있는 프로세슫들의 대기시간이 매우 길게 됨
• 따라서 FCFS 방식은 앞에 어떤 프로세스가 있느냐에 영향을 엄청 받는다.
• Convoy effect: 긴 프로세스가 하나 도착해서 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상

SJF(Shortest-Job-First)

• 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• Two schema:
  • Nonpreemptive
    • 일단 CPU 를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preeption) 당하지 않음
  • Preemptive
    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • 이 방법은 Shortest-Remaining-Time-First(SRTF) 이라고도 부름
  • Nonpreemptive 는 프로세스가 끝나면 스케줄링을 하는데, Preemptive는 프로세스가 들어올 때 스케줄링을 한다는 차이가 있음
• SJF is optimal
  • 주어진 프로세스들에 대해 minimum average waiting time을 보장 → Preemptive 한 방식으로  동작할 때

문제점

1. Starvation 기아현상: 극단적으로 짧은 걸 선호해서 상대적으로 실행시간이 긴 프로세스는 영원히 실행되지 않을 수 있다.
2.  CPU 사용시간을 미리 알 수 없다.

다음 CPU Burst Time의 예측

• 다음번 CPU burst time을 어떻게 알 수 있는가?
• 추정(estimate) 만이 가능하다.
• 과거의 CPU burst time을 이용해서 추정(exponential averaging)

• t: 실제 CPU 사용시간
• T(타우): CPU 사용시간 예측시간
• a: 일정 비율
• n+1번째 CPU사용시간 예측시간 = a*(n번째 실제 CPU 사용시간) + (1-a)*(n번째 CPU 사용 예측 시간)
• 이 식을 계속 재귀해서 나열하면 결국 예측시간은 사라지고 t로만 가득찬 식이 생성된다.

• a와 (1-a)가 둘다 1 이하이므로 후속 term은 선행 term보다 적은 가중치 값을 가진다.

Priority Scheduling

• A priority number(integer) is associated with each process
• highest priority를 가진 프로세스에게 CPU 할당(small integer - highest priority)
  • Preemptive
  • Nonpreemptive
• SJF는 일종의 priority scheduling 이다
  • priority = predicted next CPU burst time
• 문제점
  • Starvation(기아 현상): 낮은 우선순위를 가진 프로세스는 절대 실행되지 않음
• 해결책
  • Aging(노화): 시간이 지남에 따라 프로세스의 우선순위를 높여줌

Round Robin(RR)

• 현대적인 CPU 스케줄링은 Round Robin 기반의 스케줄링 기법을 사용하고 있다.
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  • 일반적으로 10 -100 milliseconds
• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
  • 즉 실행시간이 짧은 프로세스는 대기시간도 짧고, 긴 프로세스는 대기시간도 길다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
  • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• Performance
  • q large → FCFS
  • q small → context switch 오버헤드가 커진다
• 일반적으로 SJF 보다 average turnaround time이 길지만 response time은 더 짧다.

Multilevel Queue

• Ready queue를 여러 개로 분할
  • foreground (interactive)
  • background (batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
    • 사람과 상호작용할 때에는 응답성이 좋은 것이 좋음
  • background - FCFS
    • 사람과 상호작용하지 않으면 그냥 들어온대로 처리해도 괜찮음
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • serve all from foreground then from background.
    • Possibility of starvation
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • Eg. 80%  to foreground in RR, 20% to background in FCFS

높은 우선순위의 Queue가 비어야 밑의 queue 실행

Multilevel Feedback Queue

여러 줄로 줄을 서면서 프로세스가 중간에 위치를 바꿀 수 있도록 하는 스케줄링 기법

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
• Multilevel-feedback-queue schedular 를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
• 보통 어떻게 처리하느냐
  • 처음 들어올 때는 일단 프로세스를 우선순위가 가장 높은 큐에 집어넣음
  • 우선순위가 가장 높은 큐는 RR기법으로 time quantum를 짧게 줌
    • 밑으로 갈수록 RR의 할당 시간을 길게 줌
  • 제일 아래 큐는 FCFS방식 사용
  • 어떤 큐에서  프로세스가 실행될 때 할당시간 내 처리가 다 안끝났으면 다음 큐로 넘어가는 식

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
• Homogeneous processor인 경우
  • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard real-time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
  • 데드라인을 두고, 그 안에 반드시 끝내도록 함
• Soft real-timee computing
  •  Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할 지 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

알고리즘 평가 Algorithm Evaluation

• Queueing models
  
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index(성능 평가) 값을 계산
  • 이론적인 방법
• Implementation (구현) & Measurement (성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation (모의 실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
  • trace: 실제 프로그램을 통해 추출한 input  데이터. 시뮬레이션에 input으로 들어갈 데이터. 임의로 만들수도, 프로그램을 통해 뽑을 수도 있다.