[CS] CPU 스케줄링

📌 다수의 프로세스가 준비 상태에 있을 때, CPU가 어느 프로세스를 먼저 처리하도록 할 것 인가를 결정하기 위한 작업

☑️ 스케줄링의 단계

1. 장기 스케줄링(Long-term Scheduling)
   1. 장기 스케줄링은 고수준 스케줄링, 작업 스케줄링이라고도 함
   2. 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정
   3. 가장 큰 틀에서 이루어지는 CPU 스케줄링으로 시스템 내의 전체 작업수를 조절
2. 중기 스케줄링(Medium-term Scheduling)
   1. 중기 스케줄링은 중간 수준 스케줄링이라고도 불림
   2. 중기 스케줄링은 이미 활성화가 된 프로세스들에 대한 관리를 함
   3. → 이미 활성화된 프로세스들의 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막음
   4. 운영체제는 처리가 보류된 프로세스들을 처리 재개가 가능할 때까지 주기억장치에서 하드 디스크로 옮기는데, 이 과정을 스왑아웃(Swap Out)이라고 부르고, 반대를 스왑인(Swap In)이라고 함
3. 단기 스케줄링(Short-term Scheduling)
   1. 단기 스케줄링은 가장 작은 단위의 스케줄링으로 저수준 스케줄링이라고도 불림
   2. 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정.
   3. 보통 CPU스케줄링이라고 하면 바로 이 단계를 말함

☑️ 스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정 받아야하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안됨
• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 함
• 안정성 : 우선 순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하는 프로세스로부터 보호해야 함
• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야함. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 함
• 반응 시간 보장 : 응답이 없는 사용자는 시간이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함
• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안됨

 

---

스케줄링 시 고려 사항

☑️ 선점형 스케줄링과 비선점형 스케줄링

• 선점형 스케줄링(Preemptive Scheduling)
  • ‘선점’은 빼앗을 수 있음을 뜻함
  • 어떤 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
  • Timeout, I/O Interrupt, System call emd
  • 문맥교환 같은 부가적인 작업으로 인해 오버헤드가 발생
• 비선점형 스케줄링(Non-Preemptive Scheduling)
  • 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
  • 문맥교환에 의한 낭비가 적지만, CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 될 수 있음

---

1️⃣실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 ( ex : I/O 발생 ) → 비선점형 스케줄링

2️⃣실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : intterupt 발생 ) → 선점형 스케줄링

3️⃣대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : I/O 완료 시 ) → 선점형 스케줄링

4️⃣종료(Terminated, Exit)될 때 → 비선점형 스케줄링

 

---

☑️ 프로세스 우선순위

• 대부분의 CPU스케줄러는 우선순위를 사용 → 우선순위가 있다는 것은 프로세스의 중요도가 다르다는 의미
• 프로세스는 크게 커널 프로세스와 일반프로세스로 나누며, 보통 커널 프로세스를 높은 우선순위에 둠

☑️ CPU bound process와 I/O bound process

• 프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하면 CPU burst, 입출력 작업을 하면 I/Oburst라고 함
• CPU bound process (CPU 집중 프로세스) : 수학 연산과 같이 CPU를 많이 사용하여 CPU burst가 많은 프로세스
• I/O bound process (입출력 집중 프로세스) : 입출력을 많이 사용해 I
• 두 프로세스 간에는 I/O bound process를 먼저 실행상태로 옮기는 것이 효율적
• → I/O bound process의 경우 CPU를 할당받아도 금방 대기 상태로 빠지는 반면 CPU bound process의 경우 할당받은 CPU 시간을 전부 사용하는 경우가 많기 때문

☑️ 전면 프로세스와 후면 프로세스

• 전면 프로세스 : GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스. 사용자와 상호작용이 가능해 상호작용 프로세스라고도 불림
• 후면 프로세스 : 사용자와 상호작용이 없는 프로세스이며, 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고 불림

 

---

CPU 스케줄링 알고리즘

☑️ 스케줄링 알고리즘의 선택 기준

1. CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정
2. 처리량 : 단위 시간 당 작업을 마친 프로세스의 수
3. 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기한 시간
4. 응답 시간 : 프로세스 시작 후 첫번째 출력 또는 반응이 나올때까지 걸린 시간
5. 변환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간

☑️ 스케줄링 알고리즘의 종류

📌 선입 선처리(FCFS: First-Come First-Served) 스케줄링

• 프로세스들이 준비 대기열에 도착하는 순서에 따라 CPU를 할당하는 방식
• 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어지는 문제가 있음. (→ 호위 효과 :: Convoy Effect)

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

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU에 할당하는 방식
• 작업 시간이 긴 프로세스의 처리가 계속해서 뒤로 밀리는 아사(starvation) 현상이 발생할 수 있음
• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움. 때문에 SJF 스케줄링을 사용하기 힘듦

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

• 각 프로세스에 동일한 크기의 시간을 할당받은 후, 해당 시간 동안 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 프로세스가 CPU를 일정 시간 동안 사용한 후, 다른 프로세스에 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 콘베이 효과가 줄어듦
• 타임 슬라이스가 너무 큰 경우 FCFS 스케줄링과 다를게 없어짐
• 타임 슬라이스가 너무 작은 경우 문맥 교환이 너무 자주 일어나 전반적인 성능이 떨어짐
• 결론적으로 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는것이 중요

📌 최소 잔류 시간 우선(SRT: Shortest Remaining Time) 스케줄링

• SJF 스케줄링과 RR 스케줄링을 혼합한 방식.
• 기본적으로 RR 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때, 남아있는 작업시간이 가장 적은 프로세스를 선택
• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 추가 작업 시간이 발생

📌 우선순위(Priority Scheduling) 스케줄링

• 정수로 우선순위 값을 설정하여 스케줄링하는 방식. 즉, 우선순위가 높은 프로세스를 먼저 처리해주는 방식
• 비선점형 방식과 선점형 방식에 모두 적용할 수 있음
• 우선순위 스케줄링 역시 SJF처럼 Starvation 문제가 있을 수 있지만, Aging 기법을 사용하여 이를 해결할 수 있음

👉🏻 Aging 기법? : 프로세스가 기다리는 시간이 길어질수록 우선순위를 높여 한 프로세스가 무한정 기다리지는 않도록 해주는 방법

📌 다단계큐(MQ: Multilevel Queue) 스케줄링

• 프로세스 특성별로 준비 큐를 여러 개 두어 우선순위를 부여하고, 높은 우선순위 큐들이 모두 비었을때만 다음 단계의 낮은 우선순위의 큐 프로세스들에게 CPU를 할당하는 방식
• 한 번 우선순위가 매겨서 준비 큐에 들어가면 이 우선순위는 바뀌지 않음
• 각 큐에는 자체 스케줄링 알고리즘을 구현할 수 있음

📌 다단계 피드백 큐(MFQ: Multi-level Feedback Queue) 스케줄링

• 현재 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘임
• Multilevel Feedback Queue 역시 큐를 여러 개로 분할했다는 점에서는 Multilevel Queue와 동일하지만, 다른 점은 바로 프로세스가 다른 큐로 이동이 가능하다는 것
• 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화함
• 반대로, 실행 중인 프로세스가 주어진 타임 퀀텀을 모두 소진한 후 CPU를 강제로 회수당하면, 이 프로세스는 계산 성향이 강해진 것으로 인식하여 이 프로세스를 입/출력 성향 기준 한 단계 낮은 준비 큐로 이동시킴
• 우선 순위가 낮은 프로세스가 높은 프로세스보다 CPU를 얻을 확률이 여전히 낮음. 따라서 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정함.
• 맨 마지막 큐는 FCFS방식으로 처리됨

---

[운영체제(OS)] CPU 스케줄링 - (1) CPU 스케줄링의 개념

[운영체제(OS)] CPU 스케줄링 - (2) 스케줄링 알고리즘