[운영체제](반효경) 6강. CPU Scheduling
CPU Scheduling
CPU and I/O Bursts in Program Execution
CPU-burst Time의 분포
- 여러 종류의 job(process)들이 섞여있기 때문에 CPU 스케줄링이 필요하다.
- Interactive job에게 적절한 response 제공 요망
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
프로세스의 특성 분류
- I/O- bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- Many short CPU bursts
- CPU-bound process
- 계산 위주의 job
- Few very long CPU bursts
CPU Scheduler & Dispatcher
운영체제의 특정 기능임
- CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
- Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
- 이 과정을 context switch(문맥 교환)라고 한다.
- CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태변화가 있는 경우이다.
- Running → Blocked(e.g. I/O 요청하는 시스템 콜)
- Running → Ready(e.g. 할당시간 만료로 timer interrupt)
- Blocked → Ready(e.g. I/O 완료 후 인터럽트)
- Terminate
- 예시일뿐 더 많은 케이스가 있을 수도
1번과 4번의 경우는 nonpreemptive(= 강제로 빼앗지 않고 자진 반납) / 비선점형
나머지 모든 스케줄링은 preemptive(= 강제로 빼앗음) / 선점형
Scheduling Criteria
Performance Index ( = Performance Measure, 성능 척도)
위의 2가지는 CPU입장, 밑의 3가지는 프로세스 입장
프로세스 전체의 시작과 종료 기준이 아니라 프로세스가 CPU를 잡는 시간 기준(버스트 기준) 이라는 것에 유의
- CPU utilization 이용률
- keep the CPU as busy as possible
- Throughput 처리량
- number of prcesses that complete their excution per time unit
- Turnaround time 소요시간, 반환시간
- amount of time to excute a particular process
- Waiting time 대기시간
- amount of time a process has been waiting in the ready queue
- Response time 응답시간
- amount of time it takes from when a request was submitted until the first response is produced, not output(for time-sharing environment)
Scheduling Algoritm
- FCFS
- SJF
- SRTF
- Priority Scheduling
- RR
- Multilevel Queue
- Mutilevel Feedback Queue
FCFS(First-Come First-Served)
- 비선점형(unpreemptive)
SJF(Shortes-Job-First)
- 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 적용
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴
- 두가지 스킴(Scheme)
- Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(premmption)당하지 않음
- Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법을 Shortest-Remaining-Time-First(SRTF)라고도 부른다.
- Nonpreemptive
- SJF is optimal
- 주어진 프로세스들에 대해 minimun average waiting time을 보장 → 모든 알고리즘 중에서 가장 짧은 waiting time을 보장한다.
- 단점
- starvation → Long process가 영원히 실행되지 않을수도 있다.
- 프로그램의 정확한 사용시간을 미리 알수가 없으므로 추정을 해야함.
Priority Scheduling
- A priority number(integer) is associated with each process
- highest priority를 가진 프로세스에게 CPU 할당
- Preemptive
- nonpreemptive
- (smallest integer - highest priority)
- SJF는 일종의 priority scheduling이다.
- priority = predicated next CPU burst time
- 문제점
- Starvation(기아 현상): low priority processes may nver execute
- 해결방법
- Aging: as time progresses increase the priority of the process
RR(Round Robin) - 현대의 운영체제가 사용하는 방법
- 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가짐
- (일반적으로 10-100 milliseconds)
- 할당 시간이 지나면 프로세스는 선점(preemted)당하고 ready queue의 제일 뒤에가서 다시 줄을 선다.
- n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit단위로 CPU 시간의 1/n을 얻는다.
- → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- 장점: 응답시간이 빨라진다.(최초로 CPU를 얻게되는 시간)
- 단점: 특정조건에서는 오히려 비효율적임(모든 프로세스의 실행시간이 동일한경우??)
턴어라운드, 웨이팅타임이 악화될 수도 있음.
- Performance
- q large → FCFS
- q small → context switch 가 빈번해져 overhead의 부담
Multilevel Queue
- Ready Queue를 여러개로 분할
- foreground(interactive)
- background(batch - no human interaction)
- 각 큐는 독립적인 스케쥴링 알고리즘을 가짐
- foreground - RR
- background - FSFS
- 개별 큐에 대해서도 스케쥴링이 필요
- Fixed priority scheduling(우선순위로 고정)
- serve all from foreground then from background
- Possibility of starvation
- Time slice(시간단위로 분배)
- 각 큐에 CPU time을 적절한 비율로 할당
- e.g. 80% to foreground in RR, 20% to background in FCFS
- Fixed priority scheduling(우선순위로 고정)
Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동 가능
- 에이징(aging)을 이와 같은 방식으로 구현할 수 있다(오래되면 프로세스를 다른 큐로 이동 시켜서)
- Multilevel-feedback-queue를 정의하는 파라미터들
- Queue의 수
- 각 Queue의 Scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Multiple-Processor Scheduling
- CPU가 여러개인 경우 스케쥴링은 더욱 복잡해짐
- Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
- Load Sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케쥴링 결정
- Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
periodic한 성격의 작업이 많다.
- Hard real-time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함 → 데드라인내 실행이 보장되어야함
- Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함
Thread Scheduling
- Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴 할지 결정
- Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄 할지 결정
Algorithm Evaluation
1. Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
2. Implementation(구현) & Mesurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
- → 운영체제 코드를 실제로 고쳐보는 것(어려움)
3. Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace(시뮬레이션 프로그램의 인풋으로 들어갈 테스트케이스?)를 입력으로 하여 결과 비교
다음 CPU Burst Time의 예측
- 다음번 CPU burst time을 어떻게 알 수 있는가?
- (Input data, branch, user)
- 추정(estimate)만이 가능하다
- 과거의 CPU burst time을 이용해서 추정 (exponential averaging)
'CS > OS' 카테고리의 다른 글
[운영체제](반효경) 8강. Deadlock (0) | 2022.08.09 |
---|---|
[운영체제](반효경) 7강. Process Synchronization (0) | 2022.08.09 |
[운영체제](반효경) 5강. Process Management (0) | 2022.08.09 |
[운영체제](반효경) 4강. Process(2) (0) | 2022.08.09 |
[운영체제](반효경) 4강. Process(1) (0) | 2022.08.09 |
댓글
이 글 공유하기
다른 글
-
[운영체제](반효경) 8강. Deadlock
[운영체제](반효경) 8강. Deadlock
2022.08.09 -
[운영체제](반효경) 7강. Process Synchronization
[운영체제](반효경) 7강. Process Synchronization
2022.08.09 -
[운영체제](반효경) 5강. Process Management
[운영체제](반효경) 5강. Process Management
2022.08.09 -
[운영체제](반효경) 4강. Process(2)
[운영체제](반효경) 4강. Process(2)
2022.08.09