CPU-burst
- CPU-burst와 I/O-burst는 교대로 동작!
- 대부분의 프로세스는 CPU-burst가 짧고, CPU를 적게 사용하는 프로세스들이 많음
CPU Scheduler
Non-preemptive (비선점)
- 자발적으로 CPU를 양도하는 상태, 공평성 x
- running → waiting : I/O를 발생시키면 자발적으로 CPU를 넘겨주어야 함
- terminates : 프로세스 종료시
- 문제 : real time process는 프로세스가 끝나는 deadline을 맞추기 위해 CPU를 빼앗아 와서라도 수행을 해야 함! → preemptive
Preemptive (선점)
- 강제로 CPU를 빼앗기는 상태, 할당된 시간 끝나면 CPU를 빼앗김 → 일반적으로 많이 사용
- running → ready : 프로세스가 자신에게 할당된 CPU time이 끝나면 비자발적으로 CPU를 넘겨주어야 함
- waiting → ready : I/O를 기다리는 프로세스가 I/O가 끝나면 ready queue에 들어감
- 문제
- 공유 자원에 대한 경쟁 (contention) 발생 - 한 프로세스가 데이터에 대한 작업이 끝난 다음에 다른 프로세스가 변경된 데이터에 대한 작업을 수행해야 함 (일관성 있게 변경되어야 함) → 그렇지 않으면 경쟁상의 overhead 발생
- 커널 상에서의 경쟁 - 한 프로세스가 커널 데이터 스트럭쳐를 수정하다가 CPU를 빼앗겨, 다른 프로세스가 수정이 끝나지 않은 변경에 자신의 변경을 덧붙일 수 있음
- 해결 : 커널을 Non-preemptive하게 바꿈 - 커널 모드의 프로세스가 I/O를 발생시키거나, 시스템 콜 요청을 완료했을 때 다른 프로세스에 CPU를 넘겨주게 하면 된다! → real processing과 같은 경우 overhead 발생
- 중요한 OS 작업 중에 발생하는 interrupt : 한 프로세스가 interrupt를 처리하고 있는 도중, 다른 프로세스에게 CPU를 빼앗긴다면 interrupt가 없어질 수 있다.
- 해결 : CPU를 빼앗기면 안 되므로 interrupt 수행 전에 interrupt disable 하고 처리한 후 빠져나오면 interrupt enable 해줌
Dispatcher
- Scheduler가 선택한 프로세스에게 CPU를 전달해주는 소프트웨어
- 컨텍스트(PCB) 스위치
- 유저 모드로 전환
- return address로 점프해 이전에 수행하던 instruction을 수행
- Dispatch latency - dispatcher이 한 프로세스를 중지하고 다른 프로세스 실행을 시작하는 데 걸리는 시간(overhead)
Scheduling Criteria
- CPU 활용률 ↑ – CPU를 최대한 사용 중으로 유지
- 단위 시간 당 처리량 ↑ – 시간 단위당 실행을 완료하는 프로세스 수
- Turnaround time 최소화 – 특정 프로세스를 실행하는 데 걸리는 시간
- Waiting time 최소화 – ready queue에서 프로세스가 대기하는 시간
- 응답 시간 최소화 – 요청이 제출된 시점부터 첫 번째 응답이 생성될 때까지 소요되는 시간(time-sharing 환경)
Scheduling Algorithm
- Waiting Time - 마지막 작업 시작 시간 - 도착 시간
- Turnaround Time - 작업 종료 시간 - 도착 시간
- Response Time - 작업이 처음 실행되는 시간 - 도착 시간
FCFS (First-Come, First-Served) Scheduling
- Non-Preemptive
- Average waiting time, average turn-around time이 긴 편이다! → 수행 시간에 따라 우선 순위를 두지 않기 때문
average turn-around time = (24 + 27 + 30) / 3 = 27
FCFS (First-Come, First-Served) Scheduling (수행 시간이 짧은 프로세스 순서대로)
- 짧은 job이 먼저 수행되어 average waiting time, average turn-around time이 줄어든다.
- Convoy effect - 수행 시간이 짧은 job이 수행 시간이 긴 job 뒤에 기다리는 현상
- CPU-bound, I/O-bound process 중 I/O-bound process의 우선 순위가 높다.
average turn-around time = (3 + 6 + 30) / 3 = 13
SJF (Shortest-Job-First) Scheduling
- Non-Preemptive
- 주어진 프로세스들에 대한 최소 평균 대기 시간 제공
- 수행 시간의 길이를 어떻게 알까?
- 사용자에게 물어봄 → 부정확
- 머신러닝 → 각 프로세스 수행시간을 수집하여 수행 시간을 예측한다.
- 장점 : 수행 시간이 빠름
- 단점 : 각 프로세스의 수행 시간을 정확하게 결정할 수 없음, 계속 수행 시간이 짧은 job이 들어오면 ready queue의 수행 시간이 긴 job들이 뒤로 밀려나게 됨
average turn-around time = (9 + 24 + 16 + 3) / 3 = 17.333
Shortest-remaining-time-First
- Preemptive SJF
- 수행 시간이 짧은 job이 들어오면 CPU를 넘겨주어야 함
average turn-around time = ((17-0) + (5-1) + (26-2) + (10-3)) / 3 = 17.333
Priority Scheduling
- CPU는 가장 높은 우선순위 프로세스부터 할당됨
- Preemptive - 우선순위가 높은 프로세스가 들어오면 CPU를 내준다.
- Non-preemptive - 현재 ready queue에 우선순위 높은 프로세스 수행, 더 높은 프로세스가 들어와도 일단 수행을 끝냄
- SJF는 priority scheduling으로 non-preemptive이다.
- 문제 : Starvation - 낮은 우선 순위의 프로세스가 무한히 기다리는 상태가 발생할 수 있다.
- 해결 : Aging - 기다리는 시간에 비례해 프로세스의 우선순위를 높여주어야 한다.
average turn-around time = (16 + 1 + 18 + 19 + 6) / 5 = 12
Round Robin (RR)
- CPU를 일정한 시간 간격으로 나눠, 해당 시간 동안 돌아가면서 수행할 수 있도록 하는 스케줄링 기법
- 준비 대기열에 프로세스가 n개 있고 time quantum이 q인 경우
- time quantum이 크다면 FCFS
- time quantum이 작다면 CPU를 빼앗길 때마다 context switch를 해줘야 하므로 overhead가 높아진다.
- 속도 : CPU 수행 시간 >> 메모리 access time
- PCB → 프로세스의 상태를 저장하기 위한 메모리 데이터 스트럭쳐로 레지스터가 아닌 메모리에 저장됨
- time quantum 안에 약 80%의 CPU를 사용하는 job 수행이 끝나야 함
average turn-around time : (30 + 7 + 10) / 3 = 15.667
- average turn-around time : RR > SJF
- response : RR < SJF
- time quantum은 context switch time보다 커야 함
- time quantum 일반적으로 10ms ~ 100ms, context switch time < 10usec
Multilevel Queue
- Ready Queue
- foreground (interactive) - 다음 명령 시작 전에 이전 명령을 끝내야 함
- background (batch) - 일괄처리 방식이 적용된 시스템으로서, 하나의 작업이 끝나기 전까지는 다른 작업을 할 수 없다.
- 프로세스가 어떤 큐에 들어가면 다른 큐로 이동할 수 없음
- 해당 큐가 수행하기 위해서는 이 큐보다 높은 큐에 있는 프로세스들이 모두 수행을 끝내야 함
- 프로세스 수행 도중 우선순위가 높은 프로세스(높은 큐의 프로세스)가 들어오면 CPU가 선점돼 Starvation 발생 가능
- 각각의 큐마다 다른 스케줄링 알고리즘으로 구현 가능
- Scheduling은 큐 사이에서 수행되어야 함
- Fixed priority scheduling(고정 우선 순위) - starvation 발생 가능
- Time slice - 각 큐는 프로세스 간에 일정한 양의 CPU 시간을 확보 가능
- 80%는 RR의 foreground, 20%는 FCFS의 background
Multilevel Feedback Queue
- 프로세스가 큐 사이를 이동할 수 있다.
- Multilevel feedback queue scheduler가 결정되는 parameters
- 큐의 개수
- 각각의 큐의 스케줄링 알고리즘 (각각의 큐마다 서로 다른 알고리즘 적용 가능)
- 프로세스를 보다 높은 우선 순위의 큐로 격상시키는 데 사용되는 방법 - aging
- 낮은 우선 순위의 큐에서 너무 오래 대기하는 프로세스를 높은 우선 순위의 큐로 이동
- 프로세스를 보다 낮은 우선 순위의 큐로 격하시키는 데 사용되는 방법
- 어떤 프로세스가 CPU 시간을 너무 많이 사용할 때
- I/O-bound를 먼저 수행하기 위해 우선 순위를 올리고 CPU-bound의 우선 순위를 내림
- 프로세스들이 들어갈 큐를 결정하는 방법
Q0 – RR, time quantum = 8 ms
Q1 – RR, time quantum = 16 ms
Q2 – FCFS
- 새 작업이 FCFS로 제공되는 큐 Q0에 들어가 8 ms 동안 수행
- 8 ms 내에 완료되지 않으면 작업이 Q1 대기열로 이동해 16 ms가 추가됨
- 그래도 완료되지 않으면 선점되어 Q2 대기열로 이동해 끝날 때까지 수행
Multiple-Processor Scheduling
- CPU 여러 개인 경우
- 멀티프로세서 내의 동종의 CPU (같은 기능을 수행하는 CPU)
- Asymmetric multiprocessing – 하나의 프로세서만 시스템 데이터 구조에 액세스하여 데이터 공유의 필요성을 줄임, Master(스케줄링 수행)와 Slave(주어진 스케줄에 따라 수행)로 나누어 공유 자원의 contention을 줄임
- SMP (Symmetric Multiprocessing) – 모든 CPU가 스케줄링, 공유 데이터 스트럭쳐에 접근 가능하고 동등한 우선 순위를 가짐, 각 CPU가 self-scheduling 되어 있고, 모든 프로세스가 common ready queue에 있거나, 각 CPU마다 ready process의 자체 queue가 있음
- Processor affinity – 프로세스는 현재 실행 중인 CPU에 대한 선호도를 가진다. 해당 작업을 지정된 CPU에서만 수행하려고 함
- soft affinity - 다른 CPU를 받을 수 있음
- hard affinity - 꼭 그 CPU여야만 함
- Cache inconsistency → affinity가 수행되지 않았기 때문에 CPU가 다른 프로세스에 할당되어 캐시 무효화(cache invalidation)의 overhead 발생
NUMA and CPU Scheduling
- 같은 칩 내의 메모리에서 수행하는 것이 빠름
Multiple-Processor Scheduling - Load Balancing
- Load Balancing(부하 균등) - affinity 위반 → 캐시 무효화 해야 함
- Push migration - idle한 CPU에 task를 몰아주기, 각 CPU의 부하를 주기적으로 확인하고, 발견되면 과부하된 CPU에서 다른 CPU로 작업을 푸시
- Pull migration - 유휴 CPU가 사용 중인 CPU에서 대기 중인 작업을 끌어냄
Multicore Processor
- 동일한 물리적 칩에 여러 프로세서 코어를 배치하는 최근의 추세
- 전력 소모 : 코어 ↑ < CPU ↑
- 속도 빠름
- 코어당 여러 개의 스레드도 증가
- 메모리에서 가져오는 동안 메모리 스톨을 활용하여 다른 스레드에서 진행
Multithreaded Multicore System
- core당 여러 개의 thread 주기
- 메모리에 접근할 때 시간 허비 → memory stall
- 다중 스레드를 이용하여 코어를 다른 스레드로 전환해 진행
- memory stall 때문에 멈출 때 다른 스레드에서 compute
참고 자료 : Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne
'CS > 운영체제' 카테고리의 다른 글
| 운영체제 ch 7. Synchronization Examples (0) | 2023.05.02 |
|---|---|
| 운영체제 ch 6. Synchronization Tools (0) | 2023.04.18 |
| 운영체제 ch 3. 프로세스 (0) | 2023.04.10 |
| 운영체제 ch 2. OS 구조 (0) | 2023.04.09 |
| 운영체제 ch 1. Introduction (0) | 2023.04.07 |
