프로세스 스케줄링

운영체제의 프로세스 스케줄링(Process Scheduling)은 CPU가 실행할 프로세스들에게 어떤 알고리즘에 따라 CPU에서의 실행 시간을 적절히 배분하는 정책을 말한다.

프로세스의 실행을 특정 조건에서 운영체제가 강제 중단시키고 다른 프로세스를 CPU가 실행하도록 바꿀 수 있으면 선점형(Preemptive) 프로세스 스케줄링, 그렇지 않고 프로세스가 직접 반환해야 하면 비선점 프로세스 스케줄링을 한다고 한다.

프로세스 스케줄링에 사용할 알고리즘은 균형 있고 공정한 실행 시간 배분, 처리율 증가 및 CPU 이용률 최대화, 오버헤드 최소화, 응답시간 최소화, 반환시간 최소화, 대기시간 최소화, 우선순위 설정 및 무한 연기로 인한 기아 상태(Starvation) 회피를 주요 목적으로 두나, 한 번에 전부 이룩하는 이상적인 알고리즘은 만들 수 없다. 그렇기 때문에 시스템의 사용 목적에 따라 알고리즘을 취사선택하게 된다.

현재 CPU에서 실행 중인 프로세스를 교체하는 작업은 컨텍스트 스위칭(Context Switching)이라고 하며, Process Control Block)이라는 메인 메모리 상의 테이블 자료구조를 활용하여 프로세스의 실행 상태를 저장하고 스위칭한 다음 프로세스를 다시 불러와야 하면 PCB를 읽어 복원하는 방법을 쓴다. 이때 CPU <-> 메인 메모리 간의 데이터 통신이 발생하므로 컨텍스트 스위칭은 지연 시간인 오버헤드(Overhead)가 존재하기 때문에 컨텍스트 스위칭 시간 간격을 너무 짧게 하면 안 되며, 그렇다고 너무 길게 하면 반응 시간이 너무 길어지므로 무리해서 CPU 실행 시간을 늘릴 필요도 없다.

종류

선점형

• Round Robin(RR): 시분할 시스템에서 정해진 시간동안 각 프로세스를 실행한 뒤 해당 시간을 넘으면 다음 프로세스에 CPU 사용권을 넘겨주고 준비상태 큐의 맨 뒤로 돌아간다.
• Shortest Remaining Time(SRT): 현재 실행 중인 프로세스의 남은 시간과 준비 상태 큐에 새로 도착한 프로세스의 실행 시간을 비교해 새로 큐에 들어온 프로세스의 실행 시간이 짧으면 선점 처리하여 CPU 사용권을 넘겨준다.
• Multi-Level Queue(MLQ): 프로세스를 그 특성에 따라 여러 그룹으로 나누어 각기 다른 준비상태 큐를 사용함
  • Multi-Level Feedback Queue(MLFQ): MLQ에 조건에 따른 프로세스의 그룹 이동 기능을 추가한 것

비선점형

• First Come First Service(FCFS): FIFO라고도 하며, 준비상태 큐에 도착한 순서에 따라 CPU에 프로세스를 할당한다.
• Shortest Job First(SJF): 실행 시간을 사전에 알 수 있는 경우 실행시간이 짧은 프로세스에 먼저 CPU를 할당한다.
• Highest Response Ratio Next(HRRN): 대기 시간과 실행 시간을 사전에 알 수 있는 경우 우선순위를 (대기 시간 + 실행 시간) / 서비스 시간으로 계산하여 높은 것부터 우선순위를 부여한다.