스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업이다.
CPU는 한 번의 하나의 작업만 처리 가능한데, 여러개의 작업이 존재할 경우 해당 작업들이 번갈아 가면서 수행되도록 만드는 것을 스케쥴링이라고 한다.
프로세스가 실행되는 순서를 정해주는 작업이라고도 한다.
스케줄링 과정
1. 문맥교환(Context Switching)
문맥교환 "Context Switching에서 Context는 현재 프로세스에 사용되는 자원 혹은 개체들의 상태를 의미한다.
Switching은 교환을 의미한다.
CPU가 스케줄링에 따라서 프로세스들에게 CPU를 할당해 줄 때
1) 현재 CPU가 할당된 프로세스의 정보를 저장.(프로세스 테이블에 레지스터값과 메모리맵(참조비트))
2) 스케줄러에 의한 다음 프로세스 선택
3) 새로운 Process의 정보를 설정.
4) CPU를 할당하여 실행.
이것이 문맥교환 Context Switching이다.
여기서 기존의 프로세스가 가진 정보를 저장하는 과정, 실행될 프로세스가 졌었던 정보를 재할당 하는 과정을 진행하게 된다.
이 과정에서 필요한 정보들은 PCB(Process Control Block) 또는 프로세스 테이블에 저장되어 있다.
brust: 어떤 특정 기준에 따라 한 단위로서 취급되는 연속된 신호 또는 데이터의 모임. 어떤 현상이 짧은 시간에 집중적으로 일어나는 현상. 또는 주기억 장치의 내용을 캐시 기억 장치에 블록단위로 한꺼번에 전송하는 것.
언제 스케줄 하는가
1. 새로운 프로세스가 생성되었을 때
- 부모 혹은 자식 어느것을 스케줄 해도 무방
2. 프로세스 종료 시
- Ready상태의 다른 프로세스
3. 프로세스가 I/O, 세마포어 등으로 대기
- 다른 프로세스 스케줄
4. I/O인터럽트가 발생(즉, 현재 프로세스 중단)
- I/O를 기다리다 이제 막 ready상태가 된 프로세스
- 원래(중단되었던)프로세스
- 제 3의 프로세스
스케줄링 방식
1. Preemptive scheduling(선점형 스케줄링):
클록 인터럽트 또는 다른 인터럽트에 의해 프로세스가 중단되었을 때, 스케줄러는 다음에 실행할 프로세스를 선정.
어떤 프로세스가 CPU를 점유하고 있어도 다른 프로세스가 실행중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.
2. Non-preemptive scheduling(비 선점형 스케줄링):
실행중(running)인 프로세스는 종료 또는 I/O요청으로 block상태로 갈 때 까지 중단되지 않음.
클록 인터럽트 시에도 스케줄링 결정은 이루어지지 않는다.
어떤 프로세스가 CPU를 점유하고 있다면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장된다.
순차적으로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 관계없이 응답시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도도 적고 문맥교환의 오버헤드 가작다.
일괄처리 시스템에 적합하다.
CPU 사용시간이 긴 프로세스 하나가 CPU 사용시간이 짧은 프로세스 여러개를 오래 대기시켜 처리율이 떨어질 수 있다.
CPU를 뺏어갈 수 있다 = 선점형
CPU를 뺏어갈 수 없다 = 비선점형
스케줄러가 프로세스 Running중에 다른 프로세스로 교체할 수 있다 = 선점형
프로세스가 자발적으로 block해야 다른 프로세스로 교체할 수 있다 = 비선점형
스케줄링 목표
All systems
Fairness: 각각의 프로세스에 공평하게 CPU를 할당한다.
balance: 시스템의 모든 부분을 사용 상태로 유지
Batch system(일괄 처리 시스템): 온라인처럼 일에 대한 요청이 발생했을 때 즉각적으로 처리하는게 아닌 일정량을 모아뒀다가 한번에 처리하는 방식
Throughput: 시간당 최대 작업량을 나타냄
Turnaround time: 프로세스의 생성부터 소멸까지의 시간을 최소화 한다.
CPU utilization: CPU가 쉬는 시간이 없도록 한다.
Interactive system(대화형 시스템): 온라인같이 일에 대한 요청을 즉각 처리하여 응답을 받을 수 있는 시스템
Response time: 즉각적으로 처리해야 하는 시스템이므로 요청에 대해 응답 시간을 줄이는게 중요하다.
Proportionality: 사용자의 요구를 만족시킨다.
Real-time system(실시간 시스템): 주어진 문제를 해결하기 위해 정해진 시간동안 처리하는 시스템
Meeting deadlines: 데이터 손실을 피하고, 정해진 시간내에 완료해야 한다.
Predictability: 멀티미디어 시스템에서 품질이 저하되는걸 막아야 한다.
용어
Throughput: 시간당 몇개의 작업을 처리하는가.
Trunaround time: 작업의 시작에서 끝까지 걸린 시간, 한개의 작업을 처리하는데 걸린 시간
CPUutilization: CPU사용률
Response time: 첫 번째 응답이 오는데에 걸린 시간
Proportionality
Deadline
Predictability
Batch System의 스케쥴링
- FCFS(First-Come First-Served)
- SJF(Shortest Job First)
- SRT(Shortest Remaining Time Next)
FCFS(First-Come First-Served)
- 먼저 온 고객을 먼저 서비스 해주는 방식, 먼저 온 순서대로 처리
- 비 선점형(Nonpreemptive)스케줄링
- CPU를 잡으면 CPU brust가 완료 될 때까지 CPU를 반환하지 않는다. 할당된 프로세스가 작업을 완료하면 반환된다.
- Turnaround time은 최소가 될 수 없다.
문제점
Convoy effect: 하나의 큰 프로세스가 CPU를 점유하면 다른 프로세스들이 장시간 실행되지 못하는 현상
| 도착시간 | 종료시간 | 수행시간 | 대기시간 | |
| Job1 | 0 | 24 | 24 | 0 |
| Job2 | 0 | 27 | 3 | 24 |
| Job3 | 0 | 30 | 3 | 27 |
Turnaround time
Job1: 24
Job2: 27
Job3: 30
Job1, 2, 3은 모두 0에 도착했지만 Job1의 긴 수행시간 때문에 수행시간이 짧은 2와 3은 긴 대기시간을 가졌다.
SJF(Shortest Job First)
- 다른 프로세스가 먼저 도착했어도 CPU brust time이 짧은 프로세스에게 선 할당.
- 비 선점형(Non preemptive) 스케줄링
- 프로세스는 더 짧은 프로세스가 도착하면 CPU를 반납한다.
- Turnaround time이 최소.
문제점
starvation: 효율성을 추구하는게 가장 중요한 목표지만 극단적으로 CPU 사용시간이 짧은 프로세스를 선호하므로 사용시간이 긴 프로세스는 영원히 할당받지 못할 수 있다.
SRT(Shortest Remaining Time Next)
- 남은 시간이 짧은것 부터 실행.
- 남은 수행시간이 짧을 수록 우선순위가 높다
- 같은 time이 남았을 경우 아무거나 실행
- SJF의 Preemptive version
Interactive System에서의 스케줄링
- Two level scheduling이 일반적이다. 메모리 스케줄러와 CPU 스케줄러를 사용한다.
Round-Robin
프로세스간의 차별 없이 일정 시간씩 번갈아가면서 실행.
10개의 프로세스가 있다면 10개를 같은 시간만큼 돌아가면서 실행한다.
네트워크 통신에서 묶음의 데이터를 전송할때 사용되기도 함.
Time quantum = 4
Time quantum이 4일 경우 차례로 1 2 3이 실행되고 1회차에 2와 3이 종료되기 때문에 1을 4씩 나누어 실행한다.
Time quantum이 4지만 3만에 작업이 끝났다고 해서 1을 기다리는게 아니라 바로 다음 작업으로 넘어간다.
throughput = 처리한 작업의 개수 / 걸린 시간
30이란 시간동안 Job1, Job2, Job3 작업을 3개를 처리 했으니 throughput은 3/30 = 0/1이 된다.
만약 Time quantum이 증가하거나 줄어들어도 전체 성능은 변하지 않는것 같지만 Time quantum이 늘어날수록 성능은 향상되고 줄어들수록 성능은 안좋아진다. 그 이유는 작업이 변경될때 Context switching이 일어나기 때문이다. Time quantum이 짧아질수록 작업 교체는 많이 일어나고 작업 교체가 일어날때마다 context switching이 더 많이 생기기 때문이다.
Context switch overhead
saving/loading registers, memory maps, updating various table, flushing/reloading memory cache등의 작업이 발생한다.
Contest switch overhead가 1mesc라고 가정)
quantum이 4일경우) CPU이용률 = 4/5
quantum이 100일경우) CPU이용률 = 100/101
Time quantum이 높을 경우 = 높은 CPU효율 / 낮은 응답성
낮을 경우 = 낮은 CPU효율 / 높은 응답성
Priority Scheduling(우선순위 스케줄링)
사용자에 따라 다른 우선순위 할당
- 기아현상을 방지해야함.
- 우선순위 정적인 할당: 교수 100 직원 90 학생 80..
- 우선순위 동적인 할당: I/O요청 등으로 time quantum을 다 사용하지 않은 경우, 더 높은 우선순위로 조정한다.
직전에 사용한 time quantum 비율이 f라고 하면 우선순위로 1/f을 부여한다
예) time quantum이 50인데 25를 사용했다면 우선순위는 50/25
우선순위가 높은 프로세스부터 실행 수가 높을수록 우선순위가 높은것.
기아현상이 일어나지 않도록 우선순위 조정 필요.
우선순위가 모두 같다면 FCFS와 같음
MLFQ(Multi-Level Feddback Queue)
1st level의 프로세스를 실행시켜주며 주어진 Time quantum을 다 사용하면 2st level을 실행시켜줌 이런식으로 점점 우선순위가 낮은 프로세스를 실행시키는데 우선순위가 낮을수록 time quantum이 많아지게 된다.
예) 100번의 quantum을 수행하기위해 필요한 switching 횟수?
1+2+4+8+16+32+64 7번째 switching인 64회 중간에서 끝나기 때문에 7회
Guaranteed Scheduling
만약 n개의 프로세스가 있다면, 약 1/n의 CPU성능을 사용하게 보장한다.
ratio = (사용한 CPU time) / 부여받은 CPU time)
ex) ratio = 0.5 받은 시간의 반 밖에 소비하지 못함
ratio = 2.0 받은 시간의 두 배를 소비
ratio가 낮은 프로세스를 실행한다.
1)5초를 부여받았지만 1초를 사용했다면 1/5 = 0.2
2)5초를 부여받았지만 10초를 사용했다면 10/5 = 2
1번 프로세스를 실행하게됨.
Lottery Scheduling
프로세스들에게 CPU time과 같은 다양한 자원을 위한 복권 티켓을 나누어준다. 더 중요한 프로세스는 더 많은 복권 티켓을 받게 해주므로 더 높은 당첨 확률을 부여해 준다. 스케줄 시에는 무작위로 당첨 복권을 선택한다.
비디오 서버에 적용 예)
만약 a, b, c 프로세스가 10 20 30 프레임을 제공하는 프로세스라면 a < b < c 순으로 더 많은 복권 티켓을 나누어 준다.
Realtime system에서의 Scheduling
Real time system이란 deadline이 있는 task들이 있는 System이다.
예를들어 과제로 비교하자면 과제는 deadline이 있는 task이다.
Real-time system은 크게 두가지로 나눌 수 있는데 Hard real time, Soft real time이 있다.
1) Hard real time system
Hard real time system은 각 task들을 무조건 deadline에 맞춰서 끝내는 시스템이다.
이 시스템에서 deadline을 못맞추는 것은 너무 치명적이여서 못 맞출바에 차라리 스케줄링을 안해주는게 더 나은 정도인 시스템이다.
대표적인 예로 자율주행 자동차나, 무기체계에 사용되는 시스템이다.
2) Soft real time system
이 시스템에선 real time task와 Non-real time task가 혼재되어 있는 상황에서 시스템이 real time task를 조금 더 신경써서 처리해주긴 하지만, 무조건 deadline에 맞춰서 처리해주는건 아니다.
Schedulable
실시간 시스템이 schedulable하다는 것은 주기적으로/비주기적으로 들어오는 task들을 다 처리할 수 있는가? 라는 것이다.
A, B, C
처리하는데 걸리는 시간: 50, 30, 100
task가 주어지는 주기: 100, 200, 500
이런A, B, C가 들어오는 real time system이 Schedulable한지 알아보려면
A = 50/100, B = 200/30, C = 100/500이 된다.
이 신호들이 1보다 작은지 보면 되는데, A = 250/500이 되고, B = 500/75가 되고, C = 100/500이다.
이 신호들을 모두 더해보면 425/500이 되는데 이는 1보다 작기 때문에 처리가 가능하다(Schedulable하다).