Computer Science/Operation System 2020. 4. 14. 13:12

✔️ Process Synchronization (프로세스 동기화)

◾️ Concurrency Control(병행 제어)라고 부르기도 한다.

◾️ 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.

◾️ 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다.

✔️ Race Condition

◾️ 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

◾️ 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

◾️ Race Condition을 막기위해서는 동시 접근을 동기화(synchronize) 해야한다.

1️⃣ Race Condition이 발생하는 예

📌 Multi-processor system에서 메모리를 공유하고 있을 때

📌 공유 메모리를 사용하는 프로세스 사이에서

2️⃣ OS에서 Race Condition이 발생하는 예

📌 커널 모드 수행 중 interrupt가 발생하여 인터럽트 처리루틴이 수행되는 경우

◾️ 인터럽트 처리 루틴도 커널 코드이다. 즉 커널 데이터에 중복으로 접근하는 경우이다.

◾️ 해결방법 : 커널모드 수행중일땐 인터럽트 처리를 막는다.

rece condition ex1) interrupt handler vs kernel

📌 프로세스가 시스템콜을 하여 커널 모드로 수행중인데 context switch가 일어나는 경우

◾️ 해결방법 : 커널모드 수행중일땐 Context switch를 하지 않는다.

rece condition ex2) preempt a process running in kernel (1)

rece condition ex2) preempt a process running in kernel (2)

📌 Multi-processor에서 shared memory 내의 kernel data에 동시 접근하는 경우

rece condition ex3) multiprocessor race condition

✔️ Critical Section

◾️ n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우에 각 프로세스가 공유 데이터에 접근하는 코드를 말한다.

◾️ 하나의 프로세스가 cs에 있을때 다른 모든 프로세스는 cs에 들어갈 수 없어야한다.

✔️ Process Synchronization 문제를 풀기 위한 조건

📌 Multual Exclusion(상호 배제)

◾️ 프로세스 Pi가 CS을 수행 중이면 다른 모든 프로세스들은 CS에 진입하면 안된다.

📌 Progress(진행)

◾️ 아무도 CS에 있지 않은 상태에서 CS에 들어가려는 프로세스가 있으면, CS 진입을 허용 해야한다.

📌 Bounded Waiting (유한 대기)

◾️ CS에 들어가기 위해 무한정 기다리는 프로세스가 존재하면 안된다. 즉, Starvation이 생기면 안된다.

◾️ 프로세스가 CS에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 CS에 들어가는 횟수에 한계가 있어야한다.

✔️ Process Synchronization을 위한 알고리즘 1

◾️ 변수 turn은 프로세스의 번호를 나타내며, CS를 수행에 대한 차례를 표현한다.

◾️ 위 슬라이드의 코드는 0번 프로세스에 대한 코드이다. ( while(turn != i) // i는 프로세스 번호 )

◾️ turn 변수는 0으로 초기화 됐으므로, while 문을 곧장 탈출하여 CS에 진입할 수 있다.

◾️ CS 수행후 turn을 1로 바꾸어서 1번 프로세스가 CS에 진입할 수 있도록 한다.

◾️ 위 알고리즘의 문제점 : Progress(진행) 조건을 만족하지 못한다. 프로세스 0번이 CS에 진입하기 위해서는 1번 프로세스가 CS에 진입해야한다. (1번 프로세스가 turn을 0으로 바꿔줄 수 있다.) 0번 프로세스가 CS에 여러번 진입하고 싶은데, 1번 프로세스는 단 한 번 CS에 진입한다면, 0번 프로세스는 CS에 여러번 진입할 수 없다.

✔️ Process Synchronization을 위한 알고리즘 2

◾️ flag 변수는 어떤 프로세스가 Critical Section에 들어가겠다는 의사를 표현한다.

◾️ i번 프로세스가 CS에 진입하기 위해서 1. flag를 올리고 2. j번 프로세스의 flag를 확인한다.

◾️ 만약, j번 프로세스의 flag가 올려졌다면(j번 프로세스가 이미 CS에 진입한 상태라면), i번 프로세스는 while문을 반복하며 대기한다.

◾️ j번 프로세스가 CS를 수행한 후 자신의 flag를 내리면, i번 프로세스는 while문을 탈출하여 CS에 진입한다. i번 프로세스는 CS 수행후 flag를 내린다.

◾️ 위 알고리즘의 문제점 : Bounded Waiting (유한 대기) 조건을 만족하지 못한다. 모든 프로세스의 flag가 올려져있는 상태라면, 모든 프로세스는 while문에서 무한 대기하며, CS에 진입할 수 없다.

✔️ Process Synchronization을 위한 알고리즘 3 (Peterson's Algorithm)

◾️ turn, flag 변수를 모두 사용하는 알고리즘이다.

◾️ CS에 진입하기전 flag를 올려서 진입에 대한 의중을 밝히고, turn 을 상대방으로 바꿔준다.

◾️ 상대방이 flag를 들고 있으면서, turn이 상대방 차례인 경우는 while 문을 반복하며 기다린다. (만약, 두 프로세스 모드 flag를 올리고 있으면, turn으로 CS 진입을 결정한다.)

◾️ 이 알고리즘은 모든 경우의 수에서 Process Synchronization 문제를 풀기 위한 조건 3가지를 만족한다.

◾️ 위 알고리즘의 문제점 : Busy Waiting(Spin Lock)방식이다. Busy Waiting이란 while문 반복 대기를 말한다. 이는 지속적으로 cpu와 memory 사용을 유발해서 비효율적인 방법이다.

정리

◾️ 위 알고리즘 1, 2, 3에 나온 고급언어의 한 문장은 실제로 여러개의 CPU Instruction으로 이루어져있다.

◾️ Context Switch는 CPU Instruction 단위로 이루어진다. 즉, 고급언어의 한 문장을 실행하는 도중 Context Switch가 발생하여 CPU를 다른 프로세스에게 선점 당할 수 있다. 이러한 상황을 가정했기 때문에 소프트웨적으로 복잡한 코드가 만들어졌다. 사실 데이터를 메모리에서 읽고, 쓰는 작업을 하드웨어적으로 Automic 하게 실행하는 방법이 있다.

✔️ Synchronization Hardware

◾️ 데이터를 메모리에서 읽고, 쓰는 작업을 하드웨어적으로 Atomic하게(동시에) 실행할 수 있다.

◾️ Test_and_set은 lock 변수를 읽어서 ture 처리하는 작업을 Atomic하게 하나의 Instruction으로 수행한다.

◾️ CS 진입전에 Lock을 걸고, CS 수행후 Lock을 푸는 작업을 위와 같이 간결하게 수행할 수 있다.

◾️ 알고리즘 1, 2, 3 처럼 소프트웨적으로 복잡하게 코드를 작성할 필요가 없다.

✔️ Semaphores

📌 Busy wating(Spin-Lock) Semaphores

◾️ 세마포어는 프로세스 동기화 기능을 간편하게 제공하는 추상 자료형이다.

◾️ 세마포어 변수는 정수 값을 가지는데, 이는 자원의 개수를 표현한다. (S가 5개라면 자원이 5개 있는 것이다.) 또한 P연산 V연산이 존재한다.

◾️ P연산은 세마포어 변수를 하나 감소시킨다. 즉, 공유 자원을 하나 획득한다.

◾️ V연산은 세마포어 변수를 하나 증가시킨다. 공유자원을 하나 반납한다.

◾️ 위 방식은 Busy wating(Spin-Lock)으로 구현한 세마포어이다.

◾️ CS 진입 전에는 P연산으로 자원을 획득하고, CS 수행후에는 V연산으로 자원을 반납한다.

◾️ 프로그래머는 위와 같이 P, V 연산을 통해 프로세스 동기화를 수행할 수 있다.

📌 Block and Wake up(Sleep-Lock) Semaphores

◾️ Busy wating(Spin-Lock)으로 구현한 세마포어의 단점을 극복하기 위해 Block and Wake up으로 세마포어를 구현해보자.

◾️ P연산 수행시 자원의 여분이 없으면, 프로세스를 Block 시킨다.

◾️ V연산은 자원을 반납한다. 이때 자원을 기다리고 있는 Block된 프로세스가 존재하면 Wake up해준다.

◾️ S.value가 음수면, 자원을 기다리는 프로세스가 있다는 것이다.

◾️ S.value가 양수면, 자원의 여분이 있기 때문에 기다리는 프로세스가 없다는 것이다.

📌 어떤 구현방식의 세마포어가 좋은가?

◾️ block and wake up 방식의 오버헤드 : 프로세스의 상태를 바꿔줘야한다.(block-wake up)

📌 두 종류의 세마포어

📌 세마포어의 문제점

◾️ 0번, 1번 프로세스는 S와 Q 두 자원이 모두 필요하다. 하지만 각각 S, Q를 하나씩 가지고 있는 상황이다. 이런 경우 무한 대기가 발생하는데, 이를 Dead Lock이라고 한다. (Starvation이라고 말할 수도 있겠다.)

✔️ 전통적인 동기화 문제

◾️ Bounded-Buffer Problem (Producer-Consumer Problem)

◾️ Readers and Writers Problem

◾️ Dining-Philosophers Problem

1️⃣ Producer-Consumer Problem

◾️ 공유 버퍼가 있다. 생산자는 빈 버퍼에 데이터를 하나 만들어서 넣고, 소비자는 데이터가 들어있는 버퍼에서 데이터를 하나 꺼내는 행위를 한다. (주황색 동그라미가 데이터)

◾️ 두 명의 생산자가 동시에 한 버퍼에 데이터를 생산하려고 할 때 또는 두 명의 소비자가 한 버퍼의 데이터를 소비하려고 할 때 동시접근이 발생하므로 동기화를 해줘야 한다. 즉 공유버퍼에 Lock을 걸어줘야한다. 따라서 데이터를 생산하거나 소비하기전에 먼저 공유 버퍼를 Lock해야한다.

◾️ 문제에서 버퍼의 크기는 유한하다. 따라서 버퍼에 데이터가 꽉찬 경우에 생산자가 도착하면, 생산자 입장에서는 가용 자원이 없는 것이다. 소비자가 데이터를 소비해서 빈 버퍼를 만들어 줄때까지 대기해야한다.

◾️ 반대로 버퍼에 데이터가 하나도 없는 경우에 소비자가 도착하면, 소비자 입장에서 가용 자원이 없는 것이다. 따라서 소비자는 생산자가 버퍼에 데이터를 만들어줄 때까지 대기해야한다.

◾️ Bounded-Buffer Problem 문제를 세마포어로 해결해보자.

◾️ 세마포어 동기화 변수 3개를 사용한다. full, empty, mutex

◾️ full : 데이터가 들어있는 버퍼의 개수 (카운팅 세마포어)

◾️ empty : 빈 버퍼의 개수 (카운팅 세마포어)

◾️ mutex : 버퍼 접근시 Lock/unLock을 위한 뮤텍스 (바이너리 세마포어)

◾️ 생산자 프로세스는 데이터 x를 만들고 P(empty) 연산을 통해 빈 버퍼가 있는지 확인한다. 있다면 버퍼에 mutex로 Lock을 걸고, 접근한다.(CS진입) 빈 퍼버가 없다면, Block 되어 소비자가 V(empty) 연산으로 빈 버퍼를 하나 만들어 줄때까지 대기한다.

◾️ 소비자 프로세스는 P(full) 연산을 통해 찬(데이터가 들어있는) 버퍼가 있는지 확인한다. 있다면 버퍼에 mutex로 Lock을 걸고, 접근한다.(CS진입) 만약 찬 버퍼가 없다면, Block 되어 생산자가 V(full) 연산으로 찬 버퍼를 하나 만들어 줄때까지 대기한다.

2️⃣ Readers-Writers Problem

◾️ DB : 공유데이터를 칭한다.

◾️ Reader : DB에서 데이터를 읽는 프로세스

◾️ Writer : DB에 데이터를 쓰는 프로세스

◾️ Writer 작업은 동시에 이루어지면 안되기 때문에 Lock/unLock을 통한 동기화 작업이 필요하다.

◾️ 반면, Read 작업은 동시에 이루어져도 된다. (동시에 여러 사람이 데이터를 읽는 것이 무슨 문제가 되겠는가?)

◾️ 따라서 Read 작업시에는 Lcok/unLock 작업을 하지 않도록 하여 오버헤드를 줄일 수 있다.

◾️ readcount : Reader가 몇 명인지 카운트하는 공유변수

◾️ DB : 공유변수

◾️ mutex : readcount 공유 변수 동기화를 위한 뮤텍스

◾️ db : DB Lock/unLock을 하기 위한 변수

◾️ Writer는 DB에 데이터를 쓰기전에 p(db) 연산으로 Lock을 걸고, 데이터를 다 쓴후 v(db) 연산으로 Lock을 푼다.

◾️ Reader는 DB에서 데이터를 읽기전에 readcount를 하나 증가시킨다. (이 때 readcount는 공유변수이므로 뮤텍스를 통한 동기화가 필요하다.) readcount를 통해 첫번째로 접근한 Reader와 마지막으로 접근한 Reader를 알 수 있다. readcount가 1라면 P(db)를 통해 DB Lcok을 건다. 즉, 최초의 Reader는 DB에 Lock을 건다. 이후 추가로 오는 Reader는 DB에 Lcok을 거는 작업 없이 접근한다.

◾️ Reader는 DB에서 데이터를 읽고 나오면서 readcount를 하나씩 뺀다. 그렇다면, 마지막 Reader는 v(db)연산을 통해 DB Lock을 풀어준다.

◾️ 즉, DB에서 데이터를 Read 할 때 최초의 Reader가 DB Lock을 걸고 마지막 Reader가 DB unLock을 한다. 이렇게 구현하면 여러명의 Reader가 DB에 접근할 수 있다.

◾️위 코드에서 Reader가 계속 도착하는 상황을 가정해보자. 이 때는 Writer에 Starvation이 발생할 수 있다. 이럴 경우 큐에 우선순위를 두어 Writer가 일정 시간 기다리지 않게하는 방법으로 해결할 수 있다.

3️⃣ Dining-Philosophers Problem

◾️5명의 철학자가 원탁에 앉아있다. 각 철학자는 생각을 하거나, 식사를 한다.

◾️철학자가 식사를 하려면 양쪽의 젓가락을 잡아야 한다.

◾️5명의 철학자가 생각을 하거나 식사를 하는 주기는 다르다.

◾️이 문제에서 젓가락은 공유 자원이다. 원탁에 놓여진 5개의 젓가락에 대한 세마포어 변수는 1로 초기화 된다.

◾️ 5명의 철학자는 먹거나 생각하는 일을 무한 반복한다.

◾️ state[5] : 각 철학자의 상태를 나타내는 공유변수

◾️ self[5] : 젓가락을 두 개 잡을 수 있음을 나타내는 세마포어 변수들. 0으로 초기화 된다. ex) self[3]=1 이면, 3번 철학자가 젓가락 두 개를 집을 수 있는 상태

◾️ mutex : 공유변수에 대한 Lock/unLock 을 위한 뮤텍스(바이너리 세마포어)

◾️ 세마포어 변수 self 5개. self[3] =1 면 3번 철학자가 젓가락 두개를 다 잡을 수 있음을 나타낸다.

◾️ pickup 함수 : 자신의 상태를 '배고픔'으로 바꾸고 현재 양쪽 젓가락을 잡을 수 있는지 확인하기 위해 test 함수를 호출한다. 잡을 수 있다면, test 함수의 V(self[i]) 연산을 수행하고 없다면, 자신의 P(self[i]) 연산을 호출해서 대기한다.

◾️ test 함수 : if 양쪽 철학자가 식사하지 않는 상태이고, 내가 배고픈 상태라면, V(self[i]) 연산을 통해 양쪽 젓가락을 잡을 수 있도록 한다. 만약 if 조건을 만족하지 않는다면, pickup 함수의 P(self[i]) 연산을 통해 대기하게 된다.

◾️ putdown 함수 : 철학자가 식사를 마친후 호출하는 함수. 자신의 왼쪽, 오른쪽 철학자에 대해 test 함수를 실행시켜서, 왼쪽 또는 오른쪽 철학자가 양쪽 젓가락을 잡을 수 있는 상태라면, V(self[i]) 연산을 통해 pickup에서 대기하던 철학자를 깨운다.

◾️ 세마포어와 모니터는 프로세스 동기화문제를 프로그래머 입장에서 쉽게 해결할 수 있도록 제공되는 것이다.

세마포어 역시 불편한 점이 있으며 모니터를 사용하면 더 편하다.

✔️ Monitor

◾️ 프로그래머의 실수로 P, V 연산의 순서가 바뀌면, 동기화가 되지 않는다.

◾️ 실수로 P연산을 두 번 한다면 DeadLock에 걸린다. Lock이 unLock이 안됨

◾️ 세마포어를 잘쓰면 문제가 없다. 하지만 인간은 실수를 한다. 세마포어를 사용할 때 실수를 하면, 버그 잡기가 힘들다.

◾️ 모니터는 프로그래밍 언어차원에서 동기화문제를 해결하는 하이레벨 동기화 컨스트럭터다.

◾️ 모니터 내부의 공유 데이터에 접근하기 위해서는 모니터 내부에 정의된 프로시저를 통해서만 접근할 수 있다.

◾️ 공유 자원은 모니터 내부의 프로시저를 통해서만 접근할 수 있다.

◾️ 모니터 내부의 프로시저는 동시에 실행되지 않고, 동시 접근을 하지 못하도록 만들어져 있다.

◾️ 모니터를 사용하면 프로그래머는 Lock/unLock을 직접하지 않아도 된다. (세마포어와의 차이점)

◾️ 생산자와 소비자는 모니터 내부에 프로시저로 정의되어 있다.

◾️ 모니터 내부의 프로시저들은 동시에 실행되지 못하게 만들어져 있다.

◾️ 따라서 버퍼에 읽기, 쓰기 작업을 할 때, 버퍼에 Lock/unLock을 따로 안해줘도 된다! (세마포어 버전 코드를 보면 버퍼에 접근하기 전에 Lock/unLock 작업을 해줬었다.)

◾️ 단지 wait()와 signal()을 사용해 프로세스를 Block 시키고 Wakeup 시키는 작업만 해준다.

◾️ empty : 빈 버퍼의 개수

◾️ full : 찬 버퍼의 개수

'Computer Science > Operation System' 카테고리의 다른 글

[OS] Memory Management (0)	2020.04.28
[OS] DeadLock (0)	2020.04.23
[OS] CPU Scheduling (0)	2020.04.10
[OS] Process Management (0)	2020.04.09
[OS] Process / Thread (0)	2020.04.09

ABOUT ME

Wook's Wook's

✔️ Process Synchronization (프로세스 동기화)