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로 옮김