2021-10-9 운영체제 (5주차)
Multiple-Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
- Homogeneous processor 인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
- Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
- Hard real-time systems
- Hard real-time tast는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함
- Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 Priority를 갖도록 해야 함
Thread Scheduling
- Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
- Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithem Evaluation
- Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
- Implementation(구현) & Measurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
- Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
Race Condition
- Storage - Box를 공유하는 Execution - Box가 여럿 있는 경우 Race Condition의 가능성이 있음
OS에서 race condition은 언제 발생하는가?
- kernel 수행 중 인터럽트 발생 시
- interrupt를 disable 하는 방법
- Process가 system call을 하여 kernel mode로 수행 중인데 context swith가 일어나는 경우
- Multiprocesso에서 shared memory 내의 kernel data
- 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
- 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법
The Critical-Section Problem
- n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
Algorithm1
- Synchronization variable
- int turn;
- initially turn = 0;
- Process P0
do {
while (turn != 0);
critical section
turn = 1;
remainder section
} while(1);
- Satisfies mutual exclusion, but not progress
- 반드시 한번씩 교대로 들어가야만 함 (swap turn) - 그가 turn 을 내값으로 바꿔줘야만 내가 들어갈 수 있음
프로그램적 해결볍의 충족 조건
- Mutual Exclusion
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
- Progress
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
- Bounded Wating
- 프로세스가 critical section에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다
Algorithm2
- Synchronization variables
- boolean flag[2];
- initially flag[모두] = false;
- Pi ready to enter its critical section if (flag [i] == true)
- Process Pi
do{
flag[i] = true
while (flag[j]); //상대가 깃발을 내릴때까지 대기
critical section
flag[i] = false; //내가 다 쓰고 내어줌
remainder section;
} while(1);
- Satisfies mutual exclusion, but not progress requirement
- 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능
Algorithm 3 (Peterson’s Algorithm)
- Combined synchronization variables of algorithms 1 and 2
- Process P-i
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j) //깃발을 들고있는지, 상대턴인지 확인, 대기
critical section
flag[i] = false;
remainder section
} while (1);
- Meets all three requirements
- Busy Waiting - 계속 CPU와 메모리를 쓰면서 wait
Synchronization Hardware
- 하드워어적으로 Test&modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
Semaphores
- 앞의 방식들을 추상화 시킴
- Semaphore S
- integer variable
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
P (S) : 자원을 획득하는 과정 - 락을 거는 과정
V (S) : 자원을 반납하는 과정 - 락을 푸는 과정
Block / Wakeup Implementation
- Semaphore를 다음과 같이 정의
tyepedef struct{
int value;
struct process *L;
}semaphore
- block 과 wakeup을 다음과 같이 가정
- block - 커널은 block을 호출한 프로세스를 suspend 시킴 이 프로세스의 PCB를 semaphore에 대한 wait queue 에 넣음
- wakeup(P) - block된 프로세스 P를 wakeup시킴 이 프로세스의 PCB를 ready queue로 옮김
Written on October 9, 2021