운영체제 - CPU 스케줄링

1. Starvation & Deadlock ?

Deadlock 은 여러 프로세스가 동일 자원 점유를 요청할때 발생하고
Starvation 은 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 영원히 자원이 할당되지 않는 경우를 말한다

Starvation 해결책

• 프로세스 우선순위를 수시로 변경해서 각 프로세스가 높은 우선 순위를 가질 기회를 준다
• 오래 기다린 프로세스의 우선순위를 높여준다 (aging 기법)
• 우선 순위가 아닌 요청 순서대로 처리하는 FIFO 기반 요청 큐를 사용한다

 

2. CPU 스케줄링 이란 ?

만약 CPU 코어가 1개라면 한번에 하나의 프로세스만 실행이 가능하다. 이때 필요한것이 CPU 스케줄링이다.

이전 글에서 알아봤듯이 프로세스는 생성되고 난 뒤 여러 상태를 거치게 된다

운영체제의 CPU 스케줄러는 Ready 상태의 프로세스 중에서 어떤 프로세스에게 CPU 를 할당할지 결정합니다
이것을 바로 CPU 스케줄링이라고 한다

CPU 스케줄링은 규모에 따라 장기, 중기, 단기 스케줄링으로 구분된다

1. 장기 스케줄링 (Long-term scheduler)
   • 가장 큰 틀에서 이루어지는 CPU 스케줄링 이다 (고수준 스케줄링, 작업 스케줄링 이라고 한다)
   • 프로세스에 Memory 를 주는 문제를 스케줄링 한다
   • 전체 시스템의 부하를 고려하여 작업요청을 받을지 거부할지에대한 결정을 한다 즉 new 상태의 프로세스를 ready 상태로 admitted 하는 작업을 장기 스케줄러가 한다
2. 중기 스케줄링 (Medium-term scheduler, Swapper)
   • 중기 스케줄링은 이미 활성화된 (Memory 에 올라가있는) 프로세스들에 대한 관리를 한다
   • 시스템의 과부하를 막기위해 활성화된 프로세스들의 중지 여부를 결정하여 활성화된 프로세스 수를 조절한다
   • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다 (Swap out)
   • 중기 스케줄링에 의해 중지된 프로세스들은 보류 상태 (Suspended, Stopped) 가 된다
3. 단기 스케줄링 (Short-term scheduler, CPU scheduler)
   
   • 단기 스케줄링은 가장 작은 단위의 스케줄링이다
   • 어던 프로세스에 CPU 를 할당할지 어떤 프로세스를 대기상태로 보낼지 등을 결정
   • 단기 스케줄러가 어떤 기준에 따라 프로세스를 선택(스케줄링 알고리즘) 하고 어느정도 자원을 배분할지에 따라 시스템에 큰 영향을 끼친다

 

CPU 스케줄러는 언제 스케줄링을 결정하는가 ?

1. 실행(running) 상태에서 대기(waiting) 상태로 전환(switching) 될 때
2. 실행(running) 상태에서 준비(ready) 상태로 전환(switching) 될 때
3. 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching) 될 때
4. 종료(Terminated) 될때

이때 1,4 번 상황에서 발생하는 스케줄링을 비선점형(non-preemptive) 스케줄링 이라고 한다
이외의 모든 스케줄링은 선점형(preemptive) 스케줄링 이라고 한다

 

3. 비선점형(non-preemptive) 스케줄링

어떤 프로세스가 CPU 를 점유하고 있다면 이를 뺏을 수 없는 방식으로 강제로 프로세스를 중지하지 않는다
따라서 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다

비선점형 스케줄링의 종류에대해 알아가보고자 한다

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

• FCFS 스케줄링은 가장 먼저 요청한 프로세스에 CPU 를 할당해주는 선착순 방식이다
• Convoy Effect (호위 효과) 가 발생할 수 있다. Convoy Effect 는 몇개의 시간이 오래 걸리는 프로세스로 인해 전체 OS 가 느려지는 현상을 말한다

 

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

• SJF 스케줄링은 실행시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘이다 
• 하지만 실제로 프로세스의 CPU 실행 시간을 예측하는 것이 어려운 문제가 존재한다
• 또한 긴 시간을 필요로 하는 프로세스가 계속 우선순위가 밀리면서 무기한 대기하게되는 기아(Starvation) 현상이 일어날 수 있다

 

우선순위 스케줄링 - Priority

• 우선순위 스케줄링은 각각의 프로세스에 우선수위 넘버가 있는 알고리즘
• 예를들어 SFJ 알고리즘의 경우, 낮은 우선순위의 프로세스가 절대 실행되지 않는 기아(Starvation) 문제가 발생할 수 있는데 이를 해결하기 위해서 노화(aging)를 사용할 수 있다

 

4. 선점형(preemptive) 스케줄링 

선점형 스케줄링은 현대 운영체재가 채택한 스케줄링 방식으로, 어떤 프로세스가 CPU 를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식. 알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU 를 할당하는 방식

처리시간이 매우긴 프로세스의 CPU 의 사용독점을 막을 수 있어 효울적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인한 오버헤드가 커질 수 있다

최소 잔류 시간 우선 스케줄링 - SRTF (Shortest Remaing Time First)

• 실행되고 있는 프로세스는 중단 없이 끝까지 실행하는 비선점형 SJF 와는 다르게 선점형 SRTF 에서는 현재 실행되고있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행하고있는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꾸게 된다
• SRTF 는 평균 대기시간을 줄일 수 있지만 역시 다음 프로세스의 CPU burst time 을 예측하는 것이 어렵다는 문제가 존재한다

 

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

• 현대 컴퓨터가 사용하는 우선순위 스케줄링 이다 각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU 를 이용하게 한다. 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어가므로 선점형 방식이다
• 응답 시간을 빠르게 할수 있는 장점이 있지만 할당 시간이 길면 FCFS 처럼 동작하고, 반대로 할당시간이 너무 짧으면 process sharing 이라고 부른다. 이것은 n 개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미한다

 

멀티레벨 큐 스케줄링 - Multi Level Queue

• 멀티레벨 큐 스케줄링은 작업들을 여러종류의 다른 스케줄링 그룹으로 분할, 그룹별 큐를 이용하여 상위 단계의 큐가 작업을 선점한다
• 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리가 안되는 기아(Starvation) 현상이 나타날 수 있으며, 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성이 떨어지는 특성이 있다

 

멀티레벨 피드백 큐 스케줄링 - Multi Level Feedback Queue

• 멀티레벨 큐 스케줄링 에서는 프로세스들이 영구적으로 하나의 준비 큐에 할당 되었다. 이와 다르게 멀티레벨 피드백 큐 스케줄링 에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다
  1. 프로세스가 처음으로 시스템에 진입했을 때에는 최상위 큐에 삽입한다
  2. 만약 실행중인 프로세스가 자꾸 모든 타임 슬라이스를 소진하여 CPU 시간을 너무 많이 사용한다면 한 단계씩 밑으로 내려보내, 하위 큐의 뒤로 삽입한다 (CPU bound 프로세스)
  3. 만약 하위 큐에 있는 프로세스가 타임 슬라이스를 다 소진하지 않고 대기상태로 돌아가면서 CPU 를 반납한다면 상위 큐에 삽입하여 위로 거슬러 올라가도록 한다 (I/O bound 프로세스)
  4. 따라서 하위 큐로 갈수록 CPU bound 프로세스임을 알 수 있으며 가장 하위 큐는 FCFS 로 스케줄링을 실행한다
• 하지만 이러한 방법은 하위 큐에서는 기아 상태가 발생할 수 있는데, 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동시키는 노화기법(Aging)을 통해 기아상태를 예방한다

 

---

참고 :

• https://velog.io/@qq7455/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9A%94%EC%95%BD%EC%A0%95%EB%A6%AC
• https://kjhoon0330.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81#3.%202.%F0%9F%A4%94%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%20%EC%8B%9C%20%EA%B3%A0%EB%A0%A4%EC%82%AC%ED%95%AD
• https://happydhkim.tistory.com/entry/%EA%B8%B0%EC%95%84%EC%83%81%ED%83%9CStarvation%EB%9E%80

• https://eun-jeong.tistory.com/17