병행제어
병행성(Concurrency)이란, 두 개 이상의 프로세스가 동시에 병렬적으로 실행될 수 있는 상태를 말합니다.
CPU가 여러 개인 경우에는 스케줄링이 더욱 복잡해 진다고 합니다.
Homogeneous processor인 경우 : 같은 종류의 프로세서인 경우- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해짐
Load sharing- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요(웹 서버로 치면, 로드 밸런서 역할)
- 별개의 큐를 두는 방법 vs 공동 큐를 두는 방법
프로세스 스케줄링 방식
Systemmetric multiprocessing (SMP)- 각 프로세스가 알아서 스케줄링을 결정하는 방식
Asymmetric multiprocessing- 하나의 프로세서(대장 프로세서)가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서가 이를 따르는 방식
Real-Time Scheduling
특정 task를 정해신 시간 내에 동작하게 하도록 스케줄링 하는 방식으로, 크게 두 가지로 나눌 수 있습니다.
Hard read-time systems: 정해진 시간 안에 반드시 끝내도록 스케줄링 해야하는 시스템- ex) 스마트 미사일 제어, 항공기 or 우주선 제어 시스템 등
Sort real-time computing: 일반 프로세스에 비해 높은 우선순위를 가짐- ex) 동영상 플레이어
- 1초에 60프레임으로 정해져있지만, 제 시간안에 데이터가 안오면 낮은 프레임으로 동영상이 제공됨
- ex) 동영상 플레이어
Thread Scheduling
하나의 프로세스 안에 CPU 수행 단위(Thread)가 여러개가 있는 경우에도 스케줄링이 필요합니다.
스레드 생성 방식
- Local Scheduling
- User level thread의 경우, 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정됨
- Global Scheduling
- Kernal level thread의 경우, 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정함
Algorithm Evaluation
어떤 알고리즘이 더 좋은지를 평가하기 위한 방법에는 여러가지가 있습니다.
Queueing models
확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산합니다.
Throughput(처리량),Waiting time(대기 시간)등의 지표를 계산가능
Implementation(구현) & Measurement(성능 측정)
실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교합니다.
하지만 이 방법은 운영체제 일부를 수정하고 실제로 실행해봐야하는 방법이라서 아주 복잡하고 어려운 작업입니다.
Simulation(모의 실험)
알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
Race Condition
Race Condition이란 하나의 데이터에 여럿이 동시에 접근해서 작업할 경우 데이터의 신뢰성을 잃거나,
누구도 접근할 수 없게 되는 현상을 일컫습니다.
그런데 CPU가 한개라도 Race Condition이 발생할 수 있다고 합니다.
여러개의 프로세스가 공유메모리에 있는 값을 참조할 경우 발생할 수 있다고 합니다.
OS 에서 race condition은 언제 발생하는가?
- kernal 수행 중 인터럽트 발생 시
- Process가 System call을 하여 kernal mode로 수행중인데, context switch가 일어나는 경우
- Multiprocessor에서 공유 메모리내의 kernal data에 접근하는 경우
위 그림은 커널 모드에서 Race condition 이 발생하는경우를 예로 든 그림입니다.P(A)가 kernal mode로 실행하다가 인터럽트가 발생하여 P(B)로 제어권이 넘어간 경우인데요.
P(A)는 증가시키기 이전값인 N을 갖고있음- 인터럽트가 발생하며,
P(B)가 다시 같은 값을참조하여 1을 더하여 N+1로 만듦 P(B)의 작업이 종료되어 다시P(A)로 돌아가며 context switch가 일어남P(A)는 CPU 제어권을 뺏기기 전 가져왔었던 N에 다시 1을 더하는 작업을 함.- 결론적으로 N+1이 됨
위 처럼, 인터럽트와 Context switch 타이밍이 엇갈리며 Race condition이 발생할 수 있는데요.
이를 방지하기 위해서는 커널 모드에서 수행 중일 때는, CPU 제어권을 빼앗지 않음
그리고 사용자 모드로 돌아갈 때 제어권을 뺏으면 된다고 합니다.
Process Synchronization
공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있습니다.
그래서 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요합니다.
The Critical-Section
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재합니다.
그래서 특정 프로세스가 critical section에 있을 경우, 다른 프로세스는 접근하지 못하게 됩니다.
이렇게 동시성 문제를 해결할 수 있습니다.
Critical-Section 알고리즘 1
do {
while(turn != 0) { // 내 차례?
critical section
turn = 1; // 이제 너 차례임
remainder section
}
} while(true)한 번씩 교대로 들어가는 알고리즘 입니다.
Critical-Section 알고리즘 2
do {
flag[i] = true; // 일단 들어가봄
while (flag[j]); // 다른사람 있나?
critical section
flag[i] = false; // 있으면 일단 기다림
remainder section
} while(1);다른 사람이 쓰고있는지 계속 확인하는데, 그러다가 무한으로 상호 양보하는 경우가 생길 수 있음
Critical-Section 알고리즘 3
do {
flag[i]= true;
turm = j;
while(flag[j] && turn == j);
critical section
flag[i] = false;
remainder section
} while(1);플래그를 드는 경우에 한해서 critical section 에 접근할 수 있도록 함