[운영체제] CPU(프로세서) 스케줄링

CPU 스케줄링 알고리즘

---

문맥교환(Context Switching) : 새로운 프로세스에게 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고, 새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업. (Overhead가 발생하는 주요 원인)

CPU 스케줄링이란?

메모리에 있는 준비(Ready) 상태의 프로세스 중 하나를 선택해 CPU자원을 할당하는 것

CPU 스케줄링이 일어나는 시점

• 실행상태에서 대기상태로 전환될 때 (예, 입출력 요청) - Non preemptive(비선점)
• 실행상태에서 준비상태로 전환될 때 (예, 인터럽트 발생) - preemptive(선점)
• 대기상태에서 준비상태로 전환될 때(예, 입출력이 종료될 때)
• 종료될 때(Terminated)

선점과 비선점의 차이는 기존에 CPU를 사용하던 프로세스가 계속 프로세스를 사용할 수 있는데도 불구하고 자원을 빼앗는지에 대한 여부

CPU 스케줄링 종류

비선점(Non-preemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다. 

일괄 처리 방식의 스케줄링(공정하지만 긴급 응답을 요하는 작업에 좋지 않다.)

종류

• FCFS(First Come First Service) : 준비상태 큐에 도착한 순서에 따라 CPU를 할당하는 기법. 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨
• SJF(Shortest Job First) : 실행시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법. 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
• HRN(Highest Response ratio) : 실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 우선순위 계산 결과 값이 높은 것부터 우선순위가 부여된다. 대기 시간이 길수록 계산 결과가 높다. (대기시간 + 서비스시간 / 서비스시간)
• 기한부(DeadLine) : 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
• 우선순위(Priority) : 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

선점(Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행 하고 있을 때 우선순위가 높은 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

선점으로 인한 많은 오버헤드가 발생한다.

시분할 시스템에 사용하는 스케줄링이다. (긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용)

선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요하다.

종류

• SRT(Shortest Remaining Time) : 현재 실행 중인 프로세스의 남은 시간과 대기 큐에 프로세스의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법 (비선점 기법인 SJF 알고리즘의 선점 형태로 변경한 기법)
• 선점 우선순위 : 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
• RR(Round Robin) : 시분할 시스템을 위해 고안된 방법으로, FCFS 알고리즘을 선점 형태로 변형한 기법. 대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다. CPU를 사용할 수 있는 시간(Quantum)동안 CPU를 사용한 후에 다시 대기 큐의 가장되로 배치된다. 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생됨
• 다단계 큐 : 프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용한다.
• 다단계 피드백 큐 : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법

에이징(Aging) 기법

특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계식 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다.