운영체제 - 프로세스 동기화

1. 동시성 & 병렬성

동시성 (Concurrency)

동시성은 하나의 시스템이 여러 작업을 동시에 처리하는 것 처럼 보이게 하는 것이다

• 동시성은 둘 이상의 작업이 동시에 실행되는 것을 의미한다. 이때 '동시' 라는 의미에서는 병렬성과 동시성의 한글 의미가 헷갈릴 수 있는데 병렬성(Parallelism) 이 물리적으로 동시에 실행하는 것이라면, 동시성(Concurrency) 은 동시에 실행하는 것 처럼 보이게 하는 것으로 이해하면 된다
• 1개의 CPU core 가 있고 4개의 테스크가 있다고 가정하면, 프로세스 or 쓰레드를 번결아가면서 조금씩 처리함 으로써 마치 프로그램이 동시에 실행되는 것 처럼 보이는 것이다
• 동기, 비동기의 예시로 1인 카페와 스타벅스를 예시로 들 수 있는데 동시성의 경우 1인 카페에서 일하는 사람(core) 1명이 주문(task)이 4개가 들어온경우 각각의 주문을 레시피별로 번갈아가면서 작업하면 4개의 음료가 거의 동시에 나오는것처럼 보이게 할수 있는것과 같다

 

병렬성 (Parallelism)

병렬성은 여러 작업을 실제로 동시에 처리하는 것이다

• 병렬성은 직관적으로 명령어를 메모리에서 뽑아 해석하고 실행하는 반도체 유닛인 여러개의 CPU core 에 맞춰 여러개의 프로세스, 쓰레드를 돌려 병렬로 작업들을 동시 수행하는 것을 말한다
• 병렬성은 멀티코어 컴퓨터에서 많이 사용되며, 실행시간을 줄이거나 처리량을 늘리는데 사용된다
• 스타벅스에 음료 주문이 들어가면 각 기계별 작업자가 분담하여 동시에 작업을 수행하는 것을 비유로들 수 있다

 

2. 프로세스 동기화

IPC (Interprocess Communication) 는 협력 프로세스 사이에서 서로 데이터를 주고 받는 방법을 말한다
(참고 : https://qkrtngus116.tistory.com/44 )

Shared Memory 는 초기 공유 메모리 할당을 제외하면 커널의 관여없이 통신할 수 있기 때문에 속도가 빠른 장점이 있지만, 여러 프로세스가 동시에 메모리에 접근하는 문제가 발생 할 수 있어 프로세스 동기화 과정이 필요하다

Critical Section (임계 구역)

• Critical Section 이란 공유 데이터를 접근하는 코드 부분을 말하는것이다
• 이때 Race Condition (임계 조건) 은 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과값이 달라 질수 있는 상황 을 말한다
• Critical Section 으로 인해 발생 하는 문제들을 해결하기 위해서는 다음 조건들을 만족해야 한다.
  1. Mutal Exclusion (상호 배제) : 이미 한 프로세스가 Critical Section 에서 작업 중이면 다른 모든 프로세스들은 Critical Section 에 진입하면 안 된다
  2. Progress (진행) : Critical Section 에서 작업 중인 프로세스가 없다면, Critical Section 에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다
  3. Bounded Waiting (한정 대기) : 프로세스가 Critical Section 에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section 에 들어가는 횟수에 한계가 있어야 한다. 즉, Critical Section 에 진입하려는 프로세스가 무한정 기다려서는 안된다

Race Condition (임계 조건)

• Race Condition 은 앞서 말한것 처럼 두개 이상의 프로세스가 공통 자원을 동시에 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다
• Race 의 뜻 그대로 두개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다

 

3. Race Condition 을 해결하기 위한 기법

뮤텍스 (Mutex)

• 옷가게에 가면 탈의실이 1개만 있다고 가정했을때, 한명의 사용자만 이용할수 있고 나머지 사용자들은 대기하는 상황과 같다
• Mutex 는 단순하게 하나의 프로세스가 Critical Section 에서 작업 중이면 다른 프로세스들은 Critical Section 에 들어갈 수 없도록 하는 Locking 메커니즘을 따른다
• 이러한 방식은 Critical Section 진입을 기다리면서 계속 CPU 와 메모리를 사용하는 Busy Waiting 의 문제점이 있다
• 이렇게 lock 이 반환될때까지 계속 확인하면서 프로세스가 기다리는 것을 다른 용어로 Spin Lock 이라고 한다
• 멀티 프로세서 시스템에서 Spin Lock 은 Critical Section 에 진입을 위한 대기 시간이 짧을 때, 즉 Context Switching 하는 비용보다 기다리는게 더 효율적인 특수한 상황을 위해 고안된 것이다

세마포어 (Semaphores)

• 세마포어는 Busy Waiting 이 필요없는 동기화 도구이며, 여러 프로세스나 스레드가 Critical Section 에 진입 할 수 있는 Signaling 메커니즘
• 세마포어는 Counter 를 이용하여 동시에 자원에 접근할 수 있는 프로세스를 제한한다. (S 라는 정수형 변수로 나타내며 이는 사용가능한 자원의 개수를 의미한다)
• 세마포어 변수(S) 는 오직 두개의 atomic 한 연산을 통해서 접근할 수 있다. 한 프로세스가 세마포어 변수를 수정할 때 다른 프로세스가 동시에 같은 세마포어 변수를 수정할 수 없다
• 세마포어에는 두가지 종류가 있다
  1. Counting Semaphore : 정수 값(S)의 범위가 0 이상으로 제한이 없다. 주로 자원의 개수를 세는데 사용한다
  2. Binary Semaphore : 정수 값(S)이 오직 0 또는 1 이다.
     (Mutex 는 같은 스레드에서 Critical Section 을 나올때만 lock 을 해제할 수 있고 Binary Semaphores 는 현재 스레드보다 우선순위가 높은 스레드도 Binary Semaphores 를 해제하고 lock 을 획득할 수 있다)
     참고 : https://www.geeksforgeeks.org/difference-between-binary-semaphore-and-mutex/
• Block & Wakeup 방식
  • Block & Wakeup 방식은 Critical Section 으로 진입에 실패한 프로세스를 기다리게 하지 않고 Block 시킨 뒤 Critical Section 에 자리가 나면 다시 깨워줌으로써 Busy Waiting 방식의 CPU 낭비 문제를 해결해 준다
  • 일반적으로는 Busy Waiting 이 비효율 적이지만, Critical Section 이 매우 짧은 경우 Block & Wakeup 의 오버헤드가 더 커질 수 도 있다
  • Block 을 수행하면 커널은 block 을 호출한 프로세스를 suspend 시키고 해당 프로세스의 PCB 를 wait queue 에 넣어준다
  • Wakeup 을 수행하면 block 된 프로세스 P 를 깨운 다음, 이 프로세스의 PCB 를 Ready Queue 로 이동시킨다
  • waiting 이나 signal 함수는 같은 세마포어에 두 프로세스가 동시해 실행할 수 없으며, 만약 wait 나 signal 을 수행하는 도중에 preempt 된다면 Critical Section Problem 에 빠지게 된다

Blocking & Wakeup 방식의 세마포어

 

모니터 (Monitor)

• 모니터란 세마포어나 뮤텍스를 잘못 사용해서 일어나는 에러를 방지하기 위해서 사용된다
• 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다
• 객체 지향 프로그래밍 언어에서 제공하는 동기화 기법으로 lock 과 unlock 을 자동으로 처리하는 개념적인 동기화 블록으로 구성
  (java 에선 Sychronize block, method 가 존재한다)
  1. 스레드가 모니터에 진입하려할 때 lock 을 획득
  2. 다른 스레드가 이미 모니터의 락을 획득한 상태라면, 현재 스레드는 대기
  3. 대기중인 스레드는 모니터 내부의 Ready Queue 에 저장후 스레드를 일시중지 시키고 스레드들의 목록을 유지
  4. 모니터 내의 조건변수를 사용해서 특정 조건이 충족될 때까지 프로세스를 대기시킬 수 있다. 이러한 경우 프로세스는 조건 대기 큐 (Condition wait queue) 에서 대기
  5. 스레드가 일시중지된 상태에서 조건이 충족된다면, Ready Queue 에 대기중인 스레드를 깨우고 다시 실행되게함
  6. 스레드가 모니터를 빠져나갈때 락을 반납하며 이때 다른 스레드들이 모니터에 진입할 수 있다

 

4. 데드락 (Deadlock)

데드락(Deadlock) 이란, 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 되어 더이상 진행이 될 수 없는 상태를 말한다.

예를들어 신호가 없는 왕복 1차선 사거리 교차로에서 4대의 차들이 중앙에서 교차되어 엑셀(요청)을 밟을 수 없는 상태이다.

프로세스가 자원을 사용하는 절차에는 Request, Allocate, Use, Release 가 있다
Request : 프로세스가 자원을 요청하고, 만약 다른 프로세스가 자원을 사용하고 있어 받을 수 없다면 대기한다
Allocate : 프로세스가 자원을 받는다
Use : 프로세스가 자원을 사용한다
Release : 프로세스가 자원을 놓아준다

Deadlock 은 모든 프로세스가 Request 상태가 되어있는 상황이다

https://rebro.kr/177

---

참고 : https://inpa.tistory.com/entry/%F0%9F%91%A9%E2%80%8D%F0%9F%92%BB-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%E2%9A%94%EF%B8%8F-%EC%93%B0%EB%A0%88%EB%93%9C-%EC%B0%A8%EC%9D%B4#%EB%8F%99%EC%8B%9C%EC%84%B1_concurrency

https://velog.io/@kwontae1313/%EB%8F%99%EC%8B%9C%EC%84%B1%EA%B3%BC-%EB%B3%91%EB%A0%AC%EC%84%B1%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%B0%A8%EC%9D%B4

https://rebro.kr/176

https://peonyf.tistory.com/entry/OS-Process-%EB%8F%99%EA%B8%B0%ED%99%94