※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

Deadlock을 막는 방법으로 Deadlock Prevention이 있다. 

이는 아주 간단한 원리이다. 이전의 포스팅에서 이야기 했듯이 Deadlock이 발생하려면 네 가지 조건이 필요하다. 다르게 말하면, 네 가지 중 한 가지라도 이루어지지 않으면 Deadlock이 발생하지 않는다는 뜻이다. 왜냐하면 모든 Deadlock은 네 가지 조건을 만족시키니까.

그렇다면 그 네 가지 조건. Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait 중 한 가지라도 일어나지 않게 하면 Deadlock을 막을 수 있다. 그런데 이는 현실적으로 불가능하다고 한다. 예를 들어, Mutual exclusion 같은 경우, sharable 해야 Deadlock을 막을 수 있는데, 프린터같은 자원은 무조건 nonsharable하다. 

(프린터 공유할수 있잖아?! 라고 말하면... -_- 이런 거다.. 여기서 공유할 수 있다? 없다?는 동시에 사용할 수 있는지 여부를 말한다. 프린터가 아주 아주 동시에 내 작업 요청과 너의 작업요청을 동시에 아주 동시에 수행할 수 있다고 생각하는가? 아니다!! 정확히 말하면 누구든지 프린터에게 작업을 요청하면 내가 동시에는 못 해주지만 순서대로는 해줄께!! 이런 개념이지 프린터 공유할 수 있다고.. 왜 프린터가 nonsharable하냐고 따지면 안 된다.)

아무튼 Deadlock Prevention은 현실적으로 불가능하다. 그렇다면 Deadlock Avoidance이다.  Deadlock Avoidance는 두 가지 방법으로 구현가능하다.

1. Safe State

2. Resource-Allocation-Graph Algorithm

1. Safe State

항상 시스템의 상태를 Safe State 상태로 놓자는 방법이다. Safe State는 다음과 같은 상태를 의미한다. 여러 개의 프로세스가 있는데, 그 프로세스가 어떤 특정 순서대로 자원을 요청할 때 아무런 문제없이 자원을 할당받을 수 있는 경우이다. 예를 들어서 설명하는 것이 이해가 빠를 것 같다. 

12개의 tape가 있다고 치자. (각각이 자원이다.) 이 tape를 사용하려고 하는 프로세스는 P0, P1, P2 세 개이다. 각각의 프로세스가 요청할 수 있는 최대의 테이프 자원의 개수와 실제 T0이라는 시간에 요청한 자원의 개수는 다음과 같다.

그러면 다음과 같은 자원 사용 현황이 나오겠다.

t0에 12개의 자원이 위와 같이 쓰여서 3개의 테이프가 남아있다.

이 상태에서 만일 < P1, P0, P2 > 순서로 프로세스를 실행시키면 어떻게 될까? P1이 실행되는 동안 어떤 일이 벌어질지는 모르지만, 아무튼 P1이 요청할 수 있는 프로세스의 개수는 4개이다. 그런데 아직 테이프는 3개나 남았기 때문에 P1은 마음 놓고 실행하고 종료할 수 있다. P1이 종료되면 다음과 같은 상태가 된다.

그 다음에 P0가 요청을 해볼까? 남아있는 칸은 다섯 칸이고 P0는 다섯 칸 사용하고 있고, 최대 사용할 수 있는 칸 수는 10칸이기 때문에 P0 역시 마음 놓고 실행하고 종료할 수 있다. 마지막으로 P2역시 마찬가지이다.

따라서 < P1, P0, P2 > 순서대로 실행을 시키면 Deadlock이 발생하지 않는 안전한 상태이다.  그런데 만일 P2가 현재 2칸을 사용하고 있는 것이 아니고 3칸을 사용하고 있다고 가정해보자. 

2칸 더 사용가능한 상태에서 P1이 최대 차지할 수 있는 칸 역시 네 칸이니까 아직은 괜찮다. P1이 수행을 마치면 아래와 같은 상태가 될 것이다. 

여기에서 P0이 다음에 수행을 하려고 한다면 문제가 발생한다. P0는 10칸 사용가능한데 현재 P0는 5칸 사용 중이고 남은 공간은 4칸 뿐이다. 만일 P0이 실행 중에 10칸을 요구할 상황이 오게 된다면 문제가 발생한다. 그런데 이는 P2에게도 문제이다. P2는 최대 9칸 사용 가능한데 현재 사용 중인 칸수 3칸에 4칸의 여유공간을 합하면 7칸 밖에 안된다. 즉, P2이든 P1이든 둘 다 서로 간의 자원이 free되기를 기다릴 수 밖에 없다.

앗!! 여기서 깜짝 질문!! 어짜피 P0이든 P2이든 무조건 한번에는 하나의 프로세스만 실행될 수 있는 것 아니야? 그런데 어떻게 P0과 P1이 동시에 서로의 자원이 free되기를 기다려서 Deadlock에 걸릴 수 있냐는 말이다. P0가 10개의 자원을 모두 사용할 수도 있기 때문에 P2가 사용하고 있는 자원 중 하나가 free되기를 기다리는 것은 말이 된다. 그런데 두 개의 프로세스가 동시에 기다릴 수가 있다고? 아!! 그럴 수 있겠다!! P0가 P2에게 자원을 요청하고 기다리고 있는 상태는 프로세스 상태 변이 중에서 wait state에 해당하니까, P0의 PCB가 Device Queue에 쌓여서 기다리지 않을까? 즉, P0와 P2 둘다 Wait State에 빠지게 되어 해당 자원을 계속 못 쓰고 Wait State에서 빠져나올 수 없는 그런 상태에 빠지게 되는 것인가? 무셔라...

2. Resource-Allocation-Graph Algorithm

알고리즘 이름대로 그래프를 그려서 Deadlock 여부를 판단하는 것이다. 여기에서 새로운 Type의 Edge를 소개하겠다. Claim Edge이다. 이는 보통 점선으로 그려지는데, P → R이 점선으로 그려지면 이는 프로세스 P가 자원 R을 미래의 언젠간 요청할 수도 있다는 뜻이다.

기본적으로 위의 상태를 의미하는 그래프를 OS는 가지고 있을 것이다. 그 상태에서 만일 P1이 실제로 R2를 요청을 하면, R2가 실제 요청을 허락한다는 가정하에 P1 → R2의 점선(Claim Edge)을 R2 → P1 방향의 실선(Assignment Edge)으로 바꾼다. 아래와 같이 말이다.

그리고 해당 그래프가 사이클이 있는지 검사한다. 검사할 때는 실선까지 포함해서 검사를 한다. 사이클이 있다. 이는 반드시 Deadlock에 걸린다는 뜻은 아니지만 Deadlock이 존재할 수도 있는 상태인 Unsafe State에 들어가게 됨을 의미한다. 이런 상태를 피해야한다. 이것이 Deadlock Avoidance이다.

지금까지 설명한 두 가지 방법은 자원에 Instance가 여러 개 있을 경우는 고려되지 않았다. 그것을 고려해서 만든 알고리즘이 있는데, 바로 다음 포스팅에서 설명할 Banker's Algorithm이다.

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

Deadlock을 공부해보자. Deadlock은 한국으로는 교착상태라고 하는데, 이것 또한 생소한 단어라... 잘 이해가 가지 않는다. 상황으로 설명하는 것이 가장 좋을 듯 하다.

철수가 신데렐라 책을 읽고 있었다. 그런데 갑자기 백설공주가 7난장이와 어떻게 되었는지 궁금한거야. 그래서 백설공주 책을 찾고 있는데 이런.. 영희가 백설공주 책을 읽고 있어. 그런데 영희는 백설공주 책을 놓을 생각을 안 하는거야. 왜냐하면 영희는 신데렐라가 12시 이후에 어떻게 되었는지 너무 궁금해서 신데렐라 책을 찾고 있거든.

Deadlock은 프로세스 A가 자원 a를 가지고 있는 상태에서 자원 b를 요청하고 있는데, 자원 b는 프로세스 B에 의해 사용되고 있고, 프로세스 B는 자원 a를 요청하고 있는 상태를 의미한다. 즉, 어떤 프로세스도 자기의 요청하는 자원을 차지할 수 없는 상태를 의미한다. 이 꼴을 제 3자의 입장에서 보자. 이상하게도 프로세스 A와 프로세스 B는 그냥 죽어있는 것처럼 아무것도 안 하고 있는 것처럼 보이겠지? 그래서 Deadlock이다.

Deadlock이 발생하려면 어떤 조건을 만족시켜야한다.

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait

이 네 가지 조건은 Deadlock이기 위해서는 반드시 필요하다. 모든 Deadlock은 위의 조건을 만족시킨다. 그런데 위의 네가지 조건을 모두 만족시키는 상황이 모두 Deadlock은 아니다. 이 내용은 참 중요한 내용이다. 그림으로 따지면 다음과 같다.

그림으로 보는 것이 더욱 쉬울 것이라고 생각한다.

나와 같이 머리가 나쁜 사람들은 이런 것의 관계를 생각하기가 굉장히 어렵다. 프로세스 A는 무슨 자원을 가지고 있는데, 프로세스 A는 b를 요청하고 있고 b는 누가 가지고 있는데 그건 누가 요청하고 있고 이건 이렇고 저건 저렇고....!@#!@%!@#

그래서 나와 같은 사람들을 위해 사람들이 이를 이해하기 쉽게 그래프로 표현하고 있다. 여기서의 그래프는 막대 그래프같은 그래프가 아니고 자료구조에 나오는 그래프를 의미한다.

위의 그래프를 조금 설명해보자.

P = { P1, P2, P3 }

R = { R1, R2, R3, R4 }

E = { R2 → P1, P1 → R1, R1 → P2, R2 → P2, P2 → R3, R3 → P3, P3 → R2 }

P는 프로세스의 집합을 의미한다. 위의 그림에서 프로세스는 3개 즉, P1, P2, P3가 있다.

R은 자원의 집합을 의미하여 R1, R2, R3, R4가 있다.

E는 Edge의 약자로 자원과 프로세스를 잇는 선을 의미한다. 

(※ R에서 P로 가는 선, assignment edge,은 자원이 그 프로세스에 의해 점유되고 있다는 뜻이며, P에서 R로 가는 선, request edge,은 프로세스가 그 자원을 요청하고 있다는 뜻이다.)

한 마디로 위의 그래프는 3개의 프로세스와 4개의 자원 그리고 7개의 Edge로 이루어져 있다.

위의 그래프는 Deadlock인가? Deadlock이기 위해서는 이 글의 가장 서두에 말했던 네 가지 조건을 모두 만족시킨다고 했다. 조건을 만족하는지 살펴보자.

1. Mutual Exclusion : 즉, 모든 자원들이 nonsharable해야한다는 것이다. Deadlock의 기본 정의 자체가 누군가가 자원을 쓰고 있기 때문에 기다려야 하는 상황을 뜻한다. 그런데 만일 그 자원이 공유 가능하다면 한 프로세스가 그 자원을 사용하고 있다하더라도 다른 프로세스는 그 자원을 사용할 수 있을 것 아니냐?! 위의 그림에서의 R1, R2, R3, R4는 nonosharable하다. R3를 보면 R3안에 두 개의 점, instance,이 있는데, 이 instance를 가진 프로세스만 그 자원을 사용할 수 있다. 이 말은 R3는 두 개의 프로세스에 의해서만 공유가능하다는 뜻이다. R3가 이미 P1과 P2에 의해 공유되고 있는 상황에서 P3는 더이상 R2를 공유할 수 없다. 즉, nonsharable하다. 

2. Hold and Wait : Hold and Wait에서 and가 가장 중요한 말인 듯 하다. 동시에 Hold하면서 Wait해야한다. 즉, 한 프로세스가 자원을 동시에 가지고 있으면서 동시에 다른 자원을 기다리고 있는 상태가 되어야 한다. 위의 그래프에서 P1은 R2를 Hold하고 있으면서(and) R1을 Wait하고 있다. 즉 P1은 Hold and Wait하고 있다. 마찬가지 원리로 P2, P3 역시 그러하다. 따라서 Hold and Wait 조건은 만족한다.

3. No Preemption : 한 프로세스가 점유하고 있는 자원이 다른 프로세스에 의해 빼앗기면 안된다는 뜻이다. 위의 그림에서 P3는 R2를 요구하고 있다. R2는 자신의 Instance 두 개를 각각 P1과 P2에게 나누어 주고 있는 상태이다. 만일 이 상태에서 P1의 자원(R2)가 갑자기 P3에 의해 Preempt된다고 하면 P3 입장에서는 Hold and Wait을 만족시키지 못 하게 된다. 왜냐하면 P3는 기다리고 있는 자원이 없다는 뜻이 되잖아?! 위의 그림은 No Preemption을 가정한 상태이다. 즉, 3번은 당연히 만족한다.

4. Circular Wait : Wait이 원형으로 이루어져있다는 것이다. 0부터 9까지가 있는데, 0이 1을 기다리고 1이 2를 기다리고 쭉쭉 가서 9가 0을 기다린다면, 그것은 끝날 수 없는 어떤 상태에 빠지게 된다. 위의 그림은 P1은 R1을 기다리고 있고, R1은 P2에 의해 사용되고 있는데 P2는 R3에 요청을 보내고 있다. 그런데 R3는 P3에 의해 사용되고 있고, 하필이면 P3는 P1이 사용하고 있는 R2에 요청을 보내고 있다. 즉, P1 → R1 → P3 → R2 → P1과 같은 사이클을 찾을 수 있다. 즉 이 조건도 만족한다.

위의 네 가지 조건을 모두 만족시키기 때문에 위의 그래프는 Deadlock이다.

다음의 그래프는 위의 네 가지 조건을 모두 만족시키지만 Deadlock은 아니다.

위의 그래프가 Deadlock이 아닌 이유는 P4때문이다. P4가 언제든지 R2의 Instance를 놓아줄 수 있기 때문이다.

여기서 질문 하나, 도대체 Instance가 무엇일까? 스터디하다가 이 부분에 대해서는 답을 내지 못 했다. 도대체 무엇일까? 위키피디아에서 Instance를 찾아보면 프로그래밍에서 나오는 Instance를 설명하고 있다;;; 흠... Resource에서의 Instance는 어디에서 찾을 수 있을까나...

다음 포스팅에서는 Deadlock을 막는 방법에 대해서 설명해보겠다.

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

Remote Procedure Call(RPC)를 공부해보자.

위키피디아에서 RPC를 이렇게 설명하고 있다.

In computer science, a remote procedure call (RPC) is an inter-process communication that allows a computer program to cause a subroutine or procedure to execute in another address space (commonly on another computer on a shared network) without the programmer explicitly coding the details for this remote interaction. That is, the programmer writes essentially the same code whether the subroutine is local to the executing program, or remote. When the software in question uses object-oriented principles, RPC is called remote invocation or remote method invocation.

즉, RPC는 하나의 프로그램이 네트워크에 연결되어있는 다른 컴퓨터에서 서브루틴이나 프로시저를 실행할수 있도록 한 IPC(프로세스간의 통신)이라고 되어있다. 쉽게 말하면, 내 프로그램이 다른 다른 컴퓨터에서 실행되고 있는 프로그램 내의 함수를 실행할 수 있도록 하는 것이다. 일종의 서버 클라이언트 개념으로 생각해도 되겠다.

RPC에서 stub이라는 개념은 굉장히 중요하다. stub은 클라이언트와 서버 양쪽에 존재하여 중요한 역할을 수행한다. stub의 역할은 다음과 같다.

1. 파라미터를 전달해준다.

생각해보자. 함수들은 파라미터가 필요하다. (물론 아닌 것도 있다.) 파라미터가 필요한데 요청은 클라이언트 컴퓨터에 하고, 함수 자체는 서버 컴퓨터에서 수행된다. 그러면, 어떤 방법을 써서 클라이언트 컴퓨터가 서버 컴퓨터에게 파라미터를 전달해줘야 하지 않겠니? 그것을 가능케 하는 것이 stub이다.

2. 메모리 주소를 바꿔준다.

생각을 해보자. 내 컴퓨터의 메모리 주소와 서버 쪽의 메모리 주소가 당연히 다를 것이다. 그런데 어떻게 내 컴퓨터에서 실행시킨 명령어가 서버쪽의 적당한 곳에 push되는 것일까?(명령어가 메모리 스택에 push되는 것은 당연한 것이다.) 클라이언트 쪽의 주소가 서버쪽의 유효한 곳으로 바뀌려면 그것을 해주는 무언가, stub,가 있어야 한다. 

3. Data representation을 호환 가능하게 한다.

integer type의 경우, 각 시스템은 big-endian 또는 little-endian방식을 사용하여 데이터를 표현한다. 이러한 부분에 대한 호환이 없으면 정보가 제대로 전달이 되지 않겠지? 따라서 이러한 부분을 맞춰준다. 일종의 통역기 기능이라고 보면 된다. 이러한 것을 external data representation(XDR)이라고 한다.

위키피디아에서 stub의 역할이 굉장히 잘 설명되어 있는 듯 하다. Reference 참조해라.

이제 예제를 통해서 RPC를 이해해보자. 참고로 예제는 publib.boulder.ibm.com에서 참고했다. 

RPC 예제이므로 서버쪽과 클라이언트 쪽을 전부 작성해야 한다.

위의 사이트에서 제공해준 코드들은 에러도 많다. 그러나 알아서 수정해봅시다. 그렇게 수정해서 실행시켜보면 다음과 같이 작동한다. 참고로 해당 RPC 프로그램은 단순히 클라이언트의 요청에 따라 hello world를 출력하는 프로그램이다.

※ 서버 : 192.168.179.131

※ 클라이언트 : 192.168.179.129

서버에서 RPC 서버를 실행시키면 다음과 같다.

클라이언트에서 RPC 클라이언트를 실행시킨다.

서버는 RPC 요청을 받고 실제 프로시저를 실행시킨다.

위의 프로그램 수행시킬 때 패킷도 캡처했다. 캡처한 내용을 보면.. 전~혀 이해가 가지 않는다. 내가 무슨 짓을 했는지 원... 이해하면 바로 포스팅 가겠습니다.

Reference : 

http://en.wikipedia.org/wiki/Remote_procedure_call

http://en.wikipedia.org/wiki/Stub_(distributed_computing)

http://publib.boulder.ibm.com