Scheduling Criteria
cpu 이용률은 전체 시간 중에 cpu가 놀지않고 일한 시간이다.
처리량은 주어진 시간에 얼마나 많은 일을 처리했는가이다.
밑에 3개는 고객의 입장이다.
3. turnaround time은 cpu를 쓰러 들어와서 다쓰고 나갈때까지의 시간이다.
4. waiting time은 cpu를 쓰고자 기다리는 시간이다.
5. response time은 큐에 들어와서 처음으로 cpu를 얻을때까지 기다린 시간이다.
FCFS (First-Come First-Served)
비선점형 방식이다. 효율적이지 않다. 긴 프로세스가 먼저 도착하면 아주 짧은 것도 오래 기다려야 한다. convoy effect라고 부른다.
SJF (Shortest-Job-First)
가장 짧은 스케줄에게 cpu를 주는 것이다. starvation이 발생한다. minimum averaging waiting time을 보장한다. 미래의 프로세스들이 얼마나 쓸지를 알기 어려운 문제점도 있다.
nonpreemptive도 있고 preemptive도 있다.
preemptive 버전을 shortest-remaining-time-first (SRTF)도 있다.
Example of Non-Preemptive SJF
Example of Preemptive SJF
다음 CPU Burst Time의 예측
Exponential Averaging
Priority Scheduling
우선 순위가 높은 스케줄이게 cpu를 준다는 것이다. 이것도 preemptive할 수도 있고 nonpreemptive할 수도 있다.
starvation을 해결하기 위해 aging 기법을 사용한다.
Round Robin (RR)
현대 OS에서 가장 많이 사용하고, preemptive한 것이다 (timer)
장점은 처음으로 cpu를 얻기까지의 시간인 response time이 짧아진다.할당 시간을 지나치 길게 잡으면 FCFS가 되고, 지나치게 짧게 잡으면 context switch가 커진다.
Example: RR with Time Quantum = 20
Turnaround Time Varies With Time
Multilevel Queue
줄마다 우선순위가 다르다. 높은 우선순위에 대기 프로세스가 있으면 우선권을 갖는다.
각 큐는 독립적인 스케줄링 알고리즘을 가진다.
Multilevel Feedback Queue
여기서는 프로세스들이 큐들을 왔다갔다 할 수 있다. 보통 처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 넣고 그다음 점차 낮은 큐에 넣는다.
Example of Multilevel Feedback Queue
Multiple-Processor Scheduling
Real-Time Scheduling
Thread Scheduling
어느 쓰레드인지에 따라서 누가 스케줄링을 할지가 결정된다.
Algorithm Evaluation
여기서는 server가 cpu다.
6장 Process Synchronization
데이터의 접근
Race Condition
커널의 데이터 역시 공유데이터가 될 수 있다.
OS에서 race condition은 언제 발생하는가?
OS에서의 race condition (1/3)
중요 데이터를 건드리는 동안에는 인터럽트 처리를 안하는 방법이 있다.
os에서의 race condition (2/3)
If you preempt CPU while in kernel mode ..
OS에서의 race condition (3/3)
cpu 자체가 여러 개인 경우에는 락을 걸어서 어느 누구도 접근하지 못하게 해야 한다.
Process Syncrhonization 문제
The Critical-Section Problem
프로그램적 해결법의 충족 조건
Initial Attempts to Solve Problem
