KOCW.이화여자대학교.반효경.운영체제
위 강의를 바탕으로 학습 및 정리했습니다
1
CPU and I/O Bursts in Program Execution
- 프로세스의 일생
- 기계어 실행 하거나 I/O 하거나
- 여기서 중요한 포인트
- CPU를 오랫동안 쓰다가 I/O를 하는지
- 중간 중간 I/O가 많이 끼어들어서 CPU연속적으로 쓰는 시간이 적은 지
CPU-Burst Time 분포
- CPU-Burst Time : CPU를 한번에 얼마나 쓰느냐
- CPU bound Job : CPU 길게 쓰는 프로그램
- I/O bound Job : CPU 짧게 쓰는 프로그램
- 사람하고 인터렉션하는 프로그램이 많음
- CPU bound Job와 I/O bound Job 중에 누구에게 먼저 CPU를 주는 것이 효율적인가?
-> I/O bound Job- I/O하러 곧가니까 그리고 사람하고 인터렉션 하는 프로그램이 많기 때문에 결과를 빨리 보여 줘야함
- CPU bound Job 한테 주면 대기 시간이 김
CPU schedular & Dispacher
- 하드웨어가 아닌 운영체제 소프트웨어 코드의 일부
- CPU Scheduler
- CPU누구한테 줄지 결정
- scsheduling은 nonpreemptive인지 preemptive인지에 따라 2가지로 나뉨
- nonpreemptive : 먼저온 순서대로
- preemptive : timer잇어서 시간되면 뺏는
- Dispatcher
- CPU Scheduler가 CPU주기로 결정한 프로세스한테 실제로 CPU를 넘기는 역할
- A에서 B로 문맥교환하는거 담당
- 빼앗기는 프로세스의 context를 save
- 얻으려는 프로세스의 context를 load
CPU scheduling 성능 척도
- 수많은 스케줄링 알고리즘 중 뭐가 좋으냐를 판단할 성능 척도
- 크게 3가지
- 이용률, 처리량, 시간입장에서 보는 성능
- 이용률
- CPU를 놀리지 않고 많이 일하게 할 수록 좋은거
- 처리량
- 단위 시간 당 프로세스를 몇개 완료 시켰는지
- 시스템 입장 (얼마나 많은 일을 했느냐)
- 시간관련
- 반환시간
- 대기시간 + CPU사용한 시간
- 대기시간
- CPU 쓰러와서 기다린 시간의 총 합 (프로그램 종료될때까지 대기시간 다 합한거)
- 응답시간
- CPU 쓰러들어올때부터 최초로 쓸때까지의 시간
- 반환시간
2
Scheduling Algorithm
- FCFS
- nonpreemptive
- Burst time 다 쓸때까지
FCFS
- CPU Scheduling에선 비효율적
- Convoy effect(호위 효과)
- 앞에 Burst time 긴 프로세스 때문에 뒤의 프로세스들이 기다리는 시간이 길어지는 안좋은 현상 -> 효율 높이려고 짧게 쓰는 애들 부터 CPU주자 == SJF
SJF(Shortest-Job-First)
-
optimal
- 다른 어떤 알고리즘 보다도 SJF만큼 평균 waiting time이 짧을 수 없음
-
2가지 버전 있음
-
nonpreemptive
-
preemptive
- 더 짧은 프로세스가 도착하면 바로 더 짧은 프로세스한테 CPU줌
-
-
치명적인 약점 2가지가 있음
- Starvation을 발생시킴
- 너무 효율성만 챙기다보니 Long-job은 CPU를 못 씀
- CPU burst time을 미리 알수 없으니까 어느 프로세스가 짧은지 알 수 없음
- 막상 짧은 줄 알고 줬더니 I/O작업 하느라 길어지면??
- 그래서 이전의 CPU Burst time을 보고 현재의 Burst time을 예측함
- Starvation을 발생시킴
CPU Burst time 예측
- 1-a(1보다 작은값임)의 의미는 이전의 Burst time 기록들은 갈 수록 반영을 덜 하겠다는 의미 == 직전 것이 더 신빙성이 있으므로
Priority Scheduling
- SJF도 priority의 일종
- Priority의 문제점은 Starvation이 발생할 수도 있다는 것
-> Aging : 오래기다리면 우선순위 높여서 Starvation 문제 완화
Round Robin
- 현재 스케줄링에서 가장 많이 사용하는, 근간이 되는 알고리즘
- timer에 시간을 세팅해서 시간되면 다음으로 넘김
- preemptive
- 할당 시간을 어느정도로 해야하나
- 길면 FCFS같아짐
- 너무 짧으면 context switch하느라 오버헤드 발생
- 할당시간 20인 예
Multilevel Queue
- 여러 줄 서는거
- background에는 Starvation의 가능성이 존재
Priority
Multilevel Feedback Queue
3
Multiple-Processor Scheduling
-
CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
-
homogeneous processor인 경우
- 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해짐
-
Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
-
SMP, Symmetric Multiprocessing
- 각 프로세서가 각자 알아서 스케줄링 결정
-
Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
- 효과적임
Real-Time Scheduling
-
보통 우리가 사용하는 PC는 Real-Time 시스템이 아님
-
Hard Real-Time System
- Dead line을 절대 어기면 안되는 시스템
- 대부분 스케줄링을 오프라인으로 미리 해놓고 그대로 수행시키게 함
- 주기적인 job이 많음
-
Soft Real-Time System
- Dead line을 어기면 큰일이 나진 않지만 불편한 정도
- 이를 위한 고가의 시스템을 구축하는 등보다는 일반 프로세스에 비해 높은 priority를 갖는 정도로 함
- Dead line을 어기면 큰일이 나진 않지만 불편한 정도
Thread Scheduling
-
하나의 프로세스안에 CPU수행 단위가 여러개 있는
-
Local Scheduling
-
User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
- (운영체제는 Thread의 존재를 모르므로) 운영체제가 Thread를 지목하는 방식이 아니고 프로세스 내부에서 어느 Thread한테 CPU를 줄지 결정
-
-
Global Scheduling
-
Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단시 스케줄러가 어떤 thread를 스케줄할지 결정
- 운영체제가 직접 Thread 지목
-
Algorithm Evaluation
-
어떤 CPU 스케줄링이 좋은 알고리즘인지 평가하는 3가지 방법
-
Queueing models
- 확률 분포로 주어지는 arrive rate(얼마나 빠른 빈도로 CPU쓰겠다는 요청이 도착하느냐)와 service rate(단위 시간 당 얼마나 일을 하느냐) 등을 통해 각종 performance index 값을 계산
-
Implementation(구현) & Measurement(성능측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
- 실제로 돌려보고 측정해서 알아내는거임
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
-
Simulation(모의 실험)
- 구현 & 성능측정이 어려울 때 편함
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
