운영체제

CPU 스케줄링

웜블 2022. 1. 19. 04:40

개요

운영체제가 메모리에 적재한 프로세스 중, 다음에 CPU를 할당할 프로세스를 선택하는 것.

왜 필요한 건가?

CPU는 한 번에 한 프로세스만 실행할 수 있다. 

하지만 프로세스에서는 항상 CPU를 사용하는 것은 아닌데, 입출력 장치를 통해 사용자와의 인터랙션이 진행 중일 때는 프로세스는 CPU를 사용하지 않는다. 하지만 이 때도 프로세스는 CPU를 점유하고 있다. 간단히 말하면 소중한 CPU가 아무것도 하지 않은 채 놀고 있다는 것이다. 이렇게 CPU를 점유하고 사용하지 않는 시간에 다른 프로세스를 실행하면 CPU의 사용률을 높이고 전체 시스템의 성능을 향상시킬 수 있다.

즉, 소중한 자원인 CPU를 최대한 활용하기 위한 기술이 CPU 스케줄링이다.

시스템 종류에 따른 목표

  1. Batch System : 많은 처리량
  2. Interactive System : 짧은 응답 시간과 대기 시간
  3. Real-time System : 마감 기간(Deadline)

 

선점/비선점 스케줄링

선점 스케줄링

  • 운영체제가 프로세스에 할당되었던 CPU를 강제로 뺏어올 수 있음(선점 가능)
  • 우선순위가 높은 프로세스에 CPU 할당 가능

비선점 스케줄링

  • 프로세스가 대기 상태에 들어가거나 종료되지 않고서는 프로세스 전환이 일어나지 않음

 

프로세스의 상태

  • New : 프로세스 생성 중
  • Ready : CPU 할당 대기 중. 언제든지 CPU를 사용할 수 있는 상태. 메모리 등은 모두 준비됨.
  • Running : CPU를 할당받고 명령어를 실행 중
  • Blocked : 자신이 요청한 event가 만족되지 않아 기다리고 있는 상태. 명령을 수행할 수 없는 상태. (waiting, sleeping)
  • Terminated : 프로세스 실행이 끝난 상태

프로세스 상태 전이

프로세스 상태 전이

  • Dispatch
    • 레디큐 맨 앞의 프로세스가 CPU를 점유하는 것. 즉, 준비 상태에서 실행 상태로 바뀌는 것
  • Block(I/O or Event wait)
    • 실행 상태의 프로세스가 허가된 시간을 다 쓰기 전에 입출력/이벤트를 처리해야 하는 경우, 프로세스가 CPU를 반납하고 blocked 상태로 바뀌는 것
  • wakeup(I/O or Event Completion)
    • 프로세스가 기다리던 입출력/이벤트를 준비 상태로 바꾸는 것
  • Interrupt(timer interrupt/timeout)
    • 운영체제가 프로세스에 할당한 시간이 만료되어 준비 상태로 바뀌는 것

 

스케줄링 종류

비선점

  1. FCFS(First-Come First-Served)
    • 레디큐에 도착한 순서대로 CPU 할당
    • 작업 완료 시간을 예측하기 용이
    • 긴 프로세스가 앞에오면 매우 비효율적인 스케줄링이 된다
    • convoy effect
      • 긴 프로세스를 다른 모든 프로세스들이 기다림
      • CPU 사용률을 낮추기에 성능 저하 발생
    • 출처 - https://rebas.kr/863
  2. SJF(Shortest Job First)
    • 수행 시간이 가장 짧은 프로세스를 먼저 스케줄
    • FCFS보다 평균 대기 시간 감소
    • 출처 - https://rebas.kr/863
  3. HRN(Hightest Response-ratio Next)
    • 수행시간과 대기시간을 고려하여 우선순위를 결정
    • 우선순위 = (수행시간 + 대기시간) / 수행시간
    • 긴 프로세스와 짧은 프로세스간 불평등 보완(SJF 보완)

선점

  1. Priority Scheduling
    • 정적/동적으로 우선순위 부여
    • 우선순위 대로 CPU 할당
    • 우선순위가 낮은 프로세스가 무한히 기다리기만 하는 starvation 가능성 있음
    • 오래된 프로세스의 우선순위를 높이는 aging 으로 대응
  2. Round Robin  
    • 각 프로세스마다 동일한 CPU 할당 시간을 줌(time quantum)
    • FCFS로 진행됨
    • 할당 시간이 크면 FCFS와 같고, 너무 짧으면 context switch에 의해 오버헤드가 커짐
    • round robin - 위키피디아
    • 출처 - https://rebas.kr/863
  3. SRT(Shortest Remaining Time Scheduling)
    • SJF를 선점형으로 변형한 스케줄링
    • 실행중인 프로세스의 남은 실행 시간과 레디큐에 도착한 프로세스들의 실행시간을 비교함
    • 남은 실행 시간이 짧은 프로세스에 CPU 할당
    • 출처 - https://rebas.kr/863
    • 출처 - https://blog.hax0r.info/2020-05-11/process-scheduling-and-techniques/
  4. Multilevel Queue(다단계 큐)
    • 여러 개로 레디큐 분할
    • 우선순위가 낮은 큐에 starvation을 우려하여 각 큐마다 적절한 비율로 time quantum 할당.
  5. Multilevel Feedback Queue(다단계 피드백 큐)
    • 다단계 큐에서 time quantum을 채운 프로세스를 우선순위가 낮은 큐로 이동시킴. time quantum을 못 채운 프로세스는 그대로
    • 입출력 위주의 interrupt가 잦은 프로세스에 우선권을 줌
    • time quantum을 채운 프로세스는 CPU burst process라고 판단하여 뒤에 처리
    • 수행시간이 짧은 프로세스를 먼저 처리하여 평균 turnaround 시간을 줄여줌

 

스케줄러 종류

스케줄러

  1. 장기 스케줄러
    • 하드디스크에서 메모리에 적재할 작업(프로세스)를 선별함
    • 작업(job) 스케줄링
  2. 단기 스케줄러
    • 레디큐에 준비된 프로세스 중 하나를 선별해 CPU 할당
    • 일반적으로 스케줄러는 이것을 의미함
  3. 중기 스케줄러
    • 메모리에 적재된 프로세스가 너무 많아져 하드디스크 입출력이 과다해지면 시스템 성능이 급감함
    • Swapping : 일부 프로세스를 메모리에서 디스크로 보내고(swap-out), 메모리에 여유가 생기면 다시 적재함(swap-in)