추상 자료형
- 자료구조
- object와 operation으로 구성됨
- 정수 추상 자료형: 정수, 숫자들이 있고 그 숫자에 대해서 정의된 연산이 어떤 것이 있는가? 덧셈, 뺄셈, 곱셈 같은 것이 정의되는 것처럼.
- 논리적으로 정의를 하는거지. 컴퓨터에서 실제로 그러한 자료형이 어떻게 구현되는거하고 별개의 자료형을 말한다.
semaphores도 일종의추상자료형임
Semaphore S
Semaphore의 변수 S
- 정수 값을 가짐.
- 구체적인 구현을 나타내는게 아니고, 추상적으로 연산 자체를 정의하는 것.(atomic연산)
- semephore라는 변수에 대해서 정의되는 operation이 필요함.
- 2가지 정의됨
- 1) P연산
semaphore 변수 획득하는 과정 (공유 데이터를 획득하는 과정)
- 자원이 0개일 때는 기다리고,
- 자원이 1개 이상일 땐 S-1 한다.
- 자원이 없을 때busy-wait문제 생김 : S가 없을 때 계속 while 문에서 기다리다가 cpu 시간 다 쓰고 반납
- 2) V연산
공유 자원 다 쓰고 반납하는 과정
- 1) P연산
semaphore 왜 사용?
- lock을 걸고 , 풀고 하는 것도 semaphore을 이용해서 간단하게 프로그래머한테 제공
- 공유 자원을 획득하고 반납하는 것을 semaphore가 처리
semaphore S
- 자원의 개수라고 생각
- 만약, S가 5라면 자원이 5개. P연산 한번 하면 그 자원을 하나 가져가는 것. 그럼 남은 자원은 4개가 됨. 또 다른 provess가 P연산을 하면 자원이 3개가 됨. semaphore 변수 S가 5라면, P연산을 다섯번해서 다섯개의 process가 동시에 자원을 가져갈 수 있는 것. 반대로, 자원의 개수가 4개인 상태에서 V연산을 하면 자원이 5가 됨.
Critical Section of Processes
critical section에다가 semaphore를 사용하게 되면,
semaphore mutex 변수를 1로 놓고,
- critical section에 들어가야 할 때 P연산
- critical section에서 빠져나올 땐 V연산
=> critical section 문제 자연스럽게 해결
프로그래머는 semaphore가 지원이 된다면, P연산과 V연산만 해주면 됨.
P랑 V를 어떻게 구현할지는 그때그때 시스템 내에서 생각해야할 몫임/
즉, 프로그래머가 연산을 직접 짜는게 아니라 ,
추상 자료형 형태로 연산이 제공되면 / 프로그래머는 semaphore를 통해서 프로그래밍을 하면 훨씬 간단함 !!
busy-wait = spin lock
- 계속 회전을 하면서 lock을 얻기를 기다리는 것.
Block & Wakeup = sleep lock - lock을 못 얻으면 그 process가 쓸데없이 cpu를 쓰는게 아니라 blocked 상태, 잠들어버리게 한다.
프로세스의 상태 (Block & Wakeup 설명)
어떤 프로세스가 cpu를 사용하다가 i/o같이 시간이 오래 걸리는 작업 하러 가면 process 상태가 blocked된다. 그래서 cpu를 얻을 수 있는 권한 자체가 없어진다. i/o작업이 끝나면 cpu의 ready queue로 돌아올 수 있음.
마찬가지로,
공유데이터를 쓰는 것도 같다.
누군가가 공유데이터를 쓰고 있으면 내 차례가 안오니까 쓸데없이 while문을 돌면서 기다리는 방식이 아니라 그 프로세스 자체를 blocked 시켜서 cpu를 반납하고 잠들어있다가. 공유 데이터 쓰고 있던 프로세스가 공유 데이터 내놓으면 그때 깨어나서 ready queue에 들어와서 cpu를 얻어서 공유 데이터 얻으면 된다.
Block / Wake Implementation
Implementation
Which is better?
- 보통은 block/wakeup 쓰는게 더 효율적
block & wakeup 도 overhead가 있다. - 어떤 프로세스의 상태를 ready에서 잠드는 상태로 바꿔야 함.
- 공유 data의 여분이 생기면 blocked 상태에 있는걸, ready 상태로 바꿔줘야함.
critical section의 길이가 매우 짧은 경우에는, - block/wakeup 말고, busy-wait을 해도 그렇게 overhead가 생기지 않음.
Two Types of Semaphore
- Counting semaphore
- 자원의 개수가 여러개 있어서 데이터가 여분이 있으면 가져다 쓰는 것
- 여분의 자원을 세는 용도
- Binary semaphore
Deadlock and Starvation
semaphore는 쓸 때 주의해야함.
원치않은 문제가 생길 수 있음.
예) semaphore S,Q가 있음
가정) 두개 다 획득해야만 일을 할 수 있는 환경
Deadlock 해결 방법
자원을 얻는 순서를 이런식으로 설정하면 됨.
Dining-Philosophers Problem
starvation
- 한사람은 오른쪽 젓가락 못얻어서 못먹고 있다가, 오른쪽 생겨서 먹을라고 하는데 왼쪽 사람이 왼쪽 젓가락 가져가버려
deadlock - 모든 사람이 왼쪽 젓가락을 동시에 잡아.
- 영원히 먹지 못함.
