데드락: 예방·회피·탐지 기법

우리 버스 이런 것도 자원이 될테고, 하도웨어적인 자원 이외에 소프트웨어적인 자원도 있어요. 우리가 앞서 세마포그 같은 것도 소프트웨어적인 자원이죠. 세마포그를 확보를 해야 자기가 클리어 세수도 들어갈 수 있죠. 일을 할 수 있으라고 하죠. 그리고 락락락락도 열쇠 같은 경우 락을 확보한 프로세스만 일을 할 수 있죠. 소프트웨어적인 자원도 있어요. 어쨌든 프로그램 코드를 수행하기 위해 필요한 모든 재반 조건들, 그런 조건들을 우리가 리소스라고 하고 그 리소스가 확보가 되어야만 일을 할 수 있다는 게 프로세스의 기본 동작 원리에요.

그런데 어떤 프로세스에 이를 하기 위해서는 리소스가 하나만 있는 게 아니에요. 필요한 리소스가. 즉, CPU도 필요하고, 메모리도 필요하고, 버스도 필요하고, 다 필요하죠. 소프트웨어적인 리소스도 필요하고, 여러 개의 리소스를 바꿔를 해야만 진도를 나갈 수가 있는데, 어떤 프로세스들이 정말 나쁘게도 일부 리소스는 바꿔를 했는데 일부 리소스는 바꿔를 못한 상태에서 그 리소스를 가지고 있는 다른 프로세스가 그 리소스를 놓기까지 기다리고 있는 상태가 발생할 수 있죠. 그 기다리고 있는 상태가 즉, A라는 프로세스는 B라는 프로세스가 가지고 있는 리소스를 대기하고 있고, B라는 프로세스는 C라는 프로세스가 갖고 있는 리소스를 기다리고 있고, 이런 식으로 연쇄적으로 기다릴 수가 있게 되죠. 그 연쇄적인 기다림으로 인해서 모든 프로세스가, 그런 관계에 있는 프로세스들이 아무 일도 못하고 진도를 못 나간 채 멈춰서 버리는 데 불우는 대드락이라고 해요. 개념적으로 볼 때, 그래서 우리가 지난 시간에 예를 든 적 있죠. 세마포호의 경우에 밑에 예를 보면, 프로세스 0는 A의 세마포호에 대한 세마포를 획득했고, 프로세스 1은 B에 대한 세마포를 확보했을 때, 그리고 서로가 서로를의 세마포, 즉, P0는 B의 세마포를 확보하려고 기다리고, 그리고 P와는 A라는 제맛도를 기다리고 있고

이렇게 되면 서로 맞뜩게 된 거죠. 제가 보도를 맞닿고 있기 때문에 아무것도 진도로 못 나가죠. 이런 일이 벌어질 수 있기 때문에 이런 경우는 대드락이 발생했다고 우리가 보는 거예요. 대드락에 대해서 개념적으로는 그 정도 이해하고 그걸 이제 포멀하게 어떻게 정리할지 한번 보도록 합시다. 대드락이 발생하기 위한 조건이 네 가지가 있어요. 이 네 가지 조건이 동시에 만족이 될 때 대드락이 발생하게 됩니다. 첫 번째 조건이 너무나도 당연한 조건이에요. 상호 배제 조건. mutual exclusion 조건인데 이거는 자원이라는 것이 본질적으로 공유가 불가능해야 된다. 즉 어떤 프로세스가 그 자원을 잡고 있으면 다른 프로세스는 그 자원을 그런 자본에 대해서만 들어가게 발생할 수 있다.

그 다음에 두번째 조건이 no preemption. 어떤 프로세스가 자발적으로 놓을 때까지는 다른 프로세스랑 그 자원을 쓸 수 없다는 뜻이에요. 즉 자원에 대한 release, 자원을 다시 놓게 되는 행위는 그 자원을 잡고 있는 프로세스가 일을 끝마치고 나서 자발적으로 그 자원을 놓게 될 때만 그 자원을 release 될 수 있다는 뜻이에요. 강제로 뺏고 잃을 수 없다는 뜻입니다. 그게 no preemption이라는 조건이고요. 세번째 조건이 all and wait. 어떤 프로세스가 일을 하기 위해서 필요한 자원은 여러 개가 있다고 그랬죠. 근데 내가 반쯤 잡고 나머지 반을 기다리고 있어요. 그러면 나머지 반을 내가 지금 잡을 수 없는 상황이네 라는 사실을 확인했을 때 그러면 어차피 일고 타는 거 이미 내가 확고한 자원맞수 이상 놔두자, 릴리스 해버리자 라는 식으로 아주 착하게 동작하지 않는다는 뜻이에요.

모든 프로세스는 일단 자기가 확보한 자원은 손에 꽉 쥐고 있고 나머지 자원을 확보하기 위해서 손에 쥔 채로 기다리고 있다는 뜻이에요. 홀더레이트. 무슨 말인지 알겠죠? 마지막 네 번째 조건이 제일 중요한 조건이에요. 서플라웨이트. 이렇게 내가 일부 자원을 잡고 다른 프로세스가 잡고 있는 자원을 기다리고 있다. 그러면 프로세스가 다른 프로세스를 기다리는 형태로 볼 수 있죠. 그래서 P0가 P1이 갖고 있는 자원을 기다리고 있고, P1은 P2가 가지고 있는 자원을 기다리고 있고, 이런 식으로 해서 뚝뚝뚝 진도가 나가다가 Pn 제일 마지막 프로세스가 다시 제일 첫 번째 프로세스 P0가 잡고 있는 자원을 기다리고 있다. 원형 대기가 이루어지죠

원형 대기가 이루어지는 것을 운영하는 서큘러 웨잇 조건이라고 해요. 그 서큘러 웨잇 조건이 만족되어야만 대드락이 발생할 수 있어요. 그래서 이 4가지 조건이 동시에 만족될 때 대드락은 발생하게 된다는 거예요. 자 그러면 우리가 일상생활에서 대드락을 한번 보도록 합시다. 일상생활에서 자수 발생하는 대드락이에요. 도로에서 이런 모양을 한번 잘 봐요. 이건 여러분들이 아마 실제로 겪어 봤던지 아니면 텔레비전에서 봤던지 보셨을 거예요. 이 상황이 꼼짝달상 못하는 상황이죠. 차가 전혀

진행을 못하게 되는 상황이죠. 그러면 이 대드락이 발생했는데 이게 앞서 말한 4가지 조건을 충족시키는 점은 봅시다. 첫 번째 조건이 뭐라고 그랬어요? mutual exclusion. 하나의 자원은 공유될 수 없다는 거죠. 여기서 자원이 뭘까요? 트래픽에서 자원은 도로적으로 도로 한 칸을 자원이라고 합시다. 예를 들어서 요거 하나. 요게 도로 한 칸이라고 보면 요 도로는 지금 요 자동차에 의해서 정리되고 있죠. 따라서 이 자동차가 이 도로를 지나가서 이 공간이 잘 생기지 않는 한 이 트럭은 앞으로 진도를 나갈 수 없다는 뜻이에요. 공유가 안 되죠. 차 위로 트럭이 지나가가 안 되잖아.

그래서 mutual exclusion 조커는 당연히 만족이 된 거고 두 번째가 no preemption이죠 즉 자원을 내놓는 거는 자기가 그 자원을 사용하고 자발적으로 그 자원을 잡고 있는 프로세스가 그 자원을 다 사용한 다음에 자발적으로 내놓을 때만 자원은 밀리지 될 수 있다는 점이죠 이 도로가 대표적인 게 있어 이 프로세스가 이 밑에 그림을 다시 봅시다 이 자동차가 아래쪽 이 자동차가 자기가 확보하고 있는 이 도로의 공간을 내놓으려면 이 자동차가 이 도로를 지나가서 이 도로를 사용한 뒤에 앞으로 빠져나가서 자발적으로 내놓는 그때만 이 자원에 대한 반납이 오신다는 거예요 중간과 가지고 기기가 중장비가 와서 이 차를 드러내버리면 물론 자원이 확보가 되죠. 자원이 다시 릴리즈가 되는 거랑 똑같은 거죠. 중장비가 와서 이 차를 덜어내 버리는 뒤로 발생하지 않는다는 거죠.

그렇기 때문에 이 조건에서도 노 프리엠션 조건이 만족이 돼요. 이 차가 지나가야만 이 도로는 반납될 수 있다는 조건이 만족되고 있죠. 중장비가 와서 차를 들어 낸다는 건 생각 안 하는 겁니다. 세 번째 조건이 뭐였어요? 홀드 앤 웨이트였죠. 내가 다른 차가 가지고 있는 도로를 확보하기 위해서는 내가 지금 가지고 있는 도로, 내가 지금 정류하고 있는 도로를 정류한 채로 다른 차가 비켜놔주기를 바라는 거예요. 홀드 앤 웨이트. 그래서 오른쪽 이 차를 보면 이 차는 자기가 잡고 있는 이 도로 공간을 정류하고 있는 상태에서 이 앞에 있는 트럭이 정류하고 있는 이 공간을 기다리는다. 홀드한 상태로 기다린다는 조건을 만족시키고 있죠. 그래서 세 번째 조건까지 만족이 됐고, 네 번째 조건이 서로 기다리는 모양이 반형되기를 원형으로 이루어져야 된다는 조건재죠. 이걸 보면 우리가 알 수 있죠. 이 오른쪽 위에 이 자동차는 이 차를 기다리고 있죠. 이 차가 잡고 있는 공간을 기다리고 있고, 이 자동차는 이 차를 기다리고, 이 자동차는 이 트럭을 기다리고, 이 트럭은 이 자동차를 기다리고, 이 자동차는 또 이걸 기다리고, 또 이걸 기다리고, 또 이걸 기다리고, 또 이걸 기다리고, 또 트럭이 이걸 기다리고, 이 트럭은 이걸 기다리고, 이렇게 계속 기다리는 모습이 생기죠. 그다가 결국은 여기까지 오죠.

여기 아까 우리가 말했던 P재료를 보고 Pn이라고 봤을 때 Pn이 P재료를 기다리게 되는 거죠. 그래서 이게 원형, 반형이 이루어지더라. 그래서 4가지 조건이 다 만족되었기 때문에 지금 이 상황은 대드락이다 라고 자 그러면 과연 그런 현상이 실제로 나타날까? 나타날죠 봐. 실제로 존재해요. 그러니까 우리가 대드락을 방치하면, 대드락에 대해서 아무런 조치를 취하지 않으면 이런 일이 일어난다는 거예요. 교통순경이 교통제어를 하지 않으면 이런 일이 벌어질 수 있다는 거죠. 그래서 실세계에서 대드락은 충분히 발생할 수 있는 문제예요. 컴퓨터 시스템 안에도 자원을 사용하기 때문에 대드락이 발생할 수 있어요.

자 그러면 우리가 이 데드락을 이제 포멀하게 한자 꺼내봅시다. 데드락을 모델링하기 위해서 우리가 그래프를 사용할 건데요. 대표적인 모델링 툴이 리소스 알로케이션 그래프에요. 자본할당 그래프이라는 거에요. 그래프, 그래프니까 그래프의 정리는 뭐에요? 그래프는 볼텍스의 직합과 엣지의 직합의 페어죠. 그래서 g는 v-2의 페어에요. 자 v는 두가지, 볼텍스는 두가지 타입 있어요. 우리가 데드락에서 말하는 볼텍스는 두가지 타입 있어요. 첫번째가 프로세스 타입. 프로세스들이 하나의 볼텍스에요.

그리고 R, R이라는 타입의 pro-text, 자원이라는 pro-text가 있어요. 자원은 여러가지 종류가 있죠. gpu 메모리, 소프트웨어, 제마포도 하나하나가 다 자원이에요. 서로 다른 종류의 자원이죠. 그래서 자원은 여러가지 종류가 있다. R1, R2, R1 이렇게 여러가지 자원이 있다. 프로세스에 비해서 여러개의 프로세스가 있고. 그래서 P이라는 프로세스의 집합과 R이라는 자원의 집합이 전부 다 우리가 모델링하는 리소스 알로케이션 브레임에서는 pro-text로 동작한다는 거예요. 다음 엣지의 집합은 뭐가 있을까? 엣지도 두 가지 종류가 있어요. request edge 즉 어떤 프로세스가 어떤 자원을 필요로 할 때 우리는 request, 이 자원을 달라고 요청했다는 뜻으로 request edge라고 해요. 그래서 request edge는 directed edge, 방향성이 있는 edge로 이렇게 표현해요. P1이 RJ를 요청했다. 그 자원 나 필요해라고 요청했다. 라고요. assignment edge는 뭐냐면 프로세스가 그 자원을 요청해서 그 자원을 할당해줄 수 있다면. 남는 자원이 있네? 그럼 너 이거 줄게. 그러면 그 자원이 그 프로세스한테 할당이 된거죠. 그럼 그 프로세스는 그 자원을 바꾸게 된거에요. 그 경우 역시 edge로 표현하는데 그 edge를 assignment edge라고요. 할당 edge. 이건 역시 방향성이 있는 edge로 그리고, 끝불로 자원에서 프로세스로 가는 edge가 되는거죠. 그래서 resource rj가 프로세스 pi한테 할당이 된다는 뜻이에요. 이렇게 두가지 종류의 edge와 두가지 종류의 protect를 가지고 이루어지는 그래프를 resource allocation 그래프라 그래요.

자 이 그래프를 그림으로 그려봅시다. 그림으로 그릴 때 어떻게 표시할 거냐면, 프로세스는 이렇게 동그라미로 표시할 거예요. 그리고 리소스는 메모, 리소스는 메모로 표시할 거예요. 그런데 이 자원은 하나의 타입, 하나의 타입의 자원이 여러 개가 있을 수 있죠. 예를 들어서 메모리, 메모리 보면 페이지 단위로 나눠 놨으면 메모리 라는 타입의 자원은 엄청나게 많은 수의 페이지로 구성이 되어 있죠. 그래서 인스턴스가 엄청나게 많다 라고 볼 수 있고, 따라서 이렇게 그릴 거예요. 리소스는 이렇게 사각형으로 그리고 그 안에 그 리소스 타입에 해당하는 인스턴스를, 즉 메모리 같은 경우에는 페이지의 개수, 그 만큼 안에 있는, 안에 조그마한 사각형으로 그릴 거예요. 그래서 이 그림의 경우는 이 리소스 타입은 4개의 인스턴스를 가지고 있다. 즉 각각의 자원을 4개를 갖고 있으므로 하나씩 하나씩 4개의 프로세스한테 줄 수도 있고, 한 프로세스한테 2개를 줄고, 다른 프로세스한테 2개를 줄 수도 있고, 한 프로세스한테 2개를 줄 수도 있고, 이런 뜻이에요.

자 다음에 request Edge는 어떻게 되느냐? 프로세스에서 리소스로 Edge가 만들어지는 것을 request Edge라고 했죠? 그래서 pi가 rj, resource j를 요청했다고 하면 pi에서 rj로 화살표가 나타나는 이런 Edge를 그리게 되는 거예요. rj의 바깥쪽 사각형에 이렇게 화살표가 가게 되죠. 다음에 assignment Edge는 리소스가 이 프로세스한테 할당이 되었다는 것을 말하는 거였죠? 그러면 리소스의 어떤 인스턴스가 할당이 되는 거니까 안에 있는 조그마한 사각형으로부터 이 인스턴스가 이 프로세스한테 할당이 됐다는 표시를 해야 되니까 조그마한 사각형에서 프로세스로 가는 Edge가 만들어지는 거예요. 아시겠죠? 자 이렇게 표시하기로 하고 예를 한번 보도록 합시다.

리소스 알로케이션 그래프기에요. 우리는 이 그래프 보면서 쉽게 이해할 수 있죠. 프로세스는 3개가 있고, P와 P2 비스도 3개가 있고, 리소스 타입은 4가지 종류의 리소스가 있다. 그리고 각각의 리소스는 인스턴스가 하나인 놈들, R1과 R3는 인스턴스가 하나죠. 그리고 인스턴스가 두 개인 놈이 R2고, 인스턴스가 세 개인 놈이 R4에요. 리소스마다 리소스 자원이 개수가 서로 다를 수 있죠. 그리고 각각에 대해서 엣지들이 그려져 있어요. P1은 리소스 R1을 달라고 아우성 치고 있고, 근데 그 R1 대 리소스는 하나밖에 없는데, 그 하나가 P2한테 이미 가 있어요. 각각 하나씩 가지고 있어요. 기관과 피토나 리소스를 하나씩 가지고 있고

리소스 폰은 아무도 달라고 요청하지 않은 상태예요. 자 이렇게 해석할 수 있겠죠. 이걸 딱 보면 현재 리소스의 상태, 할당 상태, 요청 상태를 한눈에 우리가 볼 수 있기 때문에 리소스 알로케이션 그래프가 아주 위험하게 사용될 수 있을 것 같죠. 자 그러니까 리소스 알로케이션 그래프를 가지고 우리가 뭘 할 수 있냐 기본적인 사실이거든요. 만약에 리소스 알로케이션 그래프가 사이클을 가지고 있지 않으면 즉 엣지들로 이루어진 사이클이 만들어져 있지 않으면 현재 상황은 되돌아기 아니다라는 거예요. 그건 확실한 사실이에요. 사이클이 없으면 되돌아기 아니다. 근데 만약에 이 그래프가 사이클을 가지고 있다면

사이클이 의미하는 바가 뭐였어요? 원형대기가 이루어졌다는 표시를 나타낸 게 바로 사이클이죠. 사이클이 있다면 그럼 무조건 대드락이 아니라 그건 아니에요. 만약에 리소스 타입들이, 리소스 타입마다 인스턴스가 하나밖에 없다면 이건 무조건 대드락이에요. 인스턴스가 하나밖에 없는데 사이클이 있더라. 그럼 대드락이고, 인스턴스가 여러 개가 있는 상황에서 사이클이 있더라. 이거는 대드락이 발생했을 수도 있고, 대드락이 아닐 수도 있어요. 그걸 한번 이해해서 보도록 할게요. 자, 현재 상황이 이렇다고 합시다. 현재 상황이 이렇다면 여기서 사이클을 한번 찾아봐요.

큰 사이클이 이렇게 되는게 하나의 사이클이 되죠. 작은 사이클로는 이렇게 가는거. 사이클이 존재해요. 사이클이 존재하는데 이 경우 리소스 타임마다 인스턴스가 하나만 있는게 아니라 여러개가 있는 것도 있죠. 따라서 대드락일 수도 대드락이 아닐 수도 있어요. 현재 이 상황은 대드락일까요? 꼼짝달살 못하는 상황일까요? 뭔가 일을 할 수 있는 상황일까요? 꼼짝달살 못하는 상황이죠.

진도로 못나가는 P1, P2, P3가. P1이 일을 하려면 R1을 잡아야 되는데 R1이 P2한테 가있고 P2가 진도가 나가서 R1을 반납해야만 P1은 일을 할 수 있죠. 근데 P2가 진도를 나가려면 R3를 확보를 해야돼요. 근데 R3가 P3한테 가있죠. 그래서 P3가 R3를 반납할 때까지 기다려야 돼요. 근데 P3는 일을 하려면 R2를 받아야 돼요. 근데 R2는 두 개의 인스턴스가 P1과 P2한테 가까워있어요. 근데 P1, P2는 서로가 막 기다리고 있어가지고 P3까지 기다리고 있어가지고 일을 못하고 있죠. 그러니까 서로가 서로를 기다리면서 꼼짝할 수 없는 상황이 발생해 보는 거예요

대드락이라는 건 같이 하죠. 그럼 이 상황을 봅시다. 이것도 똑같이 사이클이 존재하죠. 요렇게 가서 요렇게 가서 요렇게 사이클이 존재해요. 근데 이건 과연 대드락일까? 이건 대드락이 아니에요. 리소스 타입마다 인스턴스가 두 개씩 있기 때문에 대드락일 수도 있고 아닐 수도 있는데 이 경우는 대드락이 아니라는 거예요. 왜요? P1이 일을 하려면 R1 인스턴스가 P1인데 현재로서는 R1 인스턴스 두 개가 P2, P2한테 다 가 있죠. 그래서 P1은 움직이질 못해요. 그러나 P2는 현재 더 이상 요구하는 리소스가 없어요. 없기 때문에 이놈은 일을 할 수 있다는 뜻이죠. 일을 해가지고 언젠가는 일이 끝날 테고 그러면 자기가 잡은 이 리소스 인스턴스를 반납하죠.

반납하면 이게 P1한테 할당될 수 있게 되죠. P1은 R1을 받았으니까 자기가 필요로 하는 R1과 R2를 다 할당받게 되고 따라서 P1도 일을 다할 수 있게 되죠. P1이 일을 다하게 되면 자기가 확보한 리소스 R2도 반납하게 되겠죠. R2를 반납하면 이 인스턴스가 이걸 요청한 P3한테 할당할 수 있겠죠. P3도 자기가 필요로 하는 R1과 R2를 다 받게 된거죠. 그러니까 일을 할 수 있게 되죠. 따라서 P3도 일을 할 수가 있게 되고 P4는 더 이상 필요로 하는 리소스가 아예 없으니까 당연히 일을 그만 지을 수 있는 거고 따라서 모든 프로세스들이 다 일을 할 수 있게 된거에요. 그래서 대드락이 아니죠. 그래서 우리가 볼 수 있듯이

리소스 Allocation 그래프에서 사이클이 존재한다고 해서 반드시 되드락이 되려면 리소스마다 인스턴스가 하나밖에 없으면 무조건 되드락이다. 그 사실은 변하지 않는 사실이에요. 그런데 리소스마다 인스턴스가 여러개의 리소스가 있는 경우는 상황에 따라 달라진다. 그 상황이 어떤 상황이냐에 따라서 되드락일 수도 있고 되드락이 아닐 수도 있다. 그래서 우리가 그래프를 보면서 이것을 따져봐야 되죠. 따져보는 행위를 우리가 알고리즘이 할 수 있어야 돼요. 그래서 그래프만 딱 보고 사이클이 있네? 그러면 되드락이네? 쉽게 결정할 수 있는 문제는 아니라는 거예요. 그래서 쉽게 결정할 수가 없기 때문에 그걸 결정하는 알고리즘이 필요하겠죠? 그걸 우리가 볼 필요가 있는 거예요.

자 어쨌든 리소스 확보를 위해서 서로 경쟁하면서 원형 대기가 일어날 때 대드락이 발생한다고 했고 그러면 대드락이 발생할 가능성은 충분히 존재한다면 그러면 오프레이팅 시스템은 대드락에 대해서 어떻게 대처를 해야 될 것이냐 우리는 그거를 사실 배우려고 하는 거예요 대드락이 대처하는 OS의 자세 크게 3가지 종목이 있어요 첫 번째 종목이 절대로 대드락 자체가 발생하지 못하도록 만들어버리는 방법 우리는 그걸 대드락 프리벤션 그리고 대드락어보이던스라는 방법이라고 해요 그래서 이 두 방법은 서로 방법이 달라요 프리벤션이라는 방법과 어보이던스라는 방법이 따로 존재해요 어쨌든 프리벤션 방법이던 어보이던스라는 방법이던 대드락은 절대로 발생하지 않게 만드는 방법이에요 두 번째 방법이 OS가 대드락을 허용한 거예요 대드락 발생해 오케이 발생하는 거 허용할게 대신에 대드락이 발생하게 되면 그때 가서 도취해줄게 어떻게? 그 대드락을 해소하기 위한 뭔가 일을 해줄게 OS가

그게 바로 데드락 디텍션이라는 방법이에요. 데드락을 계속 간지하는 거예요. 데드락 발생했나 했나 했나 보면서 어? 발생했네? 그럼 내가 조치해줄게. 리카보리 해줄게. 호쿨 해줄게. 이게 바로 디텍션 방법이에요. 프리펜션이나 어보이든스에 따라서 프리펜션이나 어보이든스는 데드락 자체가 발생할 수 없게 만드는 거예요. 아예. 자, 다음에 세 번째 방법이 뭐냐? 데드락을 무시하는 전략이에요. 발생하려고? 발생해. 발생했어? 그럼 딱히 하고자. 말도 안 되죠, 그죠? 그게 무슨 방법이에요? 그런데 방법 맞아요. 실제로 대부분의 종룡체제가 사용하고 있는 방법이 이 세 번째 방법이에요. 대드람 무시 전략.

발성하면 끝까지 키면 되잖아. 왜 이 방법을 써냐? 실제로 그만큼 데드락이 발생할 확률이 낫다는 뜻이에요. 데드락은 정말 기가 막히게 절묘하게 원형 대기가 이루어져야만 발생하는데 요즘 운영체, 요즘 컴퓨터 시스템들은 자원이 워낙 풍부해가지고 풍족해가지고 웬만하면 자원이 부족한 일이 발생하지 않아요. GPU도 빠르고, 매복이 크고, 버스도 빠르고, 그리고 소프트웨어 자원 마셔도 소프트웨어 자원이 데드락이 걸리면 누군가가 락을 잡고 있을 때 내가 그 락을 기다려야 되잖아요. 근데 워낙 CPU가 빠르다 보니까 그 락을 잡고 일을 하는 시간이 너무나도 짧다. 그러니까 락을 잡자마자 바로 나와버려요. 그러니까 락을 잡은 상태에서 기다리고 이런 일이 잘 발생하지 않는다는 거죠.

그래서 소프트웨어 리소스에 대한 자원 답보 경쟁도 그렇게 하지 않더라. 일반적인 OS에서는. 근데 제가 이 말을 한다고 해서 이런 일이 부르지 않는다는 건 아니에요. 특히 왓 같은 경우, 세마포나 왓 같은 경우에는 반드시 자원 답보를 위한 경쟁이 치열하게 실제로 존재해요. 특히 요즘처럼 코어가 많고 많은 스레드가 동시에 돌 때는 왓에 대한 경쟁이 무척 치열하다고요. 그래서 대저라이 가능성이 있어요. 특히 데이터베이스 시스템 같은 경우는 엄청나게 많은 사용자가 동시에 접근해서 일을 요청하죠. 그래서 그 일을 처리하기 위한 스레드들이 다 만들어진다고요. 그럼 그 스레드들이 동시에 데이터베이스와 공유된 데이터에 접근을 하게 되기 때문에

운영체제 입장에서 볼 때는 운영체제가 관리하는 자원들은 그렇게 심하게 경쟁이 일어나지 않기 때문에 대드락이 발생하는 경우는 별로 없더라구요 그래서 대드락이 발생해서 컴퓨터를 껐다 켜야 되는 빈도 그 빈도보다 다른 문제 때문에 컴퓨터를 껐다 켜야 하는 빈도가 더 높더라 일반적으로 그래서 굳이 대드락까지 신경 쓰기 위해서 OS가 뭔가 복잡한 일을 해줄 필요는 없다 대드락이 신경 쓰기 위해서는 계산을 해야 되잖아요 지금 대드락이 발생했을까? 아니면 지금 대드락 발생하면 안되는데 그럼 이렇게 해야 되는데 이런 조치를 취하기 위해서만 Prevention이나 Avoidance이나 Detection이라는 방법을 통해서 조치를 취하기 위해서만 OS가 계속 뭔가 일을 해줘야겠다는 거예요 그 일이 오히려 CPU를 잡으면 구매물을 잡아붙죠 그래서 오히려 그 놈이 시스템 성능을 저하시키기 때문에 그렇게 낮은 확률로 발생하는 일 때문에 이렇게 평상시에 시스템 성능을 저하시킬 필요가 있냐

그리고 그 발생비도가 높났기 때문에 사용자들은 그에 대해서 잊지 못하는데 그래서 신경 쓰지 말자 라는 전략을 대부분의 OSS가 쓰고 있어요 근데 왜 우리 매우는 운영체제 시간에 운영체제가 가지고 있지도 않은 기능을 왜 운영체제 시간에 배워야 되냐 이 개념이 중요하거든요. 개념이. 비록 운영체제 내에서는 그 일이 발생하지 않지만 아까 말했듯이 DBMS 데이터베이스 관리 시스템, Oracle 이라든지 MySQL, PostgreSQL 이란 DB 시스템에서는 이 문제가 매우 심각한 문제가 될 수 있다는 거예요 그래서 운영체제 내부에서 가 아니라 바깥쪽에서 일어날 수 있는 데이터베이스 개념을 누가 가르치는 것이냐 DBS만 일어나면 DBS 가르치면 되는데 DB 뿐만 아니라 다른 문화에서도 일어난다고 이랬던 게 운영체제 바깥에서

각각의 가격에서 다 가르칠 수는 없잖아. 그래서 운영체제에서 그걸 가르치자는 거야. 전통적으로 운영체제에서도 문제가 발생했기 때문에, 옛날에는 자원이 부족한 시기에서는 발생했기 때문에 고전적인 운영체제의 문제는 맞고, 그렇다면 고전적인 운영체제의 문제니까, 그리고 다른 분야에서도 다 발생하는 문제니까 운영체제에서 다뤄주자 라고 해서 대드락을 다루고 있는 거예요. 착하죠? 그리고 보면 운영체제는 수업이. 자 그러면 이제 하나씩 하나씩 해보도록 합시다. 대드락에 대처하는 방법. Prevention, Avoidance, Detection. 이 세가지 방법을 하나씩 보도록 합시다. 자 첫번째가 Prevention 방법.

이 Prevention은 아예 대드락 근처도 못 가진, 대드락 자체가 이동할 수 있는 조건 자체를 없애고 있는 거예요. 무슨 말이냐면, 대드락이 발생하려면 4가지 조건이 동시에 만족되어야 된다고 했죠. 그 4가지 조건 중에 하나를 아예 만독되지 못하게, 원천적으로 만독되지 못하게 만들어버리는 거예요. 그러면 대드락은 발생할 수가 없죠. 그죠? 그러면 4가지 조건 중에 하나라도 없앨 수 있는 방법을 하나는 따져봅시다. 첫 번째 조건, 상호 배제 조건. 자원을 공유할 수 있게 만들자. 이건 우리가 할 수 있는 게 아니에요. 자원을 공유할 수 있는 자원이냐 공유할 수 없는 자원이냐는 그 자원의 특성에 의해서 이미 결정이 나겠어요.

그래서 물리적으로 애초에 불가능한거에요. 그래서 자원에 대한 공유를 할 수 있게 만들어서 대드락이 발생하지 못하게 만들자는 불가능한 접근 방식이란 뜻이에요. 변고에서 관여할 수 있는 문제가 아니기 때문에. 자 그럼 두 번째 조건을 어떻게 없애보자. 홀드 앤 웨이트 조건로 없애보자. 이미 홀드 앤 웨이트가 뭐였어요? 프로세스가 일을 할 때 자기가 필요한 자원을 확보하려고 하다가 어? 이거 확보 못하겠네? 다른 놈이 잡고 있네? 어? 그러면 난 착하니까 내가 이미 확보한 자원까지도 다 반납하고 기다리자. 그렇게 움직이지 않는다는게 바로 홀드 앤 웨이트죠. 자기가 이미 확보한 자원은 꼭 쥐고 있으면서 추가적으로 확보할 자원을 기다리는 텐데 그걸 홀드 앤 웨이트 라고 했죠? 그럼 홀드 앤 웨이트 조건을 없애버리려면. 이 조건이 충족되지 못하게 하려면 어떻게 해야 돼요?

자기가 추가적인 자원을 확보할 수 없게 되면, 그러면 자기가 이미 확보한 자원마저도 다 손에 쥐고 있으면 안 된다는 거예요. 손에 쥐고 있지 못하도록 만드는 거예요. 그러면 홀드에 웨이트 조건이 없어져 버리죠. 그래서 이 조건을 현실화시키려면 어떻게 하면 되냐면, 내가 어떤 자원들이 1, 2, 3번을 확보하고 싶다. 그러면 1번만 확보하고 2번, 3번을 기다리고 이런 일이 부르지면 안 되잖아. 그러면 1, 2, 3번에 대해서 동시에 다 확보해야 돼. 동시에 다 확보하든지, 아니면 하나라도 확보가 안 될 것 같으면 아예 하나도 확보를 안 하든지.

이런식으로 움직이면 일부를 잡고 나머지를 기다리거나 일어나지 않죠 그렇게 동작하게 만들면 되지 않냐는거에요 그래서 홀드앤웨이트 조건을 없앤 무기력화시키는 방법 이 조건이 만족되지 못하게 만드는 방법이 딱 그거에요 프로세스가 필요로 하는 모든 자원을 한꺼번에 다 확보하고 당분에 다 확보할 수 있으면 그걸 다 확보하고 하나라도 확보를 못한다면 그러면 아무것도 확보하지 말자 잡지 말자 라는 방식으로 프로세스를 동작시키는거 그러면 홀드앤웨이트 조건은 절대로 발생할 수 없기 때문에 대드락이 일어날 수가 없는거에요 수단이지 알겠죠? 그렇게 만드는 방법이에요 홀드앤웨이트가 이렇게 하면 내가 지금 확보할 수 있는 자본을 확보하지 않고 기다려야 되죠.

1번 2번을 확보할 수 있고 3번을 확보 못하는데 3번 때문에 1번 2번까지도 확보를 안 하고 있는 거죠. 나중에 3번까지 확보할 수 있게 될 때 그때 1번 2번 3번을 다 확보해야 돼요. 근데 그때 1번 2번이 남아있다는 보장이 없죠. 그래서 3번이 어벨을 했었어. 그럼 어? 됐네 그럼 1번 다 확보해야지 라고 했더니만 이번에는 1번이 확보가 안돼. 그럴 수 있겠죠. 그래서 진도를 못 나가는 거예요. 그래서 남아있는 자원은 확보를 하고 있어야 내가 3번이 어벨을 했을 때 바로 3번을 잡아서 일을 바로 진행할 수 있게 되는데 그게 아니라 남아있는 자원을 확보하지 않고 그대로 놔둬리니까 남아있는 자원에 대한 유틸라이제이션이 떨어져서 전체적으로 시스템 전체의 유틸라이제이션이 떨어지고 아까 말씀드렸듯이 이것 때문에 확보 못했다가 나중에 이게 가능해서 확보할 수 있다 보니까 다른 놈이 어벨을 하지 않아가지고 확보 못하고 그래서 나는 계속 확보를 못하는 거야. 그래서 타베이션이 발생할 수도 있겠죠. 그런 일도 발생할 수 있고 해서 이런 문제들이 있더라. 홀드 앤 웨이트 조클럽 쓰려고 하다 보니까.

여기까지만 알겠는데요. 다음 세번째 조건, no preemption 조건을 없애보자. 이게 무슨 말이냐면, 아까 어떤 프로세스가 자원을 잡고 있으면 그 자원을 강제로 뺏을 수는 없다. 자기가 자발적으로 놓치기 전에는 강제로 뺏을 수 없다는 조건이었죠. 그런데 이 조건을 없애버리자. 그럼 무슨 말이에요? 이 프로세스가 자원을 확보할 수가 없어서 기다리고 있으면 그 놈이 갖고 있는 자원을 강제로 OAS가 뺏어버리자는 거야. 강제로. 즉, hold&wake 조건을 허용해줘요. 일부를 잡고 다른 프로세스를 기다리는 걸 허용해주는데, 그런데 다른 프로세스들이 자원을 받기 위해서 기다리는 순간 이 프로세스가 이미 잡고 있는 자원을 OS가 뺏어버린 거야.

그러면 결과적으로 어떻게 동작해요? 어떤 프로세스는? 1부를 잡고 기다릴 수가 없죠. 1부를 잡고 잡았는데 1번 잡고 2번 잡고 3번 잡으려고 하는데 실패했어. 그러면 OS가 1,2번을 빼서가 버린거야. 어떻게 되는지 알겠죠? 홀데레이트하고 차이가 뭐에요? 홀데레이트는 1번 잡고 2번 잡고 3번 기다리고 이게 안되요. 1,2,3번을 다 동시에 해보고 동시에 가능하면 동시에 잡아보여. 1번,2번 잡고 3번을 기다리면 이런 순간이 아예 존재하지 않아요. 1,2,3번을 동시에 잡고 동시에 놓고 하는건지. 그게 홀데레이트를 못하게 하는 방법이고. 1번 잡는거 오케이, 2번 잡는거 오케이. 3번 잡는데 실패했어? 그럼 1,2번 동시에 놔. 이렇게 되는게 높이 1편이에요. 결과적으로는 같은데 과정이 다를 뿐이에요.

자, 노프리엠션도 사실 결과적으로 홀덴 웨이트하고 똑같기 때문에 똑같은 문제를 가지고 있죠. 다음 마지막, 서클라 웨이트 조건을 없애 버리자. 지금 우리가 앞에서 봤던 홀덴 웨이트하고 노프리엠션도 그런 자원 활용률이 늘어진다라는 문제가 다 존재하는 거예요. 그래서 별로 좋은 방법이 안 되는 거죠. 서클라 웨이트는 어떻게 할까? 서클라 웨이트 조건이 발생하지 않도록 하는 방법은 뭘까? 이게 복잡해 보이지만 사실은 복잡하지 않아요. 원형 대기가 발생하지 않도록 만드는 조건이 뭘까? 어떻게 하게 되냐면, 자원의 종류마다 번호를 다 배겨요. CPU는 1번, 메모리는 2번, 3번, 4번 이렇게 자원마다 복론을 다 빼겨서

어떤 프로세스가 자기가 필요로 하는 자원이 있으면 그 자원들의 번호를 보고 번호가 낮은 번호부터 순차적으로 확보하라고 순서를 만들어 줘버린거에요. 그럼 내가 3번, 5번, 7번 자원이 필요하다 어떤 프로세스가 그러면 7번 먼저 확보해라 이게 안돼요. 7번이 어베일러블 하자면 7번은 지금 확보하면 안돼. 3번을 먼저 확보하고 그 다음에 5번을 확보하고 그 다음에 7번을 확보해야 돼요. 비록 7번이 어베일러블해서 확보가 가능하고 3번은 사용인을 확보할 수 없어서 없는 상황이라면 원래대로라면 확보 가능한 7번을 먼저 확보할텐데 서큘러 베이셔을 없애는 조건을 돌리다보면

확보가능한 7번을 먼저 확보하지 말고 확보 불구하다가 3번을 일단 기다려라 그리고 3번이 확보가 가능하면 3번을 확보하고 그 다음에 5번이 확보가 가능해지면 5번을 확보하고 그 다음에 7번이 확보가 가능해지면 7번을 확보하라 이렇게 순서대로 자원의 순서대로 확보를 하라는 거예요 자 그러면 어떤 일이 벌어져요? 원형 대기가 왜 발생하지 않을까요? 우리가 원형 대기 조건을 봐요 어떻게 하면 원형 대기가 발생해요? 어떤 프로세스 P가 이 다음 프로세스를 기다리고 또 이 놈이 이 놈을 기다려요 이게 원형 대기죠? 그러다가

제일 마지막에 요 놈이 다시 이쪽으로 와야 원형 대기가 되죠 자 그런데 요 관계가 지금 형성됐다면 요 관계가 요 요 에티는 없다고 씹시다 이렇게 선형적으로 주 리니하게 대기하고 있는 관계다 그러면 요 놈이 확보한 자원의 숫자하고 요 놈이 확보한 자원의 숫자를 비교를 입으세요 요 놈은 작은 것부터 갖고 있으니까 요 놈이 갖고 있는 자원의 번호보다 요 놈이 요 놈한테 기다리고 있는 자원의 번호가 더 크죠 그죠? 더 큰 번호의 자원을 기다리는 거예요 그래서 모든 프로세스는 자기가 다른 프로세스를 기다린다 하면 다른 프로세스의 자원을 기다리는 건데 그 자원의 번호가 내가 이미 확보한 자원보다 더 큰 번호를 가지는 자원을 기다리는 거예요 무조건 그죠? 그런데 제일 마지막 프로세스가 제일 첫 번째 프로세스로 다시 돌아오려니 빼겠지

요게 만들어지려면 똑같이 그 조건이 되어야 돼요. 그리고 제일 마지막 프로세스가 갖고 있는 자원보다 지가 기다리는 첫 번째 프로세스가 함께해서 기다리는 자원의 번호가 더 높아야 돼요. 그렇죠? 그럴 수가 있어요? 그럴 수가 없죠. 자기가 기다리는 자원의 번호는 자기가 기다리는 프로세스가 확보한 자원의 번호보다 번호 안에 있는 거고 내가 이미 확보한 자원의 번호보다는 무조건 높아야 돼요. 높아야 되는데 내가 찾고 있는 번호보다 더 낮은 번호를 갖고 있는 프로세스를 내가 기다릴 일이 존재할 수가 없다는 거예요. 무슨 말인지 알겠죠?

나는 이미 제일 마지막 프로세스는 7번까지 확보한 프로세스야. 근데 제일 첫 번째 프로세스는 1번만 확보하고 있는 놈이야. 7번까지 확보한 놈이 1번을 기다리는 건 없다는 뜻이에요. 순서대로 확보를 해야 되기 때문에. 그래서 이 조건 순서대로 자원번호를 순서대로 확보를 하는 조건에 맞춰서 자원을 확보하다가 보면 백 엣지가 만들어질 수가 없다는 뜻이에요. 뒤로 돌아가는 엣지가. 그래서 원형 대기가 애초에 불가능해지는 거예요. 아시겠죠? 그래서 이 서큘라 웨잇을 없애지는 조건은 이 자원의 번호에 자원마다 번호를 붙여가지고 번호가 높아지는 순서대로 자원을 확보해야 된다는 거예요. 근데 서큘라드 웨이트 역시 자원 활용의 효율성이 들어서요. 왜 그럴 것 같아요.

내가 아까 말했듯이 1번, 3번, 7번 자원을 필요로 하는데 7번은 현재 사용 가능해. 근데 1, 3번이 사용 불가능해. 그럼 원래대로 하면 7번부터 잡고 1, 3번을 기다리기 좋죠. 그래서 1, 3번이 어벨러블을 해주는 순간 바로 일을 할 수가 있겠네요. 근데 이 조건, circular way스를 없애는 조건에 따르다보면 7번이 어벨러블 한데도 불구하고 7번은 잡지도 않아요. 안 잡고 1번을 기다리고 있다고. 그죠? 그러니까 7번은 놀고 있는, 7번 자원은 놀게 되는 거예요. 그래서 전체적으로 리소스 유트럴 제시를 들여지게 되는 거예요. 그래서 지금까지 말한 데드락 프리벤션을 위한 4가지 방법 중에 첫 번째 방법, mutual exclusion 방법은 애초에 불가능한 방법이고 나머지 3가지 조건 중에 하나를 없애는 방법들은 전부 다 공통적으로 자원 활용의 효율성을 들여드려서 시스템 전체의 스루프스를 감소시키는 방법이라는 거예요. 별로 좋지 않은 방법이란 거죠. 그래서 데드락 프리벤션은 본질적으로 별로 좋은 방법이 아니에요.

흠! 너무 문제 때문에 아시겠죠? 지금까지 말이 좀 빨랐죠? 오늘 할 내용이 좀 많아가지고 마음이 급해서 인제 말이 좀 빠르게 나오네요. 천천히 하려고 노력할게요. 지금까지 본 방법, 즉 대드락 prevention 방법은 자원 활용의 효율성이 떨어지기 때문에 안 좋은 방법이라고 했죠? 그래서 사람들이 그 방법을 쓰기 곤란하겠다 싶어서 만든게 avoidance라는 방법이에요. 이건 회피 방법이에요. Prevention은 대드락의 싹을 자르는 방법이죠. 대드락 방지 방법이고, avoidance는 싹을 자르지 않아요. 즉 4가지 조건을 다 허용해요. 다 허용하되, 동작 과정에서 대드락이 발생하지 않도록 제어하겠다는 거예요. 어떻게 제어할 거냐 하면, 사실 운영체제 입장에서 보면 자기가 상태를 제어할 수 있어요. 즉 어떤 프로세스가 나 이 자원 좀 줘오라고 요청했을 때, 리퀘스트를 했을 때 그 자원을 지금 당장 주면 주는 길로 가게 되고 좀 기다려봐, 나 좀 이따 줄게 라고 미루면 또 다른 길로 가게 되는 거죠. 미루는 동안의 상황이 막 바뀌니까. 그래서 os가 자원에 대한 요청을 받아들이냐, 지금 당장 받아들이지 않냐에 따라서 서로 다른 길을 가게 되는 거예요.

즉 오프리킹 시스템은 시스템이 동작하는 과정에서 계속 여러가지의 길 중에서 하나를 선택하고 있다는 뜻이죠. 그래서 선택하는 과정에서 짱을 봐서 이 길로 가면 대드락이 나중에 발생할 수도 있겠는걸? 이라는 생각이 들면 아예 그 길로 가지 않겠다는 거예요. 그리고 대드락이 미래에 발생할 가능성이 없다고 판단되는 안전한 길로만 나는 걸 타겠다. 그래서 프로세스가 자원을 요청하고 지금 현재 자원이 할당 가능하게 남아있다 하더라도 남아있는 자원을 요청한 프로세스한테 바로 주면 나중에 대드락이 발생할 수도 있겠네?

라고 판단이 되면 줄 수 있는 상황에서도 안주버리는 거예요. 안주고 기다리다가 안전한 길로 가게 되는 거고, 이걸 주더라도 대드락 발생할 가능성이 없네? 그럼 주는 거예요. 그래서 대드락이 발생하지 않도록, 미래에 발생하지 않도록 안전한 길로만 가겠다. 요리조리 피해가지고 대드락을 회피해서 안전한 길로만 다니겠다는 게 대드락어보이던스예요. 그러면 우리가 대드락을 회피하기 위해서는 미래에 대드락이 발생할 가능성을 우리가 판단할 수 있어야 된다고요. 판단을 해야 된다는 뜻은 미래를 예측한다는 방법인데, 미래를 예측하려면 어떤 정보가 있어야 예측이 가능하죠. 그래서 어보이던스 방법은 미리 정보를 수집해야 돼요.

미래 예측에 필요한 정보를 수집해 가지고 그 정보를 바탕으로 안전성을 평가할 거예요. 안전성을 평가해서 안전하다고 판단이 되면 그 길로 가겠다. 즉 요청을 받아들이겠다. 이렇게 결정을 하겠다는 뜻이에요. 그러면 미리 확보하는 정보가 뭐냐. 각 프로세스마다 자기는 일을 할 동안에 이 자원은 몇 개를 최대 사용할 거고, 저 자원은 몇 개를 최대 사용할 거고, 이런 식으로 각 자원의 타입마다 최대 자원 사용량을 다 선언하게 만드는 거야. 그래서 그 정보를 미리 확보를 하고 있어요. 그 정보를 가지고 현재 실제 자원 할당된 상황을 비추어 상황과 그 정보를 다 고려해서 알고리즘을 돌려 가지고 절대로 원형 대기가 발생하지 않는 길로만 가겠다는 게 되돌아버이던 사이구의 중이에요.

그래서 현재 자원이 이렇게 할당되어 있는데, 그리고 이 프로세스는 최대 몇 개를 사용한다고 했어. 그런 정보까지 결합을 시켜서 내가 현재 요청한 이 자원을 주면 이 알고리즘에 따라서 대들락이 발생할 가능성이 있네? 그러면 요청이 왔더라도, 즉 자원이 남아있더라도 그 자원을 주지 말고 내가 이 자원을 줬다 하더라도 따져보니까 대들락이 발생할 가능성은 없어. 원형 대기가 일어날 가능성은 없으라고 판단이 되면 바로 그 자원을 줘버리겠다. 그런 결정을 하겠다는 거예요.

그래서 우리가 이 길이 과연 안전한 길인가 아니면 안전하지 않은 길인가를 판단하는 알고리즘이 바로 핵심적인 알고리즘이 될 수 있는 거죠. 그래서 일단은 안전한 길, safe state, 안전한 상태라는 것을 먼저 정리를 하고 우리가 그 상태로 밝혀진지 밝혀진지 판단하는 알고리즘을 좀 이따 다시 보도록 합시다. 안전한 상태란 무엇인가? 어떤 프로세스가 이 자원을 달라고 요청했어요. 그럼 그 자원을 그 놈한테 줬을 때, 지금 당장 줄 수 있어서 줬을 때, 그 준 상태가 안전한 상태일까?

즉 대드락이 발생할 수 없는 안전한 상태일까? 그거를 판단하고 안전한 상태이면 실제로 그 자원을 주겠다는 거야. 그래서 자원을 줬다 치고 줬을 때 안전하면 주고 실제로 주고 줬다 쳤을 때 안전하지 않으면 아예 주질 않겠다. 실제로는 주질 않겠다 라고 판단할 거고 그러면 줬을 때 안전한 상태인지를 어떻게 판단할 것이냐? 안전한 상태라는 것은 그 상태에서 모든 프로세스가 다 종료될 수 있는 프로세스의 종료 시퀀스가 존재하면 안전한 상태라고 우리는 판단을 해요.

예를 들어서 프로세스가 n개가 있다고 칩시다. n개가 있는데 즉 p1부터 pn까지 n개가 있는데 각각의 프로세스가 자기가 이미 확보한 자원의 양하고 그리고 자기보다 먼저 종료한 프로세스가 종료되면서 반납하는 자원의 양을 합해가지고 자기가 충분히 이를 끝마칠 수 있느냐를 따져보는 거에요. 그래서 이 시퀀스가 뭐냐면, 예를 들어서 p1부터 pn까지 이런 시퀀스가 만들어졌다는 것은 p1의 입장에서는

현재 자기가 확보한 자원과 남아있는 자원을 가지고 나는 충분히 일을 끝마칠 수 있어 라고 해서 P1이 직접 끝날 수 있고 그럼 P1이 끝나면서 자기가 이미 확보한 자원을 반납하겠죠 그럼 그 반납한 자원까지 P2한테 줘가지고 P2가 자기가 이미 확보한 자원과 P1으로부터 반납받은 자원까지 합하고 시스템에 여전히 남아있는 자원까지 합해가지고 그 모든 자원을 P2한테 몰빵을 시켜주면 P2가 다 끝날 수 있더라 그러면 P2가 끝이 나는거죠 그럼 P2가 끝이 났으니까 P2가 가진 자원 마저 또 반납하겠죠 그럼 그걸 다시 또 P3한테 줘요 그럼 P3는 P2한테 받은 자원과 시스템에 나와있는 자원 그리고 자기가 이미 확보한 자원을 다 몰빵받아가지고 자기가 그쳐낼 수 있고 그럼 또 자기가 이미 확보한 자원을 그 다음 놈한테 반납하고 이런 식으로 해서 제일 마지막 프로세스한테까지 모든 프로세스가 다 끝이 날 수 있는 E-Sequence E-Sequence가 존재한다면

그러면 그 상태는 안전한 상태가 된다는 뜻이에요. 즉 몰빵 시스템이에요. 몰빵 시스템. 모든 자원을 이 프로세스한테 다 할당해주고, 가용 자원을. 그래서 그 프로세스가 끝난다면 그 프로세스한테 반납받은 자원까지 포함해서 모든 자원을 그 다음 프로세스한테 할당해주고, 이런 식으로 해서 모든 프로세스가 다 끝난 수 있는 그 시퀀스가 존재한다면, 그러면 그 상태는 안전한 상태다 라고 우리가 판단하겠다는 거예요. 무슨 말인지 알겠죠? 자, 그래서 우리가 이 safe state, 안전한 상태다 라는 게 우리가 정의가 됐으니까, 어떤 시스템이 현재 safe한 state에 있다 라고 하면, 그러면 이 state에서는 대략이 발생하지 않는다는 거예요.

끝을 낼 수 있는 방법이 있으니까 대드락이 발생하지 않는 거예요. 그런데 그런 시퀀스가 존재하지 않더라. 아무리 몰빵을 시켜줘도 그런 시퀀스를 차지낼 수가 없더라. 모든 프로세스를 끝을 낼 수가 없더라. 그러면 unsafe라고 해요. unsafe state더라. 그러면 이 unsafe state는 대드락이 발생할 가능성이 있는 상태예요. 왜 가능성이냐. 그런 시퀀스가 존재하지 않으면 모든 프로세스가 끝이 문다니까 당연히 대드락이 발생하는 거 아닙니까? 당연히 발생할 수밖에 없는 거 아닙니까? 라고 생각할 수 있는데 우리가 safe하냐 safe하지 않냐를 판단하는 방법에 뭘 사용을 하냐 하면

어떤 프로세스가 우리가 끝이 날려면, 그 끝이 난다는 기준을 뭘로 잡냐 하면, 처음에 우리가 수직한 정보 있죠. 즉, 어떤 프로세스는 일을 하기 위해서 최대 몇 개의 자원을 필요로 한다. 이 타이번 몇 개, 저 타이번 몇 개, 저 타이번 몇 개. 최대 자원 요구량을 선언을 했죠. 그 최대 자원 요구량을 충족시킬 수 있을 때만 그 프로세스는 끝이 난다고 우리가 가정을 하고, 시퀀스를 찾았다고요. 그래서 그런 시퀀스가 있으면, Safe sequence, Safe state라고 판단을 내렸는데, 실제로 프로세스는 최대 자원 요구량을 동시에 요구하지 않아요. 즉, 1번 자원 3개, 2번 자원 5개, 3번 자원 7개를 나는 최대한 사용할 거야 라고 선언하는데, 3개, 5개, 7개를 동시에 줘야만 일을 할 수 있는 게 아니라고요. 예를 들어서 1번 3개 다 쓰고 나서, 1번은 다 썼어. 최대치만큼 사용해가지고 난 일 다 했어. 그래서 1번을 다 반납해버릴 수 있어. 그러고 나서, 그 다음 일을 하려고 하다보니까, 2번 자원이 3개가 필요해. 5개가 필요해. 2번 자원 5개를 받아서 다 썼어. 그리고 또 다 반납해.

그리고 3번 자원만 7개를 필요해. 이럴 수 있잖아요. 즉, 3가지 타입의 자원을 동시에 사용하지 않고 번갈아가면서 사용할 수 있잖아요. 그러면 실제로 전체적인 자원 사용을 적게 하면서도 프로세서는 이를 끝마칠 수가 있게 된다고요. 그런데 우리가 safe state를 판단할 때는 그 3가지 종류의 자원의 최대 사용량을 동시에 다 만족시킬 때만 이 프로세서는 더 친한다는 가정하에서 safe sequence를 찾아낸다고요. 따라서 그 sequence가 존재하지 않는다고 해서 반드시 대드락이 발생하는 것 아니에요. 그 프로세서가 최악으로 동작할 때 즉 모든 종류의 자원의 최대치를 한꺼번에 달라고 요청할 때만 대드락이 발생하는 거지. unsafe 상태에서 대드락이 발생하는 거지. 그게 아니라 아까 앞에서 예를 들었듯이 번갈아가면서 최대치를 사용하게 되면 동시에 최대치를 다 받는 게 요청한 게 아니기 때문에 최악의 경우로 동작하지 않는다면

무슨 말인지 알겠죠? 그래서 unsafe라 하더라도 반드시 대드락이 발생하는 건 아니고 unsafe 상태에서 대드락이 발생하려면 모든 프로세스가 동시에 모든 종류의 자원의 최대치를 다 달라고 동시에 요청했을 때만 그런 일이 발생할 수 있다는 거예요. 대드락이 발생하는 거예요. 그런데 일반적으로는 그렇게 동작하지 않아요. 최대치를 동시에 요청하는 게 아니라 이 자원의 최대치를 요청했다가 다 반납하고 저 자원의 최대치를 요청했다가 반납하고 이런 식으로 하기 때문에 우리가 너무 over해서 판단을 한 거예요. safe하지 아닌지를. 그래서 over해서 판단하기 때문에 unsafe 하다가 반드시 대드락이 발생하는 게 안 된다는 거예요. 그럼에도 불구하고 over해서 알고 있으면 over를 하더라도 우리는 안전한 쪽으로 가겠다. 즉 unsafe하다고 해서 대드락이 발생하는 건 아니지만 조금이라도 일만의 가능성이 존재하기 때문에 그 가능성이라는 게 그 프로세스들이 최악의 경우로 동작하는 경우를 말하는 거예요. 그 일만의 가능성이라도 존재하기 때문에 나는 그 기론은 가지 않겠다는 거예요. 그래서 매우 소심하게 움직이겠다는 뜻이에요. 소심하게.

그래서 우리가 그림으로 그려보면, 실제로 safe한 state에서는 절대로 되드락이 발생하지 않고, unsafe한 state라 하더라도 되드락은 매우 일부분에서만 발생한다. 즉 모든 프로세스가 최악으로 동작할 때만 발생한다 라는 거예요. 자 그러면, avoidance 알고리즘을 우리가 보도록 합시다. avoidance 알고리즘. 이 avoidance 알고리즘은 두 가지 경우로 나눌 수 있는데요. 각각의 resource type이 instance를 하나씩만 가지는 경우, 그리고 각각의 resource type이 여러 개의 instance를 가질 수 있는 경우, 이 두 가지로 나눌 거예요.

인스턴스가 하나만 있는 경우는 쉬워요. 리소스 알로케이션 그래프로 바로 결정을 할 수가 있어요. 세이프한지, 결정할 수가 있기 때문에 쉬운데 인스턴스가 여러 개일 경우는 좀 더 복잡해요. 그래서 그때 우리가 사용하는 방법을 뱅커스 알고리즘이라고 불러요. 우리가 하나씩 보도록 합시다. 자, 먼저 리소스 타입마다 인스턴스가 하나밖에 없는 경우를 보도록 합시다. 우리가 더보이던스 알고리즘을 사용하기 위해서는 전제 조건으로 모든 프로세스가 각 자원의 타입을 최대 얼마씩 사용할 것인가를 미리 선언한다고 했잖아요.

근데 자원 타임만한 인스턴스가 하나밖에 없다면 최대 사용량이 1이죠. 1. 따라서 최대 사용량을 선언할 때 사실은 이 자원을 사용할 거냐 말 거냐 이것만 선언하는 거예요. 최대 사용량이 1이기 때문에. 그래서 우리가 그래프에서 사용할 자원에 대해서는 etch를 그려주는 걸로 우리가 그 정보를 표시할 수 있다는 거예요. 그래서 그래프만 가지고도 우리는 이 문제를 해결할 수가 있어요. 인스턴스가 하나밖에 없는 경우에는. 그래서 리소스 알로케이션 그래프를 가지고 싱글 인스턴스일 경우에 avoidance 알고리즘을 공장시킬 수 있게 되더라.

그러면 최초에 나는 이 자원의 맥시멈 사용량이 얼마야 라고 선언하는 것을 맥시멈의 1이라고 했으니까 그냥 엣지 하나로 표현할 수가 있어요. 우리는 그 엣지를 claim etch라고 해요. 즉, 난 이 자원 사용할래. 두 자원은 사용하네. 이 자원은 또 사용할 거야. 이렇게 사용할 자원을 claim etch로 그리는 거예요. 그래서 이 프로세스에서 리소스로 가면 이 엣지가 claim etch고, 지금 당장 요청하는 건 아니지만, 미래에 나중에 내가 동작하기 위해서는 미래에 언젠가는 이걸 사용할 거야 라고 미리 선언해준 사전 정보라는 거죠. 그래서 우리는 이 claim etch를 dashdeline으로 점선으로 표시할 거예요.

그리고 동작하다 보면 자기가 나중에 사용할거야 라고 선언한 리소스에 대해서 실제로 달라고 요청할 때가 오겠죠 그죠? 실제로 달라고 요청하게 되면 그때 이제 claim edge가 request edge로 바뀌게 돼요 요청 edge로 request edge는 실선으로 그려질거에요 그래서 request edge는 반드시 claim edge가 있는 리소스에 대해서만 request edge가 그려지겠죠? 자기가 미리 사용할 거라고 선언한 것에 대해서만 그려질거에요 다음에 assignment edge는 실제로 그 요청이 request를 통해서 자원 사용을 할게 라고 자원 좀 주세요 라고 요청했을 때 그 요청을 받아들여서 자원을 할당하게 되면 assignment edge가 그려지는거에요 그래서 request edge가 assignment edge로 바뀌는거죠? 손수를 알겠죠? 클라임/매치 점성이 request/datch로 바뀌고 request/datch가 assignment/datch로 바뀔 거예요. 실제로 주게 되면

자 다음에 어사이먼트 엣지가 실제로 자원이 할당되었는데 그 프로세스가 그 자원을 사용하고 나면 반납하겠죠 반납하게 되면 어사이먼트 엣지가 이제 없어지겠죠 없어지면서 그냥 엣지가 사라지는 게 아니라 그 엣지는 다시 클레임 엣지로 바뀌어요 자원을 최대 1만큼 사용할 거야 라고 선언을 했는데 몇 번 사용할 거야 라고는 말이 없죠 그래서 또 사용할 수도 있어요 또 사용할 수도 있기 때문에 클레임 엣지는 다시 만들어 줘야 돼요 어사이먼 엣지로 사원 사용이 지나서 반납을 했더라도 클레임 엣지는 다시 만들어 줄 필요가 있어요 자 그래서 이제 알고 있으면 어떻게 돌아가냐면 최초의 프로세스가 시작을 하게 되면 클레임 엣지들이 먼저 그려질 거예요

클레이먼트에지들이 쫙 그려질거고, 그리고 어떤 프로세스가 리소스를 요청하게 되면 그러면 그 요청에 대해서 request에지가 만들어질거고, 클레이먼트가 request에지로 바뀌는거죠. 그리고 나서 그게 assignment에지로 어떻게 바뀌냐 하면, 내가 이걸 실제로 assign 했을때도 안전하면 assignment에지로 바꿔주고 assignment에지로 assign 했을때 안전한 상태가 아니면 assignment에지로 바꿔줘요. 그냥 request에지로 그대로 놔둬요. 잠시만요 알겠죠? 그렇게 동작하겠다는거에요. 그러면 안전한지 안한지를 어떻게 알 수 있냐? 싱글 인스턴스의 경우는 안전한지 안한지, 즉 safe state를 판단하는게 무척 쉬워요.

싱글 인스턴스일 경우는, 이걸 assign을 했을 때 사이클이 만들어지면 세이프하지 않은거에요. 무조건. 사이클이 만들어지면 세이프하지 않다. 따라서 assign을 했을 때 했다 치고 그래프를 그려봤을 때 사이클이 만들어지면 assign을 안해주고 claim request edge를 그대로 갖주고 다 주고 assign을 해줬더라도 사이클이 안 생기면 실제로 request edge를 assignment edge로 바꿔줄거에요. 실제로 자원을 할당 안단 소리죠. 자, 예를 통해서 한번 보도록 하겠습니다. 자, 현대 상태에요. 프로세스 P1은 원래 R2를 사용하겠다고 claim edge가 그려져 있는 상태에요. 이런 식으로 claim edge가 그려져 있고 P2는 P2 역시 R2를 사용할 거라고 언젠가는 사용할 거라고 claim edge를 그려봤어요. 그리고 R1은 실제로 리소스 R1은 P1한테 가있어요. 할당이 이미 assign앤드 edge가 만들어져 있고 P2는 R2를 달라고 request를 한 상태에요. 실선이죠. 요청을 한 상태에요. 이게 현재의 상태로 봅시다.

이 상태에서 P2가 리소스 R2를 달라고 요청했어요 실제로. 언젠가는 사용할거야 라고 클레임에 실을 들은 상태죠. 그러다가 P2가 나 지금 사용할래 라고 요청했어요. 그러면 이게 이제 어사이먼 대지로 바뀌죠. 어사이먼 대지 아니라 리퀘스트 대지로 바뀌죠. 이렇게 들여질거라고요. 그 상태에서 이제 OS가 판단해야 돼요. 보이던 알고있음이 판단해요. 만약에 이 요청이 받아들여지면 지금 실제로 R2는 남아있죠. 아무한테 달달이 안되있으니까 남아있어요. 남아있는 이 사원을 P2한테 줘가지고 이렇게 어사이먼 대지를 그려버리면 어떤 일이 벌어져요.

그러면 이렇게 한 바퀴 돈은 사이클리 만들어서 버리죠. 클레임에지까지 포함해서 사이클리 만들어서 버리죠. 그러면 나는 이거 주지 않겠다는 거예요. 이 리퀘스트를 받아들이지 않겠다는 거예요. 그냥 클레임에지로만 남겨주겠다는 뜻이에요. 왜 그럴까요? 안전하지 않다고 판단했으니까. 왜 안전하지 않을까요? 자 한번 봐요. R2가 P2한테 실제로 갔어요. 어사인됐어요. 그러면 실선이 어사인먼트가 이렇게. 이 R2는 P2한테 가 있고 P2는 R1을 요청하고 있고 R1은 P1한테 가 있고 이 상태에서 그 상태에서 P1이 실제로 R2를 요청을 해드리게 되면

이렇게 스탠드에 질크를 그려버리게 되면 그러면 완벽한 사이트죠. 완벽한 대드락이 되어버리는 거예요. 이렇게 되면. 그렇죠? 그래서 대드락에 그릴 가능성이 있다는 거예요. 물론 대드락이 안 그릴 수도 있어요. R2를 P2한테 준 상태에서 P1이 R2를 요청하지 않고 R1만 가지고도 현재 일을 끝마칠 수 있어 라고 해가지고 R1 가지고 현재 일을 끝마치고 R1을 반납해버릴 수 있죠. 반납하면 R1이 P2한테 넘어갈 거고 그럼 P2는 R1, R2를 다 확보했으니까 일을 다 끝마치고 둘 다 반납해버릴 수 있죠.

둘 다 반납해버리면 나중에 P1이 이걸 달라고 요청했을 때 R1과 R2를 다 얻을 수 있으니까 일을 할 수가 있게 되죠. 그죠? 그래서 어... 비록 P2가 R2를 요청을 하고 R2를 P2한테 줬다 하더라도 대드락이 발생할 수도 있고 발생 안 할 수도 있다는 거예요. P1이 어떻게 동작하냐에 따라서 P1이 최악으로 동작하면 P1을 지금 당장 달라고 해버렸으면 대드락이 발생하는 거고 P1이 R2를 달라고 요청하지 않고 R1을 먼저 반납하고 나중에 R2를 달라고 요청하면 대드락이 발생하지 않는 거예요. 무슨 말인지 알겠죠? 그죠? 그렇기 때문에

현대 상태가 unsafe 하지만 반드시 그게 deadlock이 발생한다는 걸 의미하지 않는다는 건 이해가 되죠? 그럼에도 불구하고 그 가능성 P1이 R2를 달라고 요청할 가능성이 있기 때문에 이 경우에는 R2를 P2한테 assign하지 않겠다는 거예요. 무슨 말인지 알겠죠? unsafe하기 때문에 assign하지 않겠다. 사이클이 존재하기 때문에. 이 그림이 아까 P2가 R2를 달라고 요청했을 때 실제로 R2가 P2한테 assign이 된 상태, assign이 된다고 쳤을 때의 상태를 그린 거예요.

그래서 사이클이 디테크가 됐죠. 사이클이 디테크가 된다. 따라서 나는 주지 않겠다. 그래서 이걸 주지 않고 리퀘스트 엣지 상태로 그냥 원래대로 남겨놓겠다는 거예요. 이렇게 그리지 않고 즉 이 avoidance 알고리즘은 싱글 인스턴스일 때 이 avoidance 알고리즘은 리퀘스트가 왔을 때 그 리퀘스트를 받아들였다고 가정하고 assignment 엣지를 그려봤을 때 그게 사이클을 형성하게 되면 그 리퀘스트에 대한 받, 요청에 대해서 받아들이지 않고 그냥 너 좀 기다려오라고 놔두는 거예요. 비록 리소스는 available 하지만 너한테 안 줄 거야 지금은 이라고 놔둘 거예요. 그리고 사이클이 디테크가 안 되면 받아들여고 실제로 어사인해서 받아들여주고 그렇게 일을 해 나가겠다는 게 바로 리소스 allocation 그래프를 이용해서 avoidance 알고리즘을 구현하는 게 바로 그거예요. 어떻게 동작하는지 알겠죠? 지금까지가 싱글 인스턴스일 때 모든 리소스 사이클이 인스턴스를 하나만 가졌을 때에 대한 이해했어요. 이제는 multiple 인스턴스를 가지는 리소스가 있을 경우 도대체 어떻게 하냐 를 보도록 합시다. 별도의 알고리즘이 필요할 거예요.

자, multiple instance일 경우, 배드라 보이던스 알고리즘을 위해서 사용하는 알고리즘이 벵커스 알고리즘이라는 거예요. 이 알고리즘이 기본적으로 가진 게 3가지인데, 첫 번째가 모던 프로세스는 시작하기 전에 각 리소스 타임마다 리소스의 최대 사용량을 미리 선언해야 된다는 조건이 있고요. 아까도 말했죠. 두 번째로는 어떤 프로세스가 리소스를 달라고 요청을 했으면 바로 받지 못하고 기다려야 될 수도 있다는 거예요. 그러니까 세이프하지 않으면 기다려야 된다고 했죠. 리퀘스트한 상태로.

다음에 세번째가 어떤 프로세스가 자기가 필요로 하는 모든 리소스를 다 받았으면 일을 끝내고 정해진 시간 내에 유아한 시간 내에 반드시 리소스를 반납해야 된다. 일을 끝마치지 않으니까 당연히 반납해야 되죠. 이 세가지 조건 다해서 이제 Banker's 알고리즘이 동작을 하게 될 겁니다. 자 그러면 먼저 Banker's 알고리즘에서 사용하게 될 자료구조 보도록 할게요. 자 자료구조에요. 프로세스의 개수를 n개라고 하고 리소스의 종류가 총 m가지가 있다고 합시다. 프로세스는 n개, 리소스의 type은 m가지 종류의 리소스들이 있다. 자 첫번째 자료구조가 Available이라는 자료구조에요. vector에요. 그냥 array라고 생각하면 돼요 array.

available j=k다 이게 무슨 말이냐면 j라는 리소스 타입이 k계에 남아있다 라는 뜻이에요. 시스템 전체에. 아무한테도 할당 안되고 남아있는 자원의 수가 k계다. 리소스 j는 k계에 남아있다 라는 뜻이고. 다음에 2차원 배열 max라는 자료가 있어요. n 곱하기 m 매트릭스에요. maxij는 k다 이거 무슨 말이냐면 처음에 클레임 한거에요. 각 프로세스가. 즉, 프로세스 i가 리소스 j를 최대 k계 사용한다 라는 뜻이에요. 미리 사용 미리 선언을 하는 내용이죠. 이건 변하지 않죠. 처음에 프로세스가 시작하면 이가 정해지고 끝까지 변하지 않아요.

다음에 Allocation이라는 자료구조가 있어요. Allocation도 2차원 자료구조인데 Allocation_ij=k다 라는 말은 Process_i가 resource_j를 k에게 할당받은 상태다. resource_j를 process_i한테 k에게 준 상태다. 현재 상태가 라는 뜻이에요. 현재 k에게 가있다 라는 뜻이에요. 그 다음에 need라는 2차원 매일은 뭐냐면 추가적으로 필요한 자원의 양을 나타낼 거에요. 즉 Process_i는 resource_j를 추가적으로 k에게 더 필요로 한다 라는 뜻이에요. 이걸 어떻게 볼 수 있어요? 처음에 클레임한 최대 사용량에서 현재 자기한테 할당된 양을 빼면 추가적으로 요구한 양이 나오죠. 추가적으로 필요한 양이. 그래서 need는 max에서 Allocation을 뺀 게 need가 되는 거에요. 자, 이 자료구조 잘 기억하고 계세요. 자료구조의 이름을 보면 무슨 뜻인지 대충 알겠죠?

자 그러면 이 자료 구조를 이용해서 우리가 먼저 봐야 될 게 safety 알고리즘이에요. 안전한지를 판단하는 알고리즘. 우리가 인스턴스가 하나일 경우는 resource allocation 그래프에서 사이클이 존재하는지를 가지고 safe한지 아닌지를 판단했죠. 그런데 인스턴스가 여러 개일 경우는 그래프에서 사이클을 가지고 detect를 할 수 없습니다. safe한지를 판단할 수가 없어요. 그렇기 때문에 실제로 알고리즘이 들어야 돼요. 알고리즘이. 자 이 알고리즘은 어떻게 동작하냐면 제일 처음에 work라는 임시 변수를 줘요. work라는 임시 변수인데 이게 현재 남아있는 자원의 양을 나타내는 임시 변수에요. 남아있는 자원의 양은 따라서 available이 그대로 work대로 들어가는 거죠. 현재 시스템에 남아있는 자원의 양, 리소스 타임마다 자원의 양이 몇 개 몇 개 남아있다 이렇게 돼 있죠. 다음에 finish i, 이건 뭐냐면 각각의 process i가 process i가 일을 끝만 치고 끝이 났냐는 걸 나타낸 거예요. true false에요.

그래서 끝이 난 프로세스는 1이 될 거고 추가될 거고, 끝이 안 난 프로세스는 false가 되겠죠. 따라서 처음 시작할 때는 모든 프로세스는 false에요. default로 조기값은 false가 되겠죠. 안 끝났으니까. 이렇게 조기화 시켜놓고, 이제 뭘 하냐면, 프로세스 i를 찾아요. 어떤 i냐 하면, 어떤 프로세스냐 하면, 아직 안 끝난 프로세스들 중에서 추가적으로 필요로 하는 자원의 양이 현재 남아있는 자원의 양보다 작거나 같은 프로세스를 찾아내라. 추가적으로 필요로 하는 양이 최대의 양에서 할당받은 양을 뺀 거라고 했죠. 이만큼 더 필요해라 그러죠.

이만큼이 더 필요해하는 양이 현재 남아있는 양보다 작다는 말이에요. 그 놈한테 현재 남아있는 자원을 올빵을 시켜주면 이 놈은 맥시멈을 다 확보할 수 있다는 뜻이죠. 그래서 이 놈은 끝이 날 수 있다는 소리에요. 그래서 이거 끝이 날 수 있네. 그럼 그런 아이를 찾았어요. 이 적금을 만족하는 아이를 찾았으면 그러면 3번으로 내려가요. 3번으로 내려가서 뭘 하냐면 이 놈한테 실제로 올빵을 해줬어요. 올빵을 해줬다고 가정을 해요. 남아있는 자원을. 그러면 최대치를 다 확보하죠. 그러면 최대치를 확보했으니까 이 프로세스는 끝이 나겠죠. 끝이 나면 어떻게 해요? 그 놈한테 이미 할당되어 있던 자원까지 다 반납하겠죠. 그래서 시스템 전체적으로 보면 available한 자원의 양이 그만큼 늘어나겠죠. 그 프로세스가 가지고 있던 자원까지 반납을 받게 되니까 늘어나겠죠. 그래서 그렇게 반영을 했어요. Worker는 Worker Plus Allocationary.

이 놈한테 이미 할당되어 있는 양까지 다 반납받았다. 그리고 이 프로세스는 끝이 났다. 그렇게 해서 다시 2번으로 들어가요. 이제 다른 프로세스를 찾아요. 아직 끝이 안 난 놈 중에서 추가적으로 필요한 양이 어벨이러블한 자원의 양보다 작거나 같은 놈을 찾아요. 또 찾았으면 또 3번으로 내려와요. 그래서 이렇게 2번과 3번 루프가 한 번씩 돌 때마다 워크가 증가하죠. 어벨이러블한 자원의 양이 점점 증가하죠. 계속 반납을 받게 되니까. 그래서 이렇게 계속 찾는 거예요. 계속 찾다가 2번에서 더 이상 그런 놈을 못 찾겠다.

못 찾겠다 그러면 4번으로 넘어가야 요새. 조건을 만족시키는 걸 못 찾겠다. 그럼 4번으로 넘어가서 봤더니만 모든 프로세스가 다 끝이 났다라. 그러면 이제 더이상 프로세스가 없어서 못 찾은거죠. 그러면 모든 프로세스가 종료겠다는 소리니까 그런 시퀀스가 존재하는거죠. 프로세스의 종료 시퀀스가 존재하는거죠. 그러면 이건 안전하다라고 판단된거에요. 무슨 말인지 알겠죠? 근데 만약에 모든 프로세스가 추후가 아니더라. falseing 프로세스가 존재하더라. 그러면 그 말이 무슨 말이에요? 아직 종료되지 않은 프로세스인데 현재 available한 자원의 양가직으로는 이 놈의 max를 중료시킬 수 없다는 소리죠. 그래서 이 놈이 종료가 안된다. 즉 안전하지 않다는 뜻이에요. 안전하지 않다고 해서 반드시 대드라이게 발생한다는건 아니에요. max라는게 아까도 말했듯이 모든 타입의 자원의 최대 량을 동시에 요청할때만 실제로 종료가 안될 뿐이지 또 번갈아가면서 자원을 번갈아가면서 사용하면 실제로 종료될 수도 있죠. 근데 아주 보수적으로 생각해서 종료되지 않을 수도 있기 때문에 위험하다. 그래서 unsafe하다라고 판단을 내리는거에요. 그래서 모든 프로세스가 finish가 추후면 safe하다라고 판단을 내리고 모든 프로세스의 피니쉬가 하나라도 볼수면 그러면 세이프하지 않다라고 판단하는 거예요

알겠죠? 자 그러면 이제 실제로 어떻게 동작하는지 봅시다. 자 process i가 자원을 요청했을 때 어떻게 동작하는지를 봐요. process pi가 요청을 하는 벡터를 request i로 갑시다. process i가 벡터여 자원 k를 자원 j를 k에게 요청한다는 뜻이에요. request i jk라는 뜻이 process i가 자원 j를, 리소스 타입 j를 k에게 달라고 지금 요청을 했어요. 자 그러면 이제 banker's 알고리즘을 해야 되는 거예요. 요 요청을 받아들이지 말지를 결정해야 돼요. 요 요청을. 그래서 그걸 결정하는 과정을 보도록 합시다. 만약에 지금 요청한 양이

현재 이 프로세스가 추가적으로 필요로 하는 양보다 작은 질을 먼저 검사야. 이게 무슨 말이에요? 요청한 용이 양이 추가적으로 필요로 하는 양보다 크다는 말이 무슨 말이에요? 자기가 맥시멈 사용 양이 이만큼이라고 해놓고, 현재 자기가 할당받은 양이 이만큼이면 추가적으로 필요로 하는 양이 니더죠. 그럼 그건 니더의 범위 내에서 요청하는 게 정상이에요. 그런데 리퀘스트한 양이 니더 보다 더 크면, 이건 오동작을 일으키고 있다는 뜻이죠. 그래서 이건 뭔가 문제가 있다 이 프로세스한테. 그래서 이더만 에러를 발생시켜요. 뭔가 문제가 있다고 하고, 그리고 그냥 종료를 시켜 버리는 거에요. 당연히 통과하기 또 정상적인 프로세스 하면 두 번째 뭘 검사하냐? 요청한 양이 현재 시스템에 가용한 양보다 작가를 앞둘지 검사라요.

가용량보다 작으면 줄 수 있다는 소리죠. 이때 이제 판단하는거에요. 줄 수 있을 때 실제로 줄거냐? 아니면 줄 수 있더라도 안 주고 기다리라 할 것이냐? 이걸 판단하고서 하는거죠. 만약에 줄 수 없으면 그럼 못 주는거야. 그럼 당연히 디폴드로 기다리는거에요. 무슨 말인지 알겠죠? 그래서 그때는 쉬워요. 이게 만족이 안되면 그냥 기다리라고 하는거고 만족이 되면 3번으로 내려가자. 만족이 되면. 줄 수 있는데 줘야 되냐? 결정하는게 중요하게 3번이에요. 그러면 줄 수 있으면 줬다 치자. pretend to allocate. 그러니까 이놈이 요청한 request i 만큼의 양을 줬다고 치자. 줬다고 치는걸 어떻게 우리가 실제로 현실화할래?

이렇게 하면 되지 않냐? 줬으니까, 줬다고 쳤으니까. 시스템에 남아있는 자원의 양은 그만큼 줄어들겠죠. 줬으니까. 리케스트 아이만큼 빼고야, 어베이로브를 해서. 그리고 리케스트 아이한테 할당된 자원의 양, 알로케이션이 그만큼 늘어나겠죠. 줬으니까. 그리고 추가적으로 필요한 양은 그만큼 줄어들겠죠. 요청만큼 받았으니까 추가적으로 필요한 양은 줄어들겠죠. 이렇게 싹 고쳐버리면 이제 준거처럼 되는 거예요. 그냥 계산만 하는 거예요. 실제로 자원을 주진 않았고, 실제로 줬다고 쳤을 때 값이 이렇게 바뀔 거에요. 그러면 줬을 때, 줬을 때 이렇게 값이 바뀔 때니까 그 바뀐 상태가 안전한지를 보겠다는 거예요. 바뀐 상태가 안전하면 실제로 줄 거에요. 실제로 줄 거고, 바뀐 상태가 안전하지 않으면 안 줄 거에요. 다시 이걸 돌려버릴 거에요. 무슨 말인지 알겠죠? 그래서 줬다 치고 이렇게 값을 바꾼 다음에 아까 바로 앞에서 봤던 세이피티 알고 있음을 돌리려구요.

그 결과 세이프하면 모든 프로세스가 종료될 시퀀스가 존재하면 그러면 이건 주더라도 세이프하니까 모든 프로세스가 종료할 수 있으니까 실제로 주자 그래서 리소스를 실제로 알로케이트 하는거야 그 프로세스한테 리케스트만큼 주는거야 만약에 세이프티 알고리즘에서 unsafe로 판맹이 났다 이거 되돌아기 발생할 가능성이 조금이라도 존재해 그러면 실제로 안줘 안주고 너 기다려 라고 하고 아까 우리가 여기서 바꾼 값을 원래 돌려 쫓다 치고 available location d를 다 바꿨는데 이걸 원래 다시 돌리는거야

무슨 말인지 알겠죠? 그래서 몰래대로 돌리고 기다리라고 한 상태로 놔두고 또 시스템이 계속 돌아가는 거야. 계속 움직이면서 또 다른 프로세스가 달라고 할 수 있겠죠? 그럼 그때 또 똑같은 일을 해보는 거예요. 그래서 세이프할 때만 주고 세이프할 때만 주고. 그러다가 나중에 이 프로세스, 즉 기다리라고 한 프로세스한테 줘도 되는 시점이 언제가 오겠죠? 다른 프로세스가 종료되어 리소스가 많이 반납되고 해서 이놈한테 주더라도 실제로 세이프하게 되더라. 그럼 그때 주는 거예요. 그래서 웨이트한 놈한테는 나중에 웨이트 시킨 놈이 한 때 자원을 주더라도 안전한 시점이 오면 그때 자원을 실제로 주겠다.

현재로서는 붙이겠다. 이걸 딜레이 시키는 거예요. 자원의 획땅을. 어떻게 돌아가는지 알겠죠? 그죠? 자 그럼 지금부터 예를 보고 우리가 이해를 하도록 할게요. 자, 백허설 비즈니의 example에요. 우리는 5개의 프로세스가 있다고 합니다. P0부터 P4까지 5개의 프로세스가 있고 리소스는 3가지 종류가 있어요. A, B, C 3가지 종류가 있는데 A는 10개, B는 5개, C는 7개의 인스턴스를 가진다. 이 시스템 안에 총 자원의 양이에요. 그걸 이런 식으로 네모로 묶어서 표현할게요. A, B, C가 총 10개, 5개, 7개가 있다. 이 시스템 안에는. 자, 그리고 P0 시점에서 이 시스템의 현재 상태를 스태프샷을 찍어봤더니만 이렇게 나온 거예요. 이게 현재 상태에요. 자, 이걸 해석을 해봅시다. P0한테는 리소스 A, B, C가 각각 0개, 1개, 0개, 할당이 돼 있어요. 실제로 할당이 돼 있어요. 그리고 P0는 처음에 클레임을 할 때 최대 7개, 5개, 3개를 사용할 거다. 최대 사용량을 미리 클레임해 놓은 거죠. 이 클레임한 최대 사용량을 기초로 우리가 safety를 판단한다고 아까 말했죠. 그죠?

다음에 현재 시스템에 남아있는 자원의 양은 3개, 3개의 2개에요. 자 그리고 need를 한번 계산해볼까요? need는 추가적으로 필요한 양이죠. max에서 allocation을 뺀거라고 했죠. 그래서 753, 753에서 allocation된 010을 빼면 추가적으로 743이 필요한 거죠. abcd에서 이렇게 계산이 되는거에요. 그래서 이렇게 p0부터 p4까지 이렇게 다 나와있는 상황이에요. 이 상황이 현재 상황이고, 이 상황에서 패스를 한번 검사해볼까요? 현재 상황이 안전한지. 우리는 이 bank에서 알고있으면 안전한 길로만 들어오기 때문에 항상 현재 상황은 무조건 안전해요.

그걸 한번 검포로 해보자는거에요. 진짜 만저란지. 자 이거 끝마치는 식구사만 찾아볼까요? 자 그럼 먼저 P1. P1을 끝마칠 수 있다. 왜? P1이 추가직으로 요구하는 양이 1, 2, 2죠. 그래서 1, 2, 2만 더 주면은 맥스를 다 충족시키기 때문에 끝이 날 수 있죠. 그럼 1, 2, 2를 줄 수 있어요. available이 3, 3이잖아. 3, 3이니까 1, 2, 2를 줄 수 있죠. 그럼 이 P1한테 이걸 1, 2, 2를 줘. 1, 2, 2를 주면 맥스 만큼 가지게 되고 언젠가 끝이 나겠죠. 끝이 나면서 자기가 지금 갖고 있는 이 영령을 반납하겠죠. 이 영역을 반납하면 어벨이러블이 생겨야죠? 어떻게?

532로 증가하죠. 532로. 반납된 것까지 포함해서 532로 증가하고. 그럼 P1은 끝이 났어요. 오케이. 그 다음에 P3를 한 봅시다. P3는 추가적으로 필요한 게 011이죠. 012를 줄 수 있죠. 어벨어버리 53이니까. 그래서 012를 줘. 주면은 맥스만큼 다 채우죠. 그럼 언젠가 끝이 나겠죠. 끝이 나면 제가 갖고 있는 211을 반납하겠죠. 반납하니까 어벨어버리 한 양이 532에서 211을 들여서 743이 되죠. 743으로 바뀌어요. 어벨어버리. 그리고 P3은 이제 끝이 났고. 그 다음에 P4. P4가 추가적으로 필요한 양이 431이죠. 431인데 지금 어베일러블이 743이죠

줄 수 있죠 그래서 431만큼 줘요 431만큼 주면 맥스만큼 다 가지게 되니까 언젠가는 끝이 나겠죠 끝이 나서 P4한테 할당되어 있는 0222가 반납이 되겠죠 그러면 어벨이러블이 또 증가해서 745가 되죠 그죠 745가 되고 그 다음에 마지막으로 P4가 끝이 났고 그 다음에 P2 P2는 600을 필요로 할게요 600 600 줄 수 있죠 745가 남았으니까 그래서 600을 주면 맥스를 다 충족시키게 되고 P2는 1을 변 내겠죠 그러면서 302를 반납하겠죠 자기한테 할당된 그럼 어벨이러블이 어떻게 바뀌어요 302가 더해지니까

4 그리고 7 이렇게 바뀌죠. Available이. 그리고 p2는 끝이 나고 마지막으로 p0를 보면 7, 4, 3이 필요하죠. 추가적으로. 14, 7이 남아있으니까 7, 4, 3을 줄 수 있죠. 그래서 max를 충족시켜서 다 끝이 나게 되는 거예요. p0도 끝이 나게 되는 거예요. 그래서 eSequence p1, p3, p4, p2, p0 eSequence대로 끝이 날 수 있기 때문에 현재 상태는 안전한 상태가 되는 거예요. 그죠? 자 그러면 이 상태에서 이제 실제로 어떤 일이냐는지 한번 봅시다. 자 현재 상태에서 p1이

102를 달라고 요청을 했어요. 자, 그럼 이제 밴커사 알고 있으면 이 요청을 받아들여도 되는지를 검사를 해야 돼요. 검사하는 과정에서 첫 번째 단계가 이 리퀘스트가 Need보다 작거나 같은지, 즉 이 프로세스가 정상적으로 동작하고 있는 날을 먼저 판단해야 되죠. 원래 Need가 P1의 Need가 122였기 때문에 102보다 더 크죠. 따라서 이 프로세스는 정상적으로 동작하고 있는 건 맞아요. 다음 단계로 이 요청의 양이 현재 Available의 양보다 작거나 같은지를 검사를 해야 되죠. Available이 332라고 있고 현재, 그리고 102를 달라고 했으니까 줄 수 있죠. 줄 수 있으니까 진짜 줘도 되는지를 판단해야 돼요. 못 준다면, 판단할 필요도 없죠. 기다려오라고 하면 끝이에요. 줄 수 있으니까 진짜 조회해야 되는지 판단해봅시다. 세이프티가 알고 있으면 조회해야 되는 상황이에요.

자 어떻게 한다고 했어요 자료구절을 먼저 바꾼다고 했죠 유놈한테 줬다 치고 값들을 다 바꿔야 돼요 줬다 치니까 available이 일단 줄어들죠 332에서 102만큼 줬다 치니까 230이 남게 되죠 230이 남게 되고 그리고 P1이 102만큼 추가적으로 받았으니까 allocation이 302로 증가해요 원래 200이었죠 200인데 102를 받아서 302가 된 거예요 그리고 그만큼 leader는 줄어들죠 추가적으로 P1량이 자 이렇게 이제 값을 바꾸고 나서 여기서 이제 safety 알고리즘을 돌려요 돌리는데 즉 하나씩 하나씩 종료시킬 수 있는 시퀀스를 찾아보자 라는 거죠 자 이렇게 답이 나와있죠 이렇게 P1부터 P3P4, P0P2 순으로 끝을 낼 수 있다는 거예요. P1 먼저 정료시킬 수 있는지 봅시다.

이 P1이 추가적으로 필요한 양이 020이죠. available는 230이에요. 그러면 020 줄 수 있죠. 그래서 020을 줘요. 020을 줘가지고. max만큼 다 채웠으니까 이 놈은 끝이 나서 302를 반납하겠죠. 그럼 available이 532가 되죠. 이렇게 바뀌고. 다음으로 P3. P3가 추가적으로 필요한 양이 011이죠. 011이니까 available이 줄 수 있죠. 따라서 P3한테 줘요. P3한테 주면 언젠가는 끝이 나겠죠. 그래서 211을 반납할 거잖아요. 그럼 211을 반납하면 available는 743이 되죠. 743이 될 거고.

자 다음에 P3까지 끝났어요. P4를 보면 P4는 431이 추가적으로 필요해요. 그러면 432을 줘요. 432을 줄 수 있으니까 주고, 그러면 P4가 002를 반납하겠죠. 그래서 어벨어버들이 또 745로 증가할거에요. 어벨어버들은 항상 증가해요 계속. 다음에 P4까지 끝났고 P0를 끊을 수 있더라. P0가 743을 필요해요. 근데 지금 어벨어버들이 745죠? 줄 수 있죠? 따라서 이만큼 743만큼 추면은 그러면 P0가 언젠가 끝이 날테고 끝이 나면 010을 반납하겠죠. 그래서 어벨어버들이 755로 바뀌죠. 755로 바뀔거에요.

그 다음에 마지막으로 P2가 필요한 명이 600이에요. 그럼 600을 75에서 줄 수 있죠. 주면 이 놈이 끝이 나고 301을 반납하겠죠. 그래서 모든 프로세스가 다 끝이 나는 세퀀스가 이렇게 존재하죠. 따라서 내가 이 요청을 받아들였을 때도 안전하다는 게 이제 결론이 났죠. 안전하기 때문에 실제로 이 요청을 받아들이면 되는 거예요. 그래서 자원을 할당해주면 돼요. 102만큼. 어떻게 동작하는지 알겠죠? 자 그럼 여러분들의 연습으로 현대 상태에서 즉 P1이 101을 요청하지 않은 상태가 아니라 이 바로 슬라이드 상태에서 P4가 330을 요청했을 때 P4가 330을 요청했을 때 실제로 줄 거냐 말 거냐 여러분들 한번 실제로 해보세요. 그리고 P0가 020을 요청했을 때 줘도 되냐? 이것도 여러분들이 판단해보세요. 연습해보라는 거예요. 아셨죠?

자 그러면 지금까지 데드락어보이든스 알고리즘을 공부를 했어요. 이제 남은 거는 데드락 디텍션 하나 남았죠. 디텍션을 보도록 합시다. 데드락 디텍션 알고리즘은 데드락이 발생하기 전까지는 아무도 안 해요. 즉 프로세스가 자원 주세요 라고 요청하면 그리고 현재 시스템에 자원이 줄 수 있을 정도가 남아있으면 그냥 아무 생각 없이 줘버리는 거예요. 그걸 계속 반복해요. 물론 못 주면 기다리면 방법이 없는 거예요. 그건 당연히 그렇게 해야 되는 거고 줄 수 있으면 무조건 주는 거예요. 아무 생각 없이 계속 그렇게 하다가 언젠가 데드락이 걸릴 수 있겠죠. 그러면 데드락이 걸리면 그때 조치를 해주겠다는 거예요. 그래서 데드락 디텍션은 미래를 예측하는 게 아니에요. 어버이든스는 미래를 예측해서 불안함에 돌아가라 이런 방법을 쓰는 거고 디텍션은 무조건 현재 기준이에요.

현재 대드락이 발생했냐 아니냐 그것만 가지자는 거죠. 그래서 일단 기본적으로 대드락을 디텍트 할 수 있는지 알아야 돼요. 현재 상태가 대드락이 아니냐 그걸 판단할 수 있는지 알아야 되고 대드락이라고 판단이 됐으면 그것을 복구하는 방법이 있어야 돼요. 그래서 대드락 디텍션 방법은 디텍트 하는 것과 리커버리 하는 것 이 두 개로 구성이 되는 거예요. 자 이 디텍트와 리커버리는 별도로 합시다. 디텍트가 되고 나서 리커버리는 별도로 하는 걸로 하고 일단 디텍트 하는 방법이 중요하니까 어떻게 하냐면 두 가지 케이스로 똑같이 나눠요. 어보이던 세수도 두 가지 케이스로 나눴죠. 리소스 타입당 인스타스 개수가 하나인 경우와 네르기인 경우 이 두 가지로 나눠서 보도록 할게요.

먼저 resource type당 instance가 하나밖에 없는 경우에 detect를 어떻게 할 것인가를 보죠 그때 우리는 wait for graph라는 걸 사용할 거에요 wait for graph 우리는 지금까지 resource allocation graph라는 걸 사용을 했었죠 resource allocation graph는 process가 resource를 요청하고 그 resource가 다른 process한테 가있다 그러면 사실은 요청한 process가 다른 process가 그 resource를 release할 때를 기다린다고 볼 수 있죠 따라서 이 process가 저 process를 기다린다 라고 볼 수 있는 거에요 그렇게 표현하는게 wait for graph에요 그래서 resource allocation graph에서 resource vortex를 없애버린 거에요 없애버리고 process에서 process로 바로 lg를 그리면 wait for graph가 되는 거에요 실제로 wait for graph에는 모든 protect가 process vortex 밖에 없어요 그리고 모든 엔지는 process에서 process로 가는 엔지 이런 식으로 그려지게 되는거죠 pk가 pj가 가지고 있는 resource를 기다리고 있다는 뜻이죠

우리가 왜 리소스 알로케이션 그래프 대신에 wait for 그래프를 쓰냐면 우리가 이 그래프에서 deadlock을 디텍트하기 위해서는 싱글 인스턴스일 경우에는 deadlock 디텍션이 사이클이 만들어지면 무조건 deadlock이라고 했잖아요 그래서 결국은 cycle detection 하는게 deadlock detection 알고리즘으로 그대로 사용이 될텐데 이 cycle detect하는 알고리즘 자체가, 그래프에서 cycle을 디텍트하는 알고리즘 자체가 vertex의 개수에 의해서 복잡도가 따라서 생가하게 돼요 일반적으로 그래프에서 cycle detection 알고리즘은 odd of n 제곱을 타임커플레이스를 가져요 n이 vertex의 개수라고 할 때 따라서 vertex의 수가 적으면 속도가 더 빠르다는 뜻이죠 그래서 굳이 리소스라는 vertex를 중간에 끼워넣어서 cycle detect하는 것보다 리소스라는 vertex를 빼버리고 프로세스와 프로세스 사이에 waiting 관계만 엘지로 그려넣어서 줄어든 vertex를 대상으로 우리가 cycle detect하면 더 빨라지기 때문에 wait for 그래프를 리소스 알로케이션 그래프 대신 사용하게 되는 겁니다

자 이 그림에서 왼쪽에 있는 그래프가 resource allocation 그래프에요. 그리고 그거를 wait for 그래프로 변화시킨게 오른쪽 그래프에요. 예를 들어서 왼쪽 그래프에서 p1은 resource r1을 요청하고 있고 resource r1은 p2에 가있죠? 그럼 이 말은 무슨 말이냐? p2가 r1을 release 할 때까지 p1이 기다리고 있다는 뜻이잖아요. 그래서 이 resource라는 vortex를 싹 빼버리고 바로 p1에서 p2로 가는. 오른쪽 그래프를 p1에서 p2로 가는 엣지를 그냥 하나 그려버리는거에요. 이런 식으로 왼쪽 그래프를 오른쪽 그래프로 다 reduce, 줄이면 결국은 이런 식으로 vortex의 개수가 5개가 없어져버리죠. r1부터 r5까지가 없어져버리고 process들 사이에서만 선이 다 연결되는 형태로 그래프를 바꿔버릴 수 있죠. 이런 식으로 1대1 매칭이 돼요. 그러면 오른쪽 그래프의 vortex 개수는 5개밖에 안되지만 왼쪽의 그래프의 vortex 개수는 10개죠. 그래서 그래프가 훨씬 단순화되어 있는다고요. 이 단순화된 이 그래프에서 우리가 cycle를 detect해서 cycle이 존재하면 이건 대드락이 발생했다는 거에요. 오른쪽 그래프에서 p1에서 p2로 가는 엣지가 있고 p2에서 p4로 가는 엣지가 있고 p4에서 다시 p1로 가는 엣지가 있죠. 이 사이에서 사이클이 만들어진 거예요. 이러면 인스턴스가 하나밖에 없기 때문에 이거 무조건 대드락이에요. 그래서 대드락이 딕 디테크가 될 수가 있다는 거죠.

이런식으로 single instance는 wait for 그래프를 이용해서 베드랍을 디텍트한다는 뜻입니다. 다음으로는 인소스 타임마다 인스턴스가 여러개가 있을 수 있는 경우에 대한 Detection 알고리즘을 보도록 하죠. 이 경우에는 그래프를 해결할 수 없고 역시 알고리즘을 사용할거에요. Detection 알고리즘을 사용할건데 이 Detection 알고리즘이 avoidance 알고리즘에서 사용했던 safety를 평가하는 알고리즘하고 매우 비슷해요. 매우 비슷하기 때문에 그 safety 알고리즘에서 사용했던 자료구조를 비슷하게 사용을 해요. 실제로 available이라는 자료구조, array였죠. 똑같이 사용을 해요. 현재 남아있는 사용가능한 자원의 양이고 location 역시 각 프로세스한테 어떤 타입의 자원이 얼마만큼 할당되어 있는가를 나타내는 이 차원의 대열이죠. 그리고 avoidance 알고리즘, safety 알고리즘에서는 미래의 대드락이 발생할 수 있는지 미래를 예측하기 위해서 미래에 대한 평가를 위해서 사용했죠. 그래서 최대 얼마를 사용할 수 있는지 나중에 그리고 추가적으로 필요한게 얼마냐 이런 것들에 대한 정보가 필요했고 그래서 max와 need라는 자료구조가 필요했는데 Detection 알고리즘은 미래를 평가하는게 아니라 현재 상태의 대드락이 발생이 아니냐를 평가하는거죠. 그래서 max 이런거 다 필요 없어요. 미래에 대한 자료구조는 다 필요 없고 현재 상태만 나타내는 정보가 있으면 되잖아요. 그래서 현재 상태를 나타내기 위해서 필요한게 request해요. 그래서 request라는 자료구조는 2차원 배열이에요. n도관리는 2차원 배열이고 process request i, j가 k라는 것은 process i가 resource j를 지금 k계에 요청하고 있다는 뜻이에요.

그런 정보를 담고 있는 자료구조가 리페스트해요. 현재의 상태를 나타내는 자료구조에요. 이 자료구조를 이용해서 데드락을 어떻게 딕텍트하는지 알고리즘을 보도록 합시다. 이게 딕텍션 알고리즘이에요. 이 알고리즘이 아까 말했듯이 safety 알고리즘하고 매우 유사하다고 했죠. 현재 상태가 과연 데드락인지 아닌지를 평별하기 위해서 어떤 일을 하는지 봅시다. 제일 먼저 walker는 available, 똑같아요. safety 알고리즘하고 똑같고 사용 가능한 자원의 양을 나타내고. 두 번째 여기서 좀 달라요. 아까 avoidance 알고리즘에서는 모든 프로세서는 finish가 false였죠. 아직까지 하지 않았다. 근데 여기서는

만약에 어떤 프로세스한테 할당된 자원의 양이 Allocation J가 0이 아니면 그러면 이놈은 아직 끝이 나지 않았다 라고 생각하고 만약에 이게 0이면 어떤 프로세스한테 Allocation 된 자원이 하나도 없다 그러면 이 프로세스는 무슨 뜻이에요 지금 요청하고 있는 자원이 요청이 아니라 가지고 있는 자원이 하나도 없잖아요 가지고 있는 자원이 하나도 없으면 그 프로세스를 기다리는 프로세스도 없다는 소리죠 뭐 뭔가를 가지고 있어야 그 자원을 릴리즈하기를 기다리는 프로세스가 존재할 수 있잖아요 근데 아무것도 없는 프로세스는 그 프로세스를 기다리면 다른 프로세스가 존재할 수가 없죠 가진 게 없으니까 따라서 디테크하는 순간에는 이 프로세서는 없는 프로세서랑 마찬가지예요.

아무도 그 프로세스를 기다리지 않으니까 대들에게 긁일 수가 없는 프로세스가 되는거죠 서큘러 웨이스에 들어가야 있을 수가 없는 프로세스가 되죠 따라서 디텍터하는 입장에서 보면 자원 할당이 전혀 이루어지지 않은 프로세스는 그냥 없는 프로세스는 마찬가지다 그런데 있는 프로세스를 없다고 할 수는 없기 때문에 그냥 이거를 종료된 프로세스로 취급해버리자는거에요 그래서 자원 할당이 전혀 안된 프로세스는 그냥 없는 프로세스처럼 취급하기 위해서 피니쉬를 추후로 세팅을 해버려요 그래서 우리의 대상에서 대제시켜버리겠다 우려대상에서 그런 뜻이에요 자 다음으로 safety 알고리즘하고 매우 유사하게 들어와요 프로세스를 하나씩 찾아내서 그 프로세스가 요구하는 자원 리퀘스트 요청하는 자원을 충족시킬 수 있는지를 간단히 보겠다는거에요 자 아직 끝이 나지 않은 프로세스들 중에서 그놈이 현재 요청하고 있는 자원의 양이 어벨러블한 자원의 양보다 작거나 같은 프로세스를 찾아라

원래 safety 알고리즘에는 이게 리퀘스트 대신에 need가 들어갔죠. need가 워크보다 작아진 것 같았지. 근데 need는 뭐였어요? 향후에 더 필요한 자원의 양이죠. 근데 우리는 향후는 관심이 없다고 그랬죠. need댁신 알고리즘은. 현재만 중요해요. 따라서 현재 요청하고 있는 양이 중요한거죠. 그래서 need 대신에 request를 쓰게 돼요. 현재 요청하고 있는 자원의 양을 충족시킬 수 있느냐. 그래서 충족이 시킬 수 있다면 그 놈한테 자원을 줄 수 있다는 소리고, 자원을 줄 수 있다면 줘요. 그럼 이놈이 지금 현재 요구하는 자원을 줬으니까, 이놈은 최소한 현재 상태에서는 대드락의 체인에 들어가 있지 않은 거예요.

원형 배기를 하는 체인에 이놈은 들어갈 수가 없는 거죠. 이놈한테 지거 요청하는 자원을 줄 수 있으니까 다른 프로세스를 기다릴 필요가 없는 거죠. 따라서 이놈도 배제시켜 버려야 돼요. 대들아 검사는 데서. 그래서 이놈을 찾아가지고 그 놈은 배제시켜 버려. 이놈은 대들아하고 상관없는 놈이니까 나의 검사 대상에서 빼겠다. 그럼 빼면서 뺀다는 일 자체가 이놈이 지금 요구하는 자원을 다 충족시켜줬다 치고 충족시켜줬으니까 이놈은 지금 현재 할 수 있는 일은 다 할 수 있을 것이다. 요구하는 만큼 다 줬으니까 할 수 있을 것이다. 그러면 하고 나서 그 놈이 자기가 이를껏 맞췄으니까 원래 자기가 가지고 있던 자원을 반납해야 되겠죠. 그래서 반납했다 치고 어베일러블한 자원의 양을 증가시켜줘요. 그 놈이 갖고 있던 양을 다시 반납받아서 증가시켜주고 그 프로세스는 끝이 났다라고 한단 내려버리는 거예요. 대들아과 무관한 프로세스니까 끝이 났다. 반납 내리고 빼버리는 거예요. 죽으로 만들어서.

또 그리고 나서 2번으로 넘어가요. 또 아까같이 똑같은 프로세스를 찾아요. 아직 끝나지 않은 놈 중에서 요청하는 자원의 양이 어벨이로브를 한 자원의 양보다 작거나 같은 놈을 찾아서 그 놈 역시 끝났다고 표시해버리고 그 놈이 갖고 있는 자원을 회수하고 이걸 계속 반복해요. 언제까지? 더 이상 그런 프로세스를 찾을 수 없을 때까지. 그래서 찾을 수 없으면 4번으로 내려오죠. 4번으로 내려와서 모든 프로세스가 추우면 이건 대드락이 아니다 현재 상태만. 모든 프로세스가 피니쉬 해버렸으면 대드락이 아니고 하나라도 피니쉬를 못했으면 그 놈한테 자원을 할당해 줄 수 없다 뜻이잖아. 그럼 이건 대드락이 틀린거에요. 그래서 피니쉬 아이가 false 인 프로세스가 존재한다면 현재 이 상태는 대드락이다 라고 판단을 드리는거에요. 모든 놈이 추우면 피니쉬가 추우면 현재 상태는 자원을 원하는 대로 다 줄 수 있다는 뜻으로 대드락이 아니다 라고 판단을 드리는거에요. 무슨 말인지 알겠죠 그죠?

그러면 예를 한번 들어봅시다. 아까 어보이던스 알고리즘처럼 비슷한 형태로 예를 보여줄게요. 지금 프로세스가 5개 있고, 리소스 타입이 abc 3가지 종류가 있고, abc는 각각 7,2,6개의 인스턴스를 가지는 자원들이에요. 시스템 전체적으로. 그리고 현 시점에서의 스냅샷을 찍어보니깐 이런 상태에요. 각 프로세스의 상태가. p0한테는 010이 assign되어 있고, blockade 되어 있고, 이놈은 현재 하나도 요구하는게 없고, 그리고 p1한테는 e00이 assign, blockade 되어 있고, 현재 e02를 달라고 요청한 상태다. 이런식으로 되어 있는거에요. 그리고 현재 자원의 시스템에는 남아있는 자원이 하나도 없다.

이 상태에서 이 상태가 데드락인지 아닌지를 판별해보자는거에요. 그럼 어떻게 한다고 그랬어요? 일단은 request가 0인 프로세스는 다 finish가 true로 세팅한다고 그랬죠? 그래서 이거는 p0은 request가 0이니까 끝났다. 그리고 p2도 요청하는게 없으니까 끝났다. 이분들은 데드락하고 상관없는 놈이니까 빼버리자. 자 그러면 request가 0인 놈들만 남죠? p1, p3, p4가. 그쵸? 그러면 제일 먼저 p3가 현재 요청하는게 100이에요. 100.

자, 100을 지금 출 수 있나 없나? 어베일러블이 000이 되실 수 있어요. 못 두죠. 어, 그런 문제인데? 아니에요. 우리가 P0와 P2가 대두락과 무관한 놈이니까 더 이상 요청하는 게 없으니까 빼버렸잖아요. 피니시에서 추우로 세팅을 했잖아요. 그러면 피니시에서 추우로 세팅하는 순간 이놈들이 가지고 있는 자원은 안 납이 되는 거예요. 더 이상 요청하는 자원이 없으니까 이놈은 끝난 것이다. 끝날 테니까 현재 시점에서는 이놈들이 갖고 있는 자원을 회수할 수 있다. 그래서 P0와 P2가 갖고 있던 자원이 회수가 되면서 실제로 어베일러블은 313이 되는 거예요. 3132.

313이 available 해지고, 그러면 313을 가지고 다른 프로세서의 리퀘스트를 만족시킬 수 있는 날을 보는 거에요. P3가 100을 요청했죠. 그거 만족시킬 수 있죠. 오케이 그럼 이놈도 지금 311 available하게 남아있는 놈 자원에서 100을 줘가지고 이놈의 요청을 충고시킬 수 있으니까 이놈은 진도를 나갈 수 있어 라고 판단하고 진도를 나가게 만들어서 212를 회수하는 거에요. 진도가 나갔다고 치고 그러면 available이 524가 되죠. 그죠? 그 상태에서 P1이 202를 요청하죠.

그러면 202를 524에서 줄 수 있죠 이놈한테도 요청을 다 받아들일 수 있으므로 이놈들한테 요청을 받아줬다 치고 그러면 이놈이 갖고 있던 자원을 다시 반납을 하게 되면 available는 724가 되죠 그리고 마지막으로 이 724를 P4한테 주면 P4는 현재 002를 요청하고 있죠 그러니까 줄 수 있죠 P4한테 주면 이놈도 지나게 되죠 그래서 P0 제일 먼저 끝내서 요청이 없으니까 할당된 놈을 반납받아서 끝내버리고 P2도 요청이 없으니까 할당된 자원을 반납받아서 끝내고 다음에 P3한테 요청한 만큼 줘서 끝내고 P1한테 요청한 만큼 줘서 끝내고 P1한테 요청한 만큼 줘서 끝내면 모던 프로세서의 피니쉬가 추가되죠 그러면 이 상태는 대드락이 아니라는 거예요 여기서 좀 궁금할 거예요

지금 요청한 양을 받았다고 해서 이 프로세스가 끝이 나서 Allocation이 Allocation된 놈을 반납받을 수가 있냐 나중에 또 요청할 수 있지 않냐 또 추가적으로 요청할 수 있지 않냐 예를 들어서 P1이 현재로서는 2021을 요청하지만 2021을 다 쓰고 나서 또 다른 계속 일을 진행하다 보면 또 다른 자원을 요청할 수 있지 않느냐 그럼 이게 끝났다고 볼 수 없지 않느냐 그렇게 생각할 수 있죠. 그럼 어떻게 자원을 회수하냐 P1이 갖고 있는 이 영역이라는 자원을 회수하냐 그건 중요하잖아요. 미래일이잖아요 미래일. 현재만 따지면 돼요 우리는. 현재만 따지면 되기 때문에 현재 이놈이 대들하게 걸리려면, 이놈은 요청한 자원을 못 받아서 꼼짝 결산 못하고 진도를 못 나가야 되잖아요.

그래야 되드락이 흘리죠. 근데 이놈이 현재 202를 요청했다는 뜻은 일단 202를 주면 나는 진도를 나갈 수 있다는 뜻이에요. 그럼 이놈은 되드락이 아닌거에요. 그래서 되드락이 아니라고 생각하고 이놈이 요청한 자원을 다 줘가지고 진도가 다 나가게 만들고 이놈이 나중에 다시 나한테 자원을 반납할 거라고 우리는 긍정적으로 생각하는거에요. 미래에 되드락이 발생할지는 모르지만 일단 현재로서는 되드락이 아니니까 나는 긍정적으로 생각하겠다는거에요. 그런 차원에서 우리가 판단하기 때문에 여러분들이 avoidance 알고리즘에서 사용한 bankers 알고리즘하고는 다른 시각에서 봐야 돼요. 지금 한 칸이라도 진도를 나갈 수 있으면 되드락이 아니니까 그렇다면 우리랑 긍정적으로 생각할 수 있다. 되드락이 아닌지를 판단할 때는 우리가 편한대로

조금 좋은 쪽으로 생각해서 우리가 판단을 하면 된다라는 거예요. 방금 본 베드라 디텍션 알고리즘의 콤픽스트를 한번 볼까요? 알고리즘의 콤픽스트를 여러분들이 루프를 잘 따져보면 콤픽스트가 order of m 곱하기 n 제곱이 나와요. m이 리소스 타입이고 n이 프로세스의 개수고 근데 리소스 타입과 프로세스의 개수가 비슷하다고 가정하면 order of n 3승짜리 알고리즘이 되는 거죠. 매우 복잡한 알고리즘이죠. 그래서 이 알고리즘이 너무 자주 돌아가면 시스템 성명을 저하시키겠죠. OS의 성명을. 그래서 얼마나 자주 돌아가냐 이게 문제예요. 사실 디텍션 알고리즘이. 원칙대로 하면 상태가 변할 때마다 자원할당이나 요청의 상태가 바뀔 때마다 이게 돌아가야 되죠. 그래서 이미 이 프로세스가 어떤 프로세스든 자원을 요청하기만 하면 그 요청으로 인해서 사이클이 만들어질 수 있기 때문에 요청할 때마다 검사를 하자 라는 방법이 제일 오래드가 크고 그 다음으로 요청을 받아들일 수 있으면 최소한 사이클의 프로세스가 편입되지는 않지 않느냐.

요청을 받아들일 수 있으면 다른 프로세스를 기다릴 일이 없기 때문에 그 프로세스 때문에 대드락이 발생하지 않지 않느냐 따라서 요청만 가지고 대드락을 디테크하지 말고 요청을 받아들일 수 없을 때 그때만 디테크를 하자 라는 방법이 두 번째 방법이에요 그럼 이제 빈도가 좀 줄어들죠 이제 이 알고리즘을 돌려야 하는 빈도가 그리고 세 번째 방법은 더 줄이자 이 알고리즘을 수행시키는 빈도를 더 줄이자 어떻게 대드락 디테크를 굳이 실시간으로 할 필요가 있느냐 발생하자마자 바로 디테크를 할 필요가 있느냐 그럴 필요 없다 그렇다면 그냥 띄엄띄엄 축제적으로 하자 라는 게 세 번째죠 그래서 세번째는 대드락 발생핀도는 발생 환기로는 매우 같기 때문에 가끔씩 검사해서 대드락이면 조치를 하면 되지 않느냐는 방법이에요.

그래서 이렇게 이제 콤플레스틱가 높은 알고리즘을 덜 실행시키기 위해서 이런 생각을 합니다. 자 그러면 어쨌든 알고리즘을 돌려서 대드락이 디텍트됐어요. 그럼 이제 해야 되는게 리커버리죠. 문제를 해결해줘야 되죠. 리커버리를 하는 방법이 크게 두가지에요. 대드락에 관여된 프로세스를 아예 죽여버리는 방법. 그리고 두번째는 대드락에 관여된 프로세스로부터 자원을 강제로 뺏는 방법. 이게 있어요. 먼저 프로세스를 죽여버리는 방법을 봅시다. 가장 무식한 방법은 뭐에요? 대드락에 갈린 모든 프로세스를 그냥 다 어버드시켜 버리는 거에요. 정말 무식한 방법이죠. 좀 심하죠. 그래서 다른 방법으로 하나씩 하나씩 들어보자

대드락이 해소될 때까지 라는 방법이에요. 그래서 하나 죽여보고 대드락 디테크 다시 해보고 그래도 해소가 안됐으면 또 다음 두번째 프로세스를 죽여보고 대드락 디테크 해보고 언제까지? 대드락이 해소가 될 때까지. 이 방법이에요. 그러면 여기서 나타나는 문제가 그러면 어떤 프로세스를 먼저 죽일 것이냐 아니면 문제가 생기죠. 그래서 그 방법은 여러가지에요. 우선수준이가 낮은 넘어 죽이자. 중요한 것은 죽이면 안되니까. 그렇게 생각할 수도 있고 얼마나 오랫동안 돌아왔냐. 이 프로세스가 동작했냐라는 걸 기준으로 다지자. 왜? 오랫동안 동프로세스를 어버터 시키면 아깝잖아. 그러니까 시작한 지 얼마 안된 프로세스를 먼저 죽이는게 낫지 않냐 라는 생각이에요. 세번째로는 돌아간 동작한 시간보다 이 프로세스가 사용한 자원의 양이 더 중요하지 않냐. 엄청나게 많은 자원을 사용해왔 온 프로세스는 비록 짧게 돌아왔다 하더라도 이 프로세스를 어버터 시키면 나중에 다시 시작했을 때 이 프로세스가 또 그만큼 많은 자원을 필요하기 때문에 오히려 더 손해지 않냐. 오래 돌아왔다 하더라도 올해도 온 프로세스가 자원을 별로 사용 안했다면 그러면 죽여서 다시 시작시키더라도 나중에 자원을 덜 사용할테니까 오히려 더 그게 유리하지 않냐 라는 뜻이죠. 그래서 오늘 덜 사용한 놈을 먼저 죽이자는 방법이 세 번째 방법이고

네 번째 방법은 앞으로 이 프로세스가 끝날 때까지 사용할 자원의 양이 얼마나 많냐를 보고 자원의 양이 엄선하게 많이 더 필요한 프로세스를 먼저 죽이자. 앞으로 자원을 조금만 더 주면 끝이 날로만 죽이기 아깝잖아. 그래서 앞으로 사용해야 될 필요로 하는 자원의 양이 많은 것을 먼저 죽이자 라는 방법. 이것도 한 릴레이션을 하죠. 이성적으로 올바르게 그죠. 이 방법도 괜찮은 방법이에요. 그리고 다섯 번째 방법은 이 프로세스를 죽였을 때 어떻게 프로세스를 죽여야만 대드락 해소가 되냐. 즉 최소한의 프로세스를 죽여서 대드락을 해소할 수 있는 그런 집합을 찾자 라는 걸 기준으로 따질 수도 있죠. 이건 좀 계산 복잡도가 높겠죠 이 방법은.

그리고 프로세스의 성격에 따라서 인트랙티브한 프로세스를 죽이는게 사용자한테 불편을 바로 가중시키지 않냐. 표가 바로 나니까. 그래서 인트랙티브한 걸 죽이지 말고 배치 잡을, 백그라운드로 들고 있는 잡을 먼저 죽이자. 라는 방법도 있을 수 있죠. 각각의 방법이 뭐가 더 좋다라고 말할 수는 없어요. 그냥 내가 정하기 단음이에요. OS 디자인에서 정하기 단음이에요. 근데 실제로 대들하고 무시한다고 그랬죠? 실제로 오퍼렛팅 시스템은 이런 고민을 정리 안하고 있어요 사실은. 자 그리고 두 번째 방법이 자원을 뱉는 방법이라고 그랬죠. 프로세스를 죽이지 않고.

어떤 프로세스로부터 자원을 뺏을 것이냐 라는 걸 우리가 생각을 해야 되는데 우리가 빅팀을 선정해요. 어떤 프로세스로부터 자원을 뺏을 것이냐 빅팀을 선정해서 그 프로세스로부터 자원을 뺏어버리는 거예요. 어벌터시키지 말고 자원만 뺏어버리는 거예요. 그래서 자원을 뺏으면 그 자원을 가지고 있는 놈을 기다리는 프로세스 때문에 대드락이 벌려는데 그 놈으로부터 자원을 뺏어버리니까 그 뺏으면 자원을 다른 프로세스한테 줄 수 있게 되죠. 그러면 원형 대기가 깨져버리죠. 따라서 대드락이 개수가 되는 거예요. 그래서 자원을 뺏어서 이전의 안전한 상태로 돌려버리는 거예요.

그 상태에서부터 자원을 뺏어서 다시 시작을 시키면 그러면 똑같이 대드락이 들리지 않냐? 그렇지 않아요. 원형 대기가 이루어지는 것은 절묘하게 스케줄링이 일어나서 딱 그게 절묘하게 맞춰질 때만 원형 대기가 생기는 거예요. 그래서 프로세스를 자원을 뺏어서 뒤로 돌렸다가, 이전 상태로 돌렸다가 다시 시작한다고 해서 아까 대드락이 발생한 상태로 다시 그대로 돌아가지 않는다고요. 시스템이 워낙 다이나믹하게 움직이기 때문에 특히 CPU 스케줄로 해서 어떤 프로세스가 먼저 들고 어떤 프로세스가 나중에 돌고에 따라서 원형 대기가 생기기도 하고 안생기기도 하고 그렇잖아요. 그렇기 때문에 뒤로 좀 당겼다가 다시 놓는다고 해서 대드락이 반드시 발생하지 않는다. 따라서 그냥 한 프로세스의 자원을 뺏어서 그 프로세스를 이전 상태로 돌려놓고 대드락을 해소한 다음에 다시 시작하면 대드락이 아마 다시 발생하지 않을 것이라는 기대로 롤백을 시키는 거죠. 근데 이렇게 자원을 뺏다 보면

뺏기 정도만 계속 뺏길 수도 있죠. 빅팀으로 선정해서. 그래서 스타베이션이 발생할 수 있어요. 그래서 이놈이 얼마나 롤백을 자주 했냐를 빅팀으로 선정되는 프로세스를 정할 때 고려해 줄 필요는 있어요. 그런데 이런 말 하면서도 참 웃겨요. 사실은 OS에서는 아무도 고려하지 않고 있는데, 대드락에 관련된 나무 일을 하고 있지 않은데 별걸 신경을 쓰고 있죠. 스타베이션까지 신경을 쓰고 있으니 과하게 신경을 쓰고 있는데, 우리가 앞에서 말했듯이 이론적으로 이런 내용을 다 다뤄놔야 다른 분야에서 대드락을 대처할 때 우리가 이해를 할 수 있기 때문에 이런 말까지 다 해주는 거예요.

자 마지막 슬라이드에요. 이걸 한번 더 정리를 해줄 필요가 있어서 정리를 하는거에요. Avoidance와 Detection의 차이. Avoidance는 미래를 예측해서 안전한 길로 가겠다는 거잖아요. 미래를 예측하고 미래에 조금이라도 위험성이 있으면 그 길로 가지 않겠다는 거였죠. 그래서 우리가 Avoidance 알고 있었던 과정은 모든 프로세스가 자기의 최대 자원 요구량을 일제히 동시에 달라고 요청한 상황에서 대드락이 발생하느냐를 기준으로 Safe T를 결정을 했다고요. 실제로 프로세스들은 그렇게 동작하지 않을 가능성이 매우 높음에도 불구하고 Worst Case Assumption을 한거에요. Worst Case Assumption을 모든 프로세스가 최대 자원 요구량을 동시에 요청했을 때도 세이프하게 모든 프로세스를 종료시킬 수 있는 방법이 존재하면 안전하고 그렇지 않으면 안전하지 않다라고 판단한거죠. 그러다보니까 Avoidance는 일로가도 사실상은 안전한데

단지 안전하지 않을 가능성이 있기 때문에 그걸로 안가고 자원의 요청이 들어왔더라도 그 자원을 안주고 기다리라고 말했잖아요. 그러다 보니까 자원을 줘도 실제로는 대두락이 발생 안하지만 자원을 안주고 기다리라고 하는 바람에 자원의 낭비가 발생할 수 밖에 없어요. 너무 소극적으로 일을 하기 때문에 발생하는 문제죠. 반면 디텍션의 유니점은 모든 프로세스가 오븐오븐한 프로세스라고 가정을 해요. 즉 미래를 예측할 필요 없이 현재만 따지면 되기 때문에 모든 프로세스는 현재 시점에서 모든 요구를 다 하고 있다고 생각을 하는 거예요. 즉 베스트 케이스 어섬션이에요. 그래서 어떤 프로세스도 지금 현재 요청한 자원의 양 이상은 요청하지 않을 거다라고 가정을 하고 디텍션을 돌린 거예요. 현재만 판단하면 되니까 미래는 우리는 알 바가 아니다라는 거죠. 그래서 베스트 케이스 어섬션으로 현재 요구하고 있는 리퀘스트가 모든 요구량이 다 이 프로세스가 필요한 전체 요구량이다 라고 가정하고 알고리즘을 돌렸고 그래서 그렇기 때문에 현재 상태만 판단할 수 있다는 거예요. 그 두 가지가 큰 차이에요. 알고리즘은 둘 다 어피스업했지만 실제로는 매우 큰 차이를 가지고 있는 거예요. 무슨 말인지 아시겠죠? 그래서 이 두 가지 차이를 이해하면 여러분들은 사실상 우리 대두락 디텍션 알고리즘과 어보이든스 알고리즘을 잘 지기 위한 거예요. 자 여기까지가 대드락에 대한 내용이었어요.

별로 그렇게 지난 시간에 한 등기와 알고리즘에 비해서는 어렵지 않죠. 어렵지 않아요. 그리고 OSS도 사용하고 있지 않는 방법이고 그렇지만 여러분들은 대들에게 개념을 설치하게 알고 있어야 됩니다. 오늘 소원 얘기까지 할게요.