운영체제 - 반효경 6강

Race Condition

• Storage를 공유하는 CPU process들이 있는 경우 Race condition(경쟁 상태)의 가능성이 있다

• Race condition이란 하나의 data를 여러 곳에서 접근하는 상황을 의미한다

• 예)

  1. kernel 수행 중 인터럽트 발생 시

     

  2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

     

  3. Multiprocessor에서 shared memory 내의 kernel data

     

Process Synchronization 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생 시킴
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요
• race condition을 막기 위해서는 협력 프로세스는 synchronize 되어야 함

The Critical-Section Problem

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical-section이 존재
• 문제 : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함

프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호 배제) : 프로세스가 critical saction에 들어가 있으면 다른 모든 프로세스는 그들의 critical section에 들어가면 안됨
• Progress : critical section에 아무도 없을 때 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해줘야 됨
• Bounded Waiting : 특정 프로세스가 critical section에 들어가고자 할 때 starvation이 일어나서는 안됨

Initial Attempts to Solve Problem

• 프로세스들의 일반적인 구조

  

• 프로세스들은 수행의 동기화(sychronize)를 위해 몇몇 변수를 공유할 수 있음 -> synchronization variable

Algorithm 1

• turn 이라는 공유 변수를 가지며 while 문을 통해 계속 critical section에 들어갈 수 있는지 확인하는 알고리즘
• Progress 만족 X

Algorithm 2

• flag라는 공유 변수 사용
• critical section에 진입하고자 할 때 flag를 true로 만든 뒤 다른 flag들을 확인 -> flag가 모두 false면 진입
• Progress 만족 X

Algorithm 3

• Peterson’s Algorithm이라고 불림
• turn과 flag 둘 다 사용
• flag를 true로 만들고, turn을 다른 프로세스의 턴으로 설정함
• 그 뒤 상대 프로세스의 flag가 true이고 turn이 상대방 턴일 때만 while문을 반복 -> 하나라도 만족 못하면 critical section에 진입
• 위의 3가지 조건을 모두 만족. 하지만 문제가 있음
• Busy Waiting(=스핀락) : while문을 돌면서 계속해서 CPU와 memory를 쓰면서 wait을 함

Semaphores

• 추상 자료형

• Semaphore (S)

• 정수 변수를 가짐(자원의 갯수)

• 두 가지 atomic 연산에 의해서만 접근 가능

  

• P = 공유 데이터를 획득하는 과정

• V = 획득한 데이터를 반납하는 과정

• 적용 모습

  

• 위처럼 구현된 세마포는 스핀락으로 구현되어 있다는 문제가 있다 -> Block & Wakeup 방식으로 구현 가능(=sleep lock)

Block/Wakeup Implementation

• semaphore를 뜻하는 value와 프로세스들이 기다리는 queue를 변수로 가진다

• 실제 정의된 모습

  

  • 여기서 S는 실제 자원을 뜻하기 보단 value가 음수일 때 = 누군가 blocked 되어 있음과 같은 상황을 의미

• Busy-wait VS Block/Wakeup

  • 보통 Block/Wakeup을 사용
  • 하지만 Block/Wakeup 방식도 오버헤드가 있음 -> Block에서 wakeup 하는 등
  • 그렇기 때문에 critical section의 길이가 길면 Block/Wakeup, 짧으면 Busy-wait를 사용

Two Types of Semaphores

• Counting semaphore
  • 0 이상인 임의의 정수 값을 가짐
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 or 1 값만 가지는 semaphore
  • 주로 mutual exclusion(mutex) lock/unlock에 사용

Deadlock and Starvation

• semaphore를 사용할 때 2가지 문제가 발생할 수 있다.
• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• Starvation : indefinite blocking, 큐에서 자원을 얻지 못한 상태로 계속 다른 프로세스들만 자원을 가져다 쓰는 상황

Bounded-Buffer Problem

• Producer-Consumer Problem이라 불림

• mutual exclusion : Producer나 Consumer가 여럿일 때 empty 버퍼나 full 버퍼에 둘 이상이 동시에 접근하는 문제 -> lock을 걸어서 해결

• resource count(Bounded(유한)한 버퍼이기 때문에 발생하는 문제) : 모든 버퍼가 full 버퍼가 됨 -> 또 다시 Producer가 접근 -> 모든 buffer가 full이기 때문에 기다려야 함 -> 가용 자원을 카운팅해줘야 함

• 실제 코드 :

  

Readers-Writers Problem

• 한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨. read는 동시에 해도 됨

• writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 reader들에게 DB 접근 허용

-> writer는 대기 중인 reader가 하나도 없을 때 DB 접근이 허용

-> 일단 writer가 DB에 접근 중이면 reader들은 접근이 금지됨

-> writer가 DB에서 빠져나가야만 reader의 접근이 허용

• 공유 데이터 : DB, readcount(DB에 접근 중인 reader의 수)

• 동기화 변수 : mutex(readcount 접근 용도), db(db에 관한 lock mutex)

• 코드

  

  • 잘 살펴볼 부분은 Reader 부분
  • 최초에 들어온 reader라면(readcount=1) 일 때는 read를 위한 세마포를 걸어줌. 그렇지 않다면 이미 read를 위한 lock이 걸려있기 때문에 통과
  • read를 진행하다 readcount=0이 되면 마지막 일기 작업이므로 락을 해제시킴

  • 다음 작업 실행(write)

  • 이 코드는 계속해서 read 작업이 들어오면 writer가 starvation을 겪을 수 있는 문제가 있음(오래 기다린 writer에게 우선순위 주는 등으로 해결 가능)

Dining-Philosophers Problem

• 젓가락 두개를 잡아야 식사를 할 수 있다.
• 위 코드의 문제점
  • Deadlock 가능성 있음 : 모든 철학자가 동시에 왼쪽 젓가락을 잡은 경우
• 해결 방안
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 함
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 함
  • 비대칭 : 짝수는 왼쪽 젓가락부터, 홀수는 오른쪽 젓가락부터

Monitor

• Semaphore의 문제점
  • 코딩하기 힘듬
  • 정확성의 입증이 어려움
  • 자발적 협력이 필요함
  • 한번의 실수가 모든 시스템의 치명적 영향
• 그렇기 때문에 프로그래밍 언어 차원에서 동기화를 위한 Monitor를 제공함

• 공유 데이터를 접근할 수 있는 프로시저를 통해서만 접근 가능하도록 하는 것

• Monitor의 프로시저들은 동시에 접근할 수 없도록 내부적으로 구현되어있음(프로그래머가 lock을 걸 필요가 없다)

• 만약, 하나의 프로세스가 모니터 내부의 코드를 실행하다 CPU를 빼앗긴다해도 그 프로세스는 모니터 내부 코드를 실행한다고 간주 -> 만약 다른 프로세스가 Monitor에 접근하면 entry queue에서 대기하게 됨

• 공유 데이터에 접근하기 위해 기다리는 프로세스들을 위한 condition variable을 사용 -> 어떠한 조건들이 만족이 안되어서 대기해야하는 경우 해당 조건 condition variable queue에 들어가 대기함

• condition variable은 wait와 signal 연산에 의해서만 접근이 가능

• Bounded-Buffer Promblem with Monitor

  

  • 기존의 lock 방식 대신 wait와 signal을 통해 공유 데이터 관리

출처)

[운영체제 - 이화여자대학교

KOCW 공개 강의](http://www.kocw.net/home/cview.do?cid=3646706b4347ef09)