CS/OS

반효경 [운영체제] 9강, 10강 - CPU Scheduling 1

동김 2023. 5. 14. 04:48

CPU Scheduling

 

CPU and I/O Bursts in Program Execution

 

CPU-burst Time의 분포

  • 여러 종류의 job(process)들이 섞여있기 때문에 CPU 스케줄링이 필요하다.
    • Interactive job에게 적절한 response 제공 요망
    • 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를 줄 프로세스를 고른다
  • Dispatcher
    • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
    • 이 과정을 context switch(문맥 교환)라고 한다.
  • 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(= 강제로 빼앗음) / 선점형

 

Scheduling Criteria

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

위의 2가지는 시스템(CPU) 입장 성능 척도 - CPU 하나로 일을 많이하면 척도가 좋은 것

밑의 3가지는 프로그램(프로세스) 입장 - 빠르게 처리 할 수 있으면 좋은 것

프로세스 전체의 시작과 종료 기준이 아니라 프로세스가 CPU를 잡는 시간 기준(버스트 기준) 이라는 것에 유의

  • CPU utilization 이용률
    • keep the CPU as busy as possible
    • CPU를 가능한 한 사용 중으로 유지합니다
  • Throughput 처리량
    • number of prcesses that complete their excution per time unit
    • 시간 단위당 수행을 완료하는 프로세스 수
  • Turnaround time 소요시간, 반환시간
    • amount of time to excute a particular process
    • 특정 프로세스를 실행하는 데 걸리는 시간
  • Waiting time 대기시간
    • amount of time a process has been waiting in the ready queue
    • ready queue에서 프로세스가 대기한 시간
  • 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)
    • 요청이 제출된 시점부터 첫 번째 응답이 생성될 때까지 걸리는 시간

 

Scheduling Algoritm

  • FCFS
  • SJF
  • SRTF
  • Priority Scheduling
  • RR
  • Multilevel Queue
  • Mutilevel Feedback Queue

 

FCFS(First-Come First-Served)

  • 비선점형(unpreemptive)

 

SJF(Shortes-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 적용
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴
  • Two Scheme
    • Nonpreemptive
      • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(premmption)당하지 않음
    • Preemptive
      • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
      • 이 방법을 **Shortest-Remaining-Time-First(SRTF)**라고도 부른다.

  • SJF is optimal
    • 주어진 프로세스들에 대해 minimun average waiting time을 보장 → 모든 알고리즘 중에서 가장 짧은 waiting time을 보장
  • 문제점
    1. starvation → Long process가 영원히 실행되지 않을수도 있다.
    2. 프로그램의 정확한 사용시간을 미리 알수가 없으므로 추정을 해야함.
    다음 CPU Burst Time의 예측
    • 다음번 CPU burst time을 어떻게 알 수 있는가? (Input data, branch, user)
    • 추정(estimate)만이 가능하다
    • 과거의 CPU burst time을 이용해서 추정 (exponential averaging)

 

Priority Scheduling

  • A priority number(integer) is associated with each process
  • highest priority를 가진 프로세스에게 CPU 할당
    • Preemptive
    • nonpreemptive
  • (smallest integer - highest priority)
  • SJF는 일종의 priority scheduling이다.
    • priority = predicated next CPU burst time
  • 문제점
    • Starvation(기아 현상): low priority processes may nver execute
  • 해결방법
    • Aging: as time progresses increase the priority of the process

 

RR(Round Robin) - 현대의 운영체제가 사용하는 방법

  • 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가짐(일반적으로 10-100 milliseconds)
  • 할당 시간이 지나면 프로세스는 선점(preemted)당하고 ready queue의 제일 뒤에가서 다시 줄을 선다.
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit단위로 CPU 시간의 1/n을 얻는다.
  • → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
  • 장점: 응답시간이 빨라진다.(최초로 CPU를 얻게되는 시간)
  • 단점: 특정조건에서는 오히려 비효율적일 수 있다
  • 턴어라운드, 웨이팅타임이 악화될 수도 있음.
  • Performance
    • q large → FCFS
    • q small → context switch 가 빈번해져 overhead의 부담