Home 상호배제
Post
Cancel

상호배제

Posted Jun 21, 2021 Updated Mar 6, 2023
By Leeseojune
14 min read

상호배제

[TOC]

1. 상호배제와 동기화

  1. 상호배제(utual Exclusion)

    특정 공유자원을 한 순간에 한 개의 프로세스만 사용할 수 있는 경우 프로세스 하나가 데이터에 접근하는 동안 다른 프로세스가 해당 데이터를 접근할 수 없게 하는 것

  2. 동기화(Synchronous)

    • 공유자원을 동시에 사용하지 못하게 프로세스들이 상호 협력하면서 수행하는 것
    • 순차적 재사용이 가능한 자원의 공유를 위해 질서 있는 실행을 보장하고 데이터 일관성 유지해줌
    • 경쟁상태(Race Condition) - 여러 개의 서로 다른 프로세스가 동일한 자료에 접근, 자료를 조작하여 그 결과가 접근 순서에 따라 달라지는 상황 => 동기화 필요 => 임계영역을 이용한 상호배제로 구현

2. 프로세스 동기화

임계영역(critical section, CS) 개념

동시에 접근해서는 안 되는 공유자원을 사용하고 있는 코드 블록

경쟁상태(Race Condition)이 발생한다.

임계영역 문제의 해결

1. 상호배제 Method 사용 (Mutual exclusion primitives, 상호배제 기본연산)

  1. 진입영역 - 임계영역 진입 전 검사(enterCS() primitives)
    • CS에 진입하기 전 검사, 다른 프로세스가 CS안에 있는지 검사
  2. 출구영역
    • CS를 벗어날 때 후처리, CS를 벗어났음을 알림

운영체제 - 병행성(임계영역, 세마포어, 리눅스의 병행성, 뮤텍스, 스레드)

임계영역에서 자원의 공유 문제를 해결하기 위한 3가지 요구조건

1. 상호배제(Mutual exclusion)
  • 임계영역에 프로세스가 있으면, 다른 프로세스의 진입 금지
2. 진행(Progress)
  • 임계영역(CS)안에 있는 프로세스 외에는 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
  • 임계영역 안에 프로세스가 없는 경우 다음 들어갈 프로세스 선정이 무한정 미루어져서는 안됨
3. 한정된 대기(Bounded waiting)
  • 프로세스의 CS진입은 유한시간 내에 허용되어야 함

임계영역의 보호 시 고려할 사항

  1. 임계영역을 수행 중에 있는 프로세스는 교착상태가 발생해서는 안됨 (회피해야 함)
  2. 임계영역을 수행 중에 있는 프로세스는 인터럽트가 발생하지 않도록 해야 함
  3. 임계영역을 수행 중에 있는 프로세스는 무한루프가 발생하지 않도록 해야함

임계영역문제의 소프트웨어적인 해결 : 프로시저가 2개라는 전제

1. 알고리즘 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

proceduer Pi
begin
	repeat
		while turn = j do skip;
			critical section (임계영역)
		turn = j;
			remainder section (잔류영역)
	until false;
end
begin
	turn = 0;
	parbegin
		P0;
		P1;
	parend
end;
  • 두 프로세스(Pi, Pj) 병행 수행
  • 공유변수 tur을 통해 두 개의 프로세스(Pi, Pj)에 대한 상호배제 보장
  • turn = i 이면 프로세스 Pi가 임계구역에 들어갈 수 있다.
  • 진입영역에서 상대방 프로세스가 진입했는지 확인, 출구영역에서 turn을 상대방에게 넘겨준다.
문제점
  1. 반드시 번갈아 가면서 실행되어야 한다. –> Pi가 연속 두 번 실행할 수 없다.
  2. Pi가 나오면서 turn을 j로하면 Pj가 임계구역에 진입못했을 시 아무도 임계구역에 없으므로 –> 진행문제 발생

알고리즘 2

1
2
3
4
5
6
7
8
9
10

var flag : array[0..1] of boolean;
proceduer Pi
begin
	repeat
		while flag[j] do skip;
		flag[i] := true;
			critical section (임계영역)
		flag[i] := false;
			remainder section (잔류영역)
	until false;
  • 알고리즘1에서의 문제는 어떤 프로세스가 임계구역에 들어갈 수 있지만 상태를 기억하지 않아 문제가 발생함. -> turn을 배열로 대체하고 배열값을 false로 초기화 -> 진행 문제 해결
문제점

t0 : Pi가 while문을 수행해서 flag[j] = false임을 안다.

t1 : Pj가 while문을 수행해서 flag[i] = false 임을 안다.

t2 : Pi가 flag[i] = true하고 임계영역에 들어간다.

t3 : Pj가 flag[j] = true하고 임계영역에 들어간다.

상호배제 위반

#### 알고리즘 3

var flag : array[0..1] of boolean;
proceduer Pi
begin
	repeat
		flag[i] := true;
		while flag[j] do skip;
			critical section (임계영역)
		flag[i] := false;
			remainder section (잔류영역)
	until false;
  • 알고리즘2에서 상호배제 문제점을 해결하기 위해 자신의 flag를 먼저 true 시킨 후 진입 -> 상호배제 문제 해결
문제점

t0 : Pi가 flag[i] = true로 한다

t1 : Pj가 flag[j] = true로 한다.

진행문제 발생

데커(dekker) 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var flag : array[0..1] of boolean;
proceduer Pi
begin
	repeat
		flag[i] := true;
		while ( flag[j] ) do
		begin
			if ( turn = j ) then
			begin
				flag[i] = false;
				while ( turn = j ) do skip;
				flag[i] = ture;
			end;
		end
			critical section (임계영역)
		turn = j;
		flag[i] := flase;
			remainder section (잔류영역)
	until false;
  • 두 개의 프로세스를 위한 최초의 소프트웨어 해결책
  • boolean flag[i] 와 int turn의 공유변수를 가진다.
  • 초기값은 flag[i] = flag[j] = false; turn = 0 (또는 1)을 갖는다.

피터슨 알고리즘

1
2
3
4
5
6
7
8
9
10
11

var flag : array[0..1] of boolean;
proceduer Pi
begin
	repeat
		flag[i] := true;
		turn := j
		while ( flag[j] an turn = j ) do skip
			critical section (임계영역)
		flag[i] := false;
			remainder section (잔류영역)
	until false;
  • 데커 알고리즘보다 간단하게 구현된 알고리즘 하지만 상대방에게 진입 기회를 양보

N개 프로세스를 위한 상호배제 알고리즘

1. 알고리즘의 종류
  1. 다익스트라 알고리즘 : 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결. 실행시간이 가장 짧은 프로세스에 할당하는 방법
  2. 크누스 알고리즘 : 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 할당
  3. 램포트 알고리즘 : 빵집에서 번호표를 뽑아 빵 사가려고 기다리는 사람과 비슷하여 빵집알고리즘이라고도 불림. 준비 상태큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 높은 프로세스에 먼저 할당함.
2. 램포트 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

procedure Pi
var option : array[0..n-1] of boolean;
	number : array[0..n-1] of integer;
	
repeat
	option[i] := true;
	number[i] := max(number[0], number[1] ..., number[n-1]) + 1;
    option[i] := false
    for j := 0 to n-1
    	begin
    		while option[j] do skip;
    		while ( number[j] != 0 ) and (number[j], j) < (number[i], i) -- (다)
    			do skip;
    		end
    			critical section (임계영역)
    	number[i] := 0;
    		remainder section (잔류영역)
until false;
  • (다)의 명령어 대신 number[j]!=0 and number[j] < number[i]로 바꾸면 상호배제를 위반한다.
  • (다)의 명령어 대신 (number[j], j) < (number[i], i)로 바꾸면 진행을 위반한다.

소프트웨어를 이용한 해결방법의 문제점

  1. 속도가 느리다.

  2. 구현이 복잡하다.

  3. 임계영역 실행 중 선점될 수 있다. -> 공유데이터 수정 중에는 인터럽트 억제 -> 오버헤드 발생

  4. 바쁜 대기 발생 - 스핀락(spin lock)으로 인해 발생

    -> ‘바로 사용될 수 있는데 문맥교환을 해 가면서 바꿀 필요가 있는가’라는 컨셉에서 개발

    -> 문맥교화을 줄 순 있으나 CPU 과도한 낭비로 인해 가급적 sleep하는 알고리즘을 사용하는 것이 좋다.

    바쁜 대기?

    어떠한 특정 공유자원에 대하여 두 개 이상의 프로세스나 스레드가 그 이용 권한을 획득하고자 하는 동기화 상황에서 그 권한 획득을 위한 과정에서 일어나는 현상

하드웨어를 이용한 해결방법

1. TestAndSet(TAS) 명령어

  • Test와 Set을 한 번에 수행하는 기계어

  • 기계어라는 의미 : 실행 중 다른 interrupt를 받지 않아 선점되지 않는다는 것이 보장된다.

  • TestAndSet의 구조

    1
2
3
4
5

    boolean TestAndSet(boolean *target){
	boolean temp = *target;
	*target = true;
	return temp;
}

    -> TestAndSet(lock)을 호출하면 lock값을 return 해주고 내부적으로 lock은 true를 가지고 있다.

    1
2
3
4
5
6

    repeat
	while ( TestAndSet(lock)) do skip;
		critical section (임계영역)
	lock = false;
		remainder section (잔류영역)
until false;
    • 어떤 프로세스가 먼저 임계영역에 들어가면 lock은 현재 false이므로 임계영역에 들어가고 lock을 true로 한다.
    • 다음에 들어오는 프로세스는 TestAndSet(lock)을 호출하면 true가 반환되므로 대기한다.
    • 임계영역을 다 쓴 프로세스가 lock을 false로 하는 순간 다음 프로세스가 진입한다.
    문제점

    • while문에 여러 개의 프로세스가 대기하고 있다고 가정해 보면 lock = false되는 순간 가장 먼저 TestAndSet(lock)을 호출하는 프로세스가 진입한다.

      -> 원자적으로 실행되므로 먼저 TestAndSet을 호출하면 다른 프로세스는 lock이 true가 된다.

      -> 하드웨어 성능으로 계속 늦게 호출하는 프로세스는 제한된 대기 문제가 발생할 수 있다.

      ​ (멀티 프로세서 환경에서는 거의 발생하지는 않으나 가능할 수도 있다.)

CS, OS, Mutual Exclusion
CS OS Mutual Exclusion
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents