동기화, 임계구역, 데드락, 상호배제

이하연·2021년 8월 15일

OS 공통CS 면접준비 운영체제

[OS] 운영체제

목록 보기

6/12

동기화

독립적인 프로세스

시스템에서 실행중인 다른 프로세스들에게 영향을 주거나 받지 않는 프로세스

협력적인 프로세스

시스템에서 실행중인 다른 프로세스들에게 영향을 주거나 받는 프로세스

배경

협력적인 프로세스는 논리 주소 공간을 직접 공유하거나 파일 또는 메시지에 의해서 공유가 이루어지는데, 이는 스레드를 통해 도달할 수 있습니다. 이러한 경우 데이터의 비일관성을 초래할 수 있기 때문에, 데이터의 일관성 유지를 위해 데이터나 흐름에 대한 동기화가 매우 중요합니다.

정의

여러 프로세스가 하나의 공유된 자원을 동시에 접근하려고 할때, 이들에게 순서를 정해주어 공유하는 데이터의 일관성을 유지하는 것
프로세스 동기화

하나의 자원은 한 순간에 한 프로세스만 이용하도록 제어하는 것
스레드 동기화

하나의 코드블록 or 메소드를 한 순간에 하나의 스레드만이 이용하도록 보장하는 것

왜 필요할까?

어떠한 데이터에 동시 작업이 일어났을 경우, 처리순서에 상관없이 원하는 결과값을 얻기 위해서 동기화가 필요합니다.
만약 일관성이 깨지게 된다면 한 순간에 하나의 데이터 값이 여러개가 될 수 도 있습니다.

목적

데이터 일관성을 보장하기 위해서

→ 동기화가 없다면 데이터 일관성이 깨집니다.
원하는 결과값을 도출하도록 임계구역 문제를 해결하기 위해서
프로세스의 실행 순서를 원하는대로 제어하기 위해서
busy wait과 같은 비효율성을 제거하기 위해서

(busy wait : 의미없는 코드를 반복 수행하며 기다리는 것 )

동기화 문제를 임계구역 문제라고도 하는데, 이때 임계구역이 무엇인지에 대해서 말씀드리겠습니다.

경쟁상태 ??

임계구역

정의

여러 개의 스레드가 수행되는 시스템에서 각 스레드들이 공유하는 데이터를 변경하는 코드 영역을 말합니다.

공유 자원에 접근하는 코드의 일부로, 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스가 그들의 임계구역에 들어갈 수 없습니다.

임계구역 문제

임계구역으로 지정되어야 할 코드 영역이 임계구역으로 지정되지 않았을 때 발생할 수 있는 문제

3가지 조건

임계구역을 해결하기 위해서 3가지 조건이 필요합니다.

상호배제,상호배타 Mutual exclusion
- 오류가 발생하지 않도록, 오직 한 스레드만이 진입 가능한 것입니다.
- 한 스레드(프로세스)가 임계구역에서 실행 중이라면 다른 스레드(프로세스)는 이 구역을 접근할 수 없습니다.
진행 Progress
- 임계구역에 프로세스가 존재하지 않는 경우, 다른 프로세스가 접근할 수 있도록 만들어줘야 합니다.
- 임계구역에 들어간 프로세스가 없는 상태에서 들어가려는 프로세스가 여러 개 있다면 어떤 프로세스가 들어갈지를 결정하는 것으로, 이것은 유한 시간 이내에 이루어져야 합니다.
유한 대기 Bounded waiting = 한정된 대기
- 다른 프로세스의 *기아를 방지하기 위해, 한 번 임계 구역에 들어간 프로세스는 그 다음에 임계 구역에 들어갈 때 제한을 두어야 합니다.
- 임계구역으로 진입하기 위해서 대기하는 모든 스레드는 유한 시간이내에 해당 임계구역으로 진입할 수 있어야 합니다.
- 진행과 다른 점
  - 진행은 말 그래도 임계구역 해결을 위해 코드 실행이 멈추지 않는 것을 의미
  - 유한대기는 임계구역 코드 실행에 들어간 프로세스 외 나머지 프로세스들이 기아 현상이 나타나지 않도록 하기 위해 이미 임계구역을 실행한 프로세스를 제한하는 것
*기아 : 프로세스가 임계 영역에 들어가기 위해 무한정으로 기다리는 현상으로 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 발생합니다.

해결방법

임계 영역의 동시 접근을 해결하기 위한 방법으로 3가지가 존재합니다.

Lock
- 하나의 스레드나 프로세스가 자원을 사용하고 있는 동안에 잠궈서 접근을 못하게 하는 방식
- 문제점
  
  특정한 상황에서 제대로 작동하지 않는 문제가 있다
  
  예를 들어, A스레드가 lock함수를 실행하여 무한루프를 돌게끔 변수의 값을 변경하기 전에 인터럽트가 걸려 값을 변경하지 못하고 다른 스레드가 lock 함수에 들어오게 된다면, 두개의 스레드가 임계 영역에 동시접근하는 상황이 발생합니다.
- 해결방법
  - 소프트웨어 알고리즘 (피터슨 알고리즘), 더 이상 쪼개지지 않는 하드웨어 명령어로 구현하는 방법, 인터럽트를 disable하고 enable하는 방법
Semaphore ( 세마포어와 뮤텍스 —> 뮤텍스 아직 안함! )
- 사전적 의미 : 수기 신호
- 동시에 자원을 접근 할 수있도록 허용한 공유 자원의 수를 나타내는 것
- 두개의 Atomic한 함수로 제어되는 정수 변수를 이용한 교착 상태 해법
- 이진 세마포어( 뮤텍스) , 카운팅 세마포어
  - 뮤텍스 - 다른 프로세스간의 동기화를 할 때 사용, 임계 영역을 가진 스레드들의 실행시간을 서로 겹치지 않게 하나의 프로세스나 스레드를 단독으로 실행하게 하는 것
  - 세마포어와 뮤텍스 차이
    - 세마포어(Semaphore) : 공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것
    - 뮤텍스(Mutex) : 공유된 자원의 데이터를 여러 쓰레드가 접근하는 것을 막는 것
- 문제점
  
  세마포어의 두가지 연산 P,V가 있는데 P나V연산 중 한개를 생략하게 되면, 상호배제 문제와 P연산 때문에 대기하고 있는 프로세스들이 교착상태에 빠질 수 있다는 취약점이 존재한다. P 연산이 시작되면(세마포어가 사용되고 있는 동안) 프로세스는 다른 경로를 선택할 수 없다. 프로세스는 한 번에 오직 한 세마포어만 대기할 수 있으므로 자원을 할당하는 상황에서 교착상태를 가져올 수도 있다.
  
  (P: 검사 proberen , 프로세스를 대기시키는 wait 동작으로 임계 영역에 진입하기 위한 연산)
  
  (V: 증가 verhogen, 대기 중인 프로세스를 깨우는 신호를 보내는 signal 동작으로 임계영역에 나오기 위한 연산)
Monitor
- 한 프로세스내에 있는 하나의 스레드만 자원에 접근이 가능하다.
  
  ( 하나의 프로세스 안에 다른 스레드간 동기화를 할 때 사용한다 )
- 모니터는 개념적으로 이진 세마포어만 가능하다.
- 모니터는 하나 이상의 프로시저(연산 동작들)와 초기화 코드, 그리고 공유 데이터로 구성된 소프트웨어 모듈로 이루어진 객체다. 이는 데이터와 프로시저들이 순차적으로 재사용 가능한 특정 공유 자원을 할당하는 데 필요하다. 모니터 안에서 정의된 프로시저는 모니터 내에서 지역적을 정의된 변수와 형식 매개변수들만 접근할 수 있다. 마찬가지로 모니터의 지역 변수들은 지역 프로시저만 접근한다.

데드락 Deadlock

정의

무한 대기 상태
교착 상태란, 두 개 이상의 작업이 서로 상대방의 작업을 끝나기만을 기다리고 있기에, 다음 단계로 진행하지 못하는 상태를 의미

원인

제한된 자원을 효율적으로 사용하려다가 일어나는 부작용

시스템 효용성을 높이려다 일어나는 부작용

해결방안

운영체제가 교착상태를 해결하지 못하면 시스템 운영자나 사용자는 작업을 교체하거나 종료하는 외부 간섭으로 해결해야한다. 교착 상태는 하나 이상의 작업을 영향을 주기에 무한 대기나 기아상태보다 더 심각한 문제를 일으킨다.

4가지 필요 조건

교착상태가 발생하기 위해서는 아래와 같이 4가지 필요 조건이 성립해야 합니다.

만약 네가지 조건이 해당된다고 해서, 반드시 교착상태가 일어나는 것이 아니라 발생할 확률이 생기는 것입니다.

또한, 아래와 같은 조건이 한개라도 성립하지 않으면, 필수조건이 충족되지 않는 것이므로 교착상태가 발생하지 않습니다.

상호 배제 Mutual exclusion
- 한 프로세스가 자원을 사용하고 있다면, 다른 프로세스는 사용할 수 없습니다.
- 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구하는 것
- A젓가락은 한 철학자가 사용하고 있다면, 다른 사람들은 A젓가락은 사용할 수 없으므로 상호배타적
점유 대기 Hold and wait
- 한 프로세스가 자원을 가지고 있는 상태에서 대기합니다.
- 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다리는 것
- 철학자는 왼쪽 젓가락을 가지고 있는 상태에서 오른쪽 젓가락을 집기 위햇 대기합니다.
비선점 No preemption
- 한 프로세스가 자원을 수행하는 중에는 다른 프로세스가 중간에 끼어들 수 없습니다.
- 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없는 것
- 한 철학자가 젓가락을 집은 상태에서 다른 철학자가 이 젓가락을 뺏을 수 없습니다.
순환대기 Circular wait
- 프로세스가 요구하는 자원의 방향이 원형을 이룹니다.
- 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 것
- 모든 철학자는 왼쪽 젓가락부터 집을 수 있습니다.

교착 상태는 매우 드물게 일어나는 현상이지만, 한번 교착상태에 빠지면 프로세스가 무한 루프에 빠져 수행하지 못하고 해당 프로세스가 가지고 있는 자원 또한 아무도 사용하지 못합니다. 이는 컴퓨터 환경에 매우 치명적이고, 교착상태에에 의한 오류를 해결하기 또한 매우 어렵습니다.

교착 상태 처리

교착 상태 방지
- 필요조건 4가지 중 최소 한가지를 미충족 시키도록 만드는 것입니다.
- 상호 배타 - 독점적으로 사용할 수 있는 자원을 없애기
- 보유 및 대기 - 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법, 전부 할당하거나 아무것도 할당하지 않게 하기
- 비선점 - 모든 자원을 빼앗을 수 있도록 만드는 방법
- 환형대기 - 프로세스들을 한 줄로 길게 늘어뜨리기 ( 한방향 ) , 정해진 자원만 순서대로 실행하는 거
교착 상태 회피
- 교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
- 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 발생 범위라면 대기시킨다.
- 자원을 많이 할당할수록 교착 상태가 발생할 확률이 커진다.
- 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정상태로 나뉘어진다.
- 할당된 자원이 많으면 불안정이고, 할당 자원이 적으면 안정상태이다.
- 문제점
  - 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다
  - 시스템의 전체 자원수가 고정적이어야 한다.
  - 자원이 낭비된다.
교착 상태 검출 및 복구
- 교착 상태가 되도록 허용한 후 검출하여 복구 시키는 방법
- 가장 현실적인 방법
- os가 프로세스의 작업을 관찰하면서 교차 상태 발생여부를 계속 주시하는 방식
- 타임 아웃을 사용하여 가벼운 교착 상태를 검출
- 교착상태를 유발한 프로세스를 강제 종료
  - 교착상태를 일으킨 모든 프로세스를 동시에 종료
  - 교착상태를 일으킨 프로세스 중 하나를 골려 순서대로 종료
    - 우선 순위 낮은놈
    - 우선 순위가 같은 경우 작업 시간이 짧은 놈
    - 자원을 많이 사용하는 프로세스를 먼저 종료
교착 상태 무시

대부분 교착 상태는 드물게 발생하고 예방,회피,탐지 및 복구는 비용이 많이 들기때문에 그냥 무시하는 방식

데드락 vs 기아

1) 데드락

자원을 자유롭게 할당하게 자원이 부족한 결과
여러 프로세스가 동일 자원 점유를 요청할 때 발생

2) 기아

기다리는 결과를 예방하기 위해 자원할당할 때 발생하는 결과
여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 발생
해결 방안
- 프로세스 우선순위 수시 변경을 통해 각 프로세스 높은 우선순위 가지도록 기회 부여
- 오래 기다린 프로세스의 우선순위 높이기
- 우선순위가 아닌 요청 순서대로 처리하는 요청큐 사용

Busy-wait : 프로세스P가 자원이 모두 사용 중이라면, wait하는 방식이다. 자원의 여유가 생기면 s—자원을 획득하고, 자원을 모두 사용했다면, 자원을 s++ 자원 할당

block-wakeup : 어떤 스레드가 critical section에 들어가게 되면 wait for single object(mutex handle)을 무한 Loop 돌면서 대기하는것이 아니라wait queue에 들어가 대기하게 된다. ( 세마포어 )

만약 너무 빨리 해당 critical section이 끝난다면, 빈번한 context switching으로 인해 block and wake up 보다 busy waiting 방식을 쓰는게 좋겠다.

Trello