[ KOCW 운영체제와 정보기술의 원리 | 반효경 ] CPU 스케쥴링
CPU-burst Time
CPU-burst가 짧다는건 중간중간 I/O가 자주 끼어든다는 말.
이게 긴 경우도 있고 짧은 경우도 있다.
따라서 CPU 스케쥴링이 필요하다.
CPU-burst가 짧다는 말은 사람이랑 자주 인터렉션을 하는 것.
이런 잡에 CPU를 늦게 넘겨주면 사람이 답답하다.
결정해야 하는 것
누구에게 CPU를 줄것인가
줬으면 계속 쓰게 할 것인가.중간에 뺏어올 수도 있게 할 것인가
- 비선점형 | nonpreemptive scheduling
- 선점형 | preemptive scheduling
만약 뺏지 않고 끝까지 CPU를 보장해야 한다면, CPU-burst가 긴 애들이 CPU를 넘겨받았을 때 지나치게 오랜 기다림이 된다.
스케쥴링 알고리즘의 평가
성능 척도를 통해 평가한다.
- 시스템 입장에서의 성능 척도 - cpu 하나로 최대한 많은 일을 시키면 좋다 | 처리량
- 프로그램 입장에서의 성능 척도 - 시간과 관련된 성능 척도 | 시간
2. 프로그램 입장에서의 성능 척도
- Turnaround time(소요시간, 완료시간)
모든 일을 끝내고 나갈때까지 걸린 시간 - Waiting time(대기 시간)
ready queue에 줄서서 기다린 시간. - Response time(응답 시간)
ready queue에 들어와서 처음 CPU를 얻기까지 걸린 시간
preemtivescheduling은 얻었다가 뺐겼다가 한다.
이 때 프로세스는 한 번의 cpu burst 동안에도 얻었다가 뺐겼다가를 반복할 수 있음.
이 때 기다린 time을 합친게 waiting time이고
처음 queue에 들어와서 CPU를 얻기까지 걸린 시간이 response time이다.
CPU 스케쥴링 알고리즘
FCFS | First-Come First-Served
비선점형 스케쥴링. nonpreemptive
cpu를 오래 쓰는 프로그램이 먼저 CPU를 잡아버리면 interactive한 프로세스가 들어와도 오래 기다려야 한다.(Convoy effect | 호위효과)
앞에 어떤 프로세스가 들어오는가에 따라서 기다리는 시간이 정해진다
SJF | Shortest-Job-First
평균 waiting time을 최소화할 수 있다.
2가지 방식으로 나누어 생각할 수 있다.
- nonpreemptive
일단 기다리는 프로세스 중 가장 짧게 쓰는 프로세스에게 CPU를 줬다면, 더 짧은 프로세스가 들어와도 일단 하던걸 끝낸다 - preemptive
더 짧은 프로세스가 들어오면 CPU를 뺏어올 수 있다.
앞으로 남은 시간이 짧은 애한테 CPU를 넘겨준다.
문제점
- starvation | 기아 현상
극단적으로 CPU 사용이 짧은 애들을 선호.
따라서 극단적으로 CPU 시간이 긴애는 끝까지 CPU를 점유받지를 못할 수도 있다 ㅜㅜ
기아 현상이 발생할 수도 있따 - cpu 사용을 미리 알 수 없다.
매번 cpu를 쓰러 들어와서 얼마나 쓰고 나갈지를 알 수 없다.
하지만 추정할 수는 있음.
I/O bound process. 여타 프로세스등의 특징을 통해 예측할 수 있다 (과거에 CPU를 사용한 흔적을 보고 예측)
Priority Scheduling
우선순위 스케쥴링
- nonpreemptive
우선순위가 더 높은 프로세스가 도착했을 때 빼앗을 수 없다 - preemptive
우선순위가 더 높은 프로세스가 도착했을 때 빼앗을 수 있다
일반적으로 작은 정수를 우선순위가 높다고 여긴다.
문제점
starvation | 기아 현상
해결 방법
Aging | 노화~
아무리 우선순위가 낮더라도 오래 기다리면 우선순위를 높여주며 starvation을 해결해준다
Round Robin Scheduling
현대적인 방법. preemptive scheduling
CPU를 줄 때 할당 시간을 세팅해서 주게 되고,
할당 시간이 끝나면 프로세스는 CPU를 빼앗기고 ready queue에 가서 다시 줄을 선다
장점
CPU를 최초까지 얻기까지 걸리는 시간이 빠르다.
누가 CPU를 오래 쓸 지 모르는 상황에서 굳이 예측할 필요 없이 짧게 쓰는 애들이 후딱후딱 돌면서 쓰고 나갈 수 있게 해준다.
기다리면 한 번은 CPU를 얻을 기회가 주어진다
time quantom을 짧게 잡으면 CPU를 처음 잡을 기회가 더 빨라짐.
따라서 응답 시간이 빨라진다
또 다른 특징으로는,
CPU의 사용시간과 기다리는 시간이 비례하다
quantom을 길게 잡으면 FCFS와 다를 바가 없어지고
짧게 잡으면 context switch가 너무 빈번하게 일어난다(오버헤드 발생)
따라서 적당한 규모의 time quantom을 잡는 것이 바람직. 10~ 100ms
turn around time은 길어질 수 있지만
response time은 짧다
Multilevel Queue
우선순위에 따라서 줄세우기
여러줄서기는 줄마다 우선순위가 있다.
가장 우선순위가 높은 줄이 system process.
그 다음이 사람과 interaction하는 process
등등...
본인이 속한 줄을 평생 벗어날 수 없다
ready queue를 여러 개로 분할
- forground(interactive)
- background(batch - no human interaction)
각 큐는 독립적인 스케쥴링 알고리즘을 가진다
- forground - RR
- background - FCFS
고려해야 할 사항
process를 어느 줄에 넣을 것인가?
우선순위에 낮은 process의 starvation 현상
큐에 대한 스케줄링이 필요
Time slice
- 각 큐에 CPU time을 적절하게 할당 | 80%는 높은, 20% 낮은 우선순위에 부여 등
Multilevel Feedback Queue
신분이동이 가능하다. 승격이 되기도 하고 좋았지만 낮아지기도 한다.
- 프로세스가 다른 큐로 이동 가능
- 에이징을 이와 같은 방식으로 구현할 수 있다
- Multilevel-feedback-queue scheduler을 정의하는 파라미터들
- queue의 수
- 각 큐의 scheduling algorithm
- process를 상위 큐 / 하위 큐로 보내는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
각 quantum마다 실생시간을 둬서 실행 시간을 넘어가면 다음 큐로, 다음 큐로 이동함
맨 마지막 quantum은 FCFS로
지금까지 나왔던 것들은 CPU가 하나일 때 시행할 수 있는 스케쥴링.
CPU가 여러 개 있을 때
Multiple-Processor Scheduling
고려해야 할 사항
어떤 process는 특정 CPU에서만 시행되어야 하는 경우가 있을 것이다
Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케쥴링 결정
Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름.
Real-Time Scheduling
Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케쥴링해야 한다
Soft real-time computing
- 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
Thread Scheduling
프로세스 하나 안에 CPU 수행 단위가 여러개 있는 것 : Thread
Local Scheduling
- User level thread의 경우(운영체제는 존재를 모름) 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴할지 결정
Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정