[OS] CPU 스케줄링 알고리즘 7가지

 

* 선입 선처리 스케줄링 (FCFS) = first come first served

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

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

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

 

 

 

 

* 최단 작업 우선 스케줄링 (SJF) = shortest job first

 - 호위 효과를 방지하기 위해 CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행

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

선점형이나 비선점형 스케줄링으로 구현할 수 있으며 대부분 선점형으로 구현함.

 

 

 

 

* 라운드 로빈 스케줄링 (RR) = round robin

 - 선입 선처리 스케줄링 + 타임 슬라이스

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

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

"타임 슬라이스의 크기"가 매우 중요함. 타임 슬라이스의 크기가 너무 크면 호위효과가 생길 수 있음. 너무 작으면 문맥교환에서 발생하는 오버헤드 때문에 CPU의 부담이 커지게 됨.

 

 

 

 

* 최소 잔여 시간 우선 스케줄링 (SRTF) = shortest remaining time first

 - 최단 작업 우선 스케줄링 (작업 시간이 짧은 프로세스부터 처리) + 라운드 로빈 스케줄링 (정해진 타임 슬라이스만큼 돌아가며 사용)

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

 

 

 

 

* 우선순위 스케줄링 = priority

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

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

 - "최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링"은 넓은 의미에서 "우선순위 스케줄링"에 포함되는 개념임.

 - 근본적인 문제점: 기아(starvation) 현상

   -> 우선순위가 높은 프로세스만 주구장창 실행.

   -> 우선순위가 낮은 프로세스는 (준비큐에 먼저 삽입되었음에도 불구하고) 실행 연기 

- 방지 기법: 에이징(aging)

  -> 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

  -> 대기중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법: 우선순위가 낮아도 언젠가는 높아지게

 

 

 

 

* 다단계 큐 스케줄링 = multilevel queue

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

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

    -> 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리

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

- 기본적으로 큐 간의 이동 불가

    -> 우선순위 낮은 프로세스는 계속해서 실행 연기 우려

    -> 기아 현상 발생 가능

큐를 여러개 사용할 경우 큐 마다 스케줄링을 다르게 적용해서 프로세스를 유형별로 처리하는게 쉬워짐. 단 우선순위가 낮은 프로세스는 큐간의 이동이 불가하여 계속 우선순위가 낮은 큐에 머무를수 밖에 없어서 기하현상이 발생함.

 

 

 

 

* 다단계 피드백 큐 스케줄링 = multilevel feedback queue

 - 다단계 큐 스케줄링의 발전된 형태

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

- 구현이 어려울 수 있지만 CPU 스케줄링 방식의 가장 일반적인 형태로 알려져있음.

 

Q) 새로운 프로세스가 준비상태로 어떤 큐에 처음으로 삽입되고 작업 순서는 어떻게 되는지?

준비 상태인 프로세스를 가장 높은 우선순위 큐에 삽입을 하고 그 다음에 자기 차례가 되면 CPU를 할당받아서 실행을 하게 된다. 만약 실행이 안 끝났으면 다음 우선순위 큐로 이동을 해서 실행을 한다. 거기서도 실행이 안끝나면 그 다음 우선순위로 이동을 하는 식으로 스케줄링이 진행된다. 따라서, 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아진다.

프로세스가 처음 들어왔을때 가장 높은 우선순위 큐에 삽입됨.

높은 우선순위 큐에서 이동하여 낮은 우선순위 큐로 점차 이동함.

 

 

 

Q) 어떤 프로세스가 CPU를 엄청나게 많이 이용해야 되는데 낮은 우선순위 큐에서 한도 끝도 없이 기다리고 있다면?

일정 시간 이상 어떤 프로세스가 낮은 우선순위 큐에서 기다리고 있었다면 이 프로세스의 우선순위를 점차 높임으로써 에이징 기법을 적용해서 기하현상을 예방할 수 있다. 즉, 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식이 적용된다.  

다단계 피드백 큐에서의 에이징 기법 적용