CPU Scheduling
Multiple-Processor Scheduling
Real-Time Scheduling
Deadline이라는 것을 지키는 것이 중요.
- Hard real-time systems
정해진 시간 안에 반드시 끝내도록 스케줄링 - Soft real-time computing
일반 프로세스에 비해 높은 priority를 갖도록
ex) 동영상 스트리밍
Thread Scheduling
- Local Scheduling
User level thread의 경우 사용자 수준의 thread library에 이해 어떤 thread를 스케줄할지 결정 - Global Scheduling
Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
Process Synchronization
데이터의 접근
한 군데에서 연산을 하고 저장을 한다면, 문제가 되지 않음.
Race Condition
여러 프로세스들이 동시에 공유 데이터에 접근하는 상황.
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐.
Race Condition이 발생하는 경우
-
Kernel 수행 중 인터럽트 발생 시
중요한 변수값을 건드리는 경우, interrupt가 들어와도 kernel에서의 작업이 끝날 때까지 interrupt 처리 루틴 실행 X. -
Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
-
Multiprocessor에서 shared memory 내의 kernel data
CPU가 여러 개 있는 상태에서 공유 변수를 건드릴 때의 문제 발생 가능성. 예를 들어, CPU 1이 변경된 값을 저장했는데 그 값을 CPU 2가 읽을 수 있음.
Process Synchronization 문제
- 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있음.
- 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요.
- Race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 함.
The Critical-Section Problem
프로그램적 해결법의 충족 조건
가정> 모든 프로세스의 수행 속도 > 0 , 프로세스들 간의 상대적인 수행 속도는 가정하지 X.
- Mutual Exclusion (상호 배제)
프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안됨. - Progress (진행)
아무도 critical section에 있지 않은 상태에서, critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해 주어야 함. - Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 함. (starvation 없어야 함)
ex) 만약, 3가지 process가 critical section에 들어가야하는데 둘만 왔다갔다 하면 bounded waiting 조건 불충족
Initial Attempts
Algorithm 1
critical section이 다 끝나면 turn을 상대방에게 돌려줌. 둘이 동시에 critical section에 들어갈 일은 확실히 없음. 확실히 번갈아 들어가도록 하는 알고리즘. 상대방이 나에게 차례를 주기 전까지는 못 들어감.
Algorithm 2
critical section에 들어갔다 나올 때, 깃발을 내림. 동시에 들어가는 문제는 이것도 잘 해결됨. 동시에 들어갈 일 없음. 깃발을 든 것은 critical section에 들어갔다는 뜻이 아니라, 들어갈 의사가 있다는 것. 상대방도 나도 깃발을 든 상태인데 아무도 critical section에 들어가지 않은 상태에 OS를 뺏겼다면 아무도 못 들어감...
Algorithm 3 (Perterson's Algorithm)
i 입장에서 보는 코드. turn을 상대방에게 맡겨둠.
비효율적인 게 문제가 됨. while문 조건이 변경이 되어야 다음 단계로 넘어갈 수 있는데, 계속 while문만 돌면서 자원을 낭비할 가능성 존재.
Synchronization Hardware
Lock == 1 , 누군가 critical section에 들어간 상태
Lock == 0, 아무도 critical sectio에 들어가지 않은 상태
Semaphores
P 연산 : 자원을 획득하는 과정
V 연산 : 자원을 반납하는 과정
While문을 돌면서 CPU 낭비.
Block/Wakeup Implementation
구조체 형식.
semaphore 변수가 음수인 경우, 자원이 없는 상태.
자원을 반납했더라도 semaphore 변수가 음수면, 누가 잠들어 있는 상태라는 것. blocked 상태에서 ready 상태로 바꾸는 작업 필요. 앞에서의 얘기처럼 semaphore 변수가 여분의 개수를 의미하지 않음.
Which is better?
당연히 block/wakeup 상태가 더 좋긴 함.
그러나, 이 경우에 block 시키고 wait 시키는 등 이 작업이 오버헤드로 볼 수 있음. 경합이 심할 땐 block/wakeup, 아닌 경우에는 busy-wait이 차라리 (효과적) 나을 수 있음.
Two Types of Semaphores
