Synchronization

 

두 개 이상의 threads나 processes간에 shared resource가 있는 경우 syschronization을 고려해줘야한다.

 

그렇지 않으면 race condition(경쟁상태)이 발생할 수 있음

 

int withdraw (account, amount)
{
	balance = get_balance (account);
	balance = balance - amount;
	put_balance (account, balance);
	return balance;
}

 

shared data에 접근과 수정을 동시에 할 수 없음.  따라서 context switch가 일어나면 균일한 결과 기대할 수 없음

이런 구간을 critical section이라고 부르고 이 section을 관리해줘서 synchronization problem을 해결해야한다.

 

 

해결 하는 가장 기본 원리는 Mutual Exclusion

 : critical section을 하나씩 사용한다.

    

 

그럼 해결을 위해 가장 간단한 방법인 Lock을 사용해보자

int withdraw (account, amount)
{
	lock(lock);
    
	balance = get_balance (account);
	balance = balance - amount;
	put_balance (account, balance);
    
	unlock(lock);
   	return balance;
}

 

 

lock 상태로 들어간 프로세스는 waiting 상태에서 기다린다.

 

lock을 간단하게 구현해보면 

struct lock { int held = 0; }
	
void lock (struct lock *l) {
	while (l->held);
	l->held = 1;
}
	
void unlock (struct lock *l) {
	l->held = 0;
}

하지만 이런 방식에는 단점이 있다. 

1) 접근 불가능한 프로세스가 무한 루프를 돌며 기다리는 busy-waiting 중인데 자신의 time quantum을 전부 무한루프 도는데 쓰니까 비효율적이다.

2) 그리고 실제로 돌려보면 안된다. 여기도 결국 변경과 접근이 동시에 이뤄지지 않기 때문에 아다리 안맞으면 언제든지 문제 생길 여지가 있다. (lock 함수 실행중에 context swtich 일어날 수 있음)

 

 

 

 

 

해결방법

---

Low-level Synchronization

• Atomic operation
  :  lock이라는 함수를 하나의 cpu 명령어로 만들면 중간에 갈릴 일이 없다.
  :  Test-and-set 

• Software-only algorithms
  : bakery Algorithm 너무 복잡해서 안씀
• Disable interrupt
  : context switching을 막자 싱글 processor에서 사용. multi에선 spin lock

 

Test-and-set

 

boolean TestAndSet(boolean &target) {
	boolean rv = target;
	target = true;
	return rv;
}

보기엔 여러 line이지만 hw적으로 한 사이클에 수행된다.

이걸 이용해서 다시 구현하면

struct lock { int held = 0; }

void lock (struct lock *l) {
	while (TestAndSet(l->held)) ;
}
void unlock (struct lock *l) {
	l->held = 0;
}

요렇게하면 문제는 해결된다. 그래도 1번의 문제인 busy waiting는 남아있다.

 

 

 

Disable interrupt

 

void lock (struct lock *l) {
	cli(); // disable interrupts;
}
void unlock (struct lock *l) {
	sti(); // enable interrupts;
}

하지만 interrupt를 제어하는 방법도 kernel에서 가능한 것이지 application level에서는 못쓴다.

그리고 single processor에서만 가능하고 multi부터는 안됨 test and set 쓰라구

 

 

 

Higher-level Synchronizaion

---

위에서 나온 내용은 low-level로서 kernel에서 쓰는 방법

실제 user level에서는 이런 방법 못쓴다. 고래서 higher level로 알아보자

 

Semaphores

• shared data 개수만큼 Semaphore를 만든다
• wait signal 두 개의 (atomic)함수만 갖는다
• waiting queue를 이용해서 busy waiting 문제를 해결하였다
  : wait시에 time quantum까지 무한루프 도는 게 아니라 그냥 waiting queue에 넣어버리고 바로 딴일 하러감

 

 

waiting 시 현재 세마포어 사용불가능하면 스스로 중지한다음 바로 waiting queue에 프로세스 넣고 waiting state 로 변경 mutex lock에서 spin lock을 해결한 방법이 semaphore라고 할 수 있다.

다른 process에서 wakeup했을 시 실행된다. 정확히 말하면 다른 프로세스에서 signal하면 waiting queue에 있던 프로세스가 ready queue로 전달된다. 

 

 

mutex의 busy waiting을 없애고자 semaphore에서 sleep 사용? mutex나 semaphore나 busy waiting없지않나.. 암튼 책에는 이런식으로 설명되어있음.

operating system concept p.274

 

 

 

세마포어를 적용했을 시

semaphore mutex; //initially mutex = 1

do {
	wait(mutex);
		critical section
	signal(mutex);
		remainder section
} while (1);

ex) 만약 사무실에 프린터가 5개라면 mutex를 5로 하고 0이 되면 사용불가 이런식으로 구현가능

 

세마포어를 이용해 순서를 제어할 수도 있다.

Pj는 Pi가 A라는 일을 할 때까지 대기한다. ex) ipc에서 shared memory로 통신할 때 사용가능

 

 

 

---

초간단 예를 들어보자

---

1.

Producer는 buffer에 값을 계속 집어넣고 Consumer은 계속 값을 빼온다.

이겨서 critical section인 buffer, count를 보호해 줘야한다.

 

 

 

먼저 mutex로 buffer를 처리하고

empty는 현재 buffer에 비어있는 개수

full은 하나 이상 있으면 1 비어있으면 0으로 유지한다.

 

2.

---

상황 ) 각 thread는 write or read 하나의 역할만 수행한다.

write는 동시에 하나만, read는 동시에 여러개 가능하다. 

이런경우 readcount를 만들어 reader들이 multiple하게 실행될 수 있게 만들어준다. 물론 readcount도 shared data이므로 보호해 줘야한다. 

 

 

 

3.

---

겁나 유명한 밥먹는 철학자 문제 한정된 젓가락을 이용해서 밥을 먹어야하는 문제이다. 

간단한 해결법은 chopstick을 세마포어로 보호하면된다.

하지만 이런 방법은 또 다른 문제인 deadlock을 유발한다. 

만약 동시에 모든 왼쪽 젓가락을 들면 그냥 하루종일 기다리는 교착상태에 빠지게 된다.

따라서 모든 shared data를 보호하는게 아닌 deadlock까지 고려해야한다.

 

향상된 방법

dead-lock free : 양쪽 들 수 있는지 검사후 먹는다. 근데 이러면 starvation 생김

pickup에서 wait(s[i])는 i번째 철학자가 못먹었을 때 걸린다.

근데 다른 애들이 putdown할때 그 양옆을 다시 test해줘서 만약 먹을 수 있으면 wait 풀리고 eat() putdown() 진행되는 방법

 

starvation free : aging 추가해서 소외되는 철학자 우선적으로 먹게해준다. 

putdown의 test에서 왼쪽오른쪽 선택할때 덜 먹는 사람 먼저 test해주는게 좋을 거 같은디

 

---

 

synchronization 문제를 해결하는 또다른 방법

---

1.

동기화 문제를 program language가 관리해준다. 컴파일러가 알아서 코드 삽입해서 보호해줌.

 

 

 

2.

모니터라는 추상화 data type을 만들고 그 안에 shared data와 data에 접근하는 함수들을 만든다.

만약 A라는 thread에서모니터의 특정 함수를 사용해서 shared data로 작업중이면 다른 thread에서는 접근 불가능하게 하는 개념.

모니터에 추가된 함수들은 알아서 관리해줌.(java의 syncrhonize   c++은 없음)

 

여기서 추가된 개념이 condition variable이다. monitor의 함수를 편리하게 쓰려면 lock된 section의 값을 알아야한다. 그렇기에 일시적으로 통신하는 방법.

 

2) a

monitor식으로 밥먹는 철학자 풀이 구현 (concept)

동기화에 쓰이는 함수들을 monitor로 구현한다. 컴파일러가 한번에 하나씩 수행되도록 보장한다.

 

---

3

Mutex : application level에서 사용하는 lock, 사실상 binary semaphore

 

 

mutex와 condition variable 이용해서 이전의 producer과 consumer을 구현해보자

 

shared data인 buffer를 mutex 보호하고 busy waiting을 피하기 위해 condition variable을 추가한다.

producer에서 mutex를 lock하고 들어간다. 하지만 만약 resource가 full이라면 not_full을 wait하면서 mutex를 잠시 풀어준다. 그냥 semaphore 여러개 써서 busy waiting 피하는 것보다 가독성이 좋은 듯.  

 

c, c++에서 semaphore를 쓸지 mutex, condition variable 쓸지 알아서 좋은거 사용 ㄱㄱ

 

 

---

요약