해당 게시글은 운영체제 스터디를 위해 반효경 교수님 운영체제 강의를 보고 기록한 게시물입니다. 틀린 정보가 있다면 언제든 지적해주세요🙏🏻

멀티프로세서 CPU 스케쥴링

1. Realtime Scheduling

• Hard Realtime System: 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
• Sofe Realtime Computing: 동영상 재생

2. Thread Scheduling

• 로컬 스케쥴링: 유저 레벨 쓰레드의 경유 사용자 수준의 쓰레드 라이브러리에 의해 어떤 쓰레드를 스케줄할지 결정
• 글로벌 스케쥴링: 커널 레벨 쓰레드의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄할지 결정

3. 알고리즘 평가방법

• Queueing models: 확률분포로 주어지는 job의 도착률과 cpu의 처리율을 가지고 계산함.
• Implementation & Measurement: 실제 구현해서 성능을 평가하는 방법
• Simulation: 가상으로 실험.

Process Synchronization

동기화의 문제

컴퓨터에서 연산을 할땐 데이터를 읽어와서 연산을 하고 어딘가에 저장함.
이 때 데이터를 여러 곳에서 읽어와서 계산을 하게 되는 문제가 생김.
하나의 고유데이터를 여러 개가 공유하는 경우 Race Condition의 가능성이 있음.

문제는 운영체제가 끼어드는 경우 발생할 수 있는데,
1. 커널 수행 중 인터럽트 발생시
2. 프로세스가 System call 하여 커널 모드로 수행 중인데 Context switch가 일어나는 경우
3. 멀티프로세서에서 Shared Memory 내의 커널 데이터

해결책

1. 커널 수행 중 인터럽트 발생시
   변수를 건들이기 전에 인터럽트를 disable 시키고 작업이 다 끝난후에 enable로 바꿔서 처리하도록 한다.

2. 프로세스가 System call 하여 커널 모드로 수행 중인데 Context switch가 일어나는 경우
   커널 모드에서 수행 중일때는 CPU를 빼앗지 않음. 커널 모드가 끝나고 유저 모드로 돌아갈때 CPU를 넘겨 주도록 한다.

3. 멀티프로세서에서 Shared Memory 내의 커널 데이터
   CPU가 여러개 있을 때 운영체제의 공유변수를 건드리는 경우엔 운영체제를 한번에 하나의 CPU만 쓸 수 있게 하면 해결. -> 하지만 이럴 땐 오버헤드가 뒤따른다.
   그래서 이렇게 하지 않고 공유 데이터 각각을 막음.(lock)
   -> 한 CPU에서 공유데이터에 접근 할때는 다른 CPU에게 Lock을 걸어서 카운트에 접근할 수 없게함.

프로세스 동기화 문제

공유데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.

Critical Section

공유데이터를 접근하는 코드를 Critical Section이라고 함
Critical Section의 문제 해결법의 충족 조건

• Mutual exclusion (상호배제)
  상호배타적으로 Critical Section에 들어가야 한다.
• Progress flexibility (진행)
  아무로 Critical Section에 있지 않은 상태에선 들어가고자 하는 프로세스가 있으면 허락해줌
• Bounded waiting (유한대기)
  기다리는 시간이 유한 해야한다. Starvation 막기 위함.
  프로세스가 Critical Section에 들어가려고 요청한 수부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다.

Critical Section 문제를 해결하는 알고리즘

알고리즘 1.
Critical Section에 번갈아 들어감.
특정 프로세스만 더 여러번 크리티컬 섹션을 들어가야 한다면..? 과잉양보문제.

do {
    while (turn != 0)
    critical section
    turn = 1;
    remainder section
} while (1);

알고리즘2.
Critical Section에 들어가고 싶으면 깃발을 든다? 의사표현.
동시에 들어가는 문제는 해결이 되지만 모두 의사표현만 되고 진행이 되지 않는 상황 발생

do {
    flag[i] = true;
    while (flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1);

알고리즘3.
피터슨 알고리즘 Peterson’s algorithm
이것도 깃발을 사용한 알고리즘. 깃발을 드는 경우에 한해서 턴을 정함.
비효율적인 것이 문제가 됨.
-> Busy waiting(spin lock) - 계속 cpu와 메모리를 쓰면서 wait하는 상황 발생.

do {
    flag[i]= true;
    turm = j;
    while(flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while(1);

싱크로나이즈의 문제를 풀기 위해 semaphores와 monitor 방식을 사용한다.

1. Semaphone
   변수 값은 정수로 정의되고 P 연산과 V 연산 두 가지를 사용하여 처리한다.
   P연산은 자원을 획득, V연산은 자원을 반환. 즉, Lock을 푸는것.