스케줄링(Scheduling)
- 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업
- 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 됨
- 장기, 중기, 단기 스케줄링이 있음
- CPU나 자원을 효율적으로 사용하기 위한 정책임
- 비선점(Non-Preemptive) 스케줄링 : 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법 → FCFS, SJF, 우선순위, HRN, 기한부 등
- 선점(Preemptive) 스케줄링 : 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법 → RR, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등
프로세스(Process)
- 실행중인 프로그램
- 프로시저가 활동중인 것
- 비동기적 행위를 일으키는 주체
- PCB의 존재로서 명시되는 것
SJF(Shortest Job First, 단기 작업 우선)
- 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
- 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
- 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생될 수 있음
RR(Round Robin)
- 시분할 시스템을 위해 고안된 방식
- 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치됨
- 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없음
SRT(Shortest Remaining Time)
- 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법
- 시분할 시스템에 유용함
- 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가함
FCFS(First Come First Service, 선입 선출) = FIFO(First In First Out)
- 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
- 가장 간단한 알고리즘
HRN(Highest Response-ratio Next)
- 대기 시간과 서비스(실행) 시간을 이용하는 기법
- 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것
- 우선순위 계산식 = (대기 시간 + 서비스 시간) / 서비스 시간