6-1. Process Synchronization 1

6-1 Process Synchronization 1

데이터의 접근, Race Condition, OS에서의 race condition(3/3), Example of a Race Condition, The Critical-Section Problem, OS에서 race condition(1/3), If you preempt CPU while in kernel mode…, Initial Attempts to Solve Problem, 프로그램적 해결법의 충족조건, Algorithm 1, Algorithm2, Algorithm3(Peterson's Algorithm), Synchronization Hardware, Semaphores

 

Initial Attempts to Slove Problem

두개의 프로세스가 있다고 가정 P0, P1

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

do{
	entry section
	critical section
	exit section
	remainder section
}while(1);

공유데이터를 접근하는 코드를 critical section이라 불렀는데 어떤 코드이건 간에 공유데이터를 접근하거나 아니거나로 반복될것임

공유데이터를 그냥 접근하게하면 동시접근을 통해 문제가 발생할 수 있기에 entry section을 넣어서 lock을 걸어서 여러 코드가 critical section에 들어가는 것을 막고, critical section이 끝나면 lock을 풀어서 다른 코드가 critical section에 들어갈 수 있도록 해줘야겠지

프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다. → synchronization variable

 

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

• Mutual Exclusion(상호배제)
  • 프로세스 Pi가 critical section 부분을 수행중이던 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
• Progress(진행) :아무도 안들어가있으면 들어가게해줘야함
  • 아무도 critical section에 있지않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해 주어야 한다.
• Bounded Waiting(유한대기) : 기다리는 시간은 유한해야한다
• 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
• 가정
  • 모든 프로세스의 수행 속도는 0보다 크다
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

알고리즘 1

• synchronization variable
• int turn;
• initially turn = 0;
• process P0

do{
	while (turn != 0); /* My turn? */ //초기조건이 0인데, 0이아닌경우니까 그럼 내차례를 계속 기다리겠지
																    //즉 1번 프로세스 차례겠지 기다리다가 turn이 1에서 0으로 되는 순간 
	critical section                  //critical section으로 들어갈 수 있게되었고,
	turn = 1 /* Now it's your turn */ //critical section에서 나오면 turn을 1로 바꿔줘서 상대방 차례로 바꿔줌
	remainder section
}while(1);

critical section에 들어가기전에 while문을 돌면서 체크를 함

알고리즘1에서는 turn이라는 변수를 사용하고 있는데 turn은 누구 차례냐는 것이다. turn 이 0이면 0번 프로세스 차례

이 코드는 mutual exclusion은 만족함, 둘이 동시에 들어가진 않겠지,

여기서 문제는..?

아무도 critical section에 없음에도 불구하고 아무도 Progress하지 못하는것

turn을 교대로만 해주어서 될 일이 아니구나..!!

 

알고리즘 2

synchronization variable

boolean flag[2]; //flag는 본인이 critical section에 들어가고자 하는 의중을 표시하는 것(2개는 flag[i], flag[j])

initially flag[모두] = false; /* no one is in CS */

“Pi ready to enter its critical section “ if(flag[i] == true)

process Pi

do{
	flag[i] = true; /* Pretend I am in */ //본인의 flag를 true로 만듦
	while (flag[j]); /* Is he also in? then wait */ //상대방 flag체크! 상대방이 flag를 셋팅하지 않았다면 
	critical section //critical section에 들어가고
	flag[i] = false /* I am out now */ //나올때 본인을 false로 만들어줌
	remainder section
}while(1);

문제점!

일단, process[i]가 본인의 깃발을 들고, 이상황에서 CPU를 뺏김. CPU는 process[j]한테 넘어가고 그 친구도 자신의 깃발만 들어 놓은 상태이고 아무도 CS에 들어가진 않은 상태인데 while문 보니 상대방 깃발 들고 있으니 못들어가지, 그럼 계속 기다리다가 아무도 못들어감...

둘이 동시에 들어가는 문제는 안생기지만 아무도 못들어가는 문제는 생김(데드락)

 

알고리즘 3 (Peterson’s Algorithm)

알고리즘 1 + 알고리즘2

Process Pi

do{
	flag[i] = true; /* My intention is to enter ... */ //들어가겠다는 의사표현
  turn = j; /* Set to his turn */ //turn을 상대방 turn으로 바꿔놓음
	while (flag[j] && turn == j); /* wait only if ... */ //상대방이 깃발을 들고 있고, 이번이 상대방 차례이면 기다리고있음
	critical section //critical section에 들어가고
	flag[i] = false 
	remainder section
}while(1);

프로그램 해결법의 충족조건 3가지 모두 만족함.

둘이 동시에 들어가지 않으면서 아무도 들어가지않으면 들어갈 수 있게 해주고, 특정 프로세스만 지나치게 오래 기다리게 하지도않음

문제점!

Busy waiting = spin lock

while문을 체크한다고 값이 바뀔리가없고, 값만 체크하며 본인의 할당시간을 다 쓰고 반납

회전하며 lock 을 걸면서 상대방이 못들어가게 막는다..? 만약 어떤 프로세스가 이미 CS에 들어가있는데, 다른 프로세스가 CPU를 돌면 while문을 돌겠지, 분명 만족 못하니 빠져나갈 수없겠고, 본인의 할당시간 동안 계속 while문만 돌것....! 비효율적인 방법이 되겠지!

 

Synchronization Hardware

하드웨어 적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

test_and_set(a)는 원래값을 읽어내고 그 자리에 1로 셋팅하게 atomic하게 처리!

Mutual Exclusion with Test & Set

synchronization variable:
		boolean lock = false; //lock이라는 변수를 0으로 두고

Process Pi
				do {
					while(Test_and_Set(lock)); 
//cricical section에 들어가기 전 lock 체크하고,lock 안걸려있으면 나를 lock하고 들어감
					critical section
					lock = false;
					remainder section
        }