상호배제 ( Mutual Exclusion )

※ 전남대학교 박태준 교수님의 운영체제 강의를 듣고, 정리한 내용입니다.

상호배제 ( Mutual Exclusion ) 를 먼저 요약하자면, 임계 구역 ( Critical Section ) 을 어떤 방법을 써서 잠글 것인지에 대한 이야기입니다.

임계 구역을 잠금으로써, 오직 1개의 프로세스 ( 혹은 쓰레드 ) 만 진입가능 하도록 만들어줘야 합니다.

개념

임계영역 ( Critical Section ), 즉 공유 자원이 존재하는 영역에는 오직 1개의 프로세스 ( 혹은 쓰레드 ) 만 진입할 수 있도록 해야 합니다.

그래서 이를 위한 여러가지 방법들이 나올 예정이지만, 결국 핵심은 다음과 같습니다.

• 입구에 게이트 를 두고, 이를 잠글 수 있는 열쇠 Lock 을 만들기

• Lock 이 걸려있으면 → 못들어가니, 열릴 때 까지 입구에서 대기

• 화장실에 걸려있는 자물쇠와 비슷함

말 그대로 문을 만들고, 이를 잠글 수 있는 열쇠를 만들어줌으로써 임계 영역 안에 하나의 프로세스 ( 혹은 쓰레드 ) 만 접근가능하도록 만들어 주는 것이 핵심이라고 볼 수 있습니다.

상호 배제를 포함하는 프로그램

1. 일반 코드 ( non - critical code )

   1. 공유 데이터를 액세스하지 않는 코드

2. 임계구역 진입 코드 ( entry code )

   1. 상호배제를 위해 필요한 코드 ( enterCS() )

   2. 현재 임계구역을 실행 중인 쓰레드가 있는지 검사

3. 임계구역 코드 ( critical code )

4. 임계구역 진출 코드 ( exit code )

   1. 상호배제를 위해 필요한 코드 ( exitCS() )

   2. entry code 에서 대기중인 쓰레드가 임계구역에 진입할 수 있도록 entry code 에서 취한 조치를 해제하는 코드

문을 아무렇게나 만들면 안된다!

문을 만들기 위해 지켜져야 하는 조건들이 존재합니다.

• 상호 배제 ( mutual exclusion )

  • 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없는 것
  • Lock 상태 표시를 정확하게 해줘야 함 ( 문을 잠궜는지, 열었는지 )
  • 다른 프로세스 ( 혹은 쓰레드 ) 가 들어오지 못하도록 해줘야 함

• 한정 대기 ( bounded waiting )

  • 어떤 프로세스도 무한 대기 ( 계속 밖에서 기다리는 것 ) 하지 않아야 함
  • 한 프로세스 ( 혹은 쓰레드 ) 가 무한적으로 자원을 독식하면 안됨
  • 유한한 시간 안에 다른 쓰레드에게 자원을 넘겨줘야 함

• 진행의 융통성 ( progress flexibility )

  • 한 프로세스가 다른 프로세스의 진행을 방해해선 안됨
  • 쓰레드 T1, T2 가 있다고 할 때, T1 이 자원을 무한정으로 독식할 경우 T2 는 무한정 대기
  • T1 에 의해 T2 의 진행이 방해되니, 이런 경우를 만들면 안됨

문을 만드는 방법 2가지

• 소프트웨어적 방법

  • 데커 알고리즘, 피터슨 알고리즘 등
  • 빵집 알고리즘 등

• 하드웨어적 방법

  • 오늘날 대부분은 하드웨어 기반 동작
  • 임계 구역 진입 / 진출 코드에 구현
  • 구현 방법 : 인터럽트 서비스 금지, 원자 명령 ( atomic instruction ) 사용

( 상호배제 구현 방법 ) 1. 인터럽트 서비스 금지

공유 자원 문제가 발생하는 이유는, 결국 context switching 간 발생하는 명령어의 분리 때문에 발생하게 됩니다.

이 context switching 은 scheduling 에 의해 발생하고, 이는 인터럽트를 활용해서 발생하게 되니 인터럽트를 금지한다면 공유 자원 문제가 발생하지 않게 됩니다.

🖥️ 인터럽트 금지 → scheduling 에 의한 context switching 도 자연스럽게 금지됨

하지만, 다음과 같은 문제점이 발생하게 됩니다.

• 모든 인터럽트가 무시되는 문제 → 시스템의 효율적인 운영 방해

• 멀티코어 CPU 또는 다중 CPU 에서는 활용이 불가능

  • 모든 CPU 의 인터럽트가 멈추게 되니, 진행의 융통성 조건 불충족

결국 Lock 을 현재 엑세스 하고 있는 메모리에만 국한시킬 필요가 있습니다.

그렇다고 Lock 이 단순하게 on/off 가 되어선 안됩니다.

문이 열려있는지, 닫혀있는지 확인하기 위한 Lock 도 공유 데이터이기 때문에, 똑같이 동기화 문제가 발생하게 됩니다.

이 경우, 상호배제 조건을 만족할 수 없습니다.

이 문제를 해결하기 위한 여러 방법들..

1. Lock 변수를 2개 만들어주기 ( 열쇠 2개 생성 )

   1. 각자의 열쇠가 잠겼는지, 안잠겼는지 확인

   2. Lock1 이 true 면, 2번 쓰레드는 대기 ( 1번 쓰레드 진행중 )

   3. Lock2 가 true 면, 1번 쓰레드는 대기 ( 2번 쓰레드 진행중 )

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
const int count = 200000;
int sum = 0; // global variable, shared data
bool lock = false; // lock
void* myThread1(void *p) {
 for(int i = 0; i < count; i++) {
 while(lock == true); // critical section
 lock = true;
 sum += 1;
 lock = false;
 }
 return 0;
}
void* myThread2(void *p) {
 for(int i = 0; i < count; i++) {
 while(lock == true); // critical section
 lock = true;
 sum -= 1;
 lock = false;
 }
 return 0;
}
int main() {
 pthread_t tid1, tid2; // thread id
 int count = 200000;
 int *ret1, *ret2;
 printf("Start!\n");
 pthread_create(&tid1, NULL, myThread1, NULL);
 pthread_create(&tid2, NULL, myThread2, NULL);
 pthread_join(tid1, (void**)&ret1); // waiting for 'tid1'
 pthread_join(tid2, (void**)&ret2); // waiting for 'tid2'
 printf("sum = %d\n", sum);
 return 0;
}

이렇게 세팅해줄 경우, 될 듯 합니다.

하지만 아래와 같은 케이스가 발생했을 때, 둘다 while문에서 대기해야 하니, 결국 무한루프에 빠지게 됩니다.

• Lock1 을 true 로 바꿨을 때 context switching 이 발생

• Lock2 를 true 로 바꾸고 진행하려고 할 때 또 context switching 이 발생

이 경우, 한정대기 조건을 만족할 수 없습니다.

이 문제를 해결하고자, 아예 서로의 사용권 자체를 주고받는 방법도 생각해볼 수 있습니다.

2. 서로 사용권 주고 받기

즉 Lock 을 int 형으로 표현해줌으로써 실행 순서를 결정해버리는 방법입니다.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
const int count = 200000;
int sum = 0; // global variable, shared data
int lock = 1; // lock
void* myThread1(void *p) {
 for(int i = 0; i < count; i++) {
 while(lock == 2); // critical section
 sum += 1;
 lock = 2;
 }
 return 0;
}
void* myThread2(void *p) {
 for(int i = 0; i < count; i++) {
 while(lock == 1); // critical section
 sum -= 1;
 lock = 1;
 }
 return 0;
}
int main() {
 pthread_t tid1, tid2; // thread id
 int count = 200000;
 int *ret1, *ret2;
 printf("Start!\n");
 pthread_create(&tid1, NULL, myThread1, NULL);
 pthread_create(&tid2, NULL, myThread2, NULL);
 pthread_join(tid1, (void**)&ret1); // waiting for 'tid1'
 pthread_join(tid2, (void**)&ret2); // waiting for 'tid2'
 printf("sum = %d\n", sum);
 return 0;
}

이 경우, 내부적으로 실행 순서를 엄격하게 결정하기 때문에 시간이 너무 오래 걸린다는 단점이 존재하여, 진행의 융통성 조건을 만족할 수 없습니다.

이 두가지 케이스의 모든 원인은 Lock 변수를 확인하는 과정에서 문제점이 발생했기 때문에, 이를 해결하고자 원자 명령 ( atomic instruction ) 방법이 도입되었습니다.

( 상호배제 구현 방법 ) 2. 원자 명령 ( atomic instruction )

Lock 변수를 이용한 상호배제의 실패 원인은, entry 코드에 존재합니다.

Lock 변수 값을 읽는 명령과 Lock 변수에 1을 저장하는 2개의 명령 사이의 context switching 이 될 때 문제가 발생하게 됩니다.

이를 해결하고자, Lock 을 읽어 들이는 명령과 Lock 변수에 1을 저장하는 명령을 한번에 처리하는 명령어를 도입하게 되었습니다.

이것이 원자 명령인 TSL ( Test and Set Lock ) 입니다.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdatomic.h>
const int count = 200000;
int sum = 0; // global variable, shared data
//bool lock = false; // lock
atomic_flag lock = ATOMIC_FLAG_INIT;
void* myThread1(void *p) {
 for(int i = 0; i < count; i++) {
 while( atomic_flag_test_and_set(&lock) );
 sum += 1;
 atomic_flag_clear(&lock);
 }
 return 0;
}
void* myThread2(void *p) {
 for(int i = 0; i < count; i++) {
 while( atomic_flag_test_and_set(&lock) );
 sum -= 1;
 atomic_flag_clear(&lock);
 }
 return 0;
}
int main() {
 pthread_t tid1, tid2; // thread id
 int count = 200000;
 int *ret1, *ret2;
 printf("Start!\n");
 pthread_create(&tid1, NULL, myThread1, NULL);
 pthread_create(&tid2, NULL, myThread2, NULL);
 pthread_join(tid1, (void**)&ret1); // waiting for 'tid1'
 pthread_join(tid2, (void**)&ret2); // waiting for 'tid2'
 printf("sum = %d\n", sum);
 return 0;
}