[운영체제-5] CPU 스케줄링

1. CPU 스케줄링 기본 개념

CPU 스케줄러

• 메모리에 있는 프로세스들 중 실행 준비가 되어있는 ready 상태의 프로세스를 선택하고, 그 프로세스에 CPU를 할당

 

CPU 스케줄링 결정은 다음의 4가지 상황에서 발생

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때    (Running -> Waiting)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (Running -> Ready)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (Wating -> Ready)
4. 프로세스가 종료될 때                                           (Exit)

 

디스패쳐

• Context Switch
• 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동

 

디스패치 지연 (Latency)

• 하나의 프로세스를 중지하고 다른 프로세스를 실행시킬 때 소요되는 시간

 

스케줄링 기준

• CPU 이용률 (Utilization) : CPU를 가능한 최대한 바쁘게 유지
• 처리량 (Throughput) : 단위 시간 당 완료된 프로세스의 개수
• 총 처리 시간 (Turnaround time) : 프로세스의 제출 시간과 완료 시간의 간격
• 대기 시간 (Wating time) : 준비 완료 큐에서 대기하면서 보낸 시간의 합
• 응답 시간 (Response time) : 하나의 요구를 제출한 후 첫 번째 응답이 발생할 때 까지의 시간

 

2. 스케줄링 알고리즘

선입 선처리 스케줄링 (First-come, First-Served, FCFS)

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받음
• FIFO 큐로 관리

장점	가장 간단한 형태 코드 작성이 쉽고 이해하기 쉬움
단점	순서에 따라 대기 시간의 차이가 큼 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다려야함 비선점형이기 때문에, 시분할에 부적합

 

최단 작업 우선 스케줄링 (Shortest-Job-First, SJF)

• CPU burst가 짧을 수록 CPU를 먼저 할당 받음

장점	최소의 평균 대기시간
단점	다음 CPU 요청의 길이 파악이 어려움 (예측 어려움)

 

선점형 최단 작업 우선 스케줄링(Preemptive SJF)

• 새로 들어온 작업의 burst가 짧다면 현재 실행 중인 작업을 중단하고 burst가 짧은 작업을 수행

 

비선점형 최단 작업 우선 스케줄링(Non-Preemptive SJF)

• 현재 작업을 완료할 때까지 중단하지 않고 계속 작업을 한 뒤에 burst가 짧은 작업을 할당

 

우선 순위 스케줄링 (Priority)

• 우선순위가 프로세스들에 연관되어 있으며, 높은 우선순위를 가진 프로세스에게 CPU 할당

장점	내부적 정의 (시간제한, 메모리 요구, open files수 등) 활용 가능 외부적 정의 (프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양 등) 활용 가능
단점	무한 봉쇄, 기아 상태 -> Aging 고려

 

라운드 로빈 스케줄링 (Round-Robin)

• 시간 할당량(Time Quantum) 이라고 일컫는 작은 단위의 시간을 정의
• 1번에 한 프로세스에게 1번의 시간 할당량 동안 CPU를 할당

장점	시분할 시스템 최적화
단점	시간 할당량에 따른 영향도 존재 너무 클 경우 - FCFS와 동일한 알고리즘이 됨 너무 작을 경우 - Context Switch에 시간을 더 뺏김