CPU Scheduling
: CPU는 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 하는데, 이 때 다음 프로세스를 선택하는 알고리즘
👉 선점 vs 비선점 , Preemptive VS Non-preemptive
선점 Preemptive
- 한 프로세스가 CPU 점유동안 I/O나 인터럽트,작업이 끝나지 않았을 때에도, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있음.
비선점 Non-preemptive
- 선점의 반대, 한 프로세스가 CPU를 점유했다면 , I/O 또는 프로세스가 종료될 때 까지는 다른 프로세스가 CPU를 점유하지 못함.
👉 Scheduling criteria (척도)
여러 스케쥴링 방법의 효율을 구분하는 기준/척도
- CPU Utilization (CPU 이용률)
- Throughput (처리율) : 단위시간 당 처리하는 작업의 수
- Turnaround time (반환시간) : 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간
- Waiting time (대기시간) : Ready 큐 소요 시간
- Response time (응답시간) : Interactive System 에서 중요
CPU Scheduling Algorithms
운영체제에서는 다양한 스케쥴링 정책을 사용함.
- First-Come, Fist-Served(FCFS)
- Shortest-Job-First (SJF)
- Shortest-Remaining-Time-First
- Priority
- Round-Robin (RR)
- Multilevel Queue
- Multilevel Feedback Queue
👉 First-Come, Fist-Served(FCFS)
- 먼저 온 프로세스가 먼저 CPU 를 점유하는 방식
- Non-preemptive
- 호위 효과 (Convoy Effect) : CPU 시간을 오래 사용하는 프로세스가 먼저 수행하는 동안 나머지 프로세스들은 그만큼 오래 기다리는 것을 의미
- 매우 단순하지만, 모든 부분에서 효율적이지 않음.
🔴 예제
소요시간 P1-24ms, P2-3ms, P3-3ms
모든 프로세스가 끝난 시간은 모두 30초로 같음.
평균 대기시간은 시작 프로세스에 따라 17, 3 으로, 들어온 순서로 수행한다고 해도 반드시 효율적이지만은 않음.
👉 Shortest-Job-First
- 실행 시간이 짧은 프로세스 먼저 CPU를 점유하는 방식
🔴 예제: SJF 와 위에서 배웠던 FCFS 의 비교
소요시간 P1-6ms, P2-8ms, P3-7ms, P4-3ms
- 평균대기시간 SJF: 7초, FCFS : 10.25초
- 대기시간 줄이기엔 증명된 최적화된 방식
- 하지만, 비현실적 : 프로세스의 CPU점유 시간을 알 수 없음, 실제로 수행하여 측정하여야 측정 가능
- SJF는 preemptive와 non-preemptive 둘 다 사용가능
🔴 예제: 도착시간이 추가됨 소요시간 ↓
-
비선점형 방식 non-preemptive
: 가장 먼저 도착한 P1 이 수행하는 동안 2,3,4 모두 도착하지만 비선점형이므로 P1이 끝날 때 까지 기다려야 함. (AWT 계산 : 8-1 은, 시작 시간 - 도착 시간)
-
선점형 방식 preemptive
: 프로세스가 도착할 때 마다, 어느 프로세스가 가장 짧은 것인지 선택!
8초인 P1 실행 중, 3초인 P2 도착으로 P1 멈추고, P2 수행
👉 Priority Scheduling
- 우선순위가 높은 프로세스가 먼저 선택되는 알고리즘
- 우선순위는 정수값, 작은 값이 우선순위가 높음
- 우선순위를 정하는 방법 : 내부적 요소, 외부적 요소로 나뉨
Internal: time limit, memory requirement, I/O to CPU burst(I/O작업은 길고, CPU 작업은 짧은 프로세스 우선) 등
External: amount of funds being paid, political factors 등 - preemprive 와 non-preemptive 두 방식 모두 사용
🔴 예제: 우선순위 : P2 > P5 > P1 > P3 > P4
‼️문제점
- Starvation(기아) : CPU의 점유를 오랫동안 하지 못하는 현상
-> 우선순위가 매우 낮은 프로세스가 ready queue 에서 대기하는 중에, 들어오는 프로세스가 모두 우선순위가 높은 상태라면 이미 기다리고 있는 우선순위가 낮은 프로세스는 하염없이 기다려야 함
💡해결방법
- aging : ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여줌
👉 Round-Robin (RR)
- 원 모양으로 모든 프로세스가 돌아가며 스케쥴링 , preemptive
- 시분할 시스템에서 주로 사용
- 일정 시간을 정하여 하나의 프로세스가 수행되고 다시 대기상태로 돌아감, 다음 프로세스 역시 같은 시간동안 수행한 후 대기
- 일정 시간 : Time Quantum (Time Slice)라 부름 , 범위 : 10~100msc
- time quantum 크기에 따라 AWT와 같은 스케줄링 척도가 바뀌기 때문에 time quantum에 매우 의존적임
time quantum 크기 무한: FCFS와 동일하게 동작
time quantum 크기 0 : switching overhead가 매우 증가하여 비효율적
👉 Multilevel Queue, Scheduling
프로세스는 기준에 따라 여러 그룹으로 나뉨
- System processes: 운영체제 커널 수준의 프로세스
- Interactive processes: 유저 수준의 대화형 프로세스
- Interactive editing processes
- Batch processes: 대화형 프로세스의 반대인 것으로 일정량을 한 번에 처리하는 프로세스(Ex, 컴파일러)
- Student processes
여러 성격에 따라 프로세스 그룹을 나눌 수 있는데 이를 하나의 큐에 사용하는 것은 비효율적
-> 각 그룹에 따라 큐를 두어 여러 개의 큐를 사용하는 것이 Muitilevel Queue
👉 Multilevel Feedback Queue
- 여러개의 queue를 사용
- 모든 프로세스는 가장 위의 큐에서 CPU의 점유를 대기
- 이 상태로 진행하다가 이 큐에서 기다리는 시간이 너무 오래 걸린다면 아래의 큐로 프로세스를 옮김
이와 같은 방식으로 대기 시간을 조정 - Multilevel Feedback Queue에서도 각 큐마다 다른 스케줄링, 다른 우선순위 등을 사용 가능
대부분의 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용
프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율을 높일 수 있는 방법 선택
--
비선점형 : FCFS, 비선점형 SJF
선점형 : RR, MLQ, MLFQ, 선점형 SJF(SRF)
--
참고
정리 - https://velog.io/@codemcd/운영체제OS-6.-CPU-스케줄링
강의 - 참고 강의 - 운영체제 양희재 교수님 강의
