[혼공학습단 10기][혼공컴운] CPU 스케줄링

✓ CPU 스케줄링 개요

✏️ CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것 

 

 

프로세스 우선순위

• 입출력 집중 프로세스 I/O bound process: 입출력 작업(입출력 버스트)이 많은 프로세스. 대기 상태에 더 많이 머무름
• CPU 집중 프로세스 CPU bound process: CPU 작업(CPU 버스트)이 많은 프로세스. 실행 상태에 더 많이 머무름

💡 입출력 집중 프로세스가 우선순위가 높다. 
입출력 집중 프로세스를 가능한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이기 때문. 

 

 

스케줄링 큐

• 준비 큐 ready queue: CPU를 이용하고 싶은 프로세스들이 서는 줄
• 대기 큐 waiting queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄 

 

 

스케줄링 종류

• 선점형 스케줄링 preemptive scheduling
  • 지금 CPU를 사용중인 프로세스로부터 CPU 자원을 강제로 빼앗아 급한 프로세스에 할당하는 스케줄링 (독점 불가능)
  • 장점: 모든 프로세스가 자원을 골고루 사용할 수 있음
  • 단점: 문맥 교환 과정에서 오버헤드가 발생할 수 있음

 

• 비전점형 스케줄링 non-preemptive scheduling
  • 프로세스가 자원을 사용하고 있다면 다른 프로세스가 끼어들 수 없는 스케줄링 (독점 가능) 
  • 장점: 문맥 교환에서 발생하는 오버헤드가 선점형 보다 적다.
  • 단점: 모든 프로세스가 골고루 자원을 사용할 수 없다. 

 

---

 

✓ CPU 스케줄링 알고리즘

1) 선입 선처리 스케줄링 FCFS First Come First Served scheduling

• 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식.
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다.

💡 호위효과: 실행 시간이 짧은 프로세스가 앞선 프로세스들의 순서가 끝날 때 까지 긴 시간을 기다려야 하는 것 

 

 

2) 최단 작업 우선 스케줄링 SJF Shortest Job First scheduling

• 기본적인 비선점형 스케줄링 알고리즘.
• 큐에 삽입된 프로세스들 중 CPU 이용 시간이 가장 짧은 프로세스부터 실행. 

 

 

3) 라운드 로빈 스케줄링 round robin scheduling

• 선입 선처리 스케줄링 + 타임 슬라이스(각 프로세스가 CPU를 사용할 수 있는 정해진 시간)
• 정해진 타임 슬라이스만큼의 시간동안 돌아가며 CPU를 이용하는 선점형 스케줄링.

❗️타임 슬라이스의 길이가 중요하다.
너무 크면 호위효과가 발생할 가능성이 생기고 너무 작으면 문백 교환에 발생하는 비용이 커서 프로세스를 처리하는 것 보다 전환하는 데 온 힘을 다 쓸 수 있기 때문이다. 

 

 

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

• 최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘
• 정해진 타임 슬라이스만큼 CPU사용하되 CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택 됨 

 

 

5) 우선순위 스케줄링 Priority scheduling

• 프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘.
• 우선순위가 같은 것들은 선입 선처리로 스케줄링된다.

💡 기아현상과 에이징 
기아현상 starvation: 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 것. 
에이징 aging: 오랫동안 대기한 프로세스의 우선순위를 점차 높여서 기아현상을 방지하는 것

 

 

 

6) 다단계 큐 스케줄링 multilevel queue scheduling

• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식.
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위에 있는 프로세스들을 처리한다.
• 이렇게 되면 큐마다 프로세스를 구분하여 실행할 수 있고 큐마다 다른 알고리즘을 사용할 수도 있다.
• 그러나 큐 사이를 이동할 수 없어서 기아현상이 발생할 가능성이 있다.  

 

 

 

7) 다단계 피드백 큐 스케줄링 Multilevel feedback queue scheduling

• 큐 사이를 이동할 수 있는 다단계 피드백 큐 스케줄링 
• 에이징 기법을 적용하여 기아 현상을 예방할 수 있다. 

💡 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킨다. 이를 통해 CPU를 오래 사용해야 하는 프로세스(CPU 집중 프로세스)의 우선순위가 점차 낮아지고 CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스럽게 우선순위가 높은 큐에서 실행이 끝남.