💡 INTRO

  • 팀과 함께 나름 큰 프로젝트를 진행했다. 또한 추후에 있을 꽤 많은 사람들(약 100명 예상)이 참여하는 데모를 준비했다.
  • 실제 사람들에게 사용되려니 고려해야할 것이 굉장히 많았다.
  • 기능이 제대로 돌아가는 것도 중요하지만 많은 사용자에게 실제로 서비스 될 수 있는지까지 고려해야했다.
  • 따라서 어플리케이션이 실제로 구동되는 OS에 대한 지식이 없이는 어플리케이션의 안정성에 대한 판단력을 가지기 어렵다고 생각했다.
  • 따라서 운영체제 관련 책을 읽고 (추후 업로드 예정) 책에 빠진 부분을 보충하여 학습한다.

🌩 KEYWORD

  • 경쟁 상태 Race Condition
  • 임계 영역 문제 The Critical-Section Problem
  • 피터슨 해결안 Peterson’s Solution - 소프트웨어 측면
  • 세마포어 Semaphores & 뮤텍스 Mutex
  • 동기화 문제들
    • 유한 버퍼 문제
    • Readers-writers 문제
    • 식사하는 철학자들 문제

🌩 경쟁 상태 Race condition

  • 프로세스 간은 각기 다른 메모리에 존재하기 때문에 통신을 위해서는 공유 데이터를 사용한다. 또한 커널을 공유자원으로 사용한다.
  • 이러한 공유 자원에 대해 여러 프로세스가 동시에 접근을 시도한다면 접근하는 프로세스의 순서에 따라서 결과값이 달라져 일관성을 헤친다.
  • 이러한 상황을 race condition 이라고 한다.

Race condition 발생하는 상황

  1. 커널 작업 중 인터럽트 발생
    • 커널은 모든 프로세스가 공유하는 부분이기 때문에 race condition이 발생할 수 있다.
    • 인터럽트 수행 코드가 반영이 되지 않을 수 있다.
  2. 프로세스의 system call로 커널모드일 때 문맥 교환 발생
    • 프로세스1이 커널모드에서 데이터를 조작하는 중 시간초과가 되어 문맥 교환이 일어나고 프로세스2가 실행된다.
    • 프로세스2가 모두 수행한 후 프로세스1이 다시 로드되어 중단되었던 코드를 이어서 실행한다. (이때 저장된 레지스터 값들을 다시 로드하여 이어한다)
    • 프로세스1이 저장했던 값으로 재진행 후 결과값이 저장되기 때문에 수행되었던 공유 자원에 대한 프로세스2의 수행은 반영되지 않는다.
  3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
    • 멀티 프로세서는 동시에 작업을 할 수 있는 CPU 처리기가 2대 이상이다.
    • 두 코어가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우 race condition이 발생한다.
  • 경쟁 조건이 발생하기 쉬운 커널 자료구조
    • 메모리를 할당하는 자료구조
    • 프로세스 리스트를 유지하는 자료구조
    • 인터럽트 처리를 위한 자료구조
    • 열린 파일 리스트를 저장하는 자료구조 등등

🌩 임계 영역 문제 The Critical-Section Problem

  • 여러 프로세스가 데이터를 공유할 때 각 프로세스에서 공유 데이터를 접근하는 부분의 코드

  • 이 부분을 불분명한 순서나 동시에 작업하는 경우 데이터 일관성을 헤치는 중요한 구역이므로 임계 영역이라고 부른다.

  • 기본적으로 공유 데이터를 지키기 위한 운영체제의 특징은 다음과 같다.

    • 한 프로세스가 자신의 임계 영역 (다른 프로세스들과 공유하는 데이터를 조작하는 부분)에서 실행 중이라면 다른 프로세스들은 자신의 임계 영역에 들어갈 수 없다.
    • 이미 한 프로세스가 공유 데이터를 조작 중이므로 다른 프로세스는 임계 영역에 접근하지 못한다.

  • 임계 영역과 관련하여 대부분의 프로세스는 다음과 같은 코드 구조를 가진다.

    do {
	// 진입 영역
		
		// 임계 영역

	// 퇴출 영역

		// 나머지 영역
} while (TRUE);

임계 영역 해결안

다음 3가지 조건을 충족해야 한다.

  1. 상호 배제 Mutual Exclusion
    • 하나의 프로세스가 임계 영역에서 실행 중이라면 다른 프로세스는 자신의 임계 영역에서 실행할 수 없다.
  2. 진행 Process
    • 임계 영역이 비어있을 때 진입하고자 하는 프로세스가 있다면 그 중에서 반드시 임계 영역에 진입할 수 있어야 한다.
  3. 유한 대기 Bounded Waiting
    • 한 프로세스가 임계 영역에 진입을 요청했다면 무한으로 기다리지 않고 반드시 들어갈 수 있어야 한다.
    • 즉, 요청 프로세스가 있다면 진입하고자 하는 다른 프로세스들에게는 제한이 있어야 한다.

운영체제에서 임계 영역을 다루는 2가지 접근

  1. 선점형 커널
    • 프로세스가 커널 모드에서 실행되는 동안 선점하는 것을 허용한다.
    • 경쟁 조건 발생 위험이 있으므로 잘 설계해야 하지만 더 선호하는 커널이다.
    • 실시간 프로그래밍에 적합하며 민첩한 응답이 가능하다.
    • 따라서 프로세스 동기화에 대한 내용은 선점형 커널인 경우 그 문제를 해결하는 방법이라고 할 수 있다.
  2. 비선점형 커널
    • 프로세스가 커널 모드에서 실행되는 동안 선점을 허용하지 않는다.
    • 커널 안에 실행 중인 프로세스가 하나 뿐이기 때문에 경쟁 조건을 염려할 필요가 없다.

🌩 피터슨 알고리즘 Peterson’s Algorithm

  • 단 두개의 프로세스에 대한 임계영역의 해결 방법이다.
  • 임계 영역에 들어가고 싶다면 flag를 true로 바꾼다.
  • 다른 프로세스에게 차례를 넘긴다.
  • 임계 영역에 들어가기 전에 상대 프로세스가 임계 영역에 접근하고 싶은지 먼저 확인한다.
    • while(flag[j] && turn == j);
  • 상대가 자원을 쓰고 싶지 않거나 (⇒ flag[j] == false) 내 차례라면 (⇒ turn ≠ j) 임계 영역에 들어갈 수 있다.
  • 상대가 자원을 쓰고 싶고 (⇒ flag[j] == true) 상대의 차례라면 (⇒ turn == j) while에 갇혀서 임계 영역에 들어가기 전에 대기한다.
    • busy wait 이라고 한다.
  • turn 이 단 하나의 변수이기 때문에 임계 영역 문제를 해결할 수 있는 경우이다.
do {

  flag[i] = true;			
  turn = j;
				
  while(flag[j] && turn == j);
  
  // critical section
  
  flag[i] = false;

  // remainder section

} while(1);

피터슨 알고리즘 증명

  • 그렇다면 피터슨 알고리즘은 위 임계 영역 해결안 조건 3가지를 충족할까?
  1. 상호 배제
    • 둘다 지나가고 싶어서 flag 값을 true로 지정하여도 turn인 프로세스만 임계 영역에 들어갈 수 있다.
  2. 진행
    • 하나의 프로세스가 빠져나올 때 해당 프로세스의 flag를 false로 진행하므로 다른 프로세스가 들어갈 수 있도록 한다.
  3. 유한 대기
    • j 프로세스가 들어가고 싶을 때 turn은 i로 지정하고 i가 들어가고 싶을 때 그 반대로 지정하므로 반드시 상대 프로세스가 먼저 진입하고 싶다면 할 수 있도록 한다.
    • 때문에 모든 프로세스는 유한 대기한다.

🌩 세마포어

  • 공유 자원의 접근을 제한하는 방법의 일종이며 자원의 개수 (S)를 통해서 몇개의 프로세스가 진입할 수 있는지를 판단한다.

  • 두 가지 연산

    • 이 두 연산은 반드시 atomic 하게 실행이 되며 인터럽트 될 수 없다.

    • P: 임계 영역에 들어가기 전에 수행

      P(S) {
	while (S <= 0);
	S--;
}
      • 프로세스 진입 여부를 자원 개수

    • V: 임계 영역에서 나올 때 수행

      V(S) {
	S++;
}
      • 자원을 반납하며 대기 중인 프로세스를 깨운다.

  • 위 두 연산을 이용해 다음과 같은 흐름으로 진행된다.

    P(S);

//-- 임계 구역 -- //

V(S);

  • 세마포어는 두 가지로 나뉜다.

    • 카운팅 세마포어
      • 세마포어의 값이 양의 정수값을 가지며 이 값만큼의 프로세스 혹은 스레드를 자원에 허락한다.
      • 동기화 대상이 2개 이상이다.
    • 이진 세마포어 (⇒ 뮤텍스)
      • 세마포어 값이 1이며 0, 1 만 가능하다.
      • 동기화 대상이 2개 뿐이다.

  • 동작 방식

    • 임계 영역에 접근하고 싶은 프로세스 혹은 스레드는 P(S) 를 호출한다.
      • 만일 세마포어 값이 0이면 진입할 수 없는 상태이므로 대기한다. (락이 걸린다)
      • 자원이 해체되면 임계 영역에 들어갈 수 있는데 이때 세마포어 값을 하나 감소시킨다.
    • 임계 영역에서 나오는 프로세스는 V(S)를 호출한다.
      • 자원을 반납하므로 세마포어 값을 하나 증가시킨다.
      • 이때 대기 중이던 다른 프로세스가 while 문에서 나와 자원을 할당 받을 수 있다.

🌩 뮤텍스

  • 이진 세마포어 라고도 불린다.
  • 상호 배제 Mutual Exclusion 의 앞 부분을 따서 Mutex라고 부른다.
  • 임계 영역에 들어갈 때 Lock 을 가지고 들어간다.
    • 다른 프로세스는 임계 영역에 들어갈 수 없다.
    • 해당 프로세스는 Lock(뮤텍스)를 소유할 수 있다.
  • 임계 영역에서 나올 때는 lock 을 반납하고 다른 프로세스에게 넘겨준다.
    • 피터슨 알고리즘이 뮤텍스의 일종이다.

뮤텍스와 세마포어의 차이점

  • 세마포어는 뮤텍스를 포괄하는 개념이다.
    • 이진 세마포어가 뮤텍스다.
  • 세마포어는 그 값만큼 프로세스나 쓰레드가 공유자원에 접근할 수 있지만 뮤텍스는 1개만 가능하다.
  • 뮤텍스는 소유될 수 있으므로 해당 lock 을 소유하는 프로세스가 반드시 반납해야하지만, 세마포어는 소유할 수 없는 것이며 락을 걸지 않은 프로세스나 스레드도 락을 해제할 수 있다.

🌩 동기화 문제들

유한 버퍼 문제

  • 유한한 버퍼에 아이템을 저장(생상)하고 빼내오는(소비) 문제를 뮤텍스와 세마포어로 해결한다.

  • 사용 값

    • Mutex : 1로 초기화 되며 버퍼풀에 접근할 수 있는 락을 의미
    • empty : 버퍼에 남은 빈 공간의 수
    • full : 버퍼에 채워진 공간의 수

  • 세마포어를 통해 버퍼의 크기를 파악하여 생산 혹은 소비할 수 있는지 판단한다.

  • 세마포어를 통과하면 버퍼에 아이템을 넣고 빼기 위한 조작을 하기 위해 뮤텍스 락을 잠군다.

  • 생산자 프로세스 구조

    do {
	// 버퍼에 추가할 아이템 생성

	wait(empty); // 빈 공간이 0 이하라면 wait, 빈 공간이 생기면 통과
	wait(mutex); // 버퍼를 조작하는 락이 0이라면 wait, 락을 획득하면 통과

	// 버퍼에 아이템 추가 

	signal(mutex); // 버퍼를 조작할 수 있는 락 반납
	signal(full); // 버퍼가 한칸 채워졌음을 알림
} while (true);

  • 소비자 프로세스 구조

    do {
	wait(full); // 버퍼에 아무 아이템이 없어 full 이 0이하라면 wait, 아이템이 생기면 통과
	wait(mutex); // 버퍼 조작 락 획득

	// 버퍼에서 아이템 빼기 (소비)

	signal(mutex); // 버퍼 조작 락 반납
	signal(empty); // 버퍼에 아이템이 빠졌음을 알림

	// 빼낸 아이템 사용
} while (true);

Readers-Writers 문제

  • 하나의 데이터베이스가 다수의 프로세스간에 공유될 때 읽는 프로세스(readers)와 읽고 쓰는 프로세스(writers)를 구분하여 접근하도록 하는 방법이다.

  • Readers 끼리는 공유데이터에 동시 접근 해도 문제가 발생하지 않지만 writer는 다른 reader 혹은 writer와 겹치면 문제가 발생한다.

  • 따라서 writer가 실행되는 동안 공유 데이터베이스에 mutual exclusion을 보장하도록 한다.

  • 이때 reader 혹은 writer가 기아상태 되지 않도록 문제를 해결해야 한다.

  • 사용 값

    • readcount : 현재 읽기를 수행하고 있는 프로세스 개수
    • mutex : readcount를 갱신하기 위한 락이며 1로 초기화
    • wrt : 쓰기를 위한 락이며 1로 초기화

  • Writer 프로세스 구조

    do {
	wait(wrt);

	// 쓰기 작업

	signal(wrt);
} while (true);

  • Reader 프로세스 구조

    do {
	wait(mutex); // readcount 갱신을 위한 락 획득
	readcount++; // 읽기 프로세스 개수 1 증가
	
	if (readcount == 1) // 만일 최초 읽기 프로세스라면 
		wait(wrt); // 쓰기가 진행 중인지 확인하고 쓰기 중이라면 대기, 아니라면 쓰기 락을 획득하고 통과

	signal(mutex); // readcount 갱신을 위한 락 반납

	// 읽기 작업 수행

	wait(mutex); 
	readcount--; // 읽기 수행 완료 후 프로세스 1 감소

	if (readcount == 0) // 만일 읽기 프로세스가 하나도 없다면
		signal(wrt); // 쓰기 락 반납하여 쓰기 프로세스 진행가능하도록 함

	signal(mutex);
} while (true);

식사하는 철학자들 문제 The Dining-Philosophers Problems

  • 다섯명의 철학자들이 원탁에 있고 다섯개의 젓가락이 철학자들 사이에 하나씩 놓여있다. 가운데 공유 밥은 한 개이다.

  • 자신의 오른쪽 젓가락이나 왼쪽의 젓가락이 없다면 먹을 수 없다.

  • 교착상태나 기아를 발생시키지 않고 여러 스레드에 여러 자원을 할당해야하는 경우다.

  • 철학자 i의 구조

    세마포어 값은 chopstick[5]; 이다. 

do {
	wait(chopstick[i]);
	wait(chopstick[(i + 1) % 5]);

	// 먹기

	signal(chopstick[i]);
	signal(chopstick[(i + 1) % 5]);

	// 생각하기
} while (true);

  • 동시에 두 철학자가 식사하지 않도록 보장하지만 교착상태를 야기할 가능성이 있다. 그 해결책이 몇개 있다.

    • 최대 4명의 철학자만 앉게 한다.
    • 한 철학자가 두개의 젓가락을 모두 집을 수 있을 때만 허용한다.
    • 홀수번 철학자는 왼쪽부터 집고, 짝수번 철학자는 오른쪽 부터 집도록 한다.

  • 교착상태를 해결하면 기아상태를 주의해야한다.



🌩 참고링크