티스토리 뷰

멀티 프로세서 환경에서는 critical section problem을 사용하여 모든 프로그램에게 적용하는 것은 비효율적이게 된다. 따라서 하드웨어 측면에서도 동기화를 유지하기 위한 방법들이 존재한다. 하드웨어 측면에서 동기화하는 방법에 대해 정리한다.

Test and set

동기화 명령 중 하나로 하드웨어의 도움을 받는다. 상호배제를 편리하게 구현할 수 있다. 하드웨어적으로 읽고, 셋팅하는 작업을 atomic하게 수행한다. 원자적인 명령이기 때문에 명령어가 실행되는 동안 인터럽트가 일어날 수 없다. boolean lock 변수를 설정하여 lock이 걸려있는 상태에서는 다른 프로세스가 critical section에 접근하지 못하도록 한다. (위키참고)

// Synchronization variable : initial = lock = true 가 동시에 실행됨
    function TestAndSet(booolean_ref lock) {
      boolean initial = lock
      lock = true
      return intitial
    }

// Process P[i]
    do{
      while (TestAndSet(&lock)); 
      // 누군가 lock을 걸어있다면 대기 
      // 여기서 누군가가 critical section을 사용하고 false로 설정하면 가장 먼저 TestAndSet을 실행한 프로세스가 진입 
      critical section // lock이 걸려있지 않다면 critical section 진입
      lock = false; // lock을 true -> false로 변환
      remainder section
    } while (1);

Semaphores

위의 방식을 추상화시킨 것으로 두 개의 원자적 함수로 조작되는 정수변수이다. P연산은 사용하는 연산, V는 반납하는 연산을 의미한다. P,V의 두 가지 원자적인 연산에 의해서만 접근이 가능하다.

Busy-waiting

P(S) :
    while (S<=0); // 양수의 값이 될때까지 대기    
    S--;

V(S) :
    S++;

P연산에서 S의 값이 음수이면 계속 반복문을 실행하며 대기한다.

// Synchronization variable
    semaphore mutex; // 초기값 = 1

// Process P[i]
    do{
      P(mutex); // mutex가 양수값이면 들어가고 아니면 대기 (음수 값이면 누군가 사용중)
      // P연산에서 while 문을 통과했다면 mutex를 감소하여 사용하고 있음을 설정
      critical section
      V(mutex); // mutex를 다시 증가시켜줌
      remainder section 
    } while(1);

바쁜 대기(busy-waiting)을 활용한 방법이다. busy-waiting은 공유자원에 대한 권한 획득이 빠르게 이뤄진다면 간단하게 사용할 수 있다. spin-lock은 바쁜대기 종류 중 하나라고 한다. 스핀락은 임계구역 진입이 불가할 때 가능해질 때까지 루프를 돌면서 재시도 하는 방식으로 구현한 락을 의미한다.

Block/wakeup implementataion

Semaphroe { 
    int value; // semaphore 정수 값
    struct process *L // process waiting queue
}

- block : 커널은 block을 호출한 프로세스를 suspend하고, 이 프로세스의 PCB를 L에 넣는다

- wakeup(P) : block된 프로세스 P를 wakeup 시켜 이 프로세스의 PCB를 ready queue로 옮긴다.

 

간단히 정리하면 critical section에 접근을 요청한 프로세스들을 block된 상태로 대기줄에 넣어둔다. 그러면서 자리가 날때 대기줄에 있는 프로세스들을 하나씩 깨워서 critical section 접근을 허가한다.

P(S) : 
    S.value--; // 대기자가 많아질수록 음수값! 갯수보단 상황을 의미
    if (S.value <0) {
        add this process to S.L; // 대기줄에 추가
        block(); // 잠들어서 대기
        }

V(S) :
    S.value++; // 사용하고 반납하는 연산이니까 대기자가 줄어듦(양수에 가까운 값으로)
    if (S.value <=0) { // 자원을 반납했는데도 0이하라면 sleep 하고 있는 프로세스들이 있다는 것
        remove a process P from S.L; // 대기줄에서 하나 빼서
        wakeup(P); // 준비큐에 넣어줌
        }

어떤 방식이 더 좋을까?

critical section의 길이가 짧으면 busy-wait, 길면 block/wakeup 방식이 더 효율적이라고 한다. 보통의 경우 block/wakeup 방식을 사용하는게 더 효율적이라고 한다.

2 types of Semaphores

- counting semaphore : 자원을 카운팅하는데 사용

- binary semaphore (=mutex) : 0 또는 1, lock 또는 unlock

Deadlock and Starvation

- Deadlock : 둘 이상의 프로세스가 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상. 서로 다른 자원을 획득한 상황에서 계속 상대방이 가진 것을 기다리는 상황이다. 자신의 상황이 충족되지 못하니까 영원히 자신이 가진 것을 내어놓지 않고 상대방의 것을 무한히 기다리는 상태

 

- Starvation : 계속 사용하지 못하고 영원히 기다리기만 하는 상태

Classical problems of synchronization

Bounded-Buffer problem (Producer-Consumer problem)

 

[ Producer ] 

1. empty 버퍼가 있는지 확인 (없으면 대기)

2. 공유데이터에 lock을 건다

3. empty 버퍼에 데이터 입력 및 조작

4. lock을 푼다

5. full 버퍼(채워진 것)가 하나 증가

 

[ Consumer ]

1. full 버퍼가 있는지 확인 (없으면 대기)

2. 공유데이터에 lock을 건다

3. full 버퍼에서 데이터를 꺼내고 조작

4. lock을 푼다

5. empty 버퍼(빈 것)가 하나 증가

 

// Synchronization variables
semaphroe full = 0, empty = n, mutex = 1;

// Producer 
do {
    ... produce an item in x 
    P(empty);
    P(mutex);
    ... add x to buffer
    V(mutex);
    V(full);
} while (1);

// Consumer
do{
    P(full);
    P(mutex);
    ... remove an item from buffer to y ...
    V(mutex);
    V(empty);
    ... consume the item in y ...
} while (1);
    

resource count인 empty와 full은 integer semaphore를 사용하고,  lock과 unlock 상태를 관리할 mutex는 binary semaphore를 사용한다. Producer에게는 empty가 자원이고 Consumer에게는 full이 자원이다.

Reader-Writers problem

DB 같은 공유데이터를 사용하는 경우이다. read는 동시에 해도 상관없지만 write는 배타적으로 하나만 사용해야 한다.

// Shared data
int readcound = 0;
DB;

// Synchronization variables
semaphore mutex = 1, db = 1; // db를 reader나 writer가 lock & unlock

//Writer
	P(db);
	... writing DB is performed ...
	V(db);

//Reader
	P(mutex); // readcount에 접근하기 위한 lock
	readcount++; // 공유데이터(readcount) 증가
	if (readcount == 1) P(db); // 1이상 읽고 있다면 db에 lock
	V(mutex); // readcount 사용을 반납
	... reading DB is performed ...
	P(mutex); // readcount에 접근하기 위한 lock
	readcount--; // 공유데이터(readcount) 감소 
	if (readcount == 0) V(db); // 읽고 있는 것이 하나도 없다면 unlock
	V(mutex); // readcount 사용을 반납

writer의 starvation 발생 가능성이 있다.

Dining-Philosophers problem

1. 최대 4명만 앉을 수 있게 한다. (max 정원을 모자르게 설정한다)

2. 양쪽 젓가락을 모두 잡을 수 있을 때만 젓가락을 잡을 수 있게 한다.

3. 비대칭으로 설계한다. 짝수는 오른쪽 먼저, 홀수는 왼쪽 먼저 젓가락을 잡게 한다.

 

[식사하는 철학자 문제란?]

5명의 철학자가 원탁 테이블에 앉아있다. 밥을 먹으려면 왼쪽 젓가락과 오른쪽 젓가락이 필요한데 모두 왼쪽 젓가락을 들고있다. 아무도 오른쪽 젓가락과 왼쪽 젓가락을 확보할 수 없기 때문에 자신이 가진 젓가락도 내려놓지도 못하고 영원히 먹을수도 없이 대기하게 된다.(deadlock)

 

Monitor

[semaphore의 문제점]

1. 코딩하기 힘들다.

2. 정확성 입증이 어렵다 (버그해결이 어렵다)

3. 한번의 실수가 모든 시스템에 치명적 영향을 줄 수 있다. (P,V 연산의 순서가 꼬이면 전체가 꼬여버린다.

 

모니터란 동시에 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct 이다.

 

- lock이 필요없다 : 동시접근 자체가 제한된다. 모니터가 알아서 하나의 프로세스만 접근 가능하게 하고 나머지는 줄을 세운다. 생산이나 소비를 하려면 모니터 내에서 코드가 실행되는데 모니터 내부에는 하나의 프로세스만 접근 가능하다.

- 프로세스가 모니터 안에서 기다릴 수 있도록 condition variable을 사용한다.

- condition variable은 wait와 signal 연산에 의해서만 접근 가능하다.

- 모니터 내에서는 1개의 프로세스만 활성화 된다.

- 큐에 줄서 있는 프로세스를 깨워서 활성화시킨다.

 

Semaphores와 비교 (Bounded-Buffer problem)

[ semaphore ]

- lock을 나타내는 mutex를 사용하여 생산자, 소비자를 공유버퍼에 넣고 뺀다.

- empty, full을 나타내는 변수 값이 존재한다.

- 자원을 확보하기 위해 프로그래머가 작성한 P,V연산을 한다.

 

[ monitor ]

- lock이 필요없다. 생산자든 소비자든 접근할 때, 다른 프로세스의 접근을 막아준다.

- 값보다는 조건을 확인한다.

- 동시접근 자체를 막아준다.

정리

원자적인 특성을 가진 명령어를 추상화한 semaphore를 사용하여 하드웨어 동기화를 유지한다. semaphore는 정수 값과 binary 특성을 가진 값을 성격에 따라 사용한다. 자원을 사용하는 P 연산, 자원을 반납하는 V연산을 사용하며 여러 프로세스가 공유데이터에 동시에 접근하지 못하도록 사용중에는 lock 상태를 유지한다. 여러가지 동기화에 관련되어 발생하는 문제를 semaphore를 사용하여 해결한다.

Monitor라는 개념도 있는데 이것은 lock이 필요없이 하나의 프로세스만 모니터 내부에 접근하게 한다. 접근을 요청한 다른 프로세스들은 모니터 안에서 대기(wait)하게 하며, signal 연산을 통해 다음 내부에 접근할 프로세스를 깨운다. semaphore는 lock, unlock 상태와 자원의 수를 가지고 진입할 프로세스를 판단하는 반면 monitor는 상황을 판단하는 느낌이다. 이 방식은 semaphore에서 block/wakeup 방식과 차이는 있지만 약간 유사하다고 생각했다.

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.

 

 

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함