CPU 스케쥴링

CPU 스케줄링

CPU를 사용하기 위해 프로세스를 배정하는 작업

 

스케줄링 알고리즘 성능 척도

1. 시스템 입장에서 성능 척도

• Cpu Utilization(이용률) : 전체 시간중에서 cpu가 놀지 않고 일하는 시간의 비율
• Throughput(처리량) : 단위 시간당 cpu가 프로세스를 얼마나 처리하는가

1. 프로세스 입장에서 성능 척도

• Turnaround Time(소요시간, 반환시간) : 프로세스가 cpu를 쓰러 들어와서 다시 반납하고 나갈 때 까지의 시간
• Waiting Time(대기시간) : ready queue에서 대기하면서 소요된 모든 시간
• Response time(응답시간) : ready queue에서 최초로 cpu를 얻기 전까지 시간

 

CPU 스케줄러

프로세스들은 queue라는 곳에서 관리가 되는데, 스케줄러는 이 프로세스들을 queue에 넣고 빼주는 역할을 한다.

 

Queue의 종류

• Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄러 종류

• 장기 스케줄러: 어떤 프로세스를 ready queue에 보낼 지 결정하는 스케줄러
• 단기 스케줄러: 어떤 프로세스를 실행시킬지 결정하는 스케줄러
• 중기 스케줄러: 메모리 공간이 부족할 경우 어떤 프로세스를 디스크로 swap out할 지 결정하는 스케줄러

 

CPU 스케줄링 알고리즘

어떤 프로세스가 CPU를 할당받아 실행 중인 상황에서..

 

선점 스케줄링: 다른 프로세스가 현재 프로세스를 중단 시키고 cpu를 선점 가능한 방식

• priority scheduling : 우선순위가 높은 순서대로 처리
  • starvation 발생 가능 → aging을 통해 해결 가능
• Round Robin : 각 프로세스에 동일한 시간의 time quantum만큼 할당하고, 할당 시간이 지나면 다시 ready queue의 맨 뒤로 보내는 방법
  • 프로세스가 기다리는 시간이 cpu를 사용할 만큼 증가하기 때문에 공평한 스케줄링이라 볼 수 있음
  • time quantum이 길어지면 FCFS와 같아지고, 짧아지면 context-switch가 잦아져 overhead가 발생
• Multilevel Queue : 작업을 여러 종류의 큐로 나누어 큐마다 다른 time quantum 할당
• Multilevel-feedback Queue : Multilevel에서 time quantum을 채우면 다음 level로 내려감

비선점 스케줄링: cpu 선점이 불가능한 방식

• FCFS(First Come First Served): 큐에 도착한 순서대로 CPU 할당
  • 소요 시간이 긴 프로세스가 먼저 도착하면 평균 대기시간이 길어짐 (convoy effect)
• SJF(Shortest Job First): 수행시간이 짧은 것 부터 CPU 할당
  • 소요 시간이 긴 프로세스는 영영 cpu를 할당 받지 못 할 수 있음 (starvation)