동기화
다중 프로그래밍
- 다중 프로그래밍 시스템은 여러 개의 프로세스들이 존재
- 프로세스들은 동시에 서로 독립적으로 동작한다.
- 공유 자원에 접근할 때 문제가 된다
- 동기화는 서로 대화하는 것이다.
병행 수행중인 비동기적인 프로세스들이 공유 자원에 동시에 접근할 때 문제가 발생한다.
공유데이터
- 여러 프로세스들이 공유하는 데이터
임계 영역
- 공유 데이터를 접근하는 코드 영역
상호배제
- 둘이상의 프로세스가 동시에 임계영역에 진입하는 것을 막는 것
임계영역
- 기계어 명령은 한 기계어 명령의 실행 도중에는 인터럽트를 받지 않는다.
- 1번 2번 사이사이에 빼앗길 수 있다.
-> 결과가 수행순서에 따라 1이 될수도 2가 될수도 있다.(Race Condition)
상호배제
- 원하는 결과를 얻기 위해서는 상호배제를 해야한다.
- enterCS() 임계영역 들어갈 때, exitCS() 임계영역 벗어날 때
요구사항
- 상호배제: 임계영역에 프로세스가 있으면, 다른 프로세스 진입 금지
- 진행: 임계영역 안에 있는 프로세스 외에는 다른 프로세스가 진입하는 걸 방해 하면 안됨(안에 비었는데 다른 프로세스가 막는 경우)
- 한정대기: 프로세스의 cs진입은 유한시간 내에 허용되어야한다.(기아현상)
sw solutions
ver1
- 자기턴이면 실행하고 턴이 끝나면 넘긴다
진행조건 위배
경우1
- 0이 돌다가 죽어버리면 그 프로세스 때문에 다른 프로세스가 임계영역 접근 못함
경우2
- P0가 한번 다 돌고 P1이 아직 오고 있어서 임계영역에 다시 들어가려 할 때 턴이 바껴서 2번 연속 진입이 불가하다
ver2
- flag를 사용 임계영역 들어가기전 true로 들고 다 사용 후 false로 내린다
상호배제 위배
경우1
- P0가 들어가기전 잠시 정지 됐을 때 P1이 들어가고 깃발을 올리고 P0가 다시 진행 할 시 깃발을 올리고 임계영역 들어가게 되면서 임계영역 침범
ver3
- 깃발을 먼저 들고 들어간다
진행과, 한정대기 위배
경우1
- P0가 들어가려고 flag를 들고 멈췄을 때 P1도 들고 들어갈때 P0의 flag가 true이므로 계속 대기한다
Dekker's 알고리즘
- 이걸로 해결 turn과 flag사용
HW solution
TestAndSet명령어
- 한번에 수행된다.
TAS
- 초기 락은 false
- 처음 프로세스가 들어오면 TAS에 넣으면 lock을 true로 바뀌고 다른 프로세스가 들어오면 대기하다가 처음 들오온게 끝나면 lock을 false로 바뀐다
한정대기 위배
- 2개 이상이 들어 왔을 때 처음 1번이 끝나고 2번이 들어가고 또다시 1번이 들어가고 하면 3번이 계속 대기하게 된다.
Busywating문제 여전히 있음
(어떠한 공유자원에 대하여 두개 이상의 프로세스나 스레드가 그 이용 권한을 흭득하고자 하는 동기화 상황에 그 권한을 얻기 위한 과정에서 일어나는 현상)
OS solution
Spinlock
- 정수 변수 S 초기화, P(), V()연산으로만 접근 가능
- P()와 V()는 OS에서 지원해주어 쫓겨나지 않고 계속 시행된다.
- S는 물건의 개수 P는 물건을 꺼내는 것 V는 물건을 집어 넣는 것
- P() 물건이 0개 이상이면 빠져나와 -1하여 꺼낸다
- V() 물건을 +1를 한다.
- Pi가 처음에 active를 1로 물건이 있어 실행하다가 끝나면 반납한다. 이후 Pj는 물건이 생긴 것을 보고 실행한다
- 원자성 보장되기에 임계영역 문제가 발생하지 않는다.
문제점
- 단일 cpu일 경우에는 pj가 계속 도는 동안 끊지 못하기에 pi는 계속 대기
- 멀티일때만 cpu1은 pj cpu2는 pi여야한다
- busywating문제 해결 안됨
Semaphored
- busywaiting문제 해결
SpinLock과 차이점- 임의의 S변수 하나에 ready queue 하나가 할당 된다.
Binary Semaphore
- S가 0,1 두 종류의 값만 갖는 경우
- 상호배제나 프로세스 동기화의 목적으로 사용
Counting Semaphore
- S가 0이상의 정수값을 가질 수 있는 경우
p, v 연산
- 물건이 없을 때 기존 SpinLock은 while로 대기했지만 세마포는 Queue에 할당된 대기실에서 대기
- 나갈 때 Queue대기실에 기다리는 것이 있을 때 wakeup하고 나온다. 없을 경우 물건을 +1를 한다.
해결가능 문제
- 상호배제 문제
- 프로세스 동기화 문제
- 생산자-소비자 문제
- reader-writer문제
- dining philosopher problem(철학자들의 저녁식사)
상호배제 문제
- Queue에 대기하고 있다가 깨워준다
프로세스 동기화 문제
경우1
- pj가 진행하고 있다가 Queue가 없으면 반납하여 sync를 1로 반납 이후 pj진행
경우2
- pi가 pj 진행중인데 접근 했을 때 대기 Queue에 넣어놓고 pj가 끝나면 wakeup을 하여 queue를 가져온다
생산자 소비문제
-
buffer에 물건을 놓는동안 소비자가 가져가면 안된다. 동기화를 해야한다.
-
한명이 buffer에 물건을 놓고 있을 때 또 놓으려고 하면 안된다.
-
buffer에 한명만 접속해야한다.(cs임계영역 같은 것)
-
Pi는 consumed가 비었는가 소비자가 소비를 했나 확인 1이면 0으로 변경
-
Cj는 produced가 생산했는지 확인 안했으면 대기실 대기 이후 소비후 소비했다고 0로 변경
n버퍼일 경우
- 세마포 변수가 많다.
- mutex로 한번에 한명만 일하도록 한다.
- nrfull은 채워진 buffer의 수
- nrempty는 비어있는 buffer의 수
pi
- 공간은 환형큐 사용하므로 in <- (in+1) mod N으로 업데이트
- 나오면서 nurfull로 물건 수를 늘린다
- v(nrfull) 대기하고 있으면 wakeUp 없으면 +1
Reader-Writer문제
- 읽을때는 여러명 읽어도 되지만 writer은 한명만 써야한다.
- 읽을때 수정할 수 없도록 한다.
- Wj는 mutex로 한명만 사용할 수 있도록한다
- Ri는 여러명 읽을 수 있지만 사전작업으로 mutex로 한명만 작업한다
- nreaders=0일때 p(wmutex)로 읽을테니까 쓰지말라고 한다.
- 사후에 nreaders가 마지막이면 writer한테 사용할 수 있도록 푼다.
정리
- wakeUp순서는 비결정적이다. 기아현상 가능
Language-Level solution
Monitor
- 공유 데이터와 임계영역으 집합
- 한명만 들어올 수 있는 책방이라고 생각하고 데이터는 책 cs는 연산
signaler queue(신호제공자 큐)
- 모니터에 항상 하나의 신호제공자 큐가 존재
- 전화부스처럼 signal()명령을 실행한 프로세스가 임시 대기
Condition queue(조건 큐)
- 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기(대기실)
자원할당문제
- 자원을 반납하는 공간 대출하는 공간이 있다.
- condition queue는 책을 빌릴 수 있는지 대기실
- signaler queue는 전화부스처럼 대기실에 있는 걸 깨우는 역할
- 대출할 때 R이 자원이 있는지 확인 없으면 wait하고 있다면 false로 한다.
- 반납은 true로 바꾸아 반납하고 r.free에 있는 것을 하나 깨운다.
과정
- 책이 없으면 컨디션에 넣는다. 이후 반납을 하면 releaseR()에 pj가 들어가게 되고 네모 공간에 한명만 들어갈 수 있으며로 signaler queue에 pj를 잠시 넣고 pk를 가져온다.
- 남은일 있을 경우 다시 들어와 하고 나간다.
생산자-소비자 문제
- 크기가 N인 문제
출처 https://www.youtube.com/watch?v=33OqgesF-mM&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=15
안녕하세요