해당 게시글은 운영체제 스터디를 위해 반효경 교수님 운영체제 강의를 보고 기록한 게시물입니다. 틀린 정보가 있다면 언제든 지적해주세요🙏🏻

병행제어

원자적으로 수행이 안되었을때의 문제는 하드웨어적인 방법으로 해결이 가능하다.
프로그램 입장에서는 Semaphore와 모니터의 방법이 그것이다.

Semaphore

• 일종의 추상자료형
• 아래의 두가지 연산에 의해서 접근 가능 한데 P와 V.
• Deadlock: 자원을 얻는 순서를 조정해서 해결할 수 있다.
• 자원이 두 개 있어서 둘 다 얻어야지 작업을 할 수 있을때 사용한다.
  예) s를 먼저 얻어야 작업이 가능하다.
• 문제: Starvation

동기화와 관련된 전통적인 문제

1. 생산자 - 소비자 문제

• 버퍼가 유한하기 때문에 자원의 갯수를 세는 방법을 사용한다. -> 세마포어가 적합.
• 생산자 프로세서는 빈 버퍼가 생길 때 까지 기다리고 공유데이터에 락을 걸어서 데이터 조작한다. 데이터 조작이 끝난 후에 락을 푼다.
  

2. Readers-writers problem

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨. 이 문제는 DB에 락을 걸면 해결 가능함.
• 하지만 Read는 동시에 여럿이 해도 되기 때문에 Readcount라는 변수를 줘서 락이 걸려있어도 읽을 수 있게함.
  

3. Dining-philosophers problem
   

• 젓가락은 공유데이터 두명이서 동시에 밥을 먹을 순 없다.
• 모두가 왼쪽 젓가락을 들면 데드락이 발생한다.
• 해결방안
  1. 4명의 철학자만 테이블에 동시에 앉게 한다
  2. 젓가락을 두개 모두 집을 수 있을때만 젓가락을 집을 수 있게 한다
  3. 비대칭. 짝수 철학자는 왼쪽 젓가락부터 집도록 한다.
     

Monitor

• 세마포어의 문제점: 코딩하기 힘들다, 정확성의 입증이 힘들다, 자발적 협력이 필요하다, 한번의 실수가 모든 시스템에 치명적 영향을 미칠 수 있다.
• 공유데이터에 대해서 락을 걸 필요없다.
• Condition Variable: 자원의 여분이 없을때는 blocked해야 하는데 (== queue에 넣어서 기다리게 해야 하는데) 이 때 queue의 역할을 함.

교착상태(Deadlock)

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태.
• 자원(Resource)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • 예: I/O Device, CPU cycle, Memory space, Semaphore 등
  • 프로세스가 자원을 사용하는 절차
    request -> allocate-> use -> release
• 자원을 동시충족 할 수 없을 때 deadlock이 발생한다.
  

Deadlock의 발생조건 4가지

1. Mutual exclusion: 매 순간 하나의 process만이 자원을 사용할 수 있음.
2. No preemption(): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음.
3. Hold and wait: 자원을 가진 프로세스가 다른 자원을 기다릴때 보유 자원을 놓지 않고 계속 가지고 있음.
4. Circular wait: 자원을 기다리는 프로세스간에 사이클이 형성 되어야 함.
   -> 하지만 Cycle이 있다고 해서 꼭 데드락이 아니다. 자원이 여러개라면 그 자원들을 가지고 Cycle을 돌 수 있기 때문에.
   

Deadlock의 처리 방법

들어가기 전에 1번과 2번은 Deadlock을 방지하는 방법이고 나머지 두 가지는 방관하는 방법이다.

1. Deadlock prevention

• 가장 강력한 방법.
• Mutual Exclution: 공유해서는 안되는 자원의 경우 반드시 성립해야 함

2. Hold and wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법이 있다. (해당 방법은 자원이 낭비 될 수 있는 가능성이 있다.)
  다른 방법은 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법이 있다.

3. No preemption

• 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된
  CPU나 메모리는 빼앗을 수 있는 작업이다. 그래서 이 방법은 state를 쉽게 save하고 restore를 할 수 있는 자원에서 주로 사용한다.

4. Circular wait

• 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당하는 방법.

• 해당 방법은 데드락의 조건을 원천 봉쇄 할 수 있지만 비효율 적인 면이 있다.

  1. Utilization 저하, Throughput 감소, Starvation 문제
  2. Deadlock Avoidance
     • 어떤 추가 적인 정보를 이용해서 데드락을 막는 방법
     • 추가적인 정보? 프로세스마다 자원을 얼마나 쓸건지의 정보가 있다고 가정한다.
     • 그 정보를 이용.
  3. Deadlock Detection and Recovery
  4. Deadlock Ignorance