[OS] Semaphore

Posted on | 0 comments

프로세스 동기화

세마포어

  • 일반적인 사용
    • 상호배타
    • Ordering

상호배타

세마포어를 사용해서 상호배타적인 프로세스 동기화를 하도록 한다.

임계구역(Critical Section)에 허용하는 숫자를 최대 1개로 정하도록 한다. 여기서 숫자 1을 세마포어 디폴트 정수값으로 정한다.

세마포어의 acquire() 메소드를 쓰는 스레드가 있으면, 정수값을 1씩 감소시킨다.

특정 스레드가 acquire()를 했을 때, 만약 세마포어의 정수값이 마이너스가 되면, 세마포어의 특정 큐에 들어가게 되어 Block 상태가 된다. 즉, 해당 스레드가 하려는 일을 잠시 멈춰두게끔한다.

그 전에 세마포어의 정수값을 감소시켜 0을 만든 프로세스(스레드)가 해당 임계구역(C.S)에서 빠져나올때, 세마포어의 release()를 사용하여 세마포어의 정수값을 다시 증가시킨다.

세마포어의 정수값이 다시 1이므로 Block 상태에 있던 스레드가 빠져나오면서 하려던 일을 마저 할 수 있도록 한다.

Ordering (우선순서)

특정 프로세스가 우선적으로 이행되어야할 때, 다른 프로세스가 먼저 실행되게 되면 세마포어의 acquire() 메소드를 넣어서 Block 상태를 만들어 놓고, 특정 프로세스를 먼저 실행되도록 만든다.

이 경우, 세마포어의 디폴트 값을 0으로 두고, 우선적으로 실행되어야하는 프로세스를 제외한 나머지 프로세스에 세마포어의 acquire()를 쓰도록 로직을 구성한다.

그렇게 우선적으로 실행되어야하는 프로세스가 실행된 후에는, 세마포어의 release()를 실행되도록하여 세마포어의 0인 값을 1로 올리도록한다.

그러면 다음 프로세스가 실행될 수 있게 된다.

교차로 이행하기

세마포어를 디폴트 정수값으로 0을 두 개 둔다. 서로의 프로세스를 진행할 때, 다른 세마포어를 acquire()하고, 프로세스의 할 일이 끝나면 해당 세마포어를 release()를 해주는 것이다.

어떤 프로세스(스레드)가 먼저 실행되어야할 경우엔 다른 프로세스를 세마포어에 Block 시키도록 해당 세마포어의 acquire()를 쓰면 될 것이다.

전통적 동기화 예제

Producer Consumer

  • 생산자-소비자

생산자가 데이터를 생산하면, 소비자는 소비를 한다.

운영체제 내에서 기계언어를 생성해내면, 생산한 후 버퍼에 담아놓는다. 그러면 컨슈머(컴파일러, 어셈블리)가 해당 버퍼에서 빼와서 소비를 해놓는 식이다.

ex> 컴파일러 > 어셈블리 > 기계언어

ex> 파일 버서 > 클라이언트, 웹 서버 > 웹 클라이언트

  • 유한버퍼

생산된 데이터는 버퍼에 일단 저장한다! 버퍼가 가득 차면, 생산자는 버퍼에 넣는 것을 중지하여야한다.(버퍼의 크기는 유한적이다.) 소비자는 버퍼가 비어있으면, 뺄 수 없다.

버퍼에는, buf 리스트, size, count, in, out이 있다.

  • buf[] : buf는 정수 배열(int[])로 만들어진다.
  • size : 배열 전체 크기
  • count : 초기값 0, 생산자가 버퍼에 넣고, 소비자가 빼는 등의 순간순간 남은 버퍼 수
  • in : 데이터를 넣는 위치 값 (처음부터 채워지는 순서)
  • out : 데이터는 빼는 위치 값

insert(), remove() 함수가 버퍼에 존재한다.

insert() : 버퍼가 찼는지 확인하고, size가 될 때까지(버퍼가 가득 찰 때까지) 지속적으로 데이터를 넣는다.(in++, count++)

remover() : 버퍼가 비어있는지 확인하고. size가 0이 될 때까지(버퍼가 빌 때까지) 지속적으로 데이터를 빼낸다.(out++, count–)

  • 잘못된 결과
    • 실행 불가
    • count = 0 (생산된 항목 숫자 != 소비된 항목 숫자)
    • 최종적으로 버퍼 내에는 0개의 항목이 있어야한다.

결과가 잘못 나오는 이유

  1. common variable인 count, buf[]에 대한 동시 업데이트
  2. Critical Section(임계구역, 공통 변수 업데이트 구간)에 대한 동시 진입 문제

해결책

  1. 임계구역에 대한 동시 접근 방지(상호배타)
  2. 세마포어를 사용한 상호배타 (Mutual exclusion)

  • Busy wait

  • 생산자는 버터가 가득차면 기다려야 한다.
  • 소비자는 버터가 비어있으면 기다려야 한다.

CPU가 생산자나 소비자가 버퍼가 가득찼거나 비어있으면 멍을 때리게 된다. 그래서 세마포어를 사용한 busy wait 회피를 해주어야 한다.

  • 생산자는 버퍼가 가득차면(count=maxIndex 값으로 세마포어의 디폴트 정수값 설정) 세마포어의 acquire()를 이용하여 세마포어의 큐에 가두게 된다. 그리고 소비자의 세마포어의 큐에서 나올 수 있도록 release() 해준다. (empty.acquire(), full.release())
  • 소비자는 버퍼가 비어있으면(count = 0으로 세마포어의 디폴트 정수값 설정) 세마포어의 acquire()를 이용하여 세마포어의 큐에 가두게 된다. 그리고 생산자의 세마포어 큐에서 나올 수 있도록 release() 해준다. (full.acquire(), empty.release())
  • 각 두 세마포어는 다른 세마포어가 되어야할 것이다.(디폴트 정수값이 다르자나??하는 역할도 다르고!)

Readers Writers

데이터베이스에 접근할 때! (공통적으로 DB를 사용하게 된다.)

  • Readers
  • Writers
  • 데이터베이스 자체가 임계구역이 된다. -> 상호배타적으로 하면 비효율적임!

효율성

  • Readers가 들어오면 데이터를 읽기만 하기 때문에, Readers에 한해서 상관없이 접근 가능하도록 허용한다.
  • Writers의 경우에만 생각해보면 된다.

Readers가 들어왔는데, Writers가 들어오면 Block되도록 한다. 반대로 Writers가 들어왔는데 Readers가 들어와도 Block 되도록!!

하지만 Readers가 들어왔을 때 다른 Readers로 들어오면, 그것은 허용되게끔 한다.

Dining Philosopher

식사하는 철학자 문제

  • 5명의 철학자가 5개의 젓가락을 가지고, 생각 -> 식사 -> 생각 -> 식사를 반복한다.

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

  • 프로그래밍
    • 5명의 철학자 index => 0 - 4
    • 5개의 젓가락 index => 0 - 4
    • 젓가락 세마포어(default index = 5)
    • 철학자 세마포어(default index = 5)
  • 잘못된 결과 (starvation)

모든 철학자가 식사를 하지 못해서 굶어 죽는다. 철학자 5명이 식사를 하려고 왼쪽 젓가락을 동시에 들었을 때, 교착 상태가 발생한다. (deadlock)

운영체제에서 제일 중요한 관리는 프로세스 관리인데, 그 중에서 CPU 스케쥴링과 프로세스 동기화이다. 프로세스 동기화에서는 상호배타적인 문제가 있고, Ordering의 문제, busy-wait 등이 있는데, 여기서 데드락의 문제도 생긴다.

Deadlock

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

  • CPU, 메모리, 파일, 프린터 등의 자원
  • 특정 자원은 갖고 있지만, 다른 자원을 가지지 못할 때(다른 프로세스가 사용 중) 대기를 해야한다.
  • 여기서 다른 프로세스도 같은 상황일 때, 데드락이 발생한다.

교착상태(데드락) 필요조건

아래 조건들이 모두 다 만족해야 일어날 수 있다.

  • Mutual Exclusion (상호배타) : 어느 한쪽이 사용하고 있어서 다른 쪽이 대기하고 있는 경우
  • Hold and Wait (보유 및 대기) : 어떤 자원을 갖고 있으면서 다른 것을 기다리고 있는 경우
  • No Preemption (비선점) : 우선적으로 자원을 가져가는 경우가 아닌, 순서대로 가져갈 수 있는 경우
  • Circular wait (환형대기) : 모든 프로세스가 원을 이룬 것처럼 자원을 가져가고, 다른 쪽의 자원을 기다리고 있는 경우

자원

  • 동일 자원

동일 형식의 자원이 여러 개 있을 수 있다. (CPU 2개, 프린터 3개)

  • 자원의 사용

프로세스가 OS에 요청 -> 사용 -> 반납

  • 자원 할당도 (Resource Allocation Graph)

  • 어떤 자원을 어떤 프로세스에게 할당하였는가

  • 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가

  • 교착상태 방지

식사하는 철학자 -> 교착상태 방지하려면??

  • 환형대기 조건이 충족되지 않게 하기 : 짝수번 철학자는 왼쪽들고, 오른쪽 젓가락을 들게끔하고, 홀수번은 오른쪽 먼저 들고, 왼쪽 젓가락을 들게끔하면 환형대기 조건이 충족되지 않는다.