[운영체제-양희재 교수님]11-12강 임계 구역 문제와 세마포

경성대학교 양희재 교수님의 운영체제 11강

경성대학교 양희재 교수님의 운영체제 12강

임계 구역 문제

• The Critical-Section Problem
  • 치명적인 오류가 일어날 수 있는 구간
• Critical section
  • A system consisting of multiple threads(or processes)에서 등장
  • Each thread has a segment of code, called critical section, in which the thread may be changing common variables, updating a table, writing a file, and so on.
• 임계 구역 문제를 해결하기 위해 만족해야 할 세 가지 조건
  • Mutual exclusion(상호 배타): 오직 한 쓰레드만 임계 구역에 진입해야 한다.
  • Progress(진행): 임계 구역에 누가 들어갈지 진입 결정은 유한 시간 내에 일어나야 한다.
  • Bounded waiting(유한 대기): 어느 쓰레드라도 유한 시간 내에 임계 구역에 들어갈 수 있어야 한다.

프로세스/쓰레드 동기화

• 틀린 답이 나오지 않도록 임계구역 문제를 해결
  • 세 가지 조건 만족
• 프로세스의 실행 순서를 원하는 대로 제어
• Busy wait 등 비효율성은 제거

동기화 도구(Synchronization Tools)

• 프로세스/쓰레드의 동기화를 위해 동기화 도구를 사용
• 종류
  • Semaphores
  • Monitors
  • Misc.

Semaphores(세마포)

• 동기화 문제 해결을 위한 소프트웨어 도구
  • 네덜란드의 Edsger Dijkstra가 제안
• 구조
  • 정수형 변수(number of permits)
  • 두 개의 동작(P, V)
  • 프로세스가 대기하는 큐(list)
• 동작
  • P: Proberen(test) → acquire()
  • V: Verhogen(increment) → release()

    class Semaphore {
    	int value; // number of permits
    	Semaphore(int value) {
    		... 
    	}
    	void acquire() {
    		value--;
    		if (value < 0) {
    			add this process/thread to list;
    			block; // list에 들어가서 ready queue로 가지 못함
    		}
    	}
    	void release() {
    		value++;
    		if (value <= 0) {
    			remove a process P from list;
    			wakeup P; // list에 갇힌 프로세스를 ready queue로 보냄
    		}
    	}
    }
  

• 세마포의 일반적인 목적
  • Mutual exclusion

    • sem.value = 1;으로 설정하면 한 번에 하나의 프로세스만 임계 구역 진입 가능

        sem.acquire();
        Critical-Section
        sem.release();
      

  • Ordering

    • sem.value = 0;으로 설정하면 프로세스의 순서를 제어 가능

        P1                   P2
                             sem.acquire();
        S1                   S2
        sem.release();
      

      • P2의 S2(Statement2)가 먼저 실행되어도 acquire()에 의해 리스트로 간다.
      • S1 앞에는 acquire()가 없으므로 바로 실행된다.

    • 두 개의 세마포를 사용하면 두 프로세스를 번갈아 작업할 수 있다.

        P1                   P2
                             sem1.acquire();
        S1                   S2
        sem1.release();      sem2.release();
        sem2.acquire();