[OS] Lock

쓰레드는 서로 메모리를 공유하기 때문에 공통으로 사용하는 공유 변수가 존재한다. 여러 쓰레드가 모두 변수의 값을 read만 하는 경우에는 문제가 되지 않지만 특정 쓰레드가 변수의 값을 write 하게 되면 동기화 문제가 발생한다. 이를 해결하기 위해 한 쓰레드가 변수를 write 할 때에는 다른 쓰레드가 해당 변수에 접근할 수 없도록 lock 걸어주는 과정이 필요하며 lock부터 unlock 사이의 구간을 임계영역(critical section)이라고 한다. 임계 영역은 해당 영역 내의 명령어를 원자적으로 실행되도록 보장한다. 

 

※ lock 관련 용어

• 임계영역(critical section)
  - 공유 자원에 접근해야하는 각 프로세스의 코드 영역으로, 다른 프로세스가 해당 영역을 수행하는 동안 수행되지 않아야 하는 코드 영역
  
  
• 상호배제(mutual exclusion)
  - 한 프로세스가 임계영역 코드를 수행 중일 때, 다른 프로세스들은 해당 자원에 접근할 수 없다는 개념
  
  
• 경쟁조건(race condition)
  - 두 개 이상의 프로세스가 공유 데이터 항목을 읽고 쓰는 상황
  
  
• 교착상태(deadlock)
  - 두 개 이상의 프로세스들이 서로 다른 프로세스가 어떠한 일을 해줄 때 까지 대기하는 상태
  
  
• 라이브락(livelock)
  - 두 개 이상의 프로세스들이 단순히 자신의 상태를 변화시키는 작업만 반복하면서 대기하는 상태
  
  
• busy waiting
  - 프로세스가 임계 영역으로 들어가기 위한 허가를 획득할 때 까지 변수를 테스트하는 명령을 반복하는 상태
  
  

---

상호배제 (mutual exclusion)

• 상호배제는 선택 사항이 아닌 필수 사항
• 임계영역 밖에 있는 어떤 쓰레드라도 임계영역 내의 쓰레드에게 간섭할 수 없음
• 교착상태 및 기아가 발생하지 않아야함
• 임계영역이 비어있을 때, 임계영역에 진입하고자 하는 프로세스는 즉시 접근 가능해야함
• 어떠한 쓰레드도 임계영역을 무한히 점유할 수 없음

 

상호배제 구현 방법

1. 

turn이라는 변수를 사용해 turn이 0이면 P0를, 1이면 P1이 임계영역에 들어갔다가 나올 때 turn 값을 반대로 바꿔주는 방식이다. 이 방식의 문제점은 다른 프로세스가 들어가지 않으면 연속해서 임계영역에 들어갈 수 없다는 것이다. 즉, 교착상태가 발생한다.

 

2. 

각 쓰레드마다 하나의 플래그를 사용해 자신이 임계영역을 점유하고 있는지를 나타낸다. 따라서 다른 쓰레드의 플래그가 켜져있지만 않으면 연속해서 임계영역에 들어갈 수 있다. 하지만 이러한 방식은 busy waiting을 발생시킨다. 만약 다른 쓰레드의 플래그를 검사하는 while문과 자신의 플래그를 true로 변경시키는 코드 사이에 스케줄링이 발생하게 된다면 두 플래그 모두 true가 되어 두 쓰레드 모두 임계영역에 접근하게 된다.

3. 

플래그를 변경하는 코드와 다른 쓰레드의 플래그를 확인하는 코드의 위치를 바꾼 경우이다. 하지만 이 경우에도 두 코드 사이에 스케줄링이 발생하면 두 플래그가 모두 true가 되어 모든 쓰레드가 다른 플래그를 확인하는 while문을 무한히 수행하게 된다.

 

 4. 

다른 쓰레드의 플래그를 검사하는 while문 내에서 자신의 플래그를 일정 시간 간격으로 토글하는 방식이다. 이러한 경우 delay 시간 내에 스케줄링이 발생하면 다른 쓰레드가 임계영역에 접근할 수 있다. 하지만 두 쓰레드의 delay가 동시에 발생하는 최악의 경우에는 라이브락 상태에 빠지게된다. 하지만 이런 경우는 현실에서 거의 불가능에 가깝기 때문에 무시하여 위의 정책을 가장 최선의 정책으로 사용하고 있다.

 

상호배제를 위한 HW 지원

1. 인터럽트 금지

HW적으로 임계영역 접근 이전에 인터럽트를 금지한 뒤, 임계영역 이후에 인터럽트를 허용함으로써 중간에 스케줄링이 일어나지 않도록 하는 것이다. 가장 쉽고 간단한 방법이지만 이는 다양한 문제점이 발생하므로 현실성이 없다.

 

2. 특별한 기계 명령어 지원

• testset
  - 인자 i의 값을 점검하여 0이라면 1로 고친 후 true, 그렇지 않으면 그대로 둔 후 false를 리턴
  - 함수 전체는 원자적으로 처리되어 중간에 인터럽트 당하지 않음
• exchange
  - 레지스터의 값과 메모리에 저장된 값을 서로 교체하는 기능을 수행

---