1. 프로세스 스케줄링

CPU 자원을 언제, 어느 프로세스에게 배당할 것인지를 결정하는 작업

성능 기준

• 중앙처리장치 이용률 : CPU 수행시간 또는 시스템 구동 시간
• 처리량 (Throughput) : 단위 시간당 완료되는 프로세스 수
• 대기시간 (Waiting Time) : 준비 큐에서 대기하는 시간
• 응답시간 (Response Time) : 작업을 제출한 후 첫 응답이 올 때까지의 시간
• 반환시간 (Turnaround Time) : 프로세스가 시스템에 진입하여 작업을 완료하기까지의 시간

2. 방법별 분류

(1) 선점 스케줄링 (preemptive scheduling)

뺏기 가능

• 빠른 응답 시간을 요구하는 시분할 시스템에 유용
• 문맥교환으로 인한 오버헤드 초래
• 응답시간 예측 힘듦
• 기법 : RR, SRT, MLQ, MFQ, 우선순위 스케줄링

(2) 비선점 스케줄링 (NON-)

못뺏음

• 모든 프로세스에 대한 대우는 공정히 처리
• 짧은 작업이 긴작업을 기다리는 경우 발생
• 응답시간 예측가능
• 기법: FCFS, SJF, HRN, 우선순위 스케줄링

3. 프로세스 스케줄링 알고리즘

1) FCFS 스케줄링 - 비선점

First Come First Served

• 대기큐에 도착 순서에 따라 cpu 할당
• 선입선출
• 겉보기엔 공정, 긴작업이 짧은 작업을 오랫동안 기다리게 할 수 있음
• 중요한 작업이 중요하지않은 작업을 기다리게 함
• 대화식 시스템에는 적합 x

2) RR 스케줄링 - 선점

Rround Robin

• FCFS 에 의해 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당
• 주어진 할당 시간내에 처리하지못하면 다음 프로세스로 넘어감. (큐의 가장 마지막으로 이동)
• 다중 프로그래밍 시스템, 시분할 시스템에 효과적
• 할당시간이 길면 FCFS에 수렴
• 할당시간이 짧으면 문맥교환으로 부하 발생

3) SJF 스케줄링 - 비선점

Shortest Job First

• 기다리고 있는 작업중에서 수행시간이 가장 짧다고 판정된 프로세스 먼저 수행
• 기아상태 발생 가능
• 최소의 평균대기시간을 가짐 벗 비현실

4) SRT 스케줄링 - 선점

Shortest Remaining Time

• SJF와 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료되는데, 가장 짧은 시간 소요된다고 판단되는 프로세스 먼저수행
• 현재 실행중인 프로세스라도, 남은 처리 시간이 더짧다고 판단되면 언제라도 실행중인 프로세스가 선점 당함 (기아상태 발생가능)
• 적은 대기시간, 선점 오버헤드 발생

5) HRN 스케줄링 - 비선점

Highest Response ratio Next

• SJF의 스케줄링 긴작업과 짧은 작업간의 지나친 불평등을 보완한 에이징 기법
• 오래 기다린 프로세스는 우선순위가 높아지게 되어 기아상태 해결
• 우선순위 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간

6) 다단계 큐 스케줄링 - 선점

Multi Level Queue

• 여러종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법
• 각 큐의 독자적인 스케줄링 알고리즘 존재
• 큐내의 작업은 FCFS, 큐 간 작업은 선점
• 프로세스 성격에 따라 분류가능

7) 다단계 피드백 큐 스케줄링 - 선점

프로세스가 큐들 사이에 이동하는 기법

• 새로 들어온 프로세스에게 높은 우선순위 할당 단계 1에서 즉시 수행
• 이후 점차 낮은 우선순위를 부여하여 단계 N 쯤되어 나중에는 그작업이 완료 될 때까지 라운드로빈으로 순환

8) 우선순위 스케줄링

각 프로세스에게 우선순위를 부여하여 순위가 높은 순서대로 처리하는 방법 ⇒ 비선점 선점 다 가능

** 기아상태가 발생하는 스케줄링 기법

→ SJF, SRT, 우선순위 스케줄링