이 글은 다음의 강의를 수강하여 정리 및 복습하는 글임을 밝힙니다.
http://kocw.or.kr/home/cview.do?mty=p&kemId=1223639&ar=relateCourse
시스템 프로그래밍 기초
이 교과목은 컴퓨터 하드웨어 시스템과 운영체제 기반에서 프로그래밍 언어를 어떻게 사용하는지에 관한 기초에 대해서 학습한다.
www.kocw.net
Semaphore (세마포어)
세마포어는 동기화를 위한 도구로 일반화한 Locks이라고 볼 수 있습니다. 여기서 Semaphore는 S로 표기하며, Integer형 변수입니다. 세마포어는 두 종류가 있습니다
1. Counting 세마포어 : integer value로 정수로 표현하는 것입니다.
2. Binary 세마포어 : integer value이지만 0과 1로 표현됩니다. mutex lock과 비슷한 원리입니다.
(여기서 mutex는 mutual exclusion의 약자였습니다)
세마포어는 2개의 operation으로 접근이 가능합니다. 이 operation은 atomic function입니다.
1. Wait() 혹은 P() : 세마포어가 현재 양수라면 1을 감소시키고 대기합니다.
2. Signal() 혹은 V() : 세마포어를 1증가시키고 waiting하고 있는 스레드 혹은 프로세스를 깨웁니다.
세마포어의 구현을 이해하자면 은행의 ATM을 생각할 수 있습니다.
현재 여러명의 사람이 대기를 하고 있는 상태입니다. 세마포어 S의 초기값은 S=2입니다. 첫번째 사람이 ATM에 들어갑니다. 이때 wait()을 function을 호출하게되고, S는 1감소합니다.
다음 사람이 ATM에 들어갑니다. 마찬가지로 S는 1감소합니다.
다음 사람이 ATM에 들어오려고 한다면 S는 0이기 때문에 wait에서 S가 0이므로 대기를 합니다. 만약 ATM의 이용을 마쳤다면 signal() 을 호출하고 S는 1이 증가하며, 줄 서있는 사람을 호출하게 됩니다.
이를 통해서 코드상으로 간단하게 구현하면 다음과 같습니다.
wait(S)
{
while(S <= 0);
S--;
}
signal(S)
{
S++;
}문제는 S가 0보다 작을 경우에 여전히 busy waiting이 발생한다는 점입니다.
Semaphore 의 두가지 사용
첫 번째는 Mutual exclusion입니다. 초기값을 1로 설정한 이후 Binary semaphore로 설정하는 것입니다.
Initial value of S = 1;
Semaphore.P() //wait()
//Critical section
Semaphore.V() //signal()두번째는 Scheduling constraints입니다. 초기값을 0으로 설정한 이후에 두 개의 프로세스가 순차적으로 일을 처리하게 하는 방법입니다.
(thread A)
Critical section
signal(S)
(thread B)
wait(S)
Critical section그 이유는 wait에서는 0보다 작으면 대기를 해야합니다. 그러므로 ThreadA가 Signal을 통해 S를 1을 더하지 않는 이상 실행할 수 없습니다. 이를 통해 순차적으로 일을 처리합니다.
Semaphore 의 busy wating없는 구현
waiting상태일 때 자신을 wait queue 에 넣어 sleep하게 하는 방법이 있습니다. 그래서 두 가지 operation이 등장합니다.
1. Block() : 프로세스를 wait queue로 넣습니다.
2. Wakeup() : waiting queue에서 프로세스를 제거하여 ready queue에 넣습니다.
그래서 코드적으로 확인하면 다음과 같습니다.
typedef struct
{
int value;
struct process *list;
} semaphore;먼저 semaphore구조체입니다. 프로세스는 서로 Linked list로 구성되어 있습니다.
wait(semaphore *S)
{
S->value--;
if (S->value < 0 )
{
add this process to S->list;
block();
}
}
signal(semaphore *S)
{
S->value++;
if(S->value <= 0)
{
remove a process P form S->list;
wakeup(P);
}
}
list는 이러한 프로세스나 스레드의 대기 큐를 나타내며, 일반적으로 연결 리스트나 큐의 형태로 구현됩니다. 세마포어의 wait 연산에서는 S->value가 0 이하로 떨어지는 경우, 현재 실행 중인 프로세스 또는 스레드를 S->list에 추가하고 block() 함수를 호출하여 해당 프로세스나 스레드를 대기 상태로 만듭니다. signal 연산에서는 S->value가 0 이하일 때, S->list에서 대기 중인 프로세스 중 하나를 선택하여 해당 프로세스를 깨웁니다. 이를 통해 대기 중인 프로세스 중 하나가 공유 자원을 사용할 수 있게 됩니다.
프로세스가 list에 추가되고, 잠에 든다, 대기 중인 프로세스를 깨우고 list에서 제거된다. 이런 느낌인거같습니다.
Classical Problems of Synchronization
Syschronization의 클래식한 문제들은 다음과 같다
1. Bounded-Buffer Problem
2. Readers and Writers Problem
3. Dining-Philosophers Problem
Producer-Consumer (Bounded-Buffer Problem)
생산자는 버퍼에 데이터를 넣고 있습니다. 그리고 소비자는 데이터를 빼내고 있습니다. 버퍼의 크기는 한정되어 있다고 할 때 예상되는 문제점은 다음과 같습니다.
1. 오직 하나의 스레드가 buffer에 manipulate(access)할 수 있습니다. 즉 데이터를 쓸 때는 읽으면 안되고, 읽을 때는 쓰면안됩니다. (mutual exclusion)
2. 생산자의 속도가 너무 빠르면 버퍼가 가득찰 우려가 있습니다.
3. 소비자의 속도가 너무 빠르면 버퍼가 빌 우려가 있습니다.
이를 코드상에서 구현하면 다음과 같습니다. 세마포어 mutex와 full 그리고 empty를 사용합니다.
mutex = 1
full = 0
empty = n
Producer
do {
wait(empty);
wait(mutex);
buffer에 데이터 삽입
signal(mutex);
signal(full);
} while(true);Consumer
do{
wait(full);
wait(mutex);
버퍼에서 data를 취합니다.
signal(mutex);
signal(empty);
}while(ture);이에 대한 동작을 그림으로 확인해보겠습니다.
1. 버퍼가 비어 있는지 확인을 합니다. empty의 초기값은 n이기 때문에 -1을 한 후 진행합니다.
2. mutex는 쓰기와 읽기가 동시에 진행되면 안되기 때문에 producer가 버퍼에 작성하기 전에 mutual exclusion를 구현합니다.
3. mutex에 signal을 주어 1을 증가시키고, 버퍼를 release합니다. 그리고 이 상태에서 잠시 consumer의 동작을 생각해볼 필요가 있습니다. full이 현재 0이기 때문에 context switching이 발생해서 consumer에게 넘어간다고 생각을해보겠습니다. wait(full)이 0이기 때문에 wait에서 대기하게 됩니다.
4. 이제 조금 간략하게 설명을 해도 될 것 같습니다. signal 신호로 full +1을 하게 되면 소비자는 이제 wait(full)을 통해 작동을 진행하고, mutex도 0으로 만들어 버퍼에서 data를 취하는 동작을 진행합니다. 그리고 mutex까지 반납을 했다고 생각을 합시다.
5. 생산자 입장에서 empty가 0이 되었다 가정을 하겠습니다. 그러면 소비자가 empty에 signal (+1) 신호를 주어 증가시키게되고, 생산자가 동작하게 됩니다.
Readers and Writers Problem
Reader는 데이터를 읽기만 할 수 있습니다. 그리고 Writers는 데이터를 읽거나 쓸 수 있습니다. 여러명의 리더는 동시에 데이터를 읽을 수 있습니다. writer 같은 경우에는 오직 한 사람만이 데이터에 access할 수 있습니다. (mutual exclusion)
즉 리더는 writer가 없을 때 데이터에 access할 수 있습니다. 그리고 writer가 데이터에 접근할려면 다른 writer나 리더가 없어야합니다.
이를 코드상에서 구현하면 다음과 같습니다. 3개의 변수가 있습니다.
1. 세마포어 rw_mutex 는 1로 초기화 되어 있습니다. (writer의 mutual exclusion을 위한 변수입니다.)
2. 세마포어 mutex 는 1로 초기화되어 있습니다. (mutual exclusion을 위한 변수입니다.)
3. 정수형 변수 read_count는 0으로 초기화되어 있습니다.
Writer
do {
wait(rw_mutex);
Writing
signal(rw_mutex);
}while(true);
Reader
do {
wait(mutex);
read_count++;
if (read_count == 1)
{
wait(rw_mutex);
}
signal(mutex)
reading
wait(mutex);
read_count--;
if(read_count == 0)
{
signal(rw_mutex_;
}
signal(mutex);
}while(true);그림으로 확인해봅시다.
1. 우선 writer의 관점에서 확인해봅시다. 가장 쉬우니까요. rw_mutex는 오직 writer를 위한 세마포어입니다. wait연산을 통해서 -1을 한 이후 writing 작업을 진행합니다. 그리고 signal을 통해서 lock을 release합니다. 여기까지는 쉽습니다.
2. Reader를 설명하자면 다음과 같습니다. 우선 리더가 실행될 때, mutex가 실행되는 이유는 그 안의 내용이 critical section이기 때문입니다. critical section에서는 read_count를 통해서 현재 데이터에 access중인 리더가 몇명인지를 나타냅니다.
만약에 리더가 한 명이라면 (그러니까 나 혼자 뿐이라면) 리더는 계속 들어올 수 있지만 writer가 들어오면 안됩니다. writer가 못들어오게 작업을 해줍니다. wait(rw_mutex)를 통해서 Writer가 계속 wait할 수 있게 만드는 겁니다.
3. 밑의 동작은 위에서 언급한 내용을 반대로 생각하면 됩니다. critical section을 위해서 mutex를 사용하고, read_count--를 한 후에 만약에 read_count가 0이면 내가 마지막 reader이므로 이제 writer가 들어와도 괜찮으니 signal(re_mutex)를 통해서 writer가 작업을 할 수 있게 만들어줍니다.
Dining Philosophers Problem (식사하는 철학자 문제)
대충 밥을 먹는데, 젓가락이 하나밖에 없다. 나무위키의 문제 설명은 다음과 같습니다.
다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 스파게티 같은 면 요리이기 때문에 식사를 하기 위해서는 동시에 두 개의 포크가 필요하다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?
첫번째 방법
1. 각자 자신의 왼쪽에 있는 젓가락이 사용가능하면 이를 집는다.
2. 각자 자신의 오른쪽에 있는 젓가락이 사용가능하면 이를 집는다.
3. 둘 다 사용가능하면, 이를 사용하고 내려놓는다.
4. 왼쪽부터 내려놓고
5. 오른쪽을 내려놓는다.
6. 이를 반복한다.
이를 코드상으로 구현하면 다음과 같다.
do{
wait (chopstick[i]);
wait (chopstick[(i+1) % 5);
eat
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
think
}while(ture);근데 우리가 생각을 해보면
모두가 왼쪽 젓가락을 잡고 있는데, 누가 오른쪽을 줄까?? 이 때 모든 프로세스는 절대 끝나지 않고 대기만 합니다. 이 상태를 우리는 deadlock 이라고 합니다. 그래서 이를 방지하기 위해 한자리는 공석으로 만들고 진행할 수 있을 것입니다. (5명 자리인데, 4명만)
이와는 반대로 작업을 진행해야하는데, 스레드가 ready 상태까지 왔는데, 무한대기를 하는 경우 starvation이라고 합니다. deadlock은 sleep 상태에서 무한 대기를 하는 것을 의미합니다.
Monitor
(뭔가 뭔가한데..)
- 시스템 프로그래밍에서 소프트웨어 모니터는 다중 프로그램 환경에서 공유 자원에 대한 접근을 제어하고 동기화를 관리하기 위한 소프트웨어 구조입니다. 주로 프로세스 간의 상호 작용 및 공유 변수의 업데이트를 조절하는 데 사용됩니다. 소프트웨어 모니터는 프로그램이나 애플리케이션 간의 경쟁 조건을 방지하고 자원 충돌을 방지하기 위해 사용됩니다.
소프트웨어 모니터의 주요 개념에는 다음과 같은 요소가 포함됩니다:
- 진입 점(entry point): 모니터에 진입하여 보호된 자원에 접근하기 위한 메서드 또는 함수.
- 조건 변수(condition variable): 프로세스 간에 상태를 공유하고 상호 작용하기 위한 변수.
- 임계 영역(critical section): 공유 자원에 대한 접근을 제한하기 위한 코드 영역.
- 뮤텍스(mutex): 임계 영역에 대한 접근을 상호 배제하기 위한 동기화 메커니즘.
이러한 개념은 다중 스레드 환경에서 자원 공유 및 동기화를 관리하기 위해 사용됩니다. 대표적으로, 모니터는 프로그램에서 공유 변수에 대한 접근을 동기화하여 스레드 간 충돌을 방지하고 데이터 일관성을 유지합니다.
예시로는 콜라 자판기가 있습니다. 이는 C++로 작성된 코드입니다.
Class CokeMachine
{
Lock lock;
int count = 0;
Condition notFull, notEmpty;
}count는 버퍼에 들어가는 콜라의 개수입니다. 나머지 두 개는 다음 코드로 이해하면 편합니다.
CokeMachine::Deposit()
{
lock->acquire();
while(count == n)
{
notFull.wait(&lock);
}
Add coke to the machine;
count++;
notEmpty.notify();
lock->release();
}콜라를 자판기에 넣는 동작을 합니다. lock을 acquire하는 이유는 자판기에 넣을 때는 누군가 콜라를 가져가면 안됩니다. 여튼 여기서 n은 버퍼의 용량입니다.
만약에 버퍼가 가득차있다면 notFull이 아닐때까지 기다리게됩니다. 일단 콜라가 가득차있지 않다고 생각하고 진행을 하면 콜라를 채우고 count를 하나 늘리고
이제 콜라가 있어라고 알리게되고 mutex를 해제합니다.
CokeMachine::Remove(){
lock->acquire();
while (count == 0)
{
notEmpty.wait(*lock);
}
Remove coke from to the machine;
count--;
notFull.notify();
lock->release();
}일단 구매하는 사람 입장에서 동작은 비슷합니다. 근데, 특별한게 콜라가 없을 경우에 콜라가 notEmpty 그러니까 채워질때까지 대기를 하게됩니다.
구매하는 사람을 깨우는 동작은 이전의 코드에서
이 부분이 담당합니다. 콜라를 채웠어라고 알리게 되고, 구매하는 사람은 콜라가 채워진걸 알아차리고 콜라를 구매하게 됩니다.
반대로 생산자 입장에서 콜라가 가득차 있어서 대기상태에 빠졌었습니다.
콜라를 구매하면, full이 아니라고 알리게 되고, 생산자가 콜라를 채워넣게됩니다.
C Language의 Synchronization
C언어에서는 Lock.acquire()하고 중간에 에러가 발생하면 직접 lock을 release해주어야합니다.
int ThreadEX()
{
lock.acquire();
if(error)
{
lock.release();
return errReturnCode;
}
lock.release();
return OK;
}C++에서는 예외처리가 가능하기 때문에 exception을 잘 관리해주면 됩니다.
void ThreadEx()
{
lock.acquire();
try
{
DoSomthing();
} catch( . . .)
{
lock.release();
throw;
}
lock.release();
}
void DoSomething()
{
if(exception) throw errException;
}C++에서 예외처리는 예외가 발생하면 throw (던진다)는 느낌입니다. 이 외에도 생성자와 소멸자를 토애헛 구현이 가능합니다.
class lock
{
mutex *m_mutex;
public:
lock(mutex &m) : m_mutex(m)
{
m.acquire();
}
~lock()
{
m.release();
}
}
Concurrency에서 발생하는 버그는 주로
1. Atomicity Violation <- 주로 공유된 자원의 under protecting 때문에
2. Order Violation <- deadlock 버그를 해결하다가 종종 발생할 수 있습니다.
3. Deadlock <- 주로 over-protection으로 인해 발생
Concurrency 버그는 작아보이지만 디버깅하는데 오래걸린다고 합니다.