프로세스 스케줄링(Process Scheduling)과 스케줄링 알고리즘

Process Scheduling icon by DALL-E

프로세스 스케줄링

프로세스 처리를 효율적으로 하기 위해서는 주어진 프로세스가 하나가 아닐 경우 운영체제는 적절하게 어떤 순서대로 프로세스를 처리해야 할지 결정하는 과정을 거치는데, 이것을 프로세스 스케줄링이라고 합니다.

 

프로세스 스케줄링의 목표

프로세스 스케줄링의 주요 목표는 여러가지가 있습니다.

 

프로세스 스케줄링의 주요 목표

• 균형성: 시스템 자원을 효율적으로 사용
• 공정성: 여러 프로세스가 공정하게 실행될 수 있도록 함
• 처리량 극대화
• 응답 시간 최소화
• 대기 시간 최소화

 

위와 같은 목표를 달성하기 위해 운영체제에는 여러 가지 스케줄링 정책과 스케줄링 정책에 따른 다양한 스케줄링 알고리즘이 있습니다.

 

스케줄링 정책

프로세스 스케줄링 정책은 크게 선점형과 비선점형으로 나뉩니다.

 

프로세스 스케줄링 정책

• 선점(Preemptive) 스케줄링 정책
• 비선점(Non-Preemptive) 스케줄링 정책

 

선점 스케줄링 정책은 운영체제가 실행 중인 프로세스를 강제로 중단하고 다른 프로세스에 CPU 할당 할 수 있습니다.

선점 스케줄링 정책은 높은 우선순위의 프로세스를 먼저 처리해야 하는 경우에 유용합니다.

선점 스케줄링 정책은 문맥 교환(Context switching)에 따른 오버헤드가 발생합니다. 이에 따라 운영체제는 문맥 교환이 매우 빠르게 실행되도록 만들어져야 합니다.

 

 

• 문맥은 CPU의 모든 레지스터와 운영체제에 따라 요구되는 프로세스의 기타  상태입니다.
• 문맥 교환(Context switching)은 CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고, 다른 프로세스의 PCB로부터 문맥을 복원하는 작업입니다.

 

 

비선점 스케줄링 정책은 프로세스에 CPU를 할당하여 실행을 시킨 프로세스가 자발적으로 CPU를 반납할 때까지 실행을 계속합니다.

비선점 스케줄링 정책은 강제적인 문맥 교환이 없어서 오버헤드가 발생하지 않습니다.

긴 프로세스가 실행 중이라면 짧은 프로세스가 오래 기다리게 되는 경우가 생깁니다.

 

 

스케줄링 알고리즘

스케줄링 알고리즘은 여러가지가 있으며, 각 알고리즘은 특정 환경이나 목적에 따라 장단점이 있어서 시스템 특성에 알맞게 선택하여 사용됩니다.

 

---

비선점형 스케줄링 알고리즘

 

FCFS(First-Come, First-Served)

• 도착 순서대로 처리
• 단순하지만 convoy effect 발생 가능

 

SJF(Shortest Job First)

• 실행 시간이 가장 짧은 작업 우선
• 평균 대기 시간 최소화
• 실행 시간 예측 어려움

HRN(Highest Response Ratio Next)

• 응답률이 높은 프로세스 우선
• 대기 시간과 서비스 시간 모두 고려

---

선점형 스케줄링 알고리즘

SRTF(Shortest Remaining Time First)

• SJF의 선점형 버전
• 남은 실행 시간이 가장 짧은 프로세스 선택

RR(Round Robin)

• 각 프로세스에 동일한 시간 할당(타임 퀀텀)
• 공정성 보장, 응답 시간 향상

 

다단계 큐(Multilevel Queue)

• 프로세스를 여러 그룹으로 분류하여 각기 다른 큐에 배치
• 각 큐마다 다른 스케줄링 알고리즘 적용 가능

 

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

• 다단계 큐의 확장형
• 프로세스가 큐 사이를 이동 가능

 

우선순위 스케줄링(Priority Scheduling)

• 우선순위가 높은 프로세스 먼저 실행
• 기아 상태(starvation) 발생 가능
  
  

 

 

참고자료

https://80000coding.oopy.io/b271bc98-65be-4722-8299-a087dc014f3c#d84948a3-797f-4c9c-91f6-61c630b4b78d

프로세스 스케줄링을 이해해보자

https://rebro.kr/175

[운영체제(OS)] 5. 프로세스 스케줄링(Process Scheduling)

한국방송통신대학교 운영체제(김진욱 교수, 이인복 교수) 강의