CPU and I/O Bursts in program Execution
여러 종류의 job(process)이 섞여 있기 때문에 CPU 스케줄링이 필요
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
I/O-bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
CPU-bound process
- 계산 위주의 job
CPU Scheduler * Dispatcher
CPU Scheduler
- Ready 상태의 프로세서 중에서 이번에 CPU를 줄 프로세스를 고름
Dispatchar
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김
- 이 과정을 context switch(문맥 교환)
CPU 스케줄링이 필요한 경우
-
Running -> Blocked
- 자진 해서 CPU를 내놓는 경우
- I/O 요청하는 시스템 콜
-
Running -> Ready
- 강제로 빼앗는 경우
- timer interrupt
-
Blocked -> Ready
- I/O 완료 후 인터럽트
-
Terminate
용어
nonpreemptive (비선점): 강제로 빼앗지 않고 자진 반납
preemptive (선점): 강제로 빼앗음
Scheduling Criteria
Performance Index
두 가지로 나눌 수 있음
-
System입장 : CPU 하나로 최대한 일을 많이 시키면 좋다-
CPU utilization(이용률) : CPU가 놀지 않고 일한 시간
-
Throughput(처리량) : 주어진 시간 동안 몇 개의 작업을 완료하는가
-
-
Process입장 : CPU를 빨리 얻어서 빨리 끝나면 좋다 (고객 입장)- Turnaround time(소요시간, 반환시간) : CPU를 사용하러 들어와서 CPU를 다 사용하고 나갈 때까지 걸린 시간 (대기 시간 + 사용 시간)
- waiting time(대기 시간) : CPU를 사용하러 기다린 시간
- CPU를 얻었다 뺏겼다 반복할 때 기다린 시간을 전부 합친 시간
- Response time(응답 시간) : CPU를 사용하러 들어와서 처음으로 CPU를 사용하기 까지 걸린 시간
Scheduling Algorithms
- FCFS (First Come First Served)
- SJF (Shortest-job-First)
- SRTF (Shortest-Remaining-Time-First)
- Priority Scheduling
- RR (Round Robin)
- Multilevel Queue
- Multilevel Feedback Queue
FCFS (First-Come First-Served) 선입선처리
프로세스를 요청하는 순서대로 프로세서를 할당
- 일괄 처리 시스템에서는 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않음
- 비선점형
- 시스템에 새로운 프로세스가 들어오면 해당 프로세스의 프로세스 제어블록을 Ready queue의 마지막에 연결
- 차례가 되면 Ready queue의 앞부분에 있던 프로세스가 프로세서를 할당 받고 ready queue에서 삭제
이는 프로레서 중심 프로세스 하나가 프로세서를 떠나기를 기다리는 convoy effect 가 발생한다. 즉 프로세서 중심 프로세스나 입출력 중심 프로세스 중 한쪽으로 치우쳐 기다리는 불균형 상태가 발생
SJF (Shortest-Job-First) 최소작업 우선 스케줄링
프로세서가 사용 가능할 때 실행 시간(CPU burst)이 가장 짧은 프로세스에 할당, 같을 때는 먼저 들어온 순서대로
-
주어진 프로세스들에 대해 minimum average waiting time을 보장
-
선점, 비선점 모두 가능
-
비선점 : CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
- 비선점 스케줄링 알고리즘은 시분할 시스템에 사용하기 어려움 : 특정 프로세스가 프로세서 사용을 연장하려고 하면 곤란해지기 때문
-
선점 : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺴앗김
- Shorted-Remaining-Time-First(SRTF) 최소잔여 시간 우선
-
단점
-
기아 문제 발생 : 긴 작업을 짧은 작업을 종료할 때까지 대기키셔야 하기 때문에 프로세서를 받지 못해 무기한 대기하는 문제
-
CPU 사용 시간을 미리 알 수가 없다는 문제
priority scheduling 우선순위 스케줄링
우선 순위가 높은 프로세스에 프로세서 할당
- 선점, 비선점 모두 가능
- 비선점 : 프로세스가 프로세서를 잡고 있을 때 우선순위가 더 높은 프로세스가 도착해도 CPU를 빼앗지 않음
- 선점 : 프로레스가 프로세서를 잡고 있을 때 우선순위가 더 높은 프로세서가 도착하면 CPU를 배앗음
단점
-
기아 문제 발생 : Ready queue에 있으나 우선 순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스는 무기한으로 기다려야 함
-
해결책 : Aging(에이징)
- 시스템에서 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
-
Round Robin(RR)
Ready queue를 circular queue로 설계하여 스케줄러가 ready queue를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량(time quantum)만큼 프로레서 제공
- Response time(응답 시간)이 짧음
- 프로세스 : n
- time unit : n
- => 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
- CPU를 길게 쓰는 프로세스는 응답 시간이 길어지고 짧게 쓰는 프로세스는 응답 시간도 짧아진다
- Performance
- q large => FCFS
- q small => context swith 오베헤드 커짐
단점
- 미완성 작업은 규정 시간량을 마친 후 프로세서를 기다리므로 평균 처리 시간이 높다
Multilevel Queue(MLQ) 다단계 큐 스케줄링
각 작업을 서로 다른 묶음으로 분류하여 스케쥴링
- 다단계 큐 스케줄링은 Ready queue를 종류별로 여러 단계로 분할
- 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정
- 각 큐는 자신만의 독자적인 스케줄링을 가짐
- 시스템 큐 : 라운드 로빈 스케줄링
- 일괄 처리 프로세스 : FCFS
- 큐 사이에도 스케줄링 필요
- 우선순위가 높은 큐가 절대적인 우선순위를 갖는 고정된 선점 우선순위 스케줄링
- 큐마다 일정한 시간을 주는 방식으로도 스케줄링 가능 (시스템은 시간의 50%, 대화식은 30%)
단점
- 여러 Ready queue와 스케줄링 알고리즘 때문에 추가 오버 헤드가 발생
- 우선순위가 낮은 큐의 프로세스는 무기한 대기하는 기아가 발생할 수 있음
MultiLevel Feedback QueueMLFQ) 다단계 피드백 큐 스케줄링
작업이 queue 사이를 이동할 수 있는 다단계 큐 스케줄링
작동
- Ready queue로 들어오는 프로세스는 우선순위가 가장 높은 Q에 입력
- 우선 순위가 가장 높은 Q에는 규정 시간량(quantum)이 8 주어진다
- 주어진 시간 안에 작업이 끝나지 않으면 2번 Q로 이동한다
- 2번 Q 에는 규정 시간량(16)이 주어진다
- 제일 마지막 Q에서는 여유가 생겼을 때 선입선처리 방식으로로 처리한다.
이처럼 다단계 피드백 큐 스케줄링은 입출력 위주의 프로세스(CPU burst가 낮은)에게 우선권이 주어진다. 또한 앞의 우선순위 스케줄링과 마찬가지로 기아 문제를 해결하기위 특정 Q에 오래 남아있던 프로세스는 우선 순위가 더 높은 Q에 할당하여 기아 문제를 해결할 수 있다.
Multiple-Processor Scheduling
1. Homogeneous processor
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 한다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우는 문제가 더 복잡해짐
2. Load Sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 queue를 두는 방법 vs 공동 queue를 사용하는 방법
3. Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
4. Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
데드라인이 있는 것. 정해진 시간에 반드시 실행이 되어야만 함
1. Hard real-time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링
2. Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함
Thread Scheduling
- Local Scheduling
- User level thread의 경우 운영체제는 해당 thread의 존재를 모르고 사용자 프로그램이 직접관리하며 thread library에 의해 어떤 thread를 스케줄할지 결정
- Glocbal Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
1. Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산
2. Implementation(구현) & (Measurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
3. Siumlation(모의 실헝)
- 알고리즘을 모의 프로그램으로 작성 trace를 입력으로 하여 비교
