[운영체제] 뮤텍스와 세마포어
cs-study에서 스터디를 진행하고 있습니다.
프로세스 동기화
프로세스들은 병렬 프로그래밍, 다중 프로그래밍에 의해 병행하게 또는 각각 병렬로 실행될 수 있다. 하지만, 이러한 병행 & 병렬적인 동작은 데이터의 무결성에 문제를 일으킬 수 있다. 각 프로세스들은 서로 영향을 미치기 때문에 데이터나 흐름에 대한 동기화가 매우 중요하다.
병행 vs 병렬
병행 (Concurrency)
동시에 실행되는 것처럼 보이는 것이다. 실제로는 Time-Sharing으로 CPU를 나눠 사용함으로써 사용자가 병행을 느낄 수 있도록 한다. 물리적으로 병렬로 동작할 수 있다.
병렬 (Parallelism)
실제로 동시에 작업이 처리되는 것이다. 오직 멀티 코어에서만 가능하다.
Bank Account Problem (은행 계좌 문제)
프로세스 동기화가 제대로 지켜지지 않는 경우 발생할 수 있는 문제의 대표적인 예시로는 은행 계좌 문제가 있다. 하나의 계좌에 입금과 출금을 하는 상황이며, 아래 코드에선 계좌인 BankAccount는 공용 자원이고 입금을 하는 객체인 Parent와 출금을 하는 객체인 Child는 각각 프로세스라고 생각할 수 있다.
class Test {
public static void main(String[] args) throws InterruptedException {
BankAccount b = new BankAccount();
Parent p = new Parent(b);
Child c = new Child(b);
p.start(); // start(): 쓰레드를 실행하는 메서드
c.start();
p.join(); // join(): 쓰레드가 끝나기를 기다리는 메서드
c.join();
System.out.println("balance = " + b.getBalance());
}
}
// 계좌
class BankAccount {
int balance;
void deposit(int amount) {
balance = balance + amount;
}
void withdraw(int amount) {
balance = balance - amount;
}
int getBalance() {
return balance;
}
}
// 입금 프로세스
class Parent extends Thread {
BankAccount b;
Parent(BankAccount b) {
this.b = b;
}
public void run() {
for (int i = 0; i < 100; i++)
b.deposit(1000);
}
}
// 출금 프로세스
class Child extends Thread {
BankAccount b;
Child(BankAccount b) {
this.b = b;
}
public void run() {
for (int i = 0; i < 100; i++)
b.withdraw(1000);
}
}
위의 코드를 실행하면 대부분 balance = 0 이라는 결과를 얻겠지만, 프로세스에서 시간 지연이 발생하거나 프로세스 순서를 변경하는 등 상황에 따라서 원치 않는 결과가 나올 수 있다. 예를 들어, 아래와 같이 입금과 출금 기능을 담당하는 BankAccount 객체에서 동작에 약간의 시간 지연을 추가해 보자.
// 계좌
class BankAccount {
int balance;
void deposit(int amount) {
int temp = balance + amount;
System.out.print("+");
balance = temp;
}
void withdraw(int amount) {
int temp = balance - amount;
System.out.print("-");
balance = temp;
}
int getBalance() {
return balance;
}
}
해당 코드를 실행하면 balance의 값이 0이 아닌 1000000이라는 알 수 없는 값이 출력된다. 이처럼 약간의 시간 지연을 준 것만으로도 공유 자원을 사용하는 프로그램은 원하는 정보를 얻을 수 없게 된다. 이는 동기화 문제를 해결하지 못하였기 때문에 생기는 문제점이며, 해당 문제가 발생하는 원인은 입출금에 대한 순서가 보장되지 않았기 때문이다. (매 실행마다 입출금의 순서가 다르게 출력된다.)
다시 말하면, 공통 변수에 대한 동시 업데이트가 발생하였기 때문이다. 위 예시에서는 입금 프로세스와 출금 프로세스가 잔액이라는 공통 변수를 동시에 업데이트하려고 했기 때문에 발생했다.
balance = balance + amount; // 입금
balance = balance - amount; // 출금
이처럼 공유된 자원에 여러 프로세스, 여러 쓰레드가 동시에 접근하면서 동기화에 대한 문제가 항상 발생할 수 있다. 여러 프로세스가 공통된 데이터를 조작할 때, 동기화 없이 공유된 자원에 접근하려는 현상, 혹은 실행 결과가 조작의 타이밍이나 접근 순서에 의해 결정되는 현상을 race condition이라고 한다.
임계 구역
여러 프로세스로 인해 공유 데이터의 일관성을 보장하지 못하는 것을 막기 위해서는 프로세스 간 동기화가 필요하다. 앞서 말한 예시에서 원치 않는 값을 반환받지 않으려면, 프로세스 A → 프로세스 B의 순서를 보장하면 된다. 혹은 공유 데이터를 한 번에 하나의 프로세스만 접근할 수 있는 방식을 사용하여 문제를 해결할 수도 있다.
다중 프로그래밍 시스템에서 여러 프로세스들이 공유하고 있는 자원을 한 시점에 하나의 프로세스만 접근할 수 있게 하는 영역, 혹은 공통 변수 구역 을 임계 구역이라고 한다.
임계 구역에서 발생하는 문제를 해결하기 위한 조건으로는 3가지가 있다.
Mutual Exclusion (상호 배제)
하나의 프로세스가 임계 구역에 들어가 있으면 다른 프로세스는 들어갈 수 없다.
Progress (진행)
임계 구역에 들어간 프로세스가 없다면, 어느 프로세스가 들어갈 것인지 적절히 선택해 줘야 한다.
Bounded Waiting (한정 대기)
기아 상태를 방지하기 위해 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다.
그리고 임계 영역의 동시 접근 문제를 해결 하기 위한 방법으로는 Lock, 세마포어, 모니터 등이 있다.
세마 포어
공유 자원을 여러 프로세스가 동시에 접근하는 것을 막기 위해 사용하는 방법으로, 세마포어의 구성 요소는 크게 세마포어 변수, P 동작, V 동작이 있다.
S (세마포어 변수)
정수 값을 가지는 정적 변수이며, 정수 값은 공유 자원에 접근 가능한 프로세스의 개수를 의미한다. 이때 세마포어 값이 0 또는 1의 값만 만들 수 있다면 (한 번에 접근 가능한 프로세스가 1개일 경우) 이진 세마포어라고 하며, 2 이상의 값도 가질 수 있는 경우 계수 세마포어라고 한다.
P (try를 의미, acquire())
프로세스가 임계 구역에 들어가긴 전에 수행되고 (try), 세마포어 값을 감소 시킨다. 만일 감소 후 값이 음수가 되면 해당 프로세스를 Ready Queue에 추가한 후, 함수를 호출한 프로세스는 Lock이 된다. 즉, 세마포어 값이 0보다 크면 프로세스의 접근을 허용하되, 1을 감소하고 난 뒤 값이 0이 되는 순간부터 프로세스 접근을 금지한다.
V (increment를 의미, release())
작업이 끝나고 프로세스나 쓰레드가 임계 구역에서 나갈 때는 세마포어 값을 증가시킨다(increase). 만약 세마포어 값이 음수이면, Ready Queue에 있던 Lock 상태의 프로세스를 하나 꺼내서 임계 구역을 수행할 수 있게 한다.
이때 변수를 수정하는 두 연산(P, V)은 모두 원자성을 만족해야 한다. 한 프로세스나 쓰레드에서 S 값을 변경하는 동안 다른 프로세스나 쓰레드가 동시에 접근해서 변경할 수 없다.
class Semaphore {
int value; // number of permits
Semaphore(int value) {
// ...
}
void acquire() {
value--;
if (value < 0) {
// add this process/thread to list
// block
}
}
void release() {
value++;
if (value <= 0) {
// remove a process P from list
// wakeup P
}
}
}
세마포어 방식에는 "Busy-Wait" 방식과 "Block-Wakeup" 방식이 있다.
Busy - Wait 방식 (최초의 방식)
- 공유 자원이 모두 사용 중이라면, 프로세스 A가 계속 Wait하는 방식. 자원의 여유가 생기면 자원을 획득하고 자원을 모두 사용했다면 자원을 반납한다.
- 임계 구역에 들어갈 수 있을 때까지 빈 반복문을 수행하기 때문에 다중 프로세스 환경에서 처리기 효율이 떨어진다. 또한 대기 중인 프로세스들 중 어느 것을 먼저 임계 구역에 진입할 지 결정할 수 없다.
- 사용 중인 화장실에 들어가기 위해 다른 일을 하지 않고 오로지 들어갈 때까지 기다리는 상황을 예시로 들 수 있다.
P(s){
while(s <= 0) do wait
s--;
}
///임계영역///
V(s){
s++;
}
Block - Wakeup 방식
- 임계 영역에 진입할 때 S를 감소하는 것이 아니라 먼저 자원의 값을 감소한 뒤, 만약 자원의 개수가 부족하여 사용할 수 없다면 프로세스를 Wait Queue에 추가하는 방법이다.
- 자원이 생기면 Wait Queue에서 프로세스를 꺼내와 wakeup()을 통해 프로세스를 수행한다.
- 사용 중인 화장실에 들어가기 위해 대기 리스트에 자기 이름 적고, 다른 일을 하다가 자기 차례가 오면 화장실에 들어가는 상황을 예시로 들 수 있다.
P(S){
S.value--;
if(S.value < 0){
// add this precess to S.queue;
block();
}
}
V(S){
S.value++;
if(S.value <= 0){
// remove a process P from S.queue;
wakeup(P);
}
}
뮤텍스
Mutual Exclusin으로 상호 배제라고도 한다. 다중 프로세스들의 공유 리소스에 접근하는 것을 조율하기 위해 locking과 unlocking을 사용한다. 뮤텍스는 이진 세마포어와 같이 초기 값을 0과 1로 갖는다. 임계 영역에 들어갈 때 lock을 걸어 다른 프로세스나 쓰레드가 접근하지 못하도록 하고, 임계 영역에서 나올 때 lock을 해제한다.
mutex = 1;
void lock () {
while (mutex != 1)
{
// mutex 값이 1이 될 때까지 대기
}
// 이 구역에 도착했다는 것은 mutex 값이 1이라는 뜻. 이제 뮤텍스 값을 0으로 만들어 다른 프로세스(혹은 쓰레드)의 접근을 제한
mutex = 0;
}
void unlock() {
// 임계 구역에서 수행을 완료한 프로세스는 다른 프로세스가 접근할 개수 있도록 뮤텍스 값을 1으로 만들어 락을 해제.
mutex = 1;
}
뮤텍스 알고리즘으로는 데커 알고리즘, 피터슨 알고리즘, 베이커리 알고리즘 등이 있다.
Dekker's Algorithm
- flag와 turn이라는 변수로 임계 영역에 들어갈 프로세스나 쓰레드를 결정하는 방식이다.
- flag 값은 프로세스 중 누가 임계 영역에 진입할 것인지 나타내는 변수이며, turn 변수는 누가 임계 영역에 들어갈 차례인지 나타내는 변수이다.
While(1) {
flag[i] = true; // 프로세스 i가 임계영역 진입을 시도.
while(flag[j]) { // 프로세스 j가 현재 임계영역에 있는지 확인
if(turn == j) { // 프로세스 j가 임계영역을 사용 중이라면
flag[i] = false; // 프로세스 i의 진입을 취소하고,
while (turn == j); // turn이 j에서 바뀔 때 까지 기다림
flag[i] = true; // j의 turn이 아니면, 즉 임계영역에서 j가 나오면 재진입을 시도
}
}
}
/* 임계영역*/
...
turn = j; // 임계영역의 사용이 끝나면, turn을 넘김
flag[i] = false; // 진입 flag값을 false로 바꾸어 임계영역 사용 완료
...
Peterson's Algorithm
데커 알고리즘과 유사하지만 상대방(다른 프로세스 혹은 쓰레드)에게 진입 기회를 양보한다는 차이가 있다.
do {
flag[i] = true; //프로세스 i가 임계영역에 진입시도
turn = j; // 다른 프로세스에게 진입 양보
while (flag[j] && turn == j); // 다른 프로세스가 진입시도하면 대기
// Critical section
flag[i] = false; //
// Remainder section
} while(true);
Bakery Algorithm
여러 개의 프로세스 혹은 쓰레드에 대한 처리가 가능하며, 가장 작은 수의 번호 표를 가지고 있는 프로세스가 임계 영역에 진입한다.
while(1) {
...
isReady[i] = true; // 번호표를 받을 준비
number[i] = max(number[0~n-1]) +1 // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
isReady[i] = false; // 번호표 수령 완료
for( j =0; j < n; j++ ) { // 모든 프로세스에 대해 번호표를 비교.
while( isReady[j] ); // 비교할 프로세스가 번호표를 받을 때까지 대기
while(number[j] && number[j] < number[i] && j<i);
}
/* 임계영역 */
...
number[i] = 0; // 임계영역 사용 완료
...
}
출처
https://worthpreading.tistory.com/90
https://junsday.tistory.com/32
https://junsday.tistory.com/31
https://dduddublog.tistory.com/25
https://dirmathfl.tistory.com/54
https://jwprogramming.tistory.com/13 https://velog.io/@whwkd11010/Mutex-Semaphores https://preamtree.tistory.com/26
예상 질문 및 답변
세마포어와 뮤텍스의 차이
- 가장 큰 차이점은 뮤텍스는 동기화 대상이 자원의 하나라면, 세마포어는 하나 이상의 자원에서 사용 가능하다. Mutex는 상태가 0과 1인 이진 세마포어라고 볼 수 있다.
- 세마포어는 소유할 수 없는 반면, 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임을 진다. (뮤텍스의 경우 상태가 두 개뿐인 lock이므로 lock을 가질 수 있다.)
- 뮤텍스는 Locking 메커니즘으로 locking을 걸은 쓰레드만이 임계 영역을 나갈 때 락을 해제할 수 있다. 하지만, 세마포어는 Signaling 메커니즘으로 lock을 걸지 않은 쓰레드도 signal을 사용해 락을 해제할 수 있다.
- 세마포어는 시스템 범위에 걸쳐 있고 파일 시스템 상의 파일 형태로 존재하지만, 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 해제된다.
이진 세마포어와 뮤텍스의 차이
뮤텍스와 이진 세마포어의 핵심 차이는 뮤텍스와 의 경우 lock을 설정한(값을 0으로 설정한) 프로세스만이 lock을 해제할 수 있다. 반면, 이진 세마포어의 경우 lock을 설정한 프로세스와 해제하는 프로세스가 서로 다를 수 있다.
'스터디 > CS 스터디' 카테고리의 다른 글
| [네트워크] IP & MAC (10) | 2021.11.30 |
|---|---|
| [운영체제] Deadlock (0) | 2021.11.28 |
| [네트워크] TCP & UDP (0) | 2021.11.26 |
| [네트워크] TLS & SSL Handshake (2) | 2021.11.23 |
| [운영체제] CPU 스케줄링 (0) | 2021.11.19 |
댓글