| 상 | Mutual Exclusion(상호배제)/뮤텍스 | [정의] 다중 프로그래밍 환경에서 공유 불가능한 자원의 동시 사용을 피하기 위한 Locking/Unlocking을 사용해 동시성을 제어하는 기법 [요구조건] 상호배제 조건, 진행 조건, 한정 대기 조건, 가정 조건 [구현기술] HW방식: TAS ( Test And Set ) SW방식: 데커알고리즘, 피터슨알고리즘, 램포트베이커리 알고리즘 |
| 토픽 이름 | Mutual Exclusion |
| 분류 | OS > 병행 제어 > Mutual Exclusion |
| 키워드(암기) | 램포트, 피터슨, 데커알고리즘, 세마포어 , swap, test and set, 인터럽트 금지 |
| 암기법(해당경우) |
기출문제
| 번호 | 문제 | 회차 |
| 1 | 분산처리 시스템에서 Mutual Exclusion을 구현하기 위한 Time Ring 알고리즘과 Time Ordering 알고리즘의 동작을 설명하시오 | 기96-응-2-3 |
| 2 | 운영체제(OS)에서의 상호배제(Mutual Exclusion)개념을 설명하고 이를 구현하는 방법을 하드웨어적 해결방안 및 소프트웨어적 해결방안으로 구분하여 설명하시오. | 기98-응-1-8 |
| 3 | 상호배제에 대하여 설명하고 상호배제 구현을 위한 데커(Dekker), 피터슨(Peterson) 알고리즘에 대해 설명하시오. | 모1410-응-2-4 |
| 4 | 운영체제(OS)에서의 상호배제(Mutual Exclusion)개념을 설명하고, 세마포어(Semaphore)를 통한 프로세스 동기화에 대해 설명하시오. | 모1610-응-2-1 |
| 5 | 병행프로세스의 동시성 제어를 위한 상호배제 기법을 HW기법과 SW기법으로 나누어서 설명하시오. | 모1704-응-4-1 |
| 6 | 운영체제(OS)에서 상호배제(Mutual Exclusion)에 대해 설명하고, 상호배제 구현 방안인 데커 알고리즘, 피터슨 알고리즘에 대해 설명하시오. | 합숙2018-관-2일-2-5 |
I. 병행프로세스의 동시성 제어를 위한 상호배제(Mutual Exclusion)의 개요
가. 상호배제(Mutual Exclusion) 정의
- 경쟁조건을 방지하기 위해 특정 프로세스가 공유자원을 사용하고 있을 경우 다른 프로세스가 해당 공유자원을 사용하지 못하게 제어하는 기법
 |
- 상호배제 해결을 위한 요구조건과 상호배제에 대한 소프트웨어적 또는 하드웨어적 해결방안 연계
나. 상호배제 해결을 위한 요구조건
| 구분 | 설명 | 관련사항 |
| 상호배제 조건 | 두 개 이상의 프로세스들이 동시에 임계영역에 있어서는 안됨 | 임계영역 |
| 진행 조건 | 임계영역 밖의 프로세스가 다른 프로세스의 임계영역 진입을 막아서는 안됨 | 교착상태 기아상태 |
| 한계대기 조건 | 어떤 프로세스도 임계구역 진입이 무한정 연기되어서는 안됨 | |
| 상대속도 조건 | 프로세스들의 상대적인 속도에 대해서는 어떠한 가정도 하지 않음 |
II. 상호배제 해결방안
가. 상호배제 해결을 위한 SW 방법
| 해결방안 | 설명 |
| 데커(Dekker) 알고리즘 |
- 두 개 프로세스를 위한 상호배제에 대한 최초 소프트웨어 해결법 - 공유변수 : 두 개 boolean flag(사용의사)와 int turn(차례) - 차례설정 : turn(차례)를 자신 프로세스에게 설정 |
| 피터슨(Peterson) 알고리즘 |
- 공유변수 : 두 개 boolean flag(사용의사)와 int trun(차례) - 의사표시 : 임계영역에 진입하려면 먼저 flag(사용의사)를 true 설정 후 임계영역 진입 - 차례양보 : turn(차례)를 다른 프로세스에게 양보 |
| 램포트(Lamport) 알고리즘 | - 분산처리 환경에서 유용한 알고리즘으로 수행순서를 위한 번호를 부여받고 낮은 번호가 먼저 수행되는 알고리즘 |
| 세마포어(Semaphores) | - 운영 체계 또는 프로그램 작성 내에서 상호배제를 지원하는 메커니즘 - 세마포어 변수(S) 및 두 개의 연산(P, V)으로 임계영역에 접근하는 잠금장치에 대한 이론적 기반 |
나. 상호배제 해결을 위한 HW 방법
| 해결방안 | 설명 |
| 인터럽트 사용금지 | - 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음 - 단일 프로세서에서 가능하고 멀티 프로세서에는 적용할 수 없음 |
| Test and Set | - HW에서 한 워드(word)의 내용을 검사하고 변경하는 명령어의 제공 function Test-and-Set(var target: boolean): boolean:
begin Test-and-Set := target: Target := true; end; |
| Swap | - HW에서 두 워드간에 내용을 원자적으로 교환할 수 있는 명령어 제공 Procedure Swap (var a, b: boolean);
var temp: boolean; begin temp := a; a := b; b := temp; end; |
III. 상호배제 기법의 발전
- 상호배제 기법은 예전 기법의 단점을 보완하면서 점점 진화 발전해오고 있음
- 더 많은 프로세스가 공유자원을 공유하는 환경에서 개발자가 쉽게 상호배제를 구현할 수 있도록 더욱 진화 발전해갈 것으로 예상됨
반응형
'정보관리기술사 > CA_OS' 카테고리의 다른 글
| 우선순위 역전 (0) | 2023.11.24 |
|---|---|
| Semaphore (1) | 2023.11.23 |
| RAID (1) | 2023.11.21 |
| HA(High Availability) (1) | 2023.11.20 |
| 결함허용 컴퓨터(FTS) (2) | 2023.11.19 |