CPU 스케줄링이 필요한 이유
CPU bound program이 CPU를 잡고 안놓아주면 I/O bound program을 쓰려고한(키보드, 마우스) 사람이 너무 답담함.
빈도수 자체도 I/O bound program이 더 높다.
스케줄링 기본 지식
프로세스의 특성 분류
1) I/O-bound process
사람과 주로 Interaction하는 Job이다. CPU사용 시간이 빈번하고 짧다.(대기시간이 길다)
2) CPU-bound process
계산위주의 Job이다. 빈번하지 않은 대신에 CPU를 연속적으로 쓰기 때문에 시간이 길게 소요된다.
CPU 스케줄러 & 디스패처
1) CPU Schedualr (결정)
Ready 상태 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
2) Dispatcher (실제로 넘긴다)
CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘긴다.
이 과정을 문맥교환이 함
결론: CPU를 실제로 주는거는 문맥교환이라 하고이는 Dispatcher가 관여하다. 어떤 프로세스에게 CPU를 줄지는 스케줄러가 관여한다.
CPU 스케줄링이 필요한 경우
1) Running -> Blocked
CPU를 어떤 프로세스가 잡고 있다가 I/O 작업하러 간 경우
2) Running -> Ready
CPU 요청한 프로세스에게 무한정 줄 수는 없음
ex> 타이퍼 인터럽트3) Blocked -> Ready
CPU를 얻을 수 있는 상태 됨
ex> I/O 완료 후 인터럽트
4) Terminate
프로세스가 종료되어서 새로운 프로세스에게 CPU를 주어야 함
위의 1)과 4)는 프로세스가 CPU를 자진반납한다. 그러나 2,3은 CPU를 강제로 뺏는다.
성능척도(Scheduling Criteria)
1. 시스템 입장
1) 이용률(CPU utilization)
2) 처리량(throughput)
몇개의 작업 처리
2. 프로세스 입장
3) 소요시간, 변환시간(turn-around time)
CPU 사용을 다 하고 나갈때까지
4) 대기시간(waiting time)
CPU받을 때 까지 기다린 시간
5) 응답시간(response time)
레디큐에 들어와서 처음 CPU를 얻을 때 까지 기다린 시간
CPU 스케줄링 알고리즘
1. FCFS(First-Come First-Served)
말 그대로 먼저온 순서대로 처리하는 알고리즘이다.
별로 효율적이지 못하다.
- Convoy effect: 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상
2. SJF(Shortest-Job-First)
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
SJF는 주어진 프로세스들에 minimum average waiting time을 보장한다.
1) 비선점형(Non Preemptive) SJF
일단 지금 기다리는 프로세스 중 CPU를 제일 짧게 쓰는 프로세스에게 CPU 줬으면 더 짧은 프로세스가 도착하더라도 전자의 CPU 사용권을 보장해줌
2) SRTF: 선점형(Preemptive) SJF: 가장 짧은 대기시간
더 짧은거 오면 그냥 CPU를 넘김
-> Non Preemptive보다 더 짧은 Average Time을 보장한다.
SRTF(Shortest-Remaining-Time-First)라고도 부른다.
선점형 SJF의 문제점
1) Starvation
CPU 사용시간이 긴 프로세스는 영원히 CPU를 못받을 수 있다.
2) CPU 사용시간 예측 불가능
내가 얼마나 쓰고 나갈지 미리 알 수 없다.
그러나 과거의 흔적을 통해 추정은 가능하다.
3. 우선순위 스케줄링(Priority Scheduling)
우선순위 높은거에 CPU를 준다. SJF는 일종의 우선순위 스케줄링 이다.(우선순위: 예측한 다음번 CPU burst time)
1) 비선점형(Non Preemptive)
더 높은 우선순위 와도 안넘김
2) 선점형(Preemptive)
더 높은 우선순위 오면 넘김
문제점: Starvation
낮은 우선순위는 영원히 CPU를 못받는다.
해결법: Aging
오래기다리면 우선순위를 높여준다.
4. 라운드 로빈 스케줄링(Round Robin Scheduling)
1) 각 프로세스는 동일한 크기의 할당시간을 가진다.(q time)
2) 할당시간이 지나면 프로세스는 Timer 인터럽트에 의해 CPU를 빼앗기고 Ready Queue의 맨 뒤에가서 줄을 선다.
3) 응답시간(response time): 최로로 CPU를 얻는데 걸리는 시간을 짧게 가져갈 수 있다.
n개의 프로세스가 Ready Queue에 있고 할당시간은 최대 q time 단위를 갖는다.
- 결국 CPU를 오래쓰는 프로세스는 더 오래 기다린다. (q가 다수, 인터럽트 계속 걸림)
- 반면 CPU를 짧게쓰는 프로세스는 더 짧게 기다린다. (q가 적음, 한번에 끝나거나 수가 적음)
라운드 로빈의 퍼포먼스
1) q를 크게하면
FCFS와 똑같아 짐 -> q의 의미가 사라지고 먼저온 순서대로 처리된다.
2) q가 작으면
문맥교환의 오버헤드가 커지고 성능이 안좋아진다.
q는 일반적으로 10~100 m/s
5. 멀티레벨 큐(Multilevel Queue)
1) 레디큐를 여러개로 분할
가. foreground(interactive)
나. background(batch-no human interaction)
2) 각 큐는 독립적인 스케줄링 알고리즘을 가짐
가. Round Robin : foreground
나. FCFS: background
3) 큐에 대한 스케줄링이 필요
가. Fixed priority scheduling
foreground가 비어있을때만 background에게 CPU를 줌
-> starvation문제 발생
나. Time slice
각 큐에 CPU time을 적절한 비율로 할당
80% to foreground(RR)
20% to background(FCFS)
5. 멀티레벨 피드백 큐(Multilevel Feedback Queue)
프로세스가 다른 큐로 이동가능
에이징을 이와 같은 방식으로 구현할 수 있다.
1) new job이 Q0으로 들어감
2) CPU를 잡아서 할당시간 8 ms 동한 수행됨
3) 8ms 동안 다 못 끝내면 Q1로 내려감 (강등)
4) Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
5) 16ms에 끝내지 못한 경우 Q2로 내려감 (강등)
6. 멀티플 프로세서 스케줄링(Multiple Processor Scheduling)
CPU가 여러개 = 화장실이 여러칸
1) Homogeneous Processor (동차)
큐에 한줄로 세워서 각 CPU가 알아서 꺼내 가게끔
2) Load Sharing
일부 CPU에 job이 몰리지 않도로 함
3) Symmetric Multiprocessing
각 CPU가 각자 알아서 스케줄링 결정
4) Asymmetric Multiprocessing
하나의 CPU가 시스템 데이터의 접근과 공유를 책임지고, 나머지 CPU는 거기에 따름
7. 리얼타임 스케줄링(Real-Time Scheduling)
정해진 시간안에 끝내야함
1) Hard real-time Systems
정해진 시간안에 반드시 끝내도록 스케줄링 해야함
2) Soft real-time Computing
우선순위만 높여주어 CPU를 얻을 수 있게함
8. 쓰레드 스케줄링(Thread Scheduling)
쓰레드 유형에 따라 CPU 할당방식을 다르게 한다.
1) Local Scheduling
유저레벨 쓰레드인 경우 OS는 쓰레드를 모른다.
만약 그 프로세스에게 CPU가 가면 내부에서 어떤 쓰레드에게 CPU를 줄지 결정한다.
A의 라이브러리가 A의 쓰레드중 어떤거를 CPU에게 줄지 결정한다.
2) Global Scheduling
커널레벨 쓰레드인 경우 커널의 단기 스케줄러(OS)가 어떤 스레드를 스케줄링 할지 결정한다. OS는 쓰레드에 대해 알고있기 때문...
알고리즘 평가
1) Queuing models
확률분포로 주어지는 arrival rate와 service rate를 통해 performance index값을 계산
2) Implementation & Measurement
실제 시스템에 알고리즘을 구현하여 실제 작업에 대해 성능을 측정하고 비교
#) Simulation
알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
