OS | Process Synchronization

tjddus0302·2022년 6월 22일
0

computer sicence

목록 보기
1/3
post-thumbnail


본 게시물의 내용은 양희재 교수님'운영체제' 수업을 참고하여 작성하였습니다.
출처 및 강의 자료는 게시글 하단에 기재된 링크를 통해 확인하세요.





1. 운영체제 관리


운영체제 관리에서 프로세스 관리는 매우 중요한 부분이다.
프로세스 관리는 크게 'CPU 스케줄링''프로세스 동기화' 2가지를 생각해볼 수 있다.

그 중 프로세스 동기화(Process Synchronization)에 대해 알아보려고 한다.





2. 프로세스 동기화


공통된 자원에 접근하고 사용하고자 하다보니 프로세스들 간에 영향을 미치며, 이에 따라 프로세스 동기화의 중요성이 높아진다.

  • 프로세스 간의 통신의 예: 전자우편, 파일 전송

  • 프로세스간 자원 공유의 예

    • 메모리 상의 자료들

    • 데이터 베이스

    • 온라인 수강 신청





BankAccount Problem

은행 계좌 문제를 통해 프로세스 동기화 문제를 이해해볼 수 있다.

  • 조건

    • 부모는 은행 계좌에 입금(deposit)

    • 자녀는 은행 계좌에서 출금(withdraw)

    • 입금과 출금은 독립적으로 발생



부모와 자녀가 동일한 빈도로 입금 및 출금을 진행한다면 이론적으로 은행계좌의 금액은 0이 되어야한다.

그러나 실제 코드를 이용해 확인해보면 다른 결과 값을 확인해볼 수 있는데, 이는 공통 변수(common variable)에 대한 동시 업데이트(concurrent update) 로 인한 것으로 생각해볼 수 있다.

이 문제는 임계 구역 문제로 한번에 한 쓰레드만 업데이트하도록 하는 것으로 해결할 수 있다.





3. Cirtical Section


임계구역은 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역이다.

시간이 지나면 임계구역은 종료된다.
따라서 다른 프로세스가 임계구역에 접근하기 위해 해당 시간 만큼 대기해야한다.

  • 쓰레드가 임계구역에 접근하는 순서

    • 요청

    • 필요시 대기

    • 임계구역 처리

    • 빠져나감





임계 구역 해결 조건

임계 구역 문제는 3가지 조건 충족 시 해결할 수 있다.

  • Mutual exclusion(상호 배타)

    • 오직 한 쓰레드만 진입

  • Progress(진행)

    • 진입 결정은 유한 시간 내

    • 어느 프로세스가 들어갈 것인지 선택


  • Bounded Waiting(유한 대기)

    • 어느 쓰레드라도 유한 시간 내

    • 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한





4. 동기화 도구


프로세스 및 쓰레드 동기화에서 해결해야 할 이슈
임계 구역 문제 해결, 프로세스 실행 순서 제어

  • 동기화 도구(Synchronization Tools)

    • Semaphores

    • Monitors

    • Misc.





5. Semaphores


세마포는 동기화 문제 해결을 위한 소프트웨어 도구이다.
정수형 변수 + 두 개의 동작 (P, V) 구조를 가진다.

  • Proberen(test, P): acquire()

  • Verhogen(increment, V): release()



// acquire: 프로세스 및 스레드 블락(큐에 추가, 잠듦)
void acquire() {
	value--;
    if(value < 0) {
    	add this process/thread to list;
        block;
    }
}

// release: 블락된 프로세스 및 스레드 진행(큐에서 제거, 깨어남)
void release() {
	value++;
    if(value <= 0) {
    	remove a process P from list;
        wakeup;
    }
}





(1) Mutual exclusion

세마포의 일반적인 사용(1): 상호 배타 목적

  • 초기값 지정: sem.value = 1;

  • 구조

sem.acquire();
critical-section
sem.release();





(2) Ordering

세마포의 일반적인 사용(2): 프로세스 실행 순서 제어

  • 초기값 지정: sem.value = 0;

  • 구조

Process 1Process 2
sem.acquire();
Statement 1Statement 2
sem.release();





6. 전통적 동기화 예제


  • Producer and Consumer Problem

    • 생산자-소비자 문제

    • 유한 버퍼 문제(Bounded Buffer Problem)


  • Readers-Writers Problem

    • 공유 데이터베이스 접근


  • Dining Philosopher Problem

    • 식사하는 철학자 문제





Producer-Consumer Problem

  • 생산자-소비자 문제

    • 생산자가 데이터를 생산하면 소비자가 소비

    • 예: 컴파일러-어셈블러, 파일 서버-클라이언트, 웹 서버-웹 클라이언트



  • Bounded Buffer

    • 생산된 데이터는 버퍼에 저장

    • 현실 시스템에서 버퍼 크기는 유한함

    • 문제: 생산자는 버퍼가 가득 차면 더이상 넣을 수 없고, 소비자는 버퍼가 비면 소비할 수 없음



  • 문제: 해당 문제가 발생하는 이유는 임계구역(공통 변수 업데이트 구간)에 대한 동시 진입으로 볼 수 있다.

  • 해결 방법

    • 상호 배타: 임계 구역에 대한 동시 접근 방지

    • 세마포를 사용한 상호 배타 (mutual exclusion)



  • Busy-wait

    • 생산자는 버퍼가 가득 차면 기다려야하고, 소비자는 버퍼가 비면 기다려야한다 → CPU를 비효율적으로 사용

    • 세마포를 사용하여 busy-wait를 회피할 수 있음


// 생산자: empty.acquire() - of permit=BUF_SIZE
// 소비자: full.acquire() - of permit=0


// 생산자
empty.acquire();
PRODUCE;
full.realese();


// 소비자
full.acquire();
PRODUCE;
empty.realese();





Readers-Writers Problem

공통 데이터 베이스에서 Reader는 데이터를 읽고 수정하지 못하며, writer는 데이터를 읽고 수정이 가능하다.

  • 한 번에 한 개의 프로세스만 접근 가능한데(상호배타), 이는 비효율적이다.

  • 효율성 제고: reader가 들어가면 내용이 바뀌지 않기 때문에 reader-reader 접근을 허용해야한다.

  • 변종

    • The first R/W problem (readers-preference)

    • The second R/W problem (writers-preference)

    • The Third R/W problem





Dining Philosopher Problem

식사하는 철학자 문제는 5명의 철학자와 5개의 젓가락이 있고 철학자는 생각-식사 행위를 반복한다.

식사를 하기 위해서는 2개의 젓가락이 필요하다.

왼쪽 젓가락을 얻은 후 오른쪽 젓가락을 얻고자 한다고 가정한다.

이 때 발생할 수 있는 문제는 무엇일까?

만약 모든 철학자가 모두 식사를 하고자 하고, 왼쪽 젓가락을 잡는다면 모든 철학자가 식사를 할 수 없다.

즉, 교착 상태(deadlock)가 발생한다.
이와 같이 동기화를 하다보면 교착 상태가 발생할 수 있다.





7. 교착 상태(Deadlocks)


프로세스는 실행을 위해 여러 자원이 필요하다.

만약 어떠한 자원은 가지고 다른 자원을 가지지 못했을 때 대기 상태가 되는데, 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태가 발생할 가능성이 있다.





필요 조건(Necessary Conditions)

필요 조건이 모두 만족되어야 교착 상태가 일어날수도 있다 (무조건 발생 X)

  • Mutual exclusion (상호 배타)

  • Hold and wait (보유 및 대기)

  • No Preemption (비선점) → 강제로 빼앗을 수 없는 것

  • Circular wait (환형 대기) → 대기 상태가 사이클을 이룬다.





자원(Resources)

  • 동일 형식 자원이 여러개 있을 수 있음

  • 요청(request) - 사용(use) - 반납(release) 순서

  • 자원 할당도(Resource Allocation Graph)

    • 자원과 프로세스의 할당 관계, 대기 상황을 나타냄

    • 지원은 사각형, 프로세스는 원, 할당은 화살표로 나타낸다.





8. 참고 자료


운영체제 강의

[운영체제(OS)] 8. 프로세스 동기화 1

동기화를 위한 도구 - Semaphore(Mutual exclusive, Ordering)

세마포어

프로세스 동기화(뮤텍스,세마포어,임계구역)

0개의 댓글