본문 바로가기
컴퓨터 사이언스/운영체제

CPU 스케줄링

by Chaein.P 2023. 7. 10.

프로세스 특성 분류

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에 의해 선택된 프로세스에게 넘긴다.
  • 이 과정을 Context Switch라고 한다.

CPU 스케줄링이 필요한 경우

  • Running -> Blocked (I/O 요청하는 시스템 콜): nonpreemptive(CPU 자진반납)
  • Running -> Ready (할당시간 만료로 timer interupt): preemptive(CPU 강제로 빼앗음)
  • Blocked -> Ready (I/O완료 후 인터럽트): preemptive(CPU 강제로 빼앗음)
  • Terminatie: nonpreemptive(CPU 자진반납)

CPU 스케줄링의 성능 척도

  • CPU utilization (이용률): CPU 이용률
  • Throughput (처리량): 단위 시간 당 처리 완료된 프로세스 개수
  • Turnaround time (소요시간, 반환시간): CPU 사용 시간 + 기다린 시간
  • Waiting time (대기 시간): Ready queue에 머무른 전체 시간 (기다린 시간의 합)
  • Response time (응답 시간): 프로세스가 최초로 CPU를 얻기까지 기다린 시간 (최초로 기다린 시간)

CPU 스케쥴링 알고리즘

FCFS(First-come First-Served)

  • nonpreemptive
  • 먼저 들어온 작업을 순서대로 처리해주는 방법
  • CPU burst time이 긴 작업이 먼저 오게 되면 전체 프로세스의 평균 대기 시간이 길어지는 문제가 있다.
  • Convoy Effect: 긴 프로세스 뒤에 짧은 프로세스가 위치되어 대기시간이 길어지는 현상

SJF(Shortest Job First)

  • CPU burst time이 가장 짧은 프로세스를 먼저 처리한다.
  • 대기시간의 평균을 최적화하는 데에 가장 좋은 알고리즘
  • Nonpreemptive 방식: CPU를 한번 선점하면 CPU burst가 완료될 때까지 선점 당하지 않음
  • Preemptive 방식: 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김 (SRTF(Shortest Remaining Time First))
  • Starvation 문제 발생: Long job은 평생 CPU를 선점할 수 없을 수 있음
  • CPU burst time을 정확하게 알 수가 없어서 예측한다.
    • 과거의 CPU burst time을 이용해서 추정한다.
    • n+1 burst time = a(n 실제 burst time) + (1-a)(n 예측 burst time) => exponential averaging

priority scheduling

  • 우선순위가 높은 프로세스가 CPU를 선점한다.
  • preemptive, nonpreemptive 모두 구현 가능
  • SJF도 priority scheduling의 일종, CPU burst time = priority
  • Starvation 문제 발생 가능
    • Aging 기법으로 문제 해결
    • 대기 시간이 길어질수록 priority를 높여주는 방법

Round Robin

  • 모든 프로세스는 동일한 크기의 할당시간을 가짐
  • 할당시간이 지나면 CPU는 회수되고 reqdy queue 맨 뒤로 들어감
  • preemptive 방식
  • 모든 프로세스는 (n-1)q time unit 이상 기다리지 않는다.
  • performance
    • q large = FCFS
    • q small = context switch 오버헤드가 커진다.
  • 일반적으로 SJF 보다 평균 turnaround time은 길지만 response time 은 더 짧다.
  • burst time이 동일한 잡들을 Round Robin으로 했을 때 turnarount time이 길어지면서 오히려 더 비효율적일 수 있다.

Multilevel Queue

  • Ready queue를 여러개로 분할 한다. 프로세스는 각 특성에 맞게 queue에 적재되고 다른 queue로 이동할 수 없다.
    • foreground (interactive): Round Robind
    • background (batch-no human interaction): FCFS
  • 두 Reqdy queue 스케쥴링 방법
    • Fixed priority scheduling: 무조건 foreground를 먼저 처리하고 더이상 처리할 foreground가 없을 때 background를 처리하는 방법, starvation 가능성이 있음
    • Time slice: 각 큐 CPU time을 적절한 비율로 할당하는 방법 ex. 80% foreground, 20% background

Multilevel Feedback Queue

  • 프로세스가 서로 다른 큐 간에 이동이 가능하다.
  • aging으로 starvation을 방지할 수 있음
  • 보통 가장 우선순위가 높은 queue에 들어와서 정해진 시간 내에 처리가 되지 않으면 다음 큐로 강등되는 방식으로 구현
  • Multilevel feedback queue 파라미터 예
    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 보내는 기준
    • Process가 ready할 큐를 결정하는 기준

특수한 경우의 Scheduling

Multiprocessor Scheduling

  • CPU가 여러개 있는 경우의 스케쥴링
  • Homogeneous processor 인 경우
    • 하나의 Queue를 사용해 각 processor가 process를 꺼내가게 할 수 있다.
    • 반드시 특정 processor에서 처리되어야하는 작업의 경우 문제가 복잡해짐
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘이 필요하다.
  • Symmetric Multiprocessing
    • 각 프로세서가 각자 알아서 스케쥴링
  • Asymmetric mulltiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

  • Hard real-time task의 경우 정해진 시간 안에 반드시 끝내도록 해야하기 때문에 offline에서 스케쥴링을 모두 해놓고 작업을 진행시키는 경우가 많다.
  • Soft real-time task(ex. 동영상 스트리밍)는 일반 프로세스에 비해 높은 priority를 갖도록 해야한다.

Thread Scheduling

  • Loacl Scheduling
    • User Level Thread의 경우 OS가 스레드의 존재를 모르기 때문에 프로세스가 자체적으로 thread library를 이용해 thread 스케줄을 결정한다.
  • Global Scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케쥴할지 결정

'컴퓨터 사이언스 > 운영체제' 카테고리의 다른 글

메모리 관리  (0) 2023.08.01
프로세스 동기화  (0) 2023.07.14
프로그램 메모리  (0) 2023.07.01
프로세스와 스레드  (0) 2023.02.26
시스템 구조  (0) 2023.02.26

댓글