Process Synchronization

컴퓨터 시스템 안에서 어떻게 데이터에 접근할까?

어떤 Data가 저장되어 있는 위치가 있다. 그 위치를 읽어오고 연산을 해서 다시 원래 Data가 있는 위치에 저장을 한다.
Storage : 데이터가 저장되어 있는 위치
Execution : 연산을 하는 부분

그래서 Process Synchronization 문제가 발생한다. 데이터를 읽기만 하면 문제가 안되는데, 읽고 수정하고 쓰고 이런 방식에서는 누가 먼저 읽었는지 등등에 따라서 문제가 발생할 수 있다. 이렇게 생기는 문제를 Process Synchronization라고 한다.

여러 주체가 하나의 데이터를 동시에 접근하려고 할 때, Race condition 문제 발생한다. 어떤 한 주체가 읽어갔는데 그때 또다른 주체가 또 읽어가면 문제가 발생할 수 있다.

컴퓨터에서 데이터에 접근해서 읽어가고 연산하고 다시 저장하는 로직들이 여러 곳에서 발생할 수 있다.

1. 만약 연산을 실행하는 주체가 CPU라면, 데이터가 저장된 곳은 메모리라고 볼 수 있다. 메모리에서 CPU로 데이터 읽어서 연산하고 다시 메모리에 저장한다.

2. 연산하는 곳을 컴퓨터라고 하면, 저장되는 곳은 I/O 장치인 하드디스크. 디스크에 있는 데이터를 컴퓨터 내부로 읽어들이고 이를 다시 Storage에 저장할 수 있다.

3. 프로세스가 연산의 주체고 프로세스가 관리하는 메모리 주소공간이 저장 위치가 될 수도 있다. 프로세스는 실행하면서 자기 주소공간 데이터를 읽어다가 연산하고 다시 자기 주소공간에 쓰게 된다.

예를 들어, CPU가 여러 개 있는 Multiprocesser system에서는 메모리를 공유하고 있다면 이런 문제가 생길 수 있다. 하나의 CPU가 A 데이터를 읽어가는 동안, 또다른 CPU가 A 데이터를 읽어간다.

프로세스는 자기 자신만의 주소공간을 접근할 수 있지만, 공유 메모리를 쓸 수도 있다. 이런 상황에서도 한 프로세스가 공유메모리에 있는 데이터를 읽어갔는데 또다른 프로세스가 또 읽어가서 작업을 하게 되면 문제가 생기게 된다.

더 중요한 문제는 운영체제 커널과 관련된 문제이다. 프로세스는 일반적인 경우라면 자기 주소공간만 접근하기 때문에 Race condition 문제가 발생할 일이 없다. 하지만 프로세스들이 직접 실행할 수 없어서 운영체제한테 대신 요청하는 부분에 대해서는 System call을 한다. 이러면 커널의 코드가 프로세스 대신해서 실행이 된다. 커널의 코드가 실행된다는 것은 커널에 있는 데이터를 접근하는 것. 커널의 변수값을 바꾸려고 읽어들이는 등등 이런 상황이다. 그런데 이런 상황에서 CPU 빼앗겨서 CPU 넘어갔는데 해당 프로세스가 또 System call을 한다면 Race Condition 문제가 발생할 수 있다.

또한 커널의 코드가 실행 중인데 Interrupt 발생이 가능하다. Interrupt 또한 커널의 코드이기 때문에 커널의 데이터를 건드리게 된다. 즉, User level에서는 별로 문제가 안되는데 Kernel level의 경우 운영체제 커널에 있는 데이터는 여러 프로세스들이 동시에 사용하는 공유 데이터이기 때문에 문제가 생긴다.

운영체제 커널이 CPU에서 실행을 하고 있다. Count라는 변수의 값을 1 증가시키고 있다. 그러면 일단 메모리에 있는 변수 값을 CPU 안에 있는 register로 불러들이고, 이 register 값을 1 증가시킨 다음에 register의 값을 메모리에 다시 쓴다.

문제는 변수를 CPU로 읽어들여서 register에 값이 왔을 때 interrupt가 들어오면, 연산을 멈추고 interrupt를 처리한다. 문제 발생!

이를 해결하기 위해서 중요한 변수 값을 건드리는 동안에는 인터럽트 들어와도 인터럽트 처리 루틴으로 넘기지 않고 이 작업이 끝날 때까지는 인터럽트 처리하지 않는다.

어떤 프로세스가 실행된다는 게, 자신의 코드만 실행하는 게 아니라 커널에게 System call로 운영체제에게 서비스를 대신해달라고 요청하는 경우가 있다. 고로 user mode와 kernel mode가 번갈아가면서 실행한다. 이때 CPU를 독점적으로 쓰는 게 아니고 할당 시간이 있고 할당 시간이 끝나면 CPU를 반납하게 되어있다.

CPU 빼앗기는 시점이 system call 요청을 해서 kernel의 코드가 실행중인 상황이다. B 역시도 똑같은 상황.

프로세스가 커널 모드에 있을 때는 할당 시간이 끝나도 CPU를 뺏기지 않도록 해결할 수 있다. kernel mode 끝나고 user mode로 빠져나올 때 CPU를 빼앗는다.

이 문제는 앞에서 말한 방식들로는 해결 안된다. 작업이 진행되는 동안 인터럽트를 막는다고 해결 안된다.

이 경우는 데이터 접근할 때 lock을 걸어야 한다. 다른 어느 누구도 이 데이터 접근할 수 없도록 한다. 개별 데이터별로 lock을 걸 수도 있고, kernel을 접근하는 CPU를 매 순간 하나만 접근할 수 있도록 할 수도 있다. kernel 전체를 하나의 lock으로 제어한다. CPU가 여러 개 있더라도 커널을 접근하는 CPU는 매순간 하나뿐. 매우 비효율적이다. 각 데이터별로 lock을 걸어서 해당 데이터에 접근하는 게 아니라면 여러 CPU가 동시에 커널코드를 실행할 수 있도록 하는 게 더 좋다.

Process Synchronization는 여럿이서 동시에 접근하려고 해서 시간적으로 잘 맞아떨어지지 않기 때문에 생기는 문제이다.

공유데이터의 동시접근은 데이터 불일치 문제 발생시킬 수 있다. 일관성 유지를 위해서는 공유데이터에 접근하는 프로세스 간에 실행 순서를 정해주는 메커니즘이 필요하다.

Race condition : 여러 프로세스들이 동시에 데이터에 접근하려는 상황

이를 막기 위해서는 동시에 진행하는 프로세스간 동기화가 필요하다.

단순히 프로세스가 넘어간다고 해서 문제가 생기는 것은 아니다. 문제가 생기는 상황들은 앞에서 설명한 상황들이다. 서로 다른 주체들이 공유데이터를 접근하려고 시도하는 상황들

Critical-Section이란 공유데이터에 접근하는 코드를 말한다. 프로세스가 critical-section 안에 들어가 있으면, CPU를 빼앗겨도 critical-section에 들어갈 수 없게 해야한다.

코드로 critical section 문제 해결한다.

critical section 문제를 해결하기 위해서 만족해야 할 조건이 무엇인가. 아래 사진에 나온 세가지.

• Mutual Exclusion(상호 배제)
• Progress
  • 아무도 critical section에 들어가 있지 않다면 내가 들어가고 싶을 때 들어갈 수 있게 해준다.
  • 동시에 진입할 때 문제 발생 가능
• Bounded Waiting
  • 기다리는 시간이 유한해야 한다.
  • 특정 프로세스 입장에서 지나치게 오래 기다리는 starvation 없어야함.

어떻게 소프트웨어적으로 lock을 걸었다가 풀 수 있는지

프로세스가 두 개 있다고 가정해보자. P0과 P1. 코드는 똑같다고 가정.
turn 변수로 어떤 프로세스 차례인지 나타낸다.
위 알고리즘은 Mutual Exclusion은 만족한다. 문제는 아무도 critical section에 없어도 critical section에 들어가지 못한다. Progress 조건을 만족하지 못한다.
critical section은 반드시 교대로 들어가야 한다. 한번 P0이 critical section 가야지 P1으로 차례가 돌아가게 된다. P1이 critical section에 들어가서 turn을 바꿔주지 않는다면 P0는 영원히 들어가지 못한다.

단순히 turn을 교대로 해주는 알고리즘은 부적절하다.

Flag라는 변수를 사용한다. 프로세스 각각이 Flag 변수를 가지고 있는다. Flag 값으로 자신이 critial section에 들어가고 싶은지 아닌지를 표현한다.
critical section에 들어가고 싶다? flag를 true로 세팅.
그리고 다른 프로세스가 flag 변수를 세팅했는지 확인한다. 만약 아무도 세팅하지 않았으면 들어가고 본인이 나오면서 flag 변수를 다시 false로 바꾼다.

이 알고리즘도 문제 있다. 만약 P0이 flag만 세팅하고 critical section은 들어가지 못한 채 CPU가 빼앗긴다. 그리고 P1도 flag를 세팅했다면 P0도 flag가 세팅되어 있는 상태라서 critical section에 들어가지 못한다. 이렇게 아무도 들어가지 못한다.

둘이 동시에 들어가는 문제는 생기지 않지만 아무도 못 들어갈 수 있다는 문제 발생.

turn과 flag 변수 모두 사용한다.
일단 P0가 critical section에 들어가고자 한다면 flag 변수를 세팅해서 의사 표현을 한다. 그리고 turn을 상대방으로 맞춰둔다.

상대방이 깃발을 들고 있으면서 turn도 상대방 차례라면, 기다린다.
상대방이 깃발을 안 들고 있으면 critical section에 관심 없다는 거기 때문에 바로 들어가도 된다.
상대방이 깃발을 들더라도 차례가 상대방 차례가 아니면 내가 critical section에 들어가도 된다.

critical section에서 빠져나올 때는 flag 다시 내려서 다른 프로세스도 들어갈 수 있도록 한다.

이렇게 하면 CPU를 중간에 빼앗겨도, 동시에 접근하지 않으면서 아무도 없다면 접근 가능하며 기아 문제도 없다.

이 코드도 문제가 있다. busy waiting(=spin lock)!
계속 spin, while문을 돌면서 lock을 건다. 어떤 프로세스가 이미 critical section에 들어간 상태에서 다른 프로세스가 CPU 잡으면, while문을 돌아도 만족이 안된다. 그러면 그 다른 프로세스는 CPU 잡아도 계속 while문만 돌면서 체크한다. 왜냐면 while문이 만족이 되려면 상대방이 CPU를 잡아서 조건을 바꿔줘야하기 때문이다. 쓸데없이 CPU 할당 시간을 while문 체크하는데만 쓰다가 끝난다. 비효율적인 방법!

문제는 CPU를 중간에 빼앗길 때 문제 발생! 하드웨어적으로 하나의 instruction만 주어지면 critical section 문제는 쉽게 해결된다.
데이터를 읽는 것과 쓰는 것을 하나의 instruction으로 실행 불가능하기 때문에 문제가 발생한다. instruction 하나로 읽고 쓰기가 모두 가능하다면 문제가 발생하지 않는다.

만약 a가 0이었다면, Test_and_set(a)를 수행한다면 0이 읽히고 a 값은 1로 바뀐다.
만약 a가 1이었다면, 1이 읽히고 a 값은 1로 다시 한번 더 세팅된다.

Semaphores

세마포어도 일종의 추상 자료형이다. 변수 S가 정수값을 가질 수 있고 세마포어 변수에 대해서 정의되어 있는 연산은 2가지가 있다.

세마포어를 왜 쓰냐면, lock을 걸고 풀고 하는 걸 간단하게 프로그래머에게 세마포어를 통해서 제공할 수 있다. 또 공유자원을 획득하고 반납하고 이런 과정을 세마포어가 처리를 해준다.

P 연산 : 세마포어 변수 값, 공유데이터 값을 획득하는 과정.
V 연산 : 다 사용하고 나서 반납하는 과정.

세마포어 변수 S가 정수값을 가질 수 있는데, 이는 자원의 개수라고 생각하면 된다. S=5라면 자원이 5개 있다. P 연산할 때는 자원을 하나 가져가고, V 연산할 때는 자원을 내어놓는다.

P 연산과 V 연산은 atomic하게 연산이 수행된다는 것을 가정한다.
여기서도 busy wait 문제는 발생한다. 자원이 없을 때 P 연산을 해봤자 계속 while문만 실행된다.

세마포어를 critical section 문제에 적용하게 되면 아래와 같다.

mutex는 세마포어 변수(Mutual Exclusion). 이를 1로 놓고 critical section 들어갈 때는 P 연산, critical section에서 나갈 때는 V 연산을 해주면 된다. P 연산과 V 연산만 지원을 한다면, 즉 세마포어만 지원이 된다면, 프로그래머는 P 연산과 V 연산만 하면 된다.

busy-wait, spin-lock은 효율적이지 못하기 때문에 Block & Wakeup(=sleep lock) 방식으로 구현한다.

공유데이터 접근할 때 누군가가 공유 데이터를 이미 쓰고 싶다면, 어차피 그 친구가 내어놓기 전까지는 본인의 차례가 오지 않는다. 쓸데없이 while문 돌면서 기다리지 말고 프로세스 자체를 block 시켜서 잠들게 한 다음, 프로세스가 공유데이터 내놓으면 깨어나서 Ready Queue로 들어온다. 이 방식이 발로 Block/Wakeup 방식

세마포어를 위한 변수와 세마포어 때문에 잠들어있는 프로세스를 연결하기 위한 queue L이 정의되어 있다.

만약 세마포어를 획득할 수 없으면 그 프로세스를 block한다. 누군가가 세마포어 쓰고 반납하면 block된 프로세스 중 하나 깨워서 wakeup을 시킨다.

세마포어 획득 못한 친구는 L에 PCB를 메달아둔다.

구체적인 구현은 아래와 같다.

P 연산은 자원을 획득하는 과정이다. 자원에 여분이 있으면 자원을 획득하고, 그렇지 않다면 잠든다. S를 1 줄인다. 이게 음수라면 자원의 여분이 없음을 의미한다.

V 연산은 자원을 반납한다. 그냥 반납하는 게 아니고 자원을 기다리면서 잠들어있는 프로세스가 있다면 이를 깨워줘야 한다.

단순히 S가 자원의 개수를 의미하는 게 아니다. S값이 음수면 누군가가 자원을 기다리고 있다. 반면 양수면 자원의 여분이 있다. 상황을 나타내는 변수가 된다.

Block/wakeup 방식이 보통은 더 효율적이다. 그렇지만 이도 오버헤드는 있다. critical section의 길이에 따라서 다를 수 있다.

counting semaphore : 자원의 개수가 여러개여서 여분이 있으면 가져다 쓸 수 있는 경우.
Binary semaphore : 자원의 개수가 하나인 경우.

세마포어 쓸 때 주의해야할 문제가 있다.

어떤 일을 하기 위해서 세마포어 S와 Q를 두 개 가져야 한다고 가정.
서로가 서로가 원하는 자원을 가지고 있으면서 내어주지 않는다. 데드락

자원을 획득하는 순서를 똑같이 맞춰주면 해결 가능하다. P0와 P1 모두 S 먼저 획득하고 Q를 획득하도록 하면 문제 해결 된다. 프로그래머가 유의해서 작성해야 할 부분이다.

Starvation은 특정 친구가 영원히 자원 얻지 못하고 기다려야 하는 상황이다. 데드락도 일종의 Starvation이라고 볼 수 있다. 여기서 얘기하는 Starvation은 특정 프로세스들만 자원을 공유하면서 다른 프로세스는 차례가 오지 못하게 하는 것. 철학자 문제

왼쪽하고 오른쪽 젓가락 집어야 밥 먹을 수 있다. 이럴 때 어떤 철학자는 계속 젓가락을 쓰지 못할 수 있다. 이게 Starvation
모두가 동시에 왼쪽 젓가락을 집으면 Deadlock

Process Synchronization(프로세스 동기화) = Concurrency Control(병행 제어)

프로세스가 동시에 무언가를 실행하면서 발생하는 문제를 해결하는 것.
문제를 해결하는 방안으로 세마포어를 프로그래머들에게 제공한다.
P 연산으로 자원 획득하고 V 연산으로 자원을 반납하는 과정.

여러 프로세스가 S라는 세마포어 변수에 대해서 P 연산을 하려고 할 때, 하나의 프로세스만 P 연산을 할 수 있다.

고전적인 프로세스 동기화 문제 세가지
1. Process-Consumer 문제
2. Readers-Writers 문제
3. Dining-Philosophers Problem 문제

세마포어 외에 프로세스 동기화 관련해서 모니터를 지원한다. 세마포어는 P 연산과 V 연산을 활용하여 동기화를 지원한다. 프로그래머가 직접 프로그래밍을 통해서 동기화를 해줘야한다. 프로그래머 실수에 따라서 원하지 않는 결과가 나올 수도.

Monitor가 프로그래머 부담 줄여주고 자동으로 동기화 문제를 해결해준다.
공유 데이터를 접근할 때는 접근하는 코드를 모니터 안에다가, 공유데이터와 접근 코드를 정의한다. 프로세스가 공유데이터를 접근하려고 하면 모니터 안에 정의된 코드만 활용해서 접근할 수 있도록 설정한다.
모니터는 항상 active한 프로세스 하나가 실행될 수 있도록 모니터가 제어해준다. 모니터는 lock을 걸 필요가 없다.

condition variable : 모니터 안에서 어떤 코드를 실행하다가 조건이 충족 안돼서 오래 기다려야 한다면 해당 프로세스를 잠들게 한다. 어떤 조건에 따라서 잠들었는지를 해당 변수로 표현. 어떤 값을 가지는 변수가 아니라, 프로세스를 잠들게 하고 줄세우게 하기 위한 변수.
wait 연산과 signal 연산 두 가지가 해당 변수에 일어날 수 있다.
wait 연산 : 프로세스를 잠들게 할 때. x.wait를 호출하면 프로세스는 x라는 condition variable에 가서 줄을 서게 된다.
signal 연산 : x라는 condition variable 조건을 기다리면서 잠들어있는 프로세스가 있으면, 깨워줘라.

모니터를 사용하면 코드가 위처럼 바뀐다. 공유버퍼에 대해서 lock을 걸 필요가 없다.
signal은 잠들어있는 게 있으면 깨워주지만, 잠들어있는 게 없으면 하는 게 없다.

모니터는 동시접근 막는 것을 모니터 차원에서 지원.
세마포어는 자원을 획득하기 위해서 프로그래머가 알아서 P 연산, V 연산을 해야함.
둘은 목적이 다르다.

위는 모니터 버전의 철학자 문제 해결 코드이다. 세마포어와 거의 비슷.