데이터의 접근
-
데이터가 저장되어있는 위치에서 읽어와서
-
연산을 해서 연산결과를 원래 위치에 저장
-
연산을 실행하는 주체 CPU
-
데이터를 저장하고 있는 곳 메모리
#CPU가 하나밖에 없는 시스템은 문제가 발생안한다.
Race Condition
OS에서 Race condition은 언제 발생하는가?
- kernel 수행 중 인터럽트 발생 시
- Process가 system call하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- Multiprocessor에서 shared memory 내의 kernel data
OS에서의 race condition(1/3)
OS에서의 race condition(2/3)
OS에서의 race condition(3/3)
Process Synchronization 문제
-
공유 데이터 (shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생 시킬 수 있다.
-
일관성(consistency)유지를 위해서는 협력 프로세스 (cooperating process)간의 실행 순서 (orderly execution)를 정해주는 메커니즘 필요
-
Race condition
#여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
#데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐 -
race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.
Synchronization Hardware
critical section에 들어갈 때 락을 걸고 나올 때 락을 푸는 간결한 방법
The Critical-Section Problem
-
n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
-
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
-
Problem
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 cirtical section에 들어갈 수 없어야 한다.
Initial Attempts to Solve Problem
-
두 개의 프로세스가 있다고 가정 P0, P1
-
프로세스들의 일반적인 구조
-
프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다. -> synchronization variable
프로그램적 해결법의 충족 조건
-
Mutual Exclusion(상호 배제)
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
*둘이 동시에 들어가는걸 막음 -
Progress(진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
*둘이 동시에 못 들어가게 막으려다 보니 아무도 안들어가는걸 막음 -
Bounded Waiting
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한께가 있어야 한다.
*기다리는 시간이 유한해야함
*가정
- 모든 프로세스의 수행속도는 0보다 크다.
- 프로세스들 간의 상대적인 수행속도는 가정하지 않는다.
Semaphores
- Semaphore S
- integer variable
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능![]
추상자료형 : 논리적으로 정의 하는거지 실제 컴퓨터에서 어떻게 구현되는지와는 별개의 자료형
Critical Section of n Process
busy-wait는 효율적이지 못함
Block & WakeUp 방식의 구현 
- busy-wain vs Block/wakeup
Block/wakeup overhead vs Critical section 길이
- Critical section의 길이가 긴 경우 Block/Wakeup이 적당
- Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/wakeup 방식이 더 좋음
Two Types of Semaphores
-
counting semaphore
- 도메인이 0 이상인 임의의 정수 값
- 주로 resource counting에 사용 -
Binary semaphore(=mutex)
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용
Deadlock and Starvation
-
Deadlock
- 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 형상 -
S와Q가 1로 초기화된 semaphore라 하자
-
Starvation
- indefinite blocking: 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
Dining-Philosophers Problem(식사하는 철학자)
Bounded-Buffer Problem(Producer-Consumer Problem)
Synchronization variables
semaphore full=0, empty = n, mutex = 1
- synchronization과 관련해서 발생할 수 있는 문제
- 공유 버퍼이기 때문이기 때문에 생산자가 둘이 동시에 도착해서 생산자 둘이 동시에 한 버퍼에 데이터를 넣으면 문제가 발생함
- 버퍼가 유한하기 때문에 생기는 문제, 생산자들이 한꺼번에 도착해서 버퍼가 다 찬 생황에서 소비자가 안오고 생산자만 오는 경우 데이터를 넣을 빈 버퍼가 없기 때문, 소비자가 올 때까지 기다려야만 한다. 생산자의 입장에서 빈버퍼가 카운팅해야 할 자원이다. 빈버퍼가 없이 전부다 차버리면 비어있는 버퍼가 0일 때 자원의 여분이 생길 때 까지 기다려야함
- 소비자 입장에서는 꺼내갈게 없을 수 있다. 내용이 들어있는 버퍼가 자원이다.
Readers-Writers Problem
-
한 process 가 DB에 write 중 일 때 다른 Process가 접근하면 안됨
-
read는 동시에 여럿이 해도 됨
-
solution
- Writer가 DB에 접근허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
- Writer는 대기 중인 Reader가 하나도 없을 때 DB접근이 허용된다.
- Writer는 대기 중인 Reader가 하나도 없을 때 DB접근이 허용된다.
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다. -
Shared data
DB자체
readcount = 현재 DB에 접근 중인 Reader의 수 -
Synchronization variables
*mutex = 공유 변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용
- DB = Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
여러 프로세스가 동시에 사용하면 안되는 구역(Critical section/임계구역)
공유자원을 서로 사용하기 위해 경쟁하는 것을 경쟁조건이라고 한다.
임계구역 문제를 해결하기 위해서는 (상호 배제/Mutual Exclusion)메커니즘이 필요하다.
상호 배제의 요구사항
1. 임계영역엔 동시에 하나의 프로세스만 접근한다.
2. 여러 요청에도 하나의 프로세스의 접근만 허용한다.
3. 임계구역에 들어간 프로세스는 빠르게 나와야한다.
세마포어의 단점을 해결한 방법 모니터
모니터는 운영체제가 아니라 프로그래밍 언어 차원에서 지원하는 방법이다.붙은
synchronized키워드가 붙은 함수는 프로세스중에서 하나만 사용해야한다.
