05. 병행 제어 1

Minseok-Choi·2022년 3월 9일
0

OS Study

목록 보기
5/12

OS에서 race condition은 언제 발생하는가?

1. kernel 수행 중 인터럽트 발생 시

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

3. Multiprocessor에서 shared memory내의 kernel data

Process Synchronization 문제

  • 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
  • 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요

Race condition

  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  • race condition을 막기 위해서는 concurrent process는 동기화되어야 한다.

The Critical-Section Problem

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

Problem

  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

문제 해결 접근

  • 두 개의 프로세스가 있다고 가정 P0, P1
  • 프로세스들의 일반적인 구조
do {
  entry section
  critical section
  exit section
  remainder section
} while(1);
  • 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다. -> synchronization variable

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

Mutual Exclusion (상호 배제)

  • 프로세스가 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

Progress (진행)

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

Bounded Waiting(유한 대기)

  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
  • starvation을 막아야 한다. (특정 프로세스만 접근하지 못하는 상황이 없도록 해야한다.)

가정

  • 모든 프로세스의 수행 속도는 0보다 크다.

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

algorithm 1

  • synchronization variable
    • int turn;
  • Process P0
do {
  while(turn != 0);
  critical section
  turn = 1;
  remainder section
} while(1);
  • Satisfies mutual exclusion, but not progress
  • 과잉양보 반드시 한번씩 교대로 들어가야만 함 (swap-turn) 다른 process가 turn을 해당 process의 turn으로 critical section으로 접근할 수 있다.
  • 특정 프로세스가 더 빈번히 critical section을 들어가야 한다면?
    • 다른 프로세스가 해당 프로세스의 turn으로 변경해주기 전까지 기다릴 수 밖에 없음.

algorithm 2

  • synchronization variables
    • boolean flag[2];
    • initially flag[i] = 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 알고리즘)

do {
  flag [i] = true;
  turn = j;
  while (flag[j] && turn == j);
  critical section
  flag[i] = false;
  remainder section
} while(1);
  • Busy waiting = Spin lock (계속 CPU와 memory를 쓰면서 wait)

Synchronization Hardware

하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

// 이 메서드가 원자적으로(atimic)하게 수행
boolean test_and_set(boolean *target) {
  boolean rv = *target;
  *target = true;
  
  return rv;
}

//Synchronization variable
boolean lock = false;

//Process Pi
  
do{
  while(test_and_set(lock));
  critical section
  lock = false;
  remainder section
}
int compare-and_swap(int *value, int expected, int new_value) {
  int temp = *value;
  
  if(*value == expected)
    *value = new_value;
  
  return temp;
}

Semaphore

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

  • Semaphore S

    • integer variable
    • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
    // P는 자원을 획득
P (S) : while(S<=0) do no-op; //waiting
				S--;
				
// V는 자원을 반납				
V (S) : S++;

Critical Section of n Process (Busy-wait)

//Synchronization variable
semaphore mutex; // initially 1 (1개가 CS에 들어갈 수 있다.)

Process Pi
do {
		P(mutex);
		critical section
		V(mutex);
		remainder section

} while(1);

Busy-wait는 효율적이지 못함

Block& wakeup 방식(=sleep lock)의 구현

  • Semaphore 구현
typedef struct
{
  int value;  // semaphore
  struct process *L // process wait queue
} semaphore;

block // 커널은 block을 호출한 프로세스를 suspend 시킴,이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  
wakeup(P) // block된 프로세스 P를 wakeup시킴, 이 프로세스의 PCB를 ready queue로 옮김
P (S) : S.value--;
				if(S.value < 0)
        {		
          	block(); // add this process to S.L
        }

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

Busy-wait versus Block/wakeup

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

자바로 구현해보기

  • 원자적 변수로만 모든 상황에서 경쟁 조건을 완벽하게 해결하지 못한다.
  • test_and_set과 compare_and_swap에 대해서 자바에서 Atomic변수 또한 compare_and_swap을 통해 구현된 것으로 아는데, 비슷한 기능이 있어서 테스트 겸 코드를 작성해보았다.
import java.util.concurrent.atomic.AtomicBoolean;

public class Peterson {

    private static int count = 0;

    private static int turn = 0;
    private static AtomicBoolean[] flag = new AtomicBoolean[]{new AtomicBoolean(), new AtomicBoolean()};

    public static void main(String[] args) throws InterruptedException {

        Thread producer = new Thread(new Producer());
        Thread consumer = new Thread(new Consumer());

        producer.start();
        consumer.start();
        producer.join();
        consumer.join();

        System.out.println(count);
    }

    private static class Producer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 30000; i++) {
                flag[0].set(true);
                turn = 1;
                while (flag[1].get() && turn == 1) {
                    // waiting
                };

                count++;
                System.out.println(Thread.currentThread().getName()+" producer in critical section 카운트 : "+count);
                flag[0].set(false);
            }
        }
    }

    private static class Consumer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 30000; i++) {
                flag[1].set(true);
                turn = 0;
                while (flag[0].get() && turn == 0) {
                    // waiting
                };
                // critical section
                count--;
                System.out.println(Thread.currentThread().getName()+" consumer in critical section 카운트 : "+count);
                //exit section
                flag[1].set(false);

                //remainder section
            }
        }
    }
}

import java.util.concurrent.atomic.AtomicBoolean;

public class TestAndSet {

    private static AtomicBoolean lock = new AtomicBoolean(false);

    private static int count = 0;

    public static void main(String[] args) throws InterruptedException {

        Thread producer = new Thread(new Producer());
        Thread consumer = new Thread(new Consumer());

        producer.start();
        consumer.start();
        producer.join();
        consumer.join();

        System.out.println(count);

    }

    public static class Producer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 30000; i++) {
                while (lock.getAndSet(true)) {
                    //do noting..
                    System.out.println("producer waiting "+ lock);
                }
                //critical section
                count++;
                System.out.println("producer in critical section, count = " + count);
                lock.set(false);
            }
        }
    }

    public static class Consumer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 30000; i++) {
                while (lock.getAndSet(true)) {
                    //do noting..
                    System.out.println("consumer waiting "+ lock);
                }
                //critical section
                count--;
                System.out.println("consumer in critical section, count = " + count);
                lock.set(false);
            }
        }
    }
}

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class Cas {

    private static AtomicBoolean lock = new AtomicBoolean(false);

    private static AtomicInteger count = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {


        Thread producer = new Thread(new Producer());
        Thread consumer = new Thread(new Consumer());

        producer.start();
        consumer.start();
        producer.join();
        consumer.join();

        System.out.println(count);

    }

    public static class Producer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                while (lock.compareAndExchange(false, true) ) {
                    //do noting..
                    System.out.println("producer waiting "+ lock);
                }
                //critical section
//                try {
//                    Thread.sleep(10);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }

                System.out.println("producer in critical section, count = " + count.incrementAndGet());
                lock.set(false);
//                try {
//                    Thread.sleep(10);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
            }
        }
    }

    public static class Consumer implements Runnable {

        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                while (lock.compareAndExchange(false, true)) {
                    //do noting..
                    System.out.println("consumer waiting "+ lock);
                }
                //critical section
//                try {
//                    Thread.sleep(10);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
                System.out.println("consumer in critical section, count = " + count.decrementAndGet());
                lock.set(false);
//                try {
//                    Thread.sleep(10);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
            }
        }
    }
}
profile
Minseok-Choi
차곡차곡
이전 포스트

04. CPU 스케줄링

다음 포스트

병행제어1 발표자료

0개의 댓글