프로세스 동기화

  • 협동 프로세스는 시스탬 내에서 실행중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스다.
  • 협동 프로세스에서 데이터 공유는 동시접근에 의한 데이터의 비 일관성을 낳을 수 있다.
  • 협동 프로세스의 질서있는 실행을 보장하며, 이를 통해 데이터의 일관성을 유지하는 기법을 알아보자.

배경

  • 프로세스는 동시 또는 병렬로 실행될 수 있다.
  • CPU 스케줄러가 프로세스 사이에서 빠르게 오가며 각 프로세스를 실행해 모든 프로세스를 동시실행 한다. 프로세스는 다른 프로세스가 스케줄 되기 전에 일부분만 진행 할 수 있다.
  • 다른 프로세스에 속한 두개의 명령어 흐름을 다른 프로세스 코어에서 동시 실행 되는 병렬 방식이 있다.
  • 프로세스 동기화에서는 동시 또는 병렬로 실행 될 때 여러 프로세스가공유하는 데이터의 무결성에 어떤 문제가 있는지 설명한다.
  • 두개의 프로세스가 동시에 하나의 변수를 조작하고, 실행 결과가 접근이 발생한 특정 순서에 의존하는 경쟁상황 race condition이 발생할 수 있다.
  • 이같은 문제를 방지하기 위해 한순간에 하나의 프로세스만 변수를 조작하도록 보장해야한다.

임계구역 문제

  • 각 프로세스는 임계구역이라 하는 코드를 포함하고 있다. 임계구역에서는 다른 프로세스와 공유하는 변수, 테이블, 파일 등의 IO를 수행한다.
  • 한 프로세스가 자신의 임계구역에서 수행하는 동안 다른 프로세스들은 그 임계구역에 들어갈 수 없다.
  • 임계구역 문제는 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것이다.
  • 임계구역 문제에 대한 해결안은 다음 세가지를 모두 충족해야 한다. 현실적으로 어렵다.
    1. 상호 배제 mutual exclusion : 한 프로세스가 자기의 임계구역에서 실행된다면 다른 프로세스들은 자신의 임계구역에서 실행될 수 없다.
    2. 진행 progress (avoid deadlock) : 임계구역에서 실행되는 프로세스가 없고, 임계구역으로 진입하려고 하는 프로세스들이 있다면 나머지 구역에서 실행중이지 않은 프로세스들만 다음에 임계구역에 진입할 프로세스를 결정하는데 참여할 수 있다.
    3. 제한된 대기 bounded waiting (avoid starvation) : 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후 부터 그 요청이 허용될 떄 까지 다른 프로세스들이 자신들의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다
  • 운영체제 내에서 임계구역을 다루기 위해 선점형 커널과 비선점형 커널 두가지 일반적인 접근법이 있다.
  • 선점형 커널 : 커널 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다. 동일한 주장을 할 수 없기 때문에 공유되는 커널 자료구조에서 경쟁조건이 발생하지 않는 다는것을 보장하도록 신중히 설계해야 한다. 강제로 방출이 가능.
  • 비선점형 커널 : 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈때 까지 또는 블로킹 될 때 까지 자발적으로 CPU의 제어를 양보할 때 까지 계속 수행한다. 커널 안에서 실행 중인 프로세스는 하나 뿐이기에 커널 자료구조에 대한 경쟁조건을 염려할 필요가 없다.
  • 선점형 커널을 선호하는 이유 : 커널 모드 프로세스가 대기중인 프로세스에게 프로세서를 양도하기 전 오랫동안 실행할 위험이 적기 때문. 그래서 선점형 커널은 응답이 민첩할 수 있다. 또한 실시간 프로세스가 현재 커널에서 실행중인 프로세스를 선점할 수 있어 리얼타임 프로그래밍에 더 적당하다.

피터슨 해결안 Peterson's solution

  • 소프트웨어 기반의 해결책.
  • 피터슨 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두개의 프로세스로 한정된다.
  • 피터슨 해결안은 두 프로세스가 두개의 데이터 항목을 공유하도록 하여 해결한다.
  • (2개의 프로세스일때 flag를 두고 해당 flag의 원소 인덱스가 ture일때만 임계구역에 진입한다는 내용)

동기화 하드웨어

  • 하드웨어 기반의 해결책
  • 모든 해결책들은 임계구역을 보호하기 위한 잠금에 대한 가정이다.

Atomicity

  • 원자적 동작이라는 것은 더이상 쪼갤 수 없는 동작의 단위다.
  • 특별한 하드웨어 인스트럭션을 사용하자 - 원자적 인스트럭션

Mutex Locks (Mutual exclusion locks)

  • 운영체제 설계자들은 임계구역 문제를 해결하기 위해 소프트웨어 도구를 개발하는데 그중 하나가 mutex lock이다.
  • 프로세스는 임계구역에 들어가기 전에 반드시 lock을 획득해야 하고 임계구역을 빠져 나올 때 lock을 반환해야 한다.
  • 바쁜 대기 busy waiting : 프로세스가 임계구역에 있는 동안 임계구역에 들어길 원하는 다른 프로세스들은 반복문을 계속 실행해햐 하는 스핀락 spin lock 문제가 있다.
  • spin lock은 context switcing을 필요로 하지 않는 것이 장점이다. 짧은 시간을 제어권을 가진다면 spin lock이 유용하다.
  • 멀티코어 시스템에서 spin lock이 선호되는 경향이 있다.
  • mutex locks 예제
#include <stdio.h>
#include <pthread.h>

int sum = 0;

pthread_mutex_t mutex;

void    *counter(void *param)
{
    int k;
    for (k = 0; k < 10000; k++){
        /* 구역 진입 */
        pthread_mutex_lock(&mutex);

        /* 임계 구역 */
        sum++;

        /* 구역 종료 */
        pthread_mutex_unlock(&mutex);

    }
    pthread_exit(0);
}

int        main(void)
{
    pthread_t tid1, tid2;
    pthread_mutex_init(&mutex, NULL);
    pthread_create(&tid1, NULL, counter, NULL);
    pthread_create(&tid2, NULL, counter, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("%d\n", sum);
}
  • 실행결과
% gcc -pthread mutex_locks_test.c 
% ./a.out
20000

Semaphores

  • mutex와 유사하게 작동하지만 세마포어는 좀 더 정교하게 동기화 할 수 있다.

세마포어 사용법

  • 카운팅 세마포어 : 유한한 갯수를 가진 자원에 대한 접근을 제어하는데 사용한다. 세마포어 값이 0이 되면 모든 자원을 사용중이란 뜻이다.
  • 이진 세마포어 : 0과 1사이의 값만 지정하므로 mutex lock과 유사하게 작동한다.
  • wait(), P() : 리소스를 사용하기 위해 세마포어의 값을 매개변수로 넘긴다.
  • signal(), V() : 사용한 리소스를 반환하기 위해 세마포어의 값을 매개변수로 넘긴다.
  • mutex와 semaphore의 간단한 이야기 뮤텍스는 하나의 자원에 대한 접근 이야기고 / 아까 뮤텍스는 그 구간전체?를 락잡는다면 세마포어는 자원을 할당할 수 있는 갯수에 대한 이야기 / 세마포어는 부분구간별로 락을 잡는 개념임 signal 은 카운트를 올리는 거고, wait는 카운트를 줄이는 거
  • 세마포어 볼만한 글 #1
  • 동시성을 위한 CountDownLatch

구현

  • mutex lock의 구현은 busy waiting을 해야 했다. 세마포어 연산 역시 같은 문제를 가지고 있다.
  • 프로세스가 wait()를 실행할 때
    • 만약에 이 세마포어가 사용불가능 해서 기다려야 할때 busy waiting보다 waiting queue에 들어가면 된다.
  • 프로세스가 signal()을 실행할 때
    • waiting queue에 대기하고 있던 프로세스를 ready queue로 넣으면 된다.
  • 이렇게 하면 busy waiting이 해결된다.
  • busy waiting을 하는 세마포어값은 음수가 될 수 없으나 음수를 절대값으로 바꾸면 세마포어를 대기하는 프로세스의 수가 된다
  • 대기하는 프로세스들의 리스트는 각 PCB에 있는 연결 필드에 의해 구현된다.
  • 세마포어는 원자적으로 실행되야 한다.
  • wait()과 signal()이 실행되는 동안 인터럽트를 금지해야 한다. 멀티 프로세서의 경우엔 모든 프로세서에서 인터럽트를 금지해야 한다.
  • binary semaphore implements
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

int sum = 0;

sem_t sem;

void    *counter(void *param)
{
    int k;
    for (k = 0; k < 10000; k++){
        /* 구역 진입 */
        sem_wait(&sem);

        /* 임계 구역 */
        sum++;

        /* 구역 종료 */
        sem_post(&sem);

    }
    pthread_exit(0);
}

int        main(void)
{
    pthread_t tid1, tid2;
    sem_init(&sem, 0, 1); // binary semaphore
    pthread_create(&tid1, NULL, counter, NULL);
    pthread_create(&tid2, NULL, counter, NULL);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("%d\n", sum);
}
  • 실행결과
20000
  • counting semaphore implements
/* ...생략 ... */
int        main(void)
{
    pthread_t tid[5];
    int i;
    sem_init(&sem, 0, 5); // counting semaphore
    for (i = 0; i < 5; i++)
        pthread_create(&tid[i], NULL, counter, NULL);
    for (i = 0; i < 5; i++)
        pthread_join(tid[i], NULL);
    printf("%d\n", sum);
}
  • 실행결과
_test1 $ ./a.out 
49209
_test1 $ ./a.out 
49150
_test1 $ ./a.out 
49291
_test1 $ ./a.out 
48852
_test1 $ ./a.out 
49184
  • 5개의 스레드가 5개의 세마포어를 가지고 진입한다. 그러면 경쟁조건이 바로 생긴다.
  • 세마포어는 n개의 인스턴스가 있다는 조건이다. 그래서 sum[5]로 해서 최종적으로 배열의 값을 합치는것으로 하면 제어가 된다.

교착상태와 기아

  • 대기 큐를 가진 세마포어를 사용하면 두개 이상의 프로세스가 이벤트를 무한정 기다리는 상황이 발생할 수 있다. 이 이벤트는 대기 중인 프로세스 중 하나만이 발생시킬 수 있는 사건으로 signal()의 실행을 의미한다. 이것을 교착상태 deadlock이라고 한다.
  • 무한봉쇄 또는 기아 상태는 세마포어와 연관된 큐에서 후입선출로 제거하는 경우 발생할 수 있다.

우선순위 역전 (Priority inversion)

  • 높은 우선순위를 가진 프로세스가 낮은 우선순위를 가진 프로세스에게 밀리는 현상.
  • 예를 들어 높은 우선순위의 프로세스가 커널 데이터에 접근하려고 하는데 낮은 우선순위의 프로세스가 점유하고 있으면 뺏을 수 없다.
  • 해결하려면 우선순위 상속을 하면 된다.
    • 낮은 순위의 프로세스가 자원을 점유하고 있을때 높은 순위의 우선순위를 복사해주는것

고전적인 동기화 문제

  • 동시성 제어 (Concurrency-control) 문제에 대한 예

유한 버퍼 문제

  • 생산자-소비자 문제
  • n개의 버퍼로 구성된 pool이 있으며 각 버퍼들은 아이템을 저장할 수 있다고 가정할때, mutex 세마포어는 버퍼 pool에 접근하기 위한 상호 배제 기능을 제공한다.
  • 생산자가 소비자를 위해 꽉 찬 버퍼를 생산해내고, 소비자는 생산자를 위해 비어있는 버퍼를 생산해 내는 것으로 해석가능하다.

Readers-Writers 문제

  • 하나의 데이터베이스가 다수의 동시 프로세스들 간에 공유된다고 가정할 때, reader와 writer가 있다. 여러개의 reader가 동시에 자원에 접근하는것은 문제가 없지만 writer가 쓰기 작업을 할 때는 배타적인 접근 권한이 필요하다.
    1. 첫번째. r-w문제에서 writer가 공유 객체의 사용허가를 얻지 못했다면, 어느 reader도 기다리게 해서는 안된다. 단순히 writer가 기다리고 있기 때문에 다른 reader들이 끝날때 까지 기다리는 reader가 있으면 안된다.
    2. 두번째. r-w문제에서 writer가 준비되면 가능한 빨리 쓰기를 수행할 것을 요구한다. writer가 자원의 접근을 기다리면 reader는 읽기를 하지 못한다.
  • r-w락은 다음과 같은 상황에서 유용하다
    1. 공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 스레드를 식별하기 쉬운 어플리케이션
    2. writer보다 reader의 개수가 많은 어플리케이션은 일반적으로 r-w락을 설정하는 데 드는 오버헤드가 세마포어나 상호배제락을 설정할 때 보다 크다. 이 오버헤드는 동시에 여러 reader가 읽게 해서 동시성을 높힘으로써 상쇄할 수 있다.

식사하는 철학자 문제

  • 리소스와 프로세스의 종류가 여러개인 경우의 교착상태와 기아에 대한 이야기.
  • 상호배제 mutex해결하기 위한 세마포어 솔루션
    • 가장 심플한 솔루션, 각 젓가락에 세마포어를 하나씩 걸어준다. (바이너리) 어떤 철학자가 젓가락에 접근할때 반드시 wait()을 호출하도록 하고 젓가락을 놓을때 signal()을 호출한다.
  • 그러나 이렇게 하면 교착상태 deadlock이 발생한다.
    • 5명의 철학자가 동시에 배가 고프다면? 각각 한개씩 젓가락을 잡고있으면?
  • 교착상태 문제에 대한 여러가지 해결책들
    • 최대 4명의 철학자들만 테이블에 동시에 앉을 수 있도록 한다.
    • 한 철학자가 젓가락 두개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.
    • 비대칭 해결안을 사용한다. 즉, 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 집고 다음에 오른쪽 젓가락을 집는다. 반면 짝수 번호의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 집는다.
  • 그러나 교착상태가 없는 해결안이 반드시 기아의 가능성도 제거하는 것은 아니다.

모니터

  • 세마포어는 발견하기 어려운 타이밍 오류가 발생할 수 있다. 타이밍 오류는 항상 일어나지 않기 때문에 발견하기 힘들다.
  • 세마포어를 사용하면서 발견하는 문제들을 없애기 위해 고급 언어 구조물들을 개발했다. 그중에 하나가 모니터 형이다.

모니터 사용법

  • Abstract data type (ADT)는 데이터와 조작하는 함수들의 집합을 하나로 묶어 보호한다. (aka 자바의 클래스)
  • 함수의 구현은 ADT구현과는 독립적이다.
  • 모니터형은 내부에서 상호 배제가 보장되는 일련의 연산자 집합을 포함하는 ADT다.
  • 모니터형은 지역변수를 가지고 프로시저를 가지며 인스턴스의 상태를 정의한다 (객체를 말하는듯?)
  • 모니터형은 다른 프로세스들이 직접 사용할 수 없다.
  • 모니터 내에 정의된 지역함수만 오직 지역변수에 접근할 수 있다.
  • 모니터 구조물은 모니터 안에 항상 하나의 프로세스만 활성화 되도록 보장해준다.
  • Conditional Variables
  • condition타입을 추가함으로써 동기화 기법을 추가적으로 제공한다.

자바의 모니터

  • 자바는 Monitor-lock (intrinsic-lock)을 제공한다
  • synchronized키워드 / wait() 와 notify() 메소드가 있다.
  • synchronized키워드 : 임계 영역에 해당하는 코드 블록을 선언할 때 사용하는 자바 키워드
    • 해당 코드블록(임계영역)에는 모니터락을 획득해야 진입 가능
    • 모니터락을 가진 객체 인스턴스를 지정할 수 있음
    • 메소드에 선언하면 메소드 코드 블록 전체가 임계영역으로 지정됨 - 이때 모니터락을 가진 객체 인스턴스는 this 객체 인스턴스임
  • wait(), notify() : Object 클래스에 선언됨 모든 자바 객체가 가진 메소드임
    • thread가 어떤 객체의 wait()를 호출하면 - 해당 객체의 모니터 락을 획득하기 위해 대기 상태로 진입
    • thread가 어떤 객체의 notify()를 호출하면 - 해당 객체 모니터에 대기중인 thread를 하나 깨움
    • notify()대신 notifyAll()메소드를 호출하면 - 해닫 객체 모니터에 대기중인 스레드를 전부 깨움

모니터를 사용하는 식사하는 철학자 솔루션

  • 식사하는 철학자문제에서 교착상태가 없는 해결안으로 모니터의 예시를 들 수 있다.
  • 이 해결안은 철학자가 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 들 수 있다는 점이다.
  • 철학자는 양쪽 두 이웃이 모두 식사를 하지 않을때만 젓가락을 들 수 있다.
  • 철학자가 배고프지만 젓가락을 잡을 수 없을때는 미룬다.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define true 1
#define NUM_PHILS 5

enum {THINKING, HUNGRY, EATING} state[NUM_PHILS];

pthread_mutex_t mutex_lock;
pthread_cond_t cond_vars[NUM_PHILS];

int leftOf(int i){
    return (i + NUM_PHILS - 1) % NUM_PHILS;
}

int rightOf(int i){
    return (i + 1) % NUM_PHILS;
}

void think(int id) {
    printf("%d: Now, I'm thiking...\n", id);
    usleep((1 + rand() % 50) * 10000);
}

void eat(int id) {
    printf("%d: Now, I'm eating...\n", id);
    usleep((1 + rand() % 50) * 10000);
}

void test(int i) {
if (state[i] == HUNGRY &&
    state[leftOf(i)] != EATING && state[rightOf(i)] != EATING)
    {
        state[i] = EATING;
        pthread_cond_signal(&cond_vars[i]);
    }
}
void pickup(int i) {
    pthread_mutex_lock(&mutex_lock);

    state[i] = HUNGRY;
    test(i);
    while (state[i] != EATING) {
        pthread_cond_wait(&cond_vars[i], &mutex_lock);
    }

    pthread_mutex_unlock(&mutex_lock);
}

void putdown(int i) {
    pthread_mutex_lock(&mutex_lock);

    state[i] = THINKING;
    test(leftOf(i));
    test(rightOf(i));

    pthread_mutex_unlock(&mutex_lock);
}

void    *philosopher(void *param){
    int id = *((int *)param);
    while (true){
        think(id);
        pickup(id);
        eat(id);
        putdown(id);
    }
}

void init() {
    int i;
    for (i = 0; i < NUM_PHILS; i++) {
        state[i] = THINKING;
        pthread_cond_init(&cond_vars[i], NULL);
    }
    pthread_mutex_init(&mutex_lock, NULL);
    srand(time(0));
}

int main(void){
    int i;
    pthread_t tid;
    init();
    for(i = 0; i < NUM_PHILS; i++)
        pthread_create(&tid, NULL, philosopher, (void *)&i);
    for(i = 0; i < NUM_PHILS; i++)
        pthread_join(tid, NULL);
    return (0);
}

세마포어를 이용한 모니터의 구현

  • 각 모니터 마다 mutex 세마포어가 정의된다 (초기값 1)
  • 프로세스는 모니터로 들어가기 전에 wait를 실행하고 모니터를 나온 뒤 signal을 실행한다.
  • signal을 호출한 뒤에은 프로세스가 모니터를 떠나거나 wait할때까지 다시 기다려야 한다. 이 부분에서 next라는 세마포어가 추가로 필요하다.

모니터 내에서 프로세스 수행 재개

  • 모니터 내에서 프로세스들이 수행재개되는 순서를 따져보자.
  • 가장 간단한 방법은 FCFS 순서다. - 가장 오래 기다린 프로세스가 가장 먼저 깨어나는 것

동기화 사례

리눅스의 동기화

  • 2.6버전 이전의 리눅스 커널은 비선점형 커널이였다. 커널 모드에서 실행중인 프로세스는 더 높은 우선순위의 프로세스가 실행 가능한 상태가 되더라도 제어권을 가지고 올 수 없었다. 그러나 지금의 리눅스 커널은 선점형이다.
  • 리눅스는 커널 안의 임계구역을 보호하기 위해 mutex lock을 제공한다.
  • 리눅스 커널은 커널 내에서 락킹을 위해 spin-lock과 세마포어 및 두 잠금의 r-w 버전도 제공한다.

Pthread 동기화

  • pthread API는 사용자 수준에서 사용가능한 동기화 기법이다.
  • mutex lock, r-w lock을 제공한다.
#include <pthread.h>

pthread_mutex_t mutex;

/* mutex lock 생성 */
pthread_mutex_init(&mutex, NULL);
  • mutex lock으로 pthread_mutex_t을 사용한다.
/* mutex lock 획득 */
pthread_mutex_lock(&mutex);

/* 임계 구역 구현*/

/* mutex lock 반환*/
pthread_mutex_unlock(&mutex);
  • 이외에 pthread를 구현하는 많은 시스템들은 세마포어도 제공한다.
  • POSIX는 namedunnamed 두 유형의 세마포어를 명기한다.
  • named 세마포어는 파일 시스템 안에 실제 이름을 갖고 있어 여러 관계 없는 프로세스들이 공유할 수 있다
  • unnamed 세마포어는 같은 프로세스에 속한 스레드만 사용가능하다.

대안

  • 멀티 스레드 어플리케이션은 race condition과 deadlock에 대한 위험을 증가시킨다.
  • Thread-safe concurrent 어플리케이션 설계에 도움이 되는 프로그래밍 언어와 하드웨어의 기능을 살펴보자.

Transactional Memory

  • 트랜잭션 메모리의 개념은 데이터베이스에서 왔지만 프로세스 동기화 전략을 제공한다.
  • 메모리 읽기와 쓰기의 연산의 원자적인 연속적 순서다.
  • mutex나 세마포어 처럼 락을 하는것 대신 작업단위의 트랜잭션을 제공하면 deadlock이 발생하지 않는다.
  • 또한 트랜잭션은 작업 내에서 공유변수에 대한 동시 읽기 연산과 같은 동시 실행될 수 있는 구문을 구별할 수 있다.

Functional Programming language

  • C, C++, Java등을 절차형 언어라고 한다.
  • 함수형 언어는 이와 다르게 상태를 유지하지 않는 특징이 있다.
  • 변수가 정의되어 값을 배정 받으면 값은 상수화 되어 변하지 않는다.
  • 함수형 언어는 상태 변경을 허용하지 않기 때문에 race condition이나 deadlock같은 쟁점에 신경쓸 필요가 없다.

교착상태 Deadlocks

  • 멀티 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁할 수 있다.
  • 대기 중인 프로세스들이 다시 그 상태를 변경시킬 수 없으면 그 상태를 교착상태 deadlock이라고 한다.

시스템 모델

  • 시스템은 유한한 수의 자원들로 구성된다.
  • 각각의 자원은 인스턴스로 구분된다. (2코어 CPU라면 2개의 CPU인스턴스를 가진다.)
  • 프로세스는 다음의 순서로만 자원을 사용할 수 있다.
    1. 요청 : 프로세스는 자원을 요청한다. 요청이 즉시 허용되지 않으면, 요청 프로세스는 자원을 얻을때 까지 대기해야 한다.
    2. 사용 : 사용 프로세스는 자원에 대해 작업을 수행할 수 있다.
    3. 방출 : 프로세스가 자원을 방출한다
  • 멀티 스레드에서는 공유자원을 차지하기 위해 경쟁할 수 있어 다중 스레드 프로그램은 교착상태를 야기할 수 있다.

교착상태의 특징

  • 교착상채는 4가지 조건이 동시에 성립할때 발생한다.
  1. 상호 배제 (Mutual exclusion) : 최소 하나의 자원이 비공유로 점유되면, 한번에 한 프로세스만 자원을 사용할 수 있다. 다른 프로세스는 자원이 방출될때 까지 대기해야한다.
  2. 점유 대기 (Hold and wait) : 프로세스는 최소 하나의 자원을 점유한 채, 다른 프로세스에 점유된 자원을 추가로 얻기 위해 대기해야 한다.
  3. 비선점 (No preemption) : 자원들을 선점할 수 없어야 한다. 자원이 강제 방출될 수 없고, 점유하고 있는 프로세스가 작업을 종료한 후 그 프로세스에 의해 자발적으로만 방출 될 수 있다.
  4. 순환 대기 (Circular wait) : 꼬리를 물며 점유한 자원을 대기한다.
  • 4가지 조건이 독립적인 것은 아니다.

교착상태 처리 방법

  • 교착상태 처리 방법의 3가지 원칙
  1. 시스템이 교착상태가 되지 않도록 보장하기 위해 교착상태를 예방하거나 회피하는 프로토콜을 사용한다.
  2. 시스템이 교착상태가 되도록 허용한 다음 회복한다.
  3. 문제를 무시하고 교착상태가 시스템에서 발생하지 않는 척 한다.
  • 3번째가 대부분의 OS에서 사용하는 방법이다. 교착상태를 어플리케이션 개발자에게 떠넘기는 것이다.
  • 교착상태가 발생하지 않도록 하는 방법
    1. 교착상태 예방 : 교착상태가 발생하는 필요조건중 하나라도 성립하지 않도록 보장하는 방법
    2. 교착상태 회피 : 사용할 자원의 정보를 미리 제공한다. 각 프로세스의 미래의 요청과 방출을 모두 고려한다.

Comments