[운영체제] 병행 프로세스와 상호배제

[한빛아카데미] 운영체제 책으로 학습한 내용을 정리한 것입니다.

 

* 병행 프로세스

- 운영체제가 프로세서를 빠르게 전환하여 프로세서 시간을 나눠서 마치 프로세스 여러 개를 동시에 실행하는 것처럼 보이게 하는 것

- 병행 프로세스는 독립 프로세스와 협력 프로세스로 구분함

- 경쟁 관계에 있는 프로세스들은 서로 정보를 교환하지 않지만, 한 프로세스의 수행이 나머지 프로세스의 수행에 영향을 미칠 수 있기 때문에 상호배제가 필요함

 

* 독립 프로세스

- 단일 처리 시스템에서 수행하는 병행 프로세스

- 다른 프로세스, 데이터와 상태를 공유하지 않고 동작도 재현 가능

- ex.  단일 프로그래밍, 다중 프로그래밍, 다중 처리

 

* 협력 프로세스

- 다른 프로세스에 영향을 주고받으며, 즉 상호작용하며 특정 기능을 수행하는 비동기적 프로세스 

- 대개 제한된 컴퓨터 자원의 효율성을 증대하고, 계산 속도를 향상시키고, 모듈적 구성을 강화하고, 개별 사용자가 여러 작업을 동시에 수행할 수 있는 편의성을 제공하는데 사용함

- ex. 두 프로세스가 동일한 파일을 사용할 때 

 

*  fork/join

- fork : 병행 프로세스를 2개 만듦

- join : 병행 프로세스 2개를 하나로 결합함

 

* 상호배제(Mutual Exclusion)

- 병행 프로세스에서 프로세스 하나가 공유 자원을 사용할 때 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법

- 임계 자원(Critical Resource) : 두 프로세스가 동시에 사용할 수 없는 공유 자원

- 임계 영역(Critical Section) : 임계 자원에 접근하고 실행하는 프로그램 코드 부분

출처 : https://velog.io/@sawol/병행-프로세스와-상호배제

 

* 임계 영역(Critical Section)

- 임계 자원에 접근하고 실행하는 프로그램 코드 부분

- 반드시 한 번에 프로세스 하나만 진입할 수 있어야 함

- 임계 영역이 무한 루프에 빠지지 않도록 주의해야 함

- 임계 영역 이용 시 간편하게 상호배제 구현 가능

 

* 임계 영역 조건

- 상호배제 : 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스는 임계 영역으로 들어갈 수 없음

- 진행 : 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때는 어떤 프로세스가 들어갈지 적절히 결정해야 함

- 한정 대기 : 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하려면 임계 영역에 한 번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한을 둠

 

* 상호배제 방법들

수준	방법	종류
고급	소프트웨어로 해결	- 데커의 알고리즘 - 램포트의 베이커리(빵집) 알고리즘 - 크누스의 알고리즘 - 핸슨의 알고리즘 - 다익스트라의 알고리즘
	소프트웨어가 제공 : 프로그래밍 언어와 운영체제 수준에서 제공	- 세마포 - 모니터
저급	하드웨어로 해결 : 저급 수준의 원자 연산	- TestAndSet(TAS, 테스)

 

* 데커의 알고리즘(Dekker's Algorithm)

- 두 프로세스가 동시에 임계 영역에 진입하려고 시도하면 순서에 따라 오직 하나만 임계 영역에 들어가도록 허용함
-> 두 프로세스가 서로 통신하려고 공유 메모리를 사용하여 충돌 없이 단일 자원을 공유할 수 있도록 개발

- 각 프로세스는 플래그를 설정할 수 있고, 다른 프로세스를 확인한 후 플래그를 재설정할 수도 있음

 

[특징]

- 특별한 하드웨어 명령문이 필요 없음

- 임계 영역 바깥에서 수행 중인 프로세스가 다른 프로세스들이 임계 영역에 들어가려는 것을 막지 않음

- 임계 영역에 들어가기를 원하는 프로세서를 무한정 기다리게 하지 않음

 

* 다익스트라(Dijkstra) 

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

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

 

* 크누스(Knuth) 

- 이전 알고리즘 관계를 분석한 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서를 할당하는 방법

- 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 함

 

* 램포트(Lamport)

- 사람들로 붐비는 빵집에서 번호표를 뽑아 빵을. 사려고 기다리는 사람들에 비유해서 만든 알고리즘

- 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그중 우선순위가 가장 높은 ㅍ로세스에 먼저 프로세서를 할당하는 방법

 

* 핸슨(Brinch Hansen)

- 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것으로 대기 시간과 실행 시간을 이용하는 모니터 방법

- 분산 처리 프로세서 간의 병행성 제어를 많이 발표함

 

* TestAndSet(TAS, 테스)

- 메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어적으로 임계 영역 문제 해결함

- 일부 시스템에서 원자 명령어의 하나로, 읽기와 쓰기 모두를 제공함

- 해당 주소의 값을 읽고 새 값으로 교체하면서 해당 메모리 위치의 이전 값을 돌려줌

- 두 기계 명령어가 존재함

1) 원자적 연산 명령어인 TestAndSet

2) TestAndSet에 지역변수 lock을 설정하는 명령어

 

* 원자적 연산(Atomic Operation)

- 중단 없이 실행하고 중간에 다른 사람이 수정할 수 없는 최소 단위 연산

- 메모리의 1비트에서 작동하고, 대다수 기계에서 워드의 메모리 참조, 할당은 원자적이지만 나머지 많은 명령은 원자적이지 않음

 

* TestAndSet 명령어 장/단점

장점	사용자 수준에서 가능함  - 메인 메모리를 공유하는 다중 프로세서나 단일 ㅍ로세서에서 프로세스 수에 관계없이 적용할 수 있음  - lock 변수 수에 상관없이 구현할 수 있음  - 구현이 단순하고 확인이 용이함  - 다중 임계 영역을 지원함
단점	바쁜 대기 발생  - 프로세서 시간 소모가 큼  - 대기 프로세스는 비생산적, 자원이 소모되는 대기 루프에 남음 기아 상태 발생  - 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상을 대기하는 경우 가능함 교착 상태 발생  - 플래그는 우선순위가 낮은 프로세스가 재설정할 수 있지만, 우선순위가 높은 프로세스가 선점함  - 우선순위가 낮은 프로세스는 lock을 가지고, 우선순위가 높은 프로세스가 이것을 얻으려고 시도할 때 높은 우선순위 프로세스는 무한정 바쁜 대기가 될 것

 

* 세마포(Semaphore)

- 값이 음이 아닌 정수인 플래그 변수

- 상호배제에 사용할 뿐만 아니라 다양한 연산의 순서 제공

S : 음이 아닌 정수형 변수
P(S) : 임계 영역에 진입하는 연산(검사, Proberen) -> 프로세스를 대기하게 하는 wait 동작
V(S) : 임계 영역에 빠져나오는 연산(증가, Verhogen) -> 대기 중인 프로세스를 깨우려고 신호를 보내는 signal 동작

- 세마포의 종류로는, 이진 세마포(Counting Semaphore)와 계수 세마포(Binary Semaphore)가 존재함

 

* 이진 세마포(Counting Semaphore)

- 세마포 S를 상호배제에 사용하고, 1 또는 0으로 초기화하고, P와 V의 연산을 교대로 실행함

P(S) : S를 검사하여 양수면 S를 0으로 재설정한 후 진행하고, 아니면 S를 준비 큐로 되돌림V(S) : S를 1로 설정하고 준비 큐에 있는 프로세스를 시작함

 

* 계수 세마포(Binary Semaphore)

- 유한한 자원에 접근하는 것을 제어할 수 있으므로, 여러 번 획득하거나 해제할 수 있도록 count를 자원의 사용 허가 값으로 사용함- 그리고 사용 가능한 자원 수로 초기화하므로, count를 초기의 세마포 수로 초기화함

 

* 세마포 문제점

- wait이나 signal 연산을 생략하면 상호배제 문제가 발생하고, wait 연산 때문에 대기하는 프로세스들이 교착 상태에 빠질 수 있다는 취약점 발생 -> wait 연산을 시작하여 세마포를 사용하는 동안 프로세스가 다른 경로를 선택할 수 없기 때문

 

* 모니터(Monitor)

- 위 세마포 문제점을 극복하려고 등장했으며,

 핸슨이 제안하고 호가 수정함

- 공유 자원과 공유 자원의 임계 영역을 관리하는 소프트웨어 구성체 - 사용자 사이에서 통신하려고 동기화하고, 자원에 배타적으로 접근할 수 있도록 프로세스가 사용하는 병행 프로그래밍 구조- 다중 프로세스 환경에서 프로세스 하나를 언제라도 모니터에서 실행할 수 있도록 보장함