(7) 운영체제에서의 CPU 스케줄링

컴퓨터 자원 할당 및 스케줄링
•컴퓨터 자원(CPU, 메모리, 디스크, 네트워크 등)을 여러 프로세스가 동시에 사용하기 위해서는 자원의 효율적인 할당 및 스케줄링 필요
•컴퓨터 자원의 종류
   –비선점 자원: 자원이 프로세스에 할당되면 스스로 반환하기 전까지 회수 불가
       •디스크, Lock, 터미널 등
–선점 자원: 자원을 프로세스에 할당하고 회수를 자유롭게 함
      •CPU, 메모리 등  (선점 자원은 메시-> 메모리, 시피유 ㅎ)
•공간 기반 자원 공유 vs 시간 기반 자원 공유
  – 물리적으로 나누어질 수 있으면 공간 기반 공유(예: 메모리, 디스크, 멀티 CPU)
  – 물리적으로 나눌 수 없으면 번갈아가면서 일정 시간 동안 공유(예: 단일 CPU)
 
CPU 스케줄링
•CPU 스케줄링의 목적
– 다수 프로세스의 효과적인 배치를 통해 CPU 사용 효율을 높이고자 함
– 응답 시간(Response time)과 작업 시간(Turn-aroundtime) 단축
• 응답 시간 = 시작 시간 – 도착 시간
• 작업 시간 = 종료 시간–도착 시간(대기, CPU, 입출력 시간 모두 포함)
 

여러 가지 CPU 스케줄링 기법
• 프로세스는 CPU 연산과 입출력 작업으로 이루어져 있으며, 프로세스의 특성에 따라 CPU 연산 및 입출력의 비율이 다름
– 입출력 작업이 실행되는 동안 CPU 자원을 활용하는 것이 스케줄링 기본 정책임
– 하지만, 각 프로세스 간에 CPU 독점이 발생되지 않게 공평한 배분이 필요함

 
• First Come, First Served (FCFS)
  – 선입 선처리 스케줄링으로 먼저 도착한 프로세스에게 CPU 자원을 할당함
  – 매우 간단한 알고리즘으로 구현이 쉽지만, 프로세스의 대기시간이 매우 길어지는 부작용이 있음
     •Convoy effect(호위효과): CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스는 먼저 도착한 프로세스가 작업을 마칠 때까지 기다려야 함

 
 
•Shortest Job First (SJF)
  – 최단 작업 우선 스케줄링으로 CPU 사용 시간이 짧은 프로세스를 먼저 실행함
  – 하지만, 모든 프로세스가 동시에 작업을 요청하는 경우에만 유효하며, 프로세스 도착 시간이 다른 경우 호위 효과가 발생할 수 있음
  – 최단 작업을 찾기 위한 정렬이 필요함
•FCFS와 SJF는 비선점형기법으로 프로세스가 CPU를 차지하면 회수할 수 없음

 
 
•Round Robin (RR)
– 라운드 로빈 스케줄링은 각 프로세스가 정해진 시간(Time slice)만큼의 시간 동안 돌아가며 CPU를 사용
– 순서대로 CPU를 사용하기 위하여 문맥 교환이 발생하며, 문맥 교환으로 인한 추가 시간이 소요됨
– 타임 슬라이스의 크기에 따라 알고리즘의 성능이 달라짐
   • 타임 슬라이스가 너무 큰 경우 FCFS 기법과 유사해져 호위 효과 발생
   • 타임 슬라이스가 너무 작은 경우 문맥 교환으로 인한 비용이 커짐
– 할당된 CPU를 다시 회수할 수 있으므로 선점형 스케줄링임

 
•Shortest Time-to-Completion First (STCF)
    –최소 잔여 시간 우선 스케줄링
•Pre-emptive(우선권) Shortest Job First (PSJF)
  •A new job enters the system:
     –Determine of the remaining jobs and new job
     –Schedule the job which has the least time left
 

 
•이외에도많은CPU 스케줄링기법이 있음
–Priority Scheduling
–Multi-level Feedback Queue
–Weighted Round Robin
–Lottery Scheduling
–Weighted Fair Queue
–Completely Fair Queue
   •오늘날 운영체제에서 주로 사용되는 스케줄링과 유사함