📌 CPU 스케줄러(Scheduler)3 & 병행제어1

추가적인 CPU 스케줄링

1. Multiple-Processor-scheduling

   CPU가 여러 개인 경우 스케줄링이 더욱 복잡해짐

   • Homogeneous한 경우
     • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
     • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더욱 복잡해짐
   • Load Sharing
     • 일부 프로세스에서 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
     • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
   • Symmetric Multiprocessing (SMP) 각 CPU가 대등함
     • 각 프로세스가 각자 알아서 결정

   • Asymmetic Multiprocessing

     조율하는 CPU가 있음

     • 하나의 프로세서가 시스템 데이터 접근을 책임지고 나머지 프로세스는 거기에 따름
2. Real time
   1. Hard real-time system (제한시간 안에 안 끝나면 큰 일 나는 것들)
      • Hard real-time Task는 반드시 정해진 시간안에 끝낼 수 있도록 스케줄링 되어야 함
   2. Soft real-time system (동영상을 스트리밍하는 것들)
      • Soft real time Task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

3. Thread Scheduling

   1. Local Scheduling - 운영체제는 스레드의 존재를 모름, 그래서 직접 접근이 불가능
      • User Level Thread의 경우 사용자 수준의 Thread library에 의해 어떤 Thread를 스케줄링 할지 결정
   2. Global Schefduling - 운영체제는 스레드의 존재를 알고 있음, 그래서 직접 접근이 가능
      • Kernel level Scheduling의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread로 스케줄링할지 결정

Algorithm Evaluation

1. Queuing models (여러 가지 상황에 전부 접목할 수 있음)
   • 확률분포로 주어지는 Arrival rate와 Service rate 등을 통해 각종 Performance Index 값을 계산
2. implementation(구현) & measurement(성능 측정)
   • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
3. Simulation(모의 실험)
   • 알고리즘을 모의 프로그램으로 작성한 후 trace를 입력하여 결과 비교

병행 제어1 (Process Synchronization)

컴퓨터 안에서 연산을 할 때는 항상 데이터를 읽어오고 연산하여 그 결과를 반드시 저장하게 되어 있음.

단순히 하나하나에 대해 연산을 한다면 문제가 될 것이 없겠지만, 여러 곳에서 데이터를 읽고 연산을 수행한다면 문제가 발생할 수 있음.

즉 S-box(Memory Address Space, Storage-box)를 공유하는 E-box(CPU Process, Evaluation-box)가 여럿 있는 경우 Race Condition의 가능성이 있음, ( 프로세스는 자기 주소공간에 있는 데이터에만 접근할 수 있음, 그래서 프로세스끼리는 문제가 발생하지 않으나, 여기서 CPU가 끼어든다면( System Call이 일어난다면 ), 문제가 발생함. 특히 CPU가 하나 일 때, 같은 데이터를 건드리는 경우에 해당 데이터를 중복해서 연산하는 문제가 발생할 수 있음. )

경쟁 상태:(race condition)란 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.

• Multiprocessor System, 공유메모리를 사용하는 프로세스들 커널 내부에 접근하는 루틴들 간(예: 커널모드 수행 인터럽트로 커널모드 다른 루틴 수행 시)

1. OS에서 Race Condition은 언제 발생하는가?

   • Kernel 수행 중 인터럽트 발생 시

     • 고유 변수로 연산하기 전에 interrupt를 disable 시키고 해당 변수를 다 사용했으면 다시 interrupt를 수행하면 해결할 수 있다.

   • Process가 system call을 하여 kernel mode로 수행 중인데, context switch가 일어나는 경우

     • 두 프로세스의 Address Space간에는 data sharing이 없음

     • 그러나 system call을 하는 동안에는 kernel address space의 data를 접근하게 됨.

     • 이 작업 중간에 CPU를 preemp 해가면 race condition 발생

     • 해결책: 커널 모드에서 수행 중일 때는 CPU를 preemptive하지 않음 커널 모드에서 사용자 모드로 돌아갈 때 preemp

       ​ 즉 kernel 모드에서 수행 중일 때는 CPU를 빼앗지 않는 것이 해결책임

   • Multiprocess에서 shared memory 내의 kernel data

     • 어떤 CPU가 마지막으로 kernel 변수를 store했는가? → race condition / multiprocessor의 경우, interrupt enable/disable로 해결되지 않음
       • Method1: 한번에 하나의 CPU만이 커널에 들어갈 수 있도록 하는 방법
         • 이 방법은 운영체제 전체에 lock/unlock을 걸어서 수행하는 방법임
       • Method2: 커널 내부에 있는 각 공유 데이터에 접근할 때 마다 그 데이터에 대한 lock/unlock을 하는 방법
         • 즉, 다른 CPU가 해당 global 변수를 사용하는 있는 것에 착안하여 다른 CPU는 해당 데이터에 접근하는 것을 lock하거나 unlock함

   • 결국은 CPU를 건드는 과정에서 일어날 수 있다는 것인데, 만약에 shared memory를 사용한다면, 이 또한 race condition이 일어날 수 있음

2. process synchronization의 문제

   • 공유 데이터(shared data)의 동시 접근(concorrent access)은 데이터의 불일치(inconsistency) 문제를 야기시킬 수 있다.
   • 일관성(consistency)을 위해서는 협력 프로세스(cooperating process)간의 실행순서(orderly execution)를 정해주는 메커니즘이 필요
   • Race-condition
     • 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
     • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
   • Race-condition을 막기 위해서는 concurrent-process는 동기화(synchronization) 되어야 한다.

3. The critical-section problem

   • n개의 프로세스가 공유데이터를 동시에 사용하기를 원하는 경우
   • 각 프로세스의 code segment에는 공유 데이터에 접근하는 코드인 critical-section이 존재
   • problem
     • 하나의 프로세스가 critical-section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

   • Initial Attempts to Solve problem

     • 두 개의 프로세스가 있다고 하자. (P0, P1)

     • 프로세스들의 일반적인 구조

       do {
         entry section; // lock을 걸고
         critical section; // 데이터에 접근 여기에 동시 접근 문제가 발생함
         exit section; // lock을 풀고
         remainder section; // 데이터에 접근하지 않던지
       } while (1)
       

     • 프로세스들은 수행의 동기화(syschonize)를 위해 몇몇 변수를 공유할 수 있다. → syschronization variable

Algorithm 1

• syschronization variable

  int turn;
  initially turn = 0; // P1 can enter its critical section if(turn == i)

• Process P0

• do {
    while (turn != 0); // My turn
    critical section;
    turn = 1; // Now it's your turn
    remainder section;
  } while (1)
  

  • Satisfies mutual exclution, but not progress

    즉, 과잉양보: 반드시 한 번씩 교대로 들어가야만 함 (swap-turn)

    ​ 그가 turn을 내값으로 바꿔줘야만 내가 들어갈 수 있음

    ​ 특정 프로세스가 더 빈번히 critical section을 들어가야만 한다면?

프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호배타)

  • 프로세스 pi가 critical section에서 수행 중이면, 다른 모든 프로세스들은 critical section에 들어가면 안 된다.

• Progress(진행)

  • 그 어떤 프로세스도 critical section에 들어가있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면, critical section에 들어가게 해주어야 한다.

• Bounded Waiting (대기 시간이 유효해야 한다. 즉 starvation을 막아야한다.)

  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 한계가 있어야 한다.

  ⭐️ 가정

  • 모든 프로세스의 수행속도는 0보다 크다.
  • 프로세스들 간의 상대적인 수행속도는 가정하지 않는다.

Algorithm 2

• syschronization variable

  bool frag[2];
  initially flag[all] = false; // no one is in cs
  // "Pi is ready to enter its critical section" if (flag[i] == true)
  

• Process Pi

  do {
    flag[i] = true; // pretend I am in
    while (flag[i]); // Is he also in? then wait
    critical section;
    flag[i] = false; // I am out now
    remainder section;
  } while (1);
  

• Satisfies mutual exclusion, but not progress requirement

• 둘 다 2행까지 수행 후 끊임없이 양보하는 상황이 발생할 수 있음

Algorithm 3 (Peterson’s Algorithm)

• combined syschronization variables of Algorithms 1 and 2

• Process P1

  do {
    flag[i] = true; // My intention is to enter...
    turn = j; // Set to his turn
    while (flag[i] && turn == j); // Wait only if
    critical section;
    flag[i] = false; // I am out now
    remainder section;
  } while(1);
  

• Meets all three requirements; solves the critical section problem for two processe
• Busy Waiting = Spin lock! (계속 CPU와 memory를 쓰면서 wait)

Synchronization Hardware

• 하드웨어적으로 Test & Modify를 atomic하게 수행할 수 있도록 지원할 경우 Busy Waiting = Spin lock! 문제를 간단히 해결할 수 있다.

• Mutual Exclusion with Test & Set

  syschronization variables:
  		boolean lock = false;
  Process Pi
    			do {
            while (Test_and_Set(lock));
            critical section;
            lock = true;
            remainder section;
          }
  

semaphores (세마푸어, 추상자료형, object와 operation으로 정의됨)

• 앞의 방식들을 추상화시킴

• Semaphore S

  여기 S에 1이 몇개 있는가? 이거에 따라서 자원을 획득할 수 있는지 없는지 알 수 있음 예를 들어서 누가 S에 있는 1을 하나 가져가면 다른 프로세스에서 가져가려고 할 때 1이 없으니까. 자원을 할당 받을 수 없음.

  • integer variable

  • 아래의 두 자기 atomic 연산에 의해서만 가능

    P(S): while(S <= 0) do no-op; // → i.e.wait 자원을 획득하는 과정, lock을 거는 과정
    			S--;
    

    If positive, decrement-&-enter. Otherwise, wait until positive (busy-wait)

    ```c++ V(S): // 자원을 반납하는 과정, lock을 푸는 과정 S++;

• Critical Section of n process

  • syschronization variables

    semaphore mutax; // initially 1: 1개가 CS에 들어갈 수 있다?
        
    Process P1
    do {
    	P(mutax); // if positive, dec-&-enter, Otherwise, wait
      critical section;
      V(mutax); // Increment semaphore
      remainder section;
    } while(1);
    

    busy-wait는 효율적이지 못함 / ex) 이미 누군가 S를 사용하고 있다면, 다른 누군가는 while을 도는 현상이 발생할 것임

    위의 문제를 Block / Wakeup을 구현하여 해결 가능

    그렇다면 P()와 S()를 어떻게 구현할 것이냐? 이는 Synchronization Hardware 방법을 사용하여 구현할 수 있음.

• Block / Wakeup Implementation

  • semaphore를 다음과 같이 정의

    typedef struct
    { int value ; // semaphore
     	struct process *L;  // process wait queue
    } semaphore;
    

  • block과 wakeup을 다음과 같이 정의

    • Block: 커널은 block을 호출한 프로세스를 suspend 시킴, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
    • wakeup: block된 process P를 wakeup 시킴, 이 프로세스의 PCB를 ready queue에 옮김

  위와 같은 정의로 인해 semaphore연산이 다음과 같이 다시 정의됨.

  Implementation block/wakeup version of P( ) & V( )

  P(S): S.value--; // Prepare to Enter
  			if (S.value < 0) { // Oops, negative, I cannot enter
          add this process to S.L;
          block();
        }
  

  V(S): S.value++;
  			if (S.value <= 0) {
          remove process from S.L;
          wakeup(P);
        }
  

• which is better?

  • Busy-wait v.s. Block-Wakeup

  • Block/Wakeup overhead v.s. Critical section의 길이

    • Critical section의 길이가 긴 경우 Block/Wakeup이 적당
    • Critical section의 길이가 매우 짧은 경우 Block/wakeup overhead가 busy-wait 오버헤드보다 더욱 커질 수 있다.
    • 일반적으로는 Block/Wakeup 방식이 더 좋음

    즉, critical section에 대한 경쟁이 매우 치열한 상태라면 Block/Wakeup이 더 좋고 그렇지 않다면, busy-wait가 더 좋음

• Two Types of semaphores
  • counting semaphore
    • 도메인이 0 이상인 임의의 정수값
    • 주로 resource counting에 사용
  • Binery semaphore
    • 0 또는 1 값만 가질 수 있는 semaphore
    • 주로 mutual exclusion (lock/unlock)에 사용