[운영체제] CPU 스케줄링 알고리즘

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

---

선입선출(FCFS:First Come First Served) 스케줄링

• 비선점형방식
• 단순히 준비 큐에 삽입된 순서대로 처리하는 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU할당
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다. (=호위효과)

 

---

 

최단 작업 우선 스케줄링(SJF:Shortest Job First)

• 선점형이나 비선점형 둘다 구현될 수 있지만 보통 비선점형으로 구현
• 호위 효과를 줄이기위해 고안된 스케줄링
• 실행 시간이 가장 짧은 프로세스에 우선순위를 매긴다.
• CPU 사용이 긴 프로세스는 나중이 실행, CPU 사용 시간이 짧은 프로세스를 먼저 실행

 

---

 

라운드 로빈(RR:Round Robin) 스케줄링

• 선점형 방식
• 선입선출 스케줄링 + 타임 슬라이스(time slice)
• 정해진 타임 슬라이스 만큼의 시간 동안 돌아가며 CPU를 이용하는 스케줄링

타임 슬라이스
각 프로세스가 CPU를 사용할 수 있는 정해진 시간.
타임 슬라이스의 크기가 너무 짧으면 오버헤드가 자주 발생하고, 너무 길면 선입선출 스케줄링과 다를게 없다.

 

---

 

최소 잔여 시간 우선 스케줄링(SRT:Shortest Remaining Time)

• 선점형 방식
• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
• 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당

 

---

 

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

• 선점형 방식과 비선점형 방식이 둘다 존재
• 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선출로 스케줄링
• 최단 작업 우선 스케줄링과, 최소 잔여 시간 스케줄링은 넓은 범위에서 우선순위 스케줄링이라고 볼 수 있다.

 

우선순위 스케줄링은 기아(starvation)현상이라는 근본적인 문제점을 가지고 있다.

기아(starvation)현상
우선순위가 높은 프로세스만 계속 실행되는 것이다. 즉, 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 계속 실행이 연기된다.

기아 현상을 해결하기위한 기법으로는 에이징(aging)이 있다.

에이징 기법은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시킨다고 해서 에이징이라고 한다.

 

---

 

다단계 큐 스케줄링(MLQ:MultiLevel Queue)

• 우선선위 스케줄링의 단점을 보완한 형태
• 우선순위별로 준비큐를 여러 개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 각 큐는 자신만의 독자적인 스케줄링 알고리즘과 타임 슬라이스를 가질 수 있다.
• 프로세스는 큐에서 다른 큐로 이동이 불가능 하기에, 기아(starvation)현상이 발생할 수 있다.

 

---

 

다단계 피드백 큐 스케줄링(MLFQ:MultiLevel Feedback Queue)

• 다단계 큐 스케줄링의 기아현상을 보완하기 위한 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 우선순위가 높은 프로세스가 타임 슬라이스 동안 처리가 되지 않으면 한 단계씩 우선순위가 낮아진다.
• 우선순위가 낮은 프로세스가 오래 기다릴수록 우선순위가 높아진다.(에이징)
• 가장 일반적인 CPU 스케줄링 알고리즘으로 알려짐

즉, 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.

구현이 복잡하지만, 가장 일반적인 CPU 스케줄링으로 알려져 있다.