CPU Scheduling

스케줄링

CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 이때 다음 프로세스가 어느 프로세스인지를 선택하는 알고리즘을 CPU Scheduling 알고리즘이라고 한다. 

 

 

비선점

 한 프로세스가 CPU를 할당받아 실행중이라면 다른 프로세스들이 CPU를 강제적으로 뺏을 수 없는 스케줄링 방식

1. FCFS (First Come First Served)  : 자료구조 큐의 데이터 처리
   • 큐에 도착한 순서대로 CPU 할당
2. SJF (Shortest Job First) : 우선순위 큐의 데이터 처리(최소 시간)
   • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행(FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리)
3. HRN (Hightest Response-ratio Next) : 우선순위 큐의 데이터 처리 (가중치)
   • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
   • 우선순위 = (대기시간 + 실행시간) / (실행시간)

 

선점

Preemptive(선점)은 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유 할 수 있다.

1. Priority Scheduling : 우선순위 큐의 데이터 처리
   • 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
   • 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
   • Aging 방법으로 Starvation 문제 해결 가능
2. Round Robin : Time Quantum만큼 배분된다는건 실행시간이 짧은 거에 우선순위를 두고 처리하자는건가?
   • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음 (Time Quantum or Time Slice : 실행의 최소 단위 시간)
   • 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가
3. Multilevel-Queue (다단계 큐)
   • 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법

4. Multilevel-Feedback-Queue (다단계 피드백 큐)

           - time quantum 가중치를 준다고 한다.

 

 

 

 

 

 

 

 

 

 

• 선점 스케줄링 : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
• 비선점 스케줄링 : I/O or Event Wait, Exit

 

 

프로세스의 상태 전이

✓ 승인 (Admitted) : 승인 = 프로세스 생성이 가능하여 승인됨.

✓ 스케줄러 디스패치 (Scheduler Dispatch) :  실행 = 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

✓ 인터럽트 (Interrupt) : 강제 변경 = 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

✓ 입출력 또는 이벤트 대기 (I/O or Event wait) : 입출력/ 이벤트 대기 = 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

✓ 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/ 이벤트 실행 완료 = 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.