CH5. CPU Scheduling

유지언·2023년 8월 23일
0

운영체제

목록 보기
5/8

CPU and I/O Bursts in Program Execution

CPU and I/O Burst

(CPU burst와 I/O burst의 정의 추가하기 )

위의 그림과 같이, 프로그램의 실행은 CPU burst와 I/O burst의 연속이다. 프로그램의 종류에 따라서 각각의 빈도와 길이가 달라진다는 점에서만 차이가 있다.

프로세스는 그 특성에 따라 다음과 같이 두 가지로 나눌 수 있다.

  • I/O-bound process
    : CPU를 사용하는 계산 위주의 작업의 시간보다 I/O에 많은 시간이 필요한 job이다. CPU burst가 짧고 빈도가 높다.

  • CPU-bound process
    : CPU를 사용하는 계산 위주의 job이다. CPU burst가 길고 빈도가 낮다.

CPU-burst Time의 분포

  • I/O bound job: CPU burst가 짧은, 즉 I/O burst의 빈도가 높은 작업(job)
  • CPU bound job: CPU burst가 긴, 즉 I/O burst의 빈도가 짧은 작업(job)

위의 표에서 볼 수 있듯이 컴퓨터에는 여러 종류의 job(=process)이 섞여있기 때문에 CPU 스케줄링이 필요하다.

이를 통해

  • Interactive job(I/O)에게 적절한 response 제공할 수 있다.
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있다.

CPU Scheduler & Dispatcher

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

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

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

  • (1) Running → Blocked (ex. I/O 요청하는 시스템 콜)
  • (2) Running → Ready (ex. 할당시간 만료로 timer interrupt가 발생)
  • (3) Blocked → Ready (ex. I/O 완료로 발생한 interrupt)
  • (4) Terminate

(1), (4)에서의 스케줄링은 nonpreemptive(=자진반납, 비선점형)이다. 다른 스케줄링은 preemptive(=강제로 빼앗음, 선점형)이다.

Scheduling Criteria

CPU scheduling의 성능 평가 척도

시스템 입장에서 성능 평가 척도
: CPU 하나로 일을 최대한 많이 시키면 좋다.

  • CPU utilization(이용료): 전체 시간 중에서 CPU가 일한 시간의 비율
    keep the CPU as busy as possible
  • Throughput(처리량): 주어진 시간동안 완료한 작업의 개수
    number of processes that complete their execution per time unit

프로세스 입장에서의 성능 평가 척도
: 내가 빨리 CPU를 얻어서 프로세스를 빨리 진행시킬 수 있으면 좋다.

  • Turnaround time(소요시간, 반환시간): CPU를 사용하려고 queue에 들어온 시점부터 CPU burst가 종료된 시점까지 걸린 시간
    amount of time to execute a particular process
  • Waiting time(대기시간): CPU를 사용하기 위해서 queue에서 대기한 시간
    amount of time a process has been waiting in the ready queue
  • Response time(응답시간): ready queue에 들어와서 CPU를 처음으로 얻기까지 기다린 시간
    amount of time it takes from when a request was submitted until the first response is produced. not ouput (for time-sharing environment)
선점형 스케줄링(preemptive scheduling)의 경우 CPU를 사용할 수 있게 되었다고 해서 계속 사용할 수 있지 않다. CPU를 얻었다가 빼앗기는 것을 반복하기 때문에 한 번의 CPU burst 동안에도 Ready queue에서 대기하는 시간이 여러 개 발생하는데 이 시간들의 총합을 waiting time이라고 한다.

response time은 CPU를 처음 얻기까지 걸린 시간이다. 즉 이후에 CPU를 다시 빼앗겨서 대기한 시간과는 상관없다. 이 대기시간까지 모두 더한 것이 waiting time.

예시)
CPU를 중국집 요리사, process를 손님이라고 생각했을 때,

  • CPU utilization:
  • Throughput: 다 먹고 나간 손님 수
  • Turnaround time: 손님이 음식을 주문하고 음식을 모두 먹을 때까지 걸린 시간
  • Waiting time: 손님이 음식을 주문하고 다 먹을 때까지 걸린 시간에서 음식 먹는 시간을 뺀 것. 코스요리라고 생각했을 때, 한 요리를 다 먹고 다음 요리가 나올 때까지 기다리는 시간들을 모두 더한 것이라고 생각하면 된다.
  • Response time: 주문하고 맨 처음 요리가 나올 때까지 기다린 시간

Scheduling Algorithm

1) FCFS (First-Come First-Served)

  • Nonpreemptive(비선점형) 스케줄링이다

위의 예시와 같이 CPU burst가 긴 프로세스가 CPU를 먼저 선점하면 빨리 끝날 수 있는 다른 프로세스가 계속 지연되기 때문에(Convoy Effect: short process behind long process) FCFS는 효율적인 스케줄링 방법은 아니다.

만약 CPU를 짧게 사용하는 프로세스가 먼저 도착했다면 다음과 같을 것이다.

즉, FCFS는 waiting time이 프로세스의 도착 순서에 크게 영향을 받는다는 특징이 있다.

2) SJF (Shortest-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용하는 방법
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄한다
  • SRTF의 경우, 주어진 프로세스들에 대하여 minimum average waiting time을 보장한다.

SJF 알고리즘의 두 가지 scheme

(1) Nonpreemptive(비선점형)

  • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않는다

(2) Preemptive(선점형)

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

하지만 SJF에도 다음과 같은 문제점이 있다.

  • CPU burst time이 긴 프로세스의 경우 영원히 실행이 안 될 수도 있다.
  • 다음 CPU burst time을 미리 알 수 없다 → 하지만 추정은 가능

다음 CPU Burst Time 예측

과거의 CPU burst time을 이용하여 추정(estimate)만이 가능하다.

  1. tnt_n = actual length of nthn^{th} CPU burst
  2. τ(n+1)τ_(n+1) = predicted value for the next CPU burst
  3. αisconstant,0<α<1\alpha is constant, 0 < \alpha < 1
  4. Define: τn+1=αtn+(1−α)τnτ_{n+1} = \alpha t_n+(1-\alpha)τ_n

즉 (n+1)번째 CPU burst time의 예측 시간(τn+1τ_{n+1})은 n번째 실제 CPU burst time(tnt_n)과 n번째 추정 CPU burst time(τnτ_n)을 일정 비율씩 반영한 값이다.

정의에 대한 식을 풀면 다음과 같다.
τn+1=αtn+(1−α)αtn−1+...+(1−α)jαtn−j+...+(1−α)nαt0+(1−α)n+1τ0τ_{n+1} = \alpha t_n+(1-\alpha) \alpha t_{n-1}+...+(1-\alpha)^j \alpha t_{n-j}+...+(1-\alpha)^n \alpha t_0+(1-\alpha)^{n+1} τ_0

α\alpha 와 (1−α)(1-\alpha) 모두 1보다 작은 값이므로 지수가 클수록 값이 작아진다. 따라서 위 식을 통해 다음 CPU burst time을 추정할 때는 직전 CPU burst time의 실제 값을 가장 크게 반영하고 더 이전 것일수록 적은 비율로 반영한다는 것을 알 수 있다.

3) Priority Scheduling

  • 우선순위가 높은 프로세스에게 CPU를 할당하는 방법
  • 앞서 언급한 SJF도 일종의 priority scheduling이다. (priority=predicted CPU burst time)

SFJ와 마찬가지로 우선순위가 낮은 프로세스가 영원히 실행되지 않을 수도 있다(Starvation, 기아 현상)는 문제점이 있다.

Starvation를 해결하기 위하여 시간이 흐를수록 프로세스의 priority를 높이는 Aging(노화)을 이용한다.

4) Round Robin (RR) Scheduling

  • preemptive(선점형) scheduling
  • 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가진다 (일반적으로 10~100ms). 때문에 response time이 짧다는 장점이 있다.
  • 할당 시간이 지나면 프로세스는 선점(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 오버헤드가 커진다. average turnout time이 길어진다.

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

RR Scheduling은 CPU burst time이 짧은 프로세스와 긴 프로세스가 혼재되어있을 때 사용하기 좋은 방법이다. 하지만 극단적으로 CPU burst time이 같은 n개의 프로세스를 짧은 time quantum으로 스케줄링하게 된다면 모든 프로그램이 마지막까지 남아있게 되기 때문에 waiting time이 굉장히 길어질 수 있다.

Multilevel Ready Queue

1) Multilevel Queue

  • Ready Queue를 여러 개로 분할하고 우선순위가 높은 Queue가 비어야 다음 우선순위의 Queue에 있는 프로세스에게 CPU를 할당해준다.
    • foreground queue(interactive jobs)
    • background queue(batch - no human interaction jobs)
  • 각 queue는 독립적인 스케줄링 알고리즘을 가진다.
    • foreground queue: PR
    • background queue: FCFS
  • 큐에 대한 스케줄링이 필요
    • Fixed prioity 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

Multilevel Feedback Queue

  • 프로세스가 다른 queue로 이동 가능
  • Aging을 이와 같은 방식으로 구현할 수 있다.
  • 처음 프로세스가 들어오면 가장 우선순위가 높은 queue로 들어간다. 그 queue에서 작업이 완료되지 않으면 우선순위가 한 단계씩 내려간다. 이때 queue의 우선순위가 높을수록 time quantum을 짧다.
  • CPU burst time이 짧은 프로세스가 빠르게 처리되는데 특화된 방식이라고 볼 수 있다.

Multiple-Processor Scheduling

: CPU가 여러 개일 때의 스케줄링

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

Real-Time Scheduling

: deadline을 보장하는 스케줄링 방법

  • Hard real-time systems
    : Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 한다.
  • Soft real-time computing
    : Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야한다.

Thread Scheduling

  • Local Scheduling
    : User level thread의 경우 OS가 아니라 사용자 수준의 thread library에 의해 어떤 thread를 스케줄링할지 결정한다.
  • Global Scheduling
    : Kernal level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다.

Algorithm Evaluation

Queueing models

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

그림에서 server가 CPU라고 보면 된다.

Implementation(구현) & Mesurement(성능 측정)

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

Simulation(모의실험)

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

profile
유지언
신입 데이터 엔지니어
이전 포스트

CH4. Process Management

다음 포스트

CH6. Process Synchronization

0개의 댓글