- 스케줄링의 개념
- 스케줄링의 기준
- 스케줄링 알고리즘
- Issues
- OS 예시
- 알고리즘 평가
1. 스케줄링의 개념
CPU Scheduling
메모리의 프로세스 중 하나를 실행 준비를 위해 CPU로 골라 할당한다.
멀티프로그래밍(I/O 작업 시에 CPU는 다른 프로세스를 잡는 시스템)을 포함하는 CPU 활용을 최대화하며,
CPU burst, I/O burst(CPU wait)의 순환이 짧게짧게 이뤄진다.
*CPU Utilization = CPU 활용시간(I/O or CPU) / CPU 활용시간 + 오버헤드
- 스케줄링 하는 프로세스는 다음과 같다:
- non-preemptive(interrupt 될 수 없음) 방식은 중단되었거나, 실행되다가 waiting(I/O 작업) 할 때
- preemptive(새로운 프로세스의 우선 순위가 높다면 interrupt 될 수 있음) 방식은 ready(interrupt) 상태가 될 때
- -> SRTF; Shortest Remaining Time First
- Dispatcher: short term 스케줄러에 의해 선정된 한 프로세스에 CPU 제어를 넘겨준다.
이는 kernel에서 user mode로 전환된다.
-> 다른 프로세스 실행으로 교체되는 switching context (PCB0에 저장, dispatch, PCB1에서 reload)
시간은 Dispatch latency로 나타낸다
2. 스케줄링의 기준
- 높은 CPU 활용도
- 높은 시간당 처리량(Throughput)
- 적은 프로세스 실행에 걸리는 시간(Turnaround time)
- 적은 Waiting 시간(in the ready queue) -> “Turnaround time - Burst time”
- 적은 반응 시간(시분할 시스템에서 고려된다)
3. 스케줄링 알고리즘
FCFS(First-Come, First-Served)
ready queue에 들어온 순서대로 처리한다
- Convoy effect: FCFS에서 짧은 프로세스가 보다 뒤에서 waiting할 경우 Average waiting time이 늘어나게 된다
SJF(Shortest-Job First)
CPU burst time이 작은 순서대로 처리하는 알고리즘으로, Average waiting time 측면에서 좋다
- non-preemptive 방식
- preemptive 방식: 평균 waiting time은 좋을 수 있지만, context switching이 잦아 오버헤드가 늘어난다
- Priority 스케줄링은 우선순위의 정수 값을 부여해 처리하는 알고리즘으로, 예측한 다음 CPU burst시간이 우선순위가 된다
(a값을 이용하여 τ(n+1) = a*t(n) + (1-a)*τ(n) 식으로 a값에 따른 다음 CPU burst를 예측할 수 있다)
낮은 우선순위의 프로세스가 계속 밀리는 문제(starvation)는 waiting 시간에 따라 우선순위를 조금씩 높여주며 해결한다(Aging 방식)
RR(Round Robin)
CPU에 할당 받을 때 실행 시간이 정해져 있다 -> 시간 quantum만큼 n개의 프로세스가 돌아가며 쓴다
q가 크면 FIFO와 같아지고, q가 작으면 context switch가 잦아져 오버헤드가 늘어난다
SJF에 비해 평균 turnaround time은 길지만 반응 시간은 적다
- Rule of Thumb: RR 알고리즘은 약 90프로의 프로세스가 한 번에 끝날 time quantum일 경우 가장 좋다
Multilevel Queue
Ready Queue를 나눠 프로세스를 나눠 처리한다.
ex) foreground는 RR 방식으로 처리 / background는 FCFS 방식으로 처리
- 분할한 큐마다 Priority를 설정한다 (-> starvation 문제의 가능성이 있다)
- 분할한 큐마다 CPU time을 지정한다: Time slice
ex) foreground: 80% / background: 20%
Multilevel Feedback Queue
프로세스들이 다음 요인을 통해 aging 방식(우선순위를 조정)을 더하고, 다른 큐로 이동할 수 있다.
- 큐의 수
- 각 큐의 스케줄링 알고리즘
- 프로세스를 다른 큐로 승격/강등하는 방법
- 어떤 큐로 들어갈지 정하는 방법
ex) job이 q=8에서 안 끝나면 다음 큐로 이동 -> q=16에서 안 끝나면 FCFS 큐로 이동
4. Issues
이슈 1. Multiple-Processor Scheduling
멀티 프로세서 스케줄링의 구조는 다음과 같다.
- 비대칭적 구조: 한 프로세서가 마스터로써 시스템 데이터 구조에 접근하여 다른 프로세서들에게 일을 준다(Push migration). 이는 데이터 공유의 필요성을 완화(alleviate)한다.
- 이외의 프로세스들은 동등한 위치로 대칭적(SMP; Symmetric MP) 구조를 가진다. 이들은 일을 받는다(Pull migration).
- -> Load Sharing: Push & Pull
- 프로세서 관련성(affinity): 모든 CPU는 프로세서를 잡고 작업을 처리한다. 이후 작업을 처리할 때 잡았던 프로세서를 다시 잡는다면 “유효한 캐시 비율(Cache hit ratio)”을 고려하게 된다.
-> Hard affinity / Soft affinity
이슈 2. Real-Time Scheduling
- Hard real-time systems: 중요한 작업을 주어진 시간을 보장하여 처리하는 시스템
- Soft real-time systems: 우선순위를 높여 최대한 처리하는 시스템
이슈 3. Thread Scheduling
시스템 프로세싱의 단위가 스레드일 경우 다음과 같이 두 가지로 분류된다.
- Local Scheduling: 유저 레벨의 threads library가 어떻게 LWP; Lightweight Process(Virtual processor)에 할당되는가
- Global Scheduling: 커널이(CPU)가 LWP에 대응되는 어느 커널 thread에 할당되는가
5. OS 예시
Solaris 2
다른 classes에 queues를 나누고, priority와 time quantum 값이 반비례 관계이다.
Windows XP
각 class와 class 관계에 priority 값을 준다.
Linux
신용도 기반(credit-based)으로 Time-sharing을 한다. 신용도가 점점 차감되며 0이 되면 다른 프로세스가 선택된다. 후에 우선순위와 기록 기반으로 신용도를 재할당한다 (Soft real-time)
6. 알고리즘 평가
다음과 같은 방법으로 알고리즘을 평가할 수 있다.
- Deterministic 모델링: 각 프로세스의 workload를 그려 성능을 평가한다
- Queuing 모델: n [Queue length] = λ [Arrival rate] * W [Waiting time in the queue]
- Simulation 모델: CPU의 trace를 tape에 담고, 데이터 값으로 통계를 내 성능을 평가한다.
'OS' 카테고리의 다른 글
[OS][운영체제] 7. Deadlocks / 데드락 (0) | 2021.05.18 |
---|---|
[OS][운영체제] 6. Process Synchronization / 프로세스 동기화(순서화) (0) | 2021.05.05 |
[OS][운영체제] 4. Threads / 스레드 (0) | 2021.04.23 |
[OS][운영체제] 3. Processes / 프로세스 (0) | 2021.04.23 |
[OS][운영체제] 2. Operating-System Structures / OS의 구조 (0) | 2021.04.22 |