Multiple-Processor Scheduling
Asymmetric multiprocessing은 하나의 CPU가 대장 역할을 하는 것이다.
Real-Time Scheduling
deadline이 주어지는 것이다.
hard real-time system은 미리 스케줄링을 다 설정해놓고 돌리기만한다.
soft real-time computing은 동영상 재생할 때 제 시간에 일을 다 못하면 끊기는 경우다.
Thread Scheduling
user level thread일 경우 운영체제가 쓰레드의 존재를 모른다.
kernellelvel thread일 경우 운영체제가 알기 때문에 관리할 수 있다.
Algorithm Evaluation
queueing model은 복잡한 계산을 통해 구한 것인데 예전에 주로 쓰였다.
최근에는 implementation & measurement를 사용한다.
데이터의 접근
Race Condition
하나의 공유 데이터에 여럿이 접근하려할 때 race condition이라 한다.
CPU가 여러개 있을 때 이런 문제가 생긴다. CPU가 하나 있을 때도 생길 수 있는데
A라는 프로세스가 시스템콜을 했는데, B로 넘어가서 B도 시스템콜을 하면 둘 다 운영체제 안에 있는 같은 데이터를 건드릴 수도 있다.
OS에서의 race condition (1/3)
해결책은 count 변수를 건드리는 동안에는 interrupt를 disable하는 것이다.
OS에서의 race condition (2/3)
user mode에서는 주소 공간을 공유하지 않기에 문제가 없지만 kernel mode에서 운영체제의 데이터는 프로세스 입장에서 공유데이터이다.
If you preempt CPU while in kernel mode..
Pa 입장에서는 count가 두번 증가되지 않고 한번만 된 셈이다.
해결책은 kernel mode 중에서 할당시간이 끝나도 끝내지않고 kernel에서의 작업을 끝내고 마무리하는 것이다.
OS에서의 race condition (3/3)
cpu가 여러 개 있으면 interrupt를 막는 것으로 해결되지 않는다. 제일 간단한 해결 방법은 커널에는 하나의 cpu만 들어갈 수 있게 하는 방법이다. 하지만 이렇게하면 비효율적이다.
그래서 나온 방법이 공유 데이터 각각을 막는 것이다.
Process Synchronization 문제
Example of a Race Condition
The Critical-Section Problem
critical section은 공유데이터가 아니라 공유데이터에 접근하는 코드이다.
Initial Attemps to Solve Problem
Algorithm 1
둘이 동시에 들어가는 경우는 없도록 보장된다. 하지만 프로그램 충족 조건의 rpgress가 충족되지 않는다. 즉 다른 프로세스는 들어가고 싶어하지도 않는데 A가 못들어 갈 수도 있다.
프로그램적 해결법의 충족 조건
Algorithm 2
i라는 프로세스가 자기 깃발을 들어서 들어가고 싶다고 하고 상대방의 깃발이 내려지면 들억간다. 들어간 프로세스는 나올때 깃발을 내린다.
mutual exclusion문제는 만족하나, progress 를 충족하지 못한다. 서로가 서로의 눈치를 보기 때문에 아무도 들어가지 못한다.
Algorithm 3 (Pterson's Algorithm)
깃발을 들어서 의중을 표시하고 턴을 상대방으로 만든다.
동시에 깃발을 들고 있으면 턴을 따진다.
하지만 여기에서도 ciritical section을 못들어가는 상황이면 cpu를 가지고 while문 계속 도는 busy waiting을 한다.
Synchronization Hardware
현재 a의 값을 읽어내고 a의 값을 세팅해준다? 값을 읽고 세팅을 쪼개지지 않고 atomic하게 해주는 것이다.
lock이 1인 것은 누군가 lock을 걸고 critical section에 들어간 것이다.
Semaphores
세마포어는 일종의 추상자료형이다. 세마포어는 정수로 정의된다.
P 연산은 자원을 획득하는 과정, V는 자우너을 반납하는 과정이다.
P가 5라는 것은 자원이 다섯개 라는 것이다. 프로세스 5개가 하나씩 가져갈 수 있다.
쉽게 말해 자원을 counting하는 변수다.
Critical Section of n Processes
여기에서도 busy-wait의 문제가 있다. busy waiting은 spin lock이라고 도 한다.
세마포어 변수가 0이면 cpu 자체가 필요없으므로 blocked 상태로 들어가는게 더 효율적이다.
Block / Wakeup Implementation
세모포어 변수 여분이 없으면 프로세스들을 잠재우고 기다리게 한다.
여기서는 S변수가 0이하여도 1을 뺀다. 그리고 음수면 프로세를 잠 재운다.
Which is better?
black/wakeup이 더 효율적이다.
하지만 프로세스의 상태를 block하고 wakeup하고 하면서 overhead가 발생하므로 때로는 busy wait이 더 효율적일 수도 있다. critical section에 대한 경합이 얼마나 치열한가에 따라 다르다.
