CPU 스케줄링 ② 스케줄링 알고리즘

7가지의 CPU 알고리즘

 

아이디어와 작동 방식 정도 숙지하기.

• 선입 선처리 스케줄링 (FCFS, First Come First Served)
• 최단 작업 우선 스케줄링 (SJF, Shortest Job First)
• 라운드 로빈 스케줄링 (RR, Round Robin)
• 최소 잔여 시간 우선 스케줄링 SRT, Shortest Remaining Time)
• 우선순위 스케줄링
• 다단계 큐 스케줄링 (Multilevel queue)
• 다단계 피드백 큐 스케줄링 (Mulitilevel feedback queue)

---

선입 선처리 스케줄링 (FCFS, First Come First Served)

단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링.

먼저 CPU를 요청한 프로세스부터 CPU 할당.

 

• 단점: 프로세스들이 기다리는 시간이 매우 길어줄 수 있다는 부작용 = 호위 효과

뒤에서 기다리는 프로세스의 대기 시간이 너무 길어질 수 있음

 

---

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

호위 효과를 방지하려면?

CPU의 사용이 긴 프로세스를 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행.

 

CPU 사용 기간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

---

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

라운드 로빈: 차례로 뭘 한다라고 할때 CS에서 많이 사용되는 용어

 

선입 선처리 스케줄링 + 타임 슬라이스(time slice)

* 타임 슬라이스(time slice) : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

 

정해진 타임 슬라이스만큼의 시간 동안을 돌아가며 CPU를 이용하는 선점형 스케줄링

• 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼 이용
• 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)

타임 슬라이스가 너무 커져버리면 선입선처리랑 비슷해짐 호위효과가 발생할 수 있음

타임 슬라이스가 너무 작아져버리면 문맥교환에 발생하는 오버헤드때문에 CPU의 부담이 커질 수 있음

---

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

 

최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링

 

정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택.

---

우선순위 스케줄링

프로세스들에 우선수위를 부여하고 우선순위 높은 프로세스부터 실행.

우선순위가 같은 프로세스들은 선입 선처리로 스케줄링.

 

최단 작업 우선 스케줄링, 최소잔여시간 스케줄링 모두 넓은 의미에서 ⊂ 우선순위 스케줄링

 

• 우선 순위 스케줄링의 근본적 문제점 : 기아 현상(starvation)
  • 우선순위 높은 프로세스만 주구장창 실행
  • 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기

한도 끝도 없이 미뤄져서 끝끝내 실행되지 않을 수 있음.

• 이를 방지하기 위한 기법: 에이징(aging)
  • 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  • 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법

---

다단계 큐 스케줄링 (Multilevel queue 스케줄링)

 

우선순위 스케줄링의 발전된 형태

우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

 

• 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
• 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스 처리

프로그램 유형별로 우선순위를 구분하는 것이 쉬워진다.

큐별로 스케줄링 방법을 다르게 해서 유형별로 처리하는 것이 쉬워진다.

 

다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동불가

큐 간의 이동이 불가 하다.

즉, 우선순위가 낮은 프로세스는 또 기아현상의 위험이 있다.

우선순위 낮은 프로세스는 계쏙해서 실행 연기 우로

---

다단계 피드백 큐 스케줄링 ( Multilevel feedback queue 스케쥴링 )

다단계 큐 스케줄링이 발전된 형태.

큐 간의 이동이 가능한 다단계 큐 스케줄링

 

• 새롭게 준비상태가 된 큐가 있으면 일단 가장 우선순위가 높은 큐에 넣는다.
• 일정시간(타임슬라이스) 동안 실행하게 한다.
• 이러고 실행이 덜 끝났다면 우선순위가 다음으로 높은 곳에 넣는다.

...의 반복

 

즉 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고

입출력 집중 프로세스의 우선순위는 상대적으로 높아진다.

 

어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고

어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식

 

CPU 스케줄링 방식 중 가장 일반적인 것으로 알려져 있다.

 

에이징기법 적용되기도 한다.