[OS] 05. CPU Scheduling

 

 

CPU and I/O Bursts in Program Execution

program path: CPU 연속적으로 사용하는 단계와 I/O 단계 번갈아가면서 실행

• CPU만 연속적으로 instruction을 실행하는 단계 CPU burst

• I/O를 실행하고 있는 단계 I/O burst (주로 사람이 interaction 하는 프로그램에 많음)

CPU-burst Time의 분포

CPU는 CPU bound job을 많이 쓰고 I/O bound job은 CPU를 짧게 쓰는데 빈도가 잦을 뿐이다.

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

• interactive job(대부분 I/O bound job)에게 적절한 response 제공 요망
  (사람이 답답함을 느끼기 때문 우선적으로 CPU 제공)

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

프로세스의 특성 분류

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

• 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를 줄 프로세스를 고른다

(운영체제 내에서 CPU 스케줄링을 하는 코드가 있음

Dispatcher

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

• 이 과정을 context switch(문맥 교환)이라고 한다.

(운영체제 내에서 CPU 디스패쳐 하는 코드가 있음)

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

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

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

3. Blocked → Ready (예: I/O 완료 후 인터럽트)
   1. 보통 I/O가 오면 기존 프로세스 인터럽트 후 I/O 요청했던 프로세스 상태를 ready로 바꿔놓고 기존 프로세스가 다시 CPU 할당받아 실행
   2. 절대적으로 우선순위에 기반한 스케줄링이라면 우선순위(priority)가 I/O 요청했던 프로세스가 가장 높은 경우 인터럽트 당했던 프로세스가 할당 시간이 남아있더라도 I/O 요청했던 프로세스 실행

4. Terminate

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

※ All other scheduling is

preemptive (=강제로 빼앗음) 선점형 → 현대적 스케줄이라고 할 수 있음

Scheduling Criteria (Performances Index = Permance Measure, 성능척도)

• CPU utilization (이용률) - CPU 입장
  keep the CPU as busy as possible
  CPU 전체 시간 중 CPU가 일하는 시간

• Throughput (처리량) - CPU 입장
  # of processes that complete their execution per time unite
  주어진 시간 동안 몇 개의 일을 처리했는지

• Turnaround time (소요시간, 반환시간) - 고객(프로세스) 입장
  amount of time to execute a particular process
  CPU를 사용하기 위해서 기다리고 쓰고 I/O 하러 나갈 때 까지 걸린 시간
  메모리 들어가기 위해 기다린 시간 + 준비 완료 큐에서 대기한 시간 + CPU 실행 시간 + 입출력 시간

• Waiting time (대기 시간) - 고객(프로세스) 입장
  amount of time a process has been waiting in the ready queue
  CPU를 쓰기 위해서 기다린 시간 종합

• Response time (응답시간) - 고객(프로세스) 입장
  amount of time it takes from when a request was submitted until first response is produced. not output (for time-sharing environment)
  CPU쓰겠다고 ready queue에 들어와서 최초의 CPU 얻기까지 걸린 시간

Scheduling Algorithm

FCFS (FIrst-Come First-Served)

먼저 온 순서대로 처리 → 비선점형 스케줄링

• 효율적이지 않음
  굉장히 CPU를 오래 쓰는 프로그램이 먼저 CPU 잡아버리면, interactive한 job들이 기다려야함

예시

Process	Burst Time
P1	24
P2	3
P3	3

• 예시1
  • 프로젝트 도착 순서 P1, P2, P3
  • Gantt Chart

    

  • Waiting time for
    P1 = 0, P2 = 24, P3 = 27
  • Average waiting time
    (0+24+27) / 3 = 17

• 예시2
  • 프로젝트 도착 순서 P2, P3, P1
  • Gantt Chart

    

  • waiting time for
    P1 = 6, P2 = 0, P3 = 3
  • Average waiting time
    (6+0+3) / 3 = 3

convoy effect (호위 효과)

short process behindng long process
→ 앞에 긴 친구가 버티고 있어서 오래 기다려야 함

SJF (Shortest-Job-Served)

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

• CPU burst tIme에 가장 짧은 프로세스를 제일 먼저 스케줄

Two schedmes

• Nonpreemptive
  • 일단 CPU를 잡으면 어떤 CPU burst가 완료될 때까지 CPU를 선점(preemptinve) 당하지 않음

• preemptive
  • 현재 수행 중인 프로세스 남은 burst time보다 더 좋은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  • 이 방법을 Shortest-Remaining-Time-First(SRTF)라고도 부른다

SJF in optimal

주어진 프로세스에 대해 minimum average wating time을 보장 → preemptive가 더 짧음

예시

• nonpreemptive

  

• preemptive (알고리즘 중 average waiting time 가장 최소)

  

문제점

• Starvation(기아현상): SFJ는 CPU 시간 짧은 잡을 선호하여 CPU 사용 시간이 짧은 것이 계속 들어오면 CPU 사용 시간이 긴 것은 영원히 기다려야 함

• CPU 사용 시간을 미리 알 수 없음 (과거 이력을 보고 예측만 가능)

다음 CPU Burst Time의 예측 (추정만 가능)

과거의 CPU burst time을 이용해서 추정 (exponential averaging)

t는 CPU 실제 사용 시간 τ는 CPU 사용 시간 예측

τn+1에다가 n-1 적용해서 τn 구함

Exponential Averaging

• α = 0
  • τn-1 = τn
  • Recent history does not count

• α = 1
  • τn+1 = tn
  • Only the actual last CPU burst counts

• 식을 풀면 다음과 같다 (결국 마지막 τ 빼고 전부 t로 구성)

  

• α와 (1-α) 둘 다 1 이하이므로 후속 term은 선행 term보다 적은 가중치 값을 가진다 (최근 것 가중치 높게, 오래된 것은 가중치 낮게)

→ 과거 값 통해 예측하고 예측치가 젤 적은 CPU에게 CPU를 주는 SJF 알고리즘으로 구현

Priority Scheduling (우선순위 스케줄링)

• A priority number (integer) is associated with each procccess
  → 제일 작은 정수가 우선순위가 높은 것

• highest priority를 가진 프로세스에게 CPU 할당 (smallest integer - highest priority)
  • prrempitve: 우선순위가 더 높은 프로세스가 있을 때 CPU 빼앗기
  • nonpreemptive: 우선순위가 더 높은 프로세스가 왔어도 기존 프로세스 CPU

• SJF는 일초의 priority scheduling이다 (priority = preicted next CPU burst time)

problem

• Starvation(기아현상): low priority processes may never execute

solution

• Aging(노화): as time progresses increse the priority of the process
  → 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위 올리기

Round Robin (RR) - 현대 CPU 스케줄링

• 각 프로세스는 동일한 크기의 할당 시간(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 이상 기다리지 않는다

• Response time(응답 시간 - 최초로 CPU 얻는 것)이 빨라진다
  → q를 짧게 잡으면 프로그램 자신이 쓸 수 있는 차례가 빨라짐

• CPU 길게 쓰는 프로그램은 기다리는 시간 길어지고, 짧게 쓰는 프로그램은 기다리는 시간이 짧아짐

Performance

• q large → FCFS

• q small → context switch 오버헤드가 커진다

예시 (RR with Time Quantum = 20)

Process	Burst Time
P1	53
P2	14
P3	68
P4	24

• Gantt chart

  

• 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다

특이사항

그렇지만, 모든 프로그램이 CPU 사용 시간이 동일한 경우, 나누어서 쭉 번갈아 실행하면 거의 모든 프로그램이 마지막까지 CPU를 쓰고 빠져나가기 때문에 waiting time이 길어져서 안 좋을 수 있음

Multi Queue (멀티 큐)

Multilevel Queue

1. system process

2. interactive process (사람과 상호작용)

3. interactive editing processes

4. batch processes (CPU만 오랫동안 사용)

5. student processes

개념

• 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 시간을 나누어서 할당)
    • 각 큐에 CPU time을 적절한 비율로 할당
    • Eg., 80% to foreground in RR, 20% to background in FCFS

한계

• 신분(큐 상태)를 영원히 극복 못함

Multilevel feedback Queue

• 프로세스가 다른 큐로 이동 가능

• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.

• Multilevel-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • process를 상위 큐로 보내는 기준
  • process를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

일반적으로, 처음 들어오는 프로세스는 우선순위가 가장 높은 queue(RR, time quantum 짧음) 집어넣음, 밑에 queue로 갈수록 RR의 time quantum을 길게 주고 제일 아래는 FCFS 방식을 줌

할당 시간이 위에 queue에서 끝나게 되면 밑의 queue로 강등이 되는 방식으로 운영

따라서 CPU Burst가 짧은 프로세스는 도착하자마자 CPU를 쓰고 바로 빠져나갈 수 있고, CPU 사용 시간이 긴 프로세스는 점점 아래 queue로 이동 (할당 시간은 더 많이 받지만, queue간의 우선순위에서 보통 위의 queue가 비어져 있어야 밑에 queue를 실행하는 방식을 사용)
→ CPU 사용 시간이 짧은 프로세스에게 우선순위를 많이 주는 스케줄링 방식
→ CPU 사용 시간이 긴지, 짧은지 예측도 필요 없으면서 짧은 프로세스가 우대를 받는 것

예시

• Three queue
  • Q0 - time quantum 8 milliseconds
  • Q1 - time quantum 16 milliseconds
  • Q2 - FCFS

• Scheduling
  • new job이 Q0로 들어감
  • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행
  • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
  • Q1에 줄서서 기다렸다가 CPU를 잡아서 16 ms 동안 수행됨
  • 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨남

Unusual case (특이 케이스)

Multiple-Processor Scheduling

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

Homogeneous processor인 경우

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

• 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
  (그것을 미리 할당하고 스케줄링)

Load sharing

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

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

CPU들 간 차이 유무

• Symmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
  • 모든 CPU가 대등

• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
  • 하나의 CPU가 전체 컨트롤, 나머지 CPU는 거기에 따르는 것

Real-Time Scheduling

그때 그때 스케줄링 하기보다 real-time job들이 주어져있고 미리 스케줄링(오프라인으로 미리 스케줄링 하거나 주기적으로(10초에 한번씩) active 되어야 하는 것이 많아서 거기에 맞게 스케줄링)을 해서 deadline이 보장하도록 적재적소에 배치

Hard real-time systems

Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함

Soft real-time computing

Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함 (데드라인 확실히 보장은 못함)

Thread Scheduling (프로세스 하나 당 CPU 수행 단위가 여러 개)

Local Scheduling

User level thread인 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할 지 결정

Global Scheduling

Kernel level thread인 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할 지 결정

Algorithm Evaluation

Queueing models (이론적 방법)

확률분포로 주어지는 arrive rate(도착률)와 service rate(처리율) 등을 통해 각종 performance index(성능척도) 값을 계산

예전에는 많이 사용했으나 최근에는 실제 시스템에서 실제로 돌려보는 것을 의미있는 값으로 보기 때문에 그렇게까지 많이 사용하지 않으나 여전히 이론적으로는 많이 사용

Implementation(구현) & Measurement(성능 측정) (실측)

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

Simulation(모의 실험)

알고리즘을 모의 프로그램으로 작성 후 trace(인풋 데이터 - 여러 패턴)를 입력으로 하여 결과 비교

→ 어떤 알고리즘이 좋다고 주장할 때 하나의 예제만으로 주장하지 않고, 실제 시스템에서 각 프로세스의 CPU 사용 패턴을 여러 개 뽑아서 실제 프로그램에 CPU Burst pattern에 근거해서 시뮬레이션 한다면 신빙성 상승

Uploaded by

N2T