Basic Concepts
Scheduling이란 무엇인가?
CPU Scheduling
- 어떻게 Process에게 CPU를 할당할 것인가
Multiprogramming에 기반함 - Memory 내의 실행 준비된(Ready State)의 Process들 가운데 하나에게 CPU를 할당함
CPU Scheduling의 목표
- CPU 사용률과 처리량의 최대화
Process 수행 사이클의 구성
CPU-I/O Burst Cycle
- CPU Burst : CPU로 연산을 수행하는 시간
- I/O Burst : I/O 처리를 위해 기다리는 시간
- 일반적인 프로세스는 두 Burst를 번갈아 가면 수행함
Process분류에 따른 CPU Burst의 특징
-
CPU-Bound Process: 짧은 주기의 긴 CPU Burst
(=> 자주자주 긴 연산 시간이 소요됨) -
I/O-Bound Process: 긴 주기의 짧은 CPU Burst (= Memory-Bound Process)
(=> 짧은 연산이 소요됨) -
어떤 종류의 Process가 많은지에 따라 스케줄링 기법의 효율성이 달라짐
Scheduling의 종류
CPU Scheduling의 결정은 다음 시점에 따라 이루어짐
- Running에서 Waiting 상태로
- Running에서 Ready 상태로
- Terminated
- Ready에서 Running 상태로
- Ready에서 Running 상태로
비선점형 스케줄링 (Non-preemptive Scheduling)
- 1(I/O, event 발생)과 4(새롭게 CPU를 할당 받는...)의 상황에서만 수행되는 Scheduling기법
- Multiprogramming의 기본 Scheduling - OS가 강제로 CPU 사용을 해제하지 못함
=> I/O나 Event발생으로 인해 프로세스가 CPU를 포기해줘야지 다른 프로세스에게 CPU를 할당해 줄 수 있다.
선점형 스케줄링 (Preemtive Scheduling)
- 그 외의 다른 Scheduling 기법
- OS가 현재 CPU를 사용하고 있는 Process의 수행을 정지할 수 있음 - 2번으로의 상태 변이가 일어남
=> 프로세스가 실행 중인데, OS가 강제적으로 프로세스로부터 CPU의 할당을 해제함.
Scheduling Criteria
CPU 사용률(CPU Utilization)
- 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
처리량 (Throughput)
- CPU가 단위 시간 당 처리하는 프로세스의 개수
응답 시간 (Response Time)
- Interactive System에서 요청 후 첫 응답이 올 때까지의 시간
대기 시간 (Waiting Time)
- Process가 Ready Queue 내에서 대기하는 시간의 총합
Turnaround Time
- Process가 시작해서 끝날 때까지 걸리는 시간
이상적인 스케줄러
- 최대의 CPU Utilization
- 최대의 Throughput
- 최소의 Response Time
- 최소의 Watiting Time
모든 조건을 만족 시키는 Scheduler를 만드는 것은 현실적으로 불가능
시스템의 용도에 따른 요구사항이 달라짐
- 슈퍼 컴퓨터 : CPU 사용률
- 개인용 컴퓨터 : 응답시간
- 워크스테이션 : 처리량
Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling
먼저 CPU 할당을 요청한 Process에 CPU를 먼저 할당한다.
- FIFO Queue를 사용하여 간단하게 구현 가능
- 비선점형 스케줄링
대기 시간 :
평균 대기 시간 : (0 + 24 + 27) / 3 = 17
대기 시간 :
평균 대기 시간 : (6 + 0 + 3) / 3 = 3
(1)의 경우 보다 짧은 대기 시간을 가짐
결론 : FCFS는 작업의 수행 순서에 따라 대기 시간이 변할 수 있다.
Shortest-Job-First (SJF) Scheduling
다음 CPU Burst Time이 가장 짧은 Process에 CPU를 먼저 할당한다.
- 최소의 평균 대기 시간을 제공
비선점형 방식
- 한 번 CPU를 할당 받으면 자신의 CPU Burst Time이 끝나기 전에는 놓지 않는다.
평균 대기 시간 : (0 + 6 + 3 + 7) / 4 = 4
(도착한 시간(Arrival Time)부터 계산함에 유의)
선점형 방식
- CPU를 할당 받아 수행 중이더라도 CPU Burst Time이 자신의 현재 남은 시간보다 짧은 시간을 가진 프로세스가 새로 생성되면 CPU를 양보한다.
- Shortest Remaining Time First Scheduling (SRTF)
평균 대기 시간 : (9 + 1 + 0 + 2) / 4 = 3
Priority Scheduling
미리 주어진 Priority에 따라 CPU를 할당
- 비선점형 방식
한 번 CPU를 할당 받으면 자신의 CPU Burst Time이 끝나기 전에는 놓지 않는다. - 선점형 방식
새로 생성된 Process가 현재 실행되는 Process보다 높은 Priority를 가지고 있을 경우, CPU를 양보한다.
문제점 - 기아 상태 (Starvation)
- 낮은 Priority를 가진 Process는 전혀 수행되지 않을 수 있다.
해결 방법 - Aging 기법
- 할당을 기다리는 시간에 따라 Priority를 증가시켜 주는 방법
Round-Robin (RR) Scheduling
CPU를 시간 단위(Time Quantum)로 할당
- 선점형 Scheduling 방식
- 보통 Time Quantum은 10-100ms
- Time Quantum만큼 수행 한 Process는 Ready Queue의 끝으로 들어가 다시 할당을 기다림
전체 CPU Burst Time을 기준으로 각 Process의 응답시간이 짧다.
Ready Queue 내의 Process
- n개
Time Quantum
- q시간
각각의 Process가 할당 받는 시간
- 1/n 만큼의 CPU시간을 q로 쪼개어 할당 받음
각 Process의 다음 Time Quantum이 돌아오기까지의 대기 시간
- 최대 (n-1)*q
성능
- q가 클 경우 : FCFS
- q가 작을 경우 : Context Switching에 필요한 시간보다 낮다면 효율이 매우 떨어짐
Multilevel Queue Scheduling
Ready Queue를 여러 개의 Queue로 분리하여, 각각에 대해 다른 Sceduling Algorithm을 사용하는 기법
Foreground Queue
- Interactive한 동작이 필요한 Process를 위한 Queue
- Round Robin 기법 사용
Background Queue
- CPU 연산 작업을 주로 수행하는 Process를 위한 Queue
- FCFS 기법 사용
각 Queue에 CPU를 어떻게 할당할 것인지를 결정해야 함
- Queue에 대한 Priority 또는 Time Slice를 사용할 수 있음
Multilevel Feedback Queue Scheduling
Multilevel Queue에서 Process들이 서로 다른 Queue로 이동할 수 있도록 한 Scheduling 기법
- Aging의 한 방법으로 사용됨
필요한 요소들
- Queue의 개수
- 각 Queue마다의 Scheduling 기법
- 언제 Process를 한 단계 높은 Queue로 옮길 것인가
- 언제 Process를 한 단계 낮은 Queue로 옮길 것인가
- 어떤 Process가 특정한 Service를 필요로 할 때 그것을 제공하는 Queue로 옮겨줄 방법
3-Level Feedback Queue Scheduling
즉, 생성되고 8 + 16ms 동안 종료되지 않은 Process는 많은 CPU작업을 필요로 하는 Process로 간주하여 FCFS기법을 이용해 충분한 CPU Time을 할당해주는 Scheduling 방법이다.
Multiple Processor Scheduling
여러 개의 CPU를 사용하는 System의 경우, CPU Scheduling이 더욱 복잡해진다.
AMD의 big.LITTLE
- 각각의 CPU에 서로 다른 I/O 장치가 연결되어 있다면?
- 각각의 CPU가 서로 다르다면? (명령어 set, 처리 속도)
비대칭 멀티프로세싱(Asymmetric Multiprocessing)
- 하나의 CPU만이 시스템 자료 구조 (Scheduling, I/O 작업, 등) 관리
- 모든 CPU가 접근할 경우보다 데이터 공유가 간단히 이루어짐
Kernel Multithread가 지원이 안되는 경우
대칭 멀티프로세싱(Symmetric Multiprocessing)
- 완전 자유
Multiprocessor Scheduling 방식
Processor Affinity
- 과거에 수행하던 CPU에 Process를 배정하는 방법
(ex. 오늘...3번 Core가 효율 지리던데...)
Load Balancing
- CPU가 동일할 경우, 동일한 Process들을 수행할 수 있음
- CPU마다 각각의 Ready Queue를 둘 경우
일부 CPU에 Process가 집중될 수 있음 - CPU 모두에 하나의 Ready Queue만을 둘 경우
사용 가능한 CPU에 차례대로 Process를 배정
in Linux
- Completely Fair Scheduling (CFS)
- 범용적으로 쓸 수 있는 운영체제로의 역할을 수행하기 위해 CFS 사용
Its me Glico