[CS] Process Synchronization and Mutual Exclusion #1

이 포스팅은 한국기술교육대학교 김덕수 교수님의 운영체제 강의를 참고하여 작성되었습니다.

 

Mutual Exclusion Solutions

SW solutions
• Dekker’s algorithm (Peterson’s algorithm)
• Dijkstra’s algorithm, Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm

HW solution
• TestAndSet (TAS) instruction

OS supported SW solution
• Spinlock
• Semaphore
• Eventcount/sequencer

Language-Level solution
• Monitor

 

동기화 (Synchronization)

프로세스들이 서로 동작을 맞추는 것

프로세스들이 서로 정보를 공유하는 것

 

비동기적 (Asynchronous) : 프로세스들이 서로에 대해 모름

병행적 (Concurrent) : 여러 개의 프로세스들이 동시에 시스템에 존재

병행 수행 중인 비동기적 프로세스들이 공유자원에 동시 접근할 때 문제가 발생할 수 있음

 

공유 데이터 (Shared data or Critical data) : 여러 프로세스들이 공유하는 데이터

임계 영역 (Critical section) : 공유 데이터를 접근하는 코드 영역(code segment)

상호 배제 (Mutual exclusion) : 둘 이상의 프로세스가 동시가 critical section에 진입하는 것을 막는 것

 

critical section 예시

Race condition에서는 실행 순서에 따라 결과가 달라진다.

이를 해결하기 위해서 우리는 상호 배제를 한다.

Mutual Exclusion Methods

Mutual exclusion primitives(기본 연산)

 

- enterCS() primitive

Critical section 진입 전 검사

다른 프로세스가 critical section안에 있는지 검사

 

- exitCS() primitive

Critical section을 벗어날 때의 후처리 과정

Critical section을 벗어남을 시스템이 알림

 

위 함수를 만들기 위해 다음 세 가지 조건을 고려해야 한다.

(1) ME(Mutual exclusion) : Critical section (CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지

(2) Progress : CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안 됨

(3) Bounded waiting : 프로세스의 CS 진입은 유한 시간 내에 허용되어야 함

 

Dekker's Algorithm

Two process ME을 보장하는 최초의 알고리즘

김덕수 교수님 운영체제 강의 中

 

N-Process Mutual Exclusion

다익스트라 Dijkstra

- 최초의 프로세스 n개의 상호 배제 문제를 소프트웨어적으로 해결

- 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공

김덕수 교수님 운영 체제 강의자료 中

flag[] 값

idle : 프로세스가 임계 지역 진입을 시도하고 있지 않을 때

want-in : 프로세스가 임계 지역 진입 시도 1단계일 때

in-CS : 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때

 

SW solution들의 문제점

- 속도가 느림

- 구현이 복잡

- ME primitive 실행 중 preemption 될 수 있음

- Busy waiting

 

 

긴 글 읽어주셔서 감사드립니다.

22.12.16