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

안녕하세요 BlockDMask 입니다.

오늘은, 운영체제에서 

프로세스의 스케줄링에 대해 알아보겠습니다.

1) 스케줄링(Scheduling)이란.

• 실행중인 모든 프로세스들에게 골고루 CPU를 할당하는일.
  
  

• 멀티 프로세스를 지원하는 운영체제의 스케줄러가 담당한다.
  
  

• 스케줄러는 일정한 기준(스케줄링 알고리즘)에 의거하여 스케줄링을 한다.

2) 선점형 운영체제, 비선점형 운영체제
(Preemptive OS, non-preemptive OS)

• Preemptive OS 
  - 현재 실행중인 프로세스A보다 높은 우선순위를 가진 프로세스B가 등장하면 스케줄러에 의해 실행 순서가 조절된다.
  - 우선순위가 높은놈이 오면 현재 running 상태에 있는 프로세스A가 ready상태로 밀려가고 프로세스 B가 running 상태로 CPU를 할당받는다.
  
  
• non-preemptive OS 
  - 현재 실행중인 프로세스A가 끝나야지 그 다음 프로세스가 CPU를 할당받을 수 있다.
  - 우선순위가 높은 높이 Ready상태에서 대기하더라도, 현재 running 상태에 있는 프로세스A의 일이 끝나야지 프로세스B가 CPU를 할당 받을 수 있다.
  

**running, ready등 프로세스의 상태변화의 자세한 내용은 여기 있습니다.

3) 우선순위 스케줄링 알고리즘 (Priority Scheduling Algorithm)

• 각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스 먼저 실행시키는 방법이다.
  
  

• 우선순위가 높은 프로세스가 ready queue의 앞쪽으로 들어가서 running 상태로 우선적으로 들어가게된다.
  
  

• 선점형 운영체제(Preemptive OS)의 대표적인 특징이다.
  
  

4) 라운드로빈 스케줄링 알고리즘
(Round Robin Scheduling Algorithm)

• 실행의 최소 단위시간을 타임퀀텀(Time Quantum) 또는 타임슬라이스(Time Slice)라 하는데, 이를 기준으로 하여서 정해진 시간마다 CPU를 할당하고 그 시간이 지나면 다음 프로세스를 타임퀀텀만큼 CPU를 할당한다.
  
  

• 타임슬라이스, 타임퀀텀의 기준이 중요합니다. 
  - 너무 길면 바로 반응이 오는 시스템에 문제가 생기고,
  - 너무 짧은 경우에는 문맥전환(Context Switching)이 자주 발생하여 그만큼 성능의 저하가 올 수 있습니다.

**대부분의 OS에서는 우선순위 스케줄링와 라운드로빈 스케줄링을 섞어서 사용하고 있습니다.

우선순위 순으로 프로세스를 CPU할당을 하면서, 우선순위가 동일한 프로세스의 경우에는 타임퀀텀 만큼 실행하고 다른 동일한 우선순위의 프로세스에게 CPU할당을 넘기는 방식으로 섞어서 사용하고있습니다.

5) 스케줄링 알고리즘에 의해서 스케줄링이 진행되는 시점.

• 매 타임슬라이스, 타임퀀텀 마다 스케줄러 동작.
  
  

• 새로운 프로세스가 등장할때마다 현재 실행중인 프로세스와 비교해야 하므로 스케줄러 동작.
  
  

• 현재 실행중인 프로세스가 종료될 때 마다 다른 프로세스를 실행시켜야 하므로 스케줄러 동작.
  
  

• 현재 실행중인 프로세스가 I/O 요청에 의해 Blocked 상태에 놓일 때 마다 스케줄러 동작.

6) 우선순위 역전현상 (Priority Inversion)

• 프로세스A, B, C가 존재하고 우선순위가 A>B>C 상태로 A가 제일 높다고 가정.
  
  

• 현재 프로세스 A가 running 상태이고 프로세스 B,C가 Ready상태에 있다고 가정하겠습니다.

오늘도 이해가 쏙쏙되는 제 그림을 보시죠.

• 프로세스A가 프로세스C의 결과값을 기다려야 하는 상황이라고 가정한다.(C가 서버프로세스라했을 때 C의 리턴값이 A에게 필요하다고 가정해보자.)
  
  

• 그렇게 되면 A는 C로부터 결과값을 받아야지만 나머지 작업을 진행을 할 수 있으므로, C의 결과값을 기대하면서 Blocked 상태로 들어가게 된다.①
  
  

• 하지만, A가 CPU를 놓게 되면 우선순위 알고리즘을 통해서 프로세스 B가 running 상태로 가서② CPU를 할당받게된다.
  
  

• 이러한 우선순위가 제일 높은 A가 blocked에서 한없이 기다리고 A보다 낮은 B가 running 상태에서 작업을 진행하는 상태를
  Priority Inversion(우선순위 역전현상)이라고 표현한다.
  
  

• 다양한 해결방법이 존재하지만, 하나만 말하자면 이러한 경우에 프로세스 A가 blocked 상태로 가면서 프로세스 C에게 자신의 우선순위를 상속해 주는 방법이 있다. 그럼으로써 A는 C의 결과값을 바로 받아 볼 수 있다. 이러한 방법을 Priority Inheritance(우선순위 상속)이라 한다.

**학교에서 학습한 것과, 참고서적 및 구글링을 통해 공부하면서 정리한 내용입니다.

내용이 이상하거나 지적할 사항들은 말씀해주시면 수정하겠습니다.

글을 쓸때 평어체와 경어체를 섞어서 쓰니 너그럽게 넘어가주시면 감사하겠습니다.