|
Go back OS Review Device Driver NS Tools Home Papers Daily Link To Main |
10. 데드락 (Deadlocks)
지난 2장에 걸처서 등장했던 키워드중 하나는 데드락(deadlock)이었죠. 데드락을 이번장에서는 좀더 그 의미를 체계화 시키고 프로세스가 꼼짝달싹 못하는 데드락 상태를 미연에 방지하거나 풀어주는 기법들을 몇가지 소개해볼까 합니다. 먼저 데드락이 발생하는 이유를 한번 살펴볼까요? 멀티프로그래밍 환경에서의 몇가지 프로세스는 유한개!의 리소스를 차지하려고 아웅다웅거립니다. 한개의 프로세스가 리소스를 요구했을때 만일 그 리소스가 현재 더이상 제공이 불가능할때는(이경우는 다른 프로세스가 이미 그 리소스를 쇽~ 가져가서 쓰고있는 경우겠죠?) 자신을 대기상태로 전환시킨뒤 해당 리소스가 제공이 가능할때까지 그 상태를 유지합니다. 이때, 대기상태에 돌입한 프로세스가 영영 자신의 상태를 전환시키지 못하는 경우가 발생하는데, 그 이유는 기다리고 있는 리소스들을 쥐고있는 프로세스들 역시 같은 이유로 대기상태에 빠져있기 때문이죠. 우리는 현재 이렇게 영원하게 대기상태로 빠져버린 일련의 프로세스들이 처해있는 상황을 바로 데드락이라고 일컫는 것입니다. (사람들 서로 자신의 책임이나 의무를 이런식으로 떠밀면 사회적으로 데드락이 일어나는게 아닐까 싶군요) 한가지 주목할 사실이 하나 있는데, 아직까지의 대부분의 오에스는 데드락 해법을 제공하지 않고 있다는 것이죠. 여태 그럼 그문제를 어떻게 해결했냐고요? 얼마전 학교 전산실에서 엔티를 데리고 노는데 점점 느려지더니 결국 맛탱이가 가서 땀을 흘리며 얼렁 어드민을 찾아갔더랬죠. "헤이 아저쒸, 마이 뽀킹 엔티 맛갔써, 콤온! 헬프미!". 그 어드민 아저씨 인상을 팍! 쓰더니 제가 있던 자리로 성큼성큼,,,역시 어드민은 다르더라구요. 그 블루 스크린에 뜬 이해못할 숫자들과 메시지를 면밀하게 관찰하더니 제게 말하더군요. "reboot,,," 리셋단추를 얄밉게 콕~ 누르고 어둠속으로 사라졌습니다. 데드락 해법은 근래에 들어서야 조금씩 추가되고 있는 경향인듯 합니다. 이는 현대의 오에스에서는 예전과는 비교할수 없을만큼 다양한 프로세스들 및 다양한 리소스들이 난무하고 있고, 한번 생성되면 예전보다 더욱 오래 개겨야 하는(long-live) 파일등이 데이터베이스 등과 함께 현대 기술의 총아로 떠오르기 때문인듯 해요. 사실 초반에 언급했던 배치시스템 차원의 오에스에는 데드락 해법이 그리 필요한 테크닉이 아니겠죠? 먼저 여기서 말하는 리소스가 무엇이냐,,, 리소스를 몇가지 범주로 나누어 보면 크게 메모리 공간, 씨피유 싸이클, I/O장치 등으로 나눌수 있겠죠. 만일 2개의 씨피유가 달린 시스템이라면 그 시스템에서 '씨피유 타입의 리소스는 두개의 인스턴스(instance)를 가지고 있다'라고 말하게 됩니다. 리소스를 정의할때 한가지 주의할 사항이 있는데, 프린터가 2대 있다고 합시다. 만일 프린팅 프로세스가 프린터 리소스의 인스탄스를 요구할때, 그 프린터가 만일 서로 옆에 놓여있다면야 둘중 하나의 인스탄스를 넘겨줄테니 2개를 같은 리소스 타입의 인스턴스로 설정해도 무방하지만, 만일 한개는 1층, 또한개는 10층에 놓여있다면 이때는 문제가 달라집니다. 즉, 다른종류 타입의 인스탄스가 1개씩 있다고 설정을 하지 않는다면 유저는 프린트 명령을 때린뒤 1층에서 10층까지 뺑이치게됩니다. 언제 어느 프린터의 리소스 인스턴트를 사용할지는 그때의 상황에 따라 달라지니까요. 리소스를 프로세스가 활용하는데에는 다음의 3단계 과정을 거치게 됩니다. 1. 요구(Request) 2. 사용(Use) 3. 해제(Release) 이때 리소스의 요구및 해제는 세마포어의 wait및 signal로 수행하게 됩니다. 또한 오에스는 리소스의 사용 가능및 불가능에 대한 기록을 시스템 테이블에 기록하게 되지요. 먼저 리소스가 일어나기 위한 4가지 필요조건이 있습니다. 필요조건이라는 뜻은 여기서 '데드락이 일어나서 한번 살펴보니 그 상황이 반드시 4가지 조건을 모두 따르더라' 입니다. '4가지 조건 모두에 어떤 상황이 해당된다고 해서 반드시 데드락이 일어날것이다'는 아니죠. 위의 말이 이해되지 않으신분 다시한번 곰곰히 되씹어보셔요. 1. 상호배타성(뮤텍스:Mutual Exclusion): 존재하는 리소스!중 최소한 한개는 절대 공유가 불가능한 모드에 놓여있는 경우입니다. 2. 쥐고기다리기(Hold&Wait): 존재하는 프로세스!중 최소한 한개는 최소한 한개의 리소스를 꼬옥 쥐고서 더 필요한 리소스를 기다리고 있는 경우입니다.(물론 더 필요한 리소스는 현재 다른 프로세스가 쥐고 있죠) 3. 선점불가(No Preemption): 리소스의 선점이 허용되지 않을경우입니다. 즉, 한개의 프로세스가 일단 리소스를 쥐게되면 자신의 임무를 완수한뒤 자진해제하지 않는 이상 그 누구도 그의 리소스를 빼앗을 수 없는 경우입니다. 4. 원형순환기다림(Circular Waiting): 기다리고 있는 프로세스의 집합 {P0, P1,..., Pn}이 반드시 존재하되, 이때 P0은 P1이 쥐고 있는 리소스를 기다리고, P1는 P2의,,,마지막으로 Pn은 P0의 가 쥐고 있는 리소스를 기다리는 경우입니다. 아, 다시한번 더퍼군 이 강좌를 작은 텍스트 에디터로 기술하며 좌절을 느끼는 순간입미다. 먼저 데드락 문제에 대한 개념을 더욱 명확히 하기 위하여 필요한 리소스 할당 그래프(Resource-allocation graph)를 그려야만 되는디, 흠, 아무래도 한번 무리를 해서라도 아스키캐릭터로 한번 시도를 해보겄습니다. / ㅁ . O 끙끙,,, 아,,,도저히 불가능합니다 -_-. 화살표와 박스 쩜 그리고 똥글배기가 필요하건만, 이모두를 나의 실력으로 여기에 그린다는것 자체가 불가능 합니다. 앞으로 펼쳐지는 설명을 좀더 명확하게 이해하고 싶으신분, 교과서 p.211부터 나오는 그림을 참고하십쇼. 먼저 P에서 R을 향한 화살표는 동그라미인 프로세스 P가 네모 타입의 점 리소스 R을 요구하고 있다는 뜻이고, R에서 P를 향한 화살표는 리소스 R이 프로세스 P에 할당되었다는 의미이죠. 먼저 리소스 할당 그래프에서 네모 타입내에 단 한개만의 점 리소스 인스탄스가 존재할때 프로세스및 리소스사이의 화살표가 서로 순환하는 루프를 그리면 짤탱이 데드락입니다. 하지만, 같은 타입의 리소스가 여러개의 인스탄스로 존재한다면 그래프에서 순환하는 루프가 나온다고 반드시 데드락은 아니죠. 데드락이 만일 발생했다면 반드시 순환하는 루프가 나오게 되고요. 갓잇? 데드락이 발생하는 경우에 대한 모델링을 이제 우리는 이해를 했으니, 데드락을 처리하는 방법을 논해보도록 합시다. 방법은 아래와 같이 크게 3가지가 있습니다. 1. 프로토콜(protocol:규약)을 이용하여 애초에 데드락이 발생하는 것을 미연에 방지하자. 2. 일단 시스템으로 하여금 데드락에 들어가는 것을 허용하되, 스스로 회복하도록 만들자. 3. 데드락문제 자체를 씹어버리자. 그리고 데드락이 안일어난척 하자. 좀 의아하겠지만, 유닉스를 비롯한 대부분의 오에스는 바로 3번의 방법을 이용한답니다. 황당하죠? 뻔뻔한것들,,,고로 우리는 영문도 모른체 수많은 데드락을 여태 당한겁니다. 먼저 1번을 구현하는 방법은 2가지로 다시 나뉩니다. 데드락방지(deadlock prevention)와 데드락피하기(deadlock aviodance)이지요. 이 둘의 뜻이 비스무레한게 어째 아리까리해 보이지만, 둘은 명확한 차이를 가지고 있습니다. 먼저 prevention은 위에서 기술된 4가지 조건중 하나라도 만족이 안되면 결코 데드락은 발생치 않는다는 확신하에 출발을 하죠. 그래서 리소스 할당시 첫 단계인 프로세스의 리소스 요구에 응하기 전에 4가지 조건을 피하도록 몇가지 제한을 가하게 됩니다. 이와 별개로 avoidance는 프로세스들이 오에스에게 먼저 리소스의 사용계획에 대한 추가적인 정보를 귀뜸해주게 됨으로서 데드락을 방지하는데, 앞으로 등장할 안전상태(Safe State)를 뱅커스알고리즘(Banker's Algorithm)을 통해 구현하는 과정에서 바로 한개의 프로세스가 최대로 몇개의 특정한 리소스를 점유할것인가에 대한 정보가 필요하게 된답니다. 2번은 시스템으로 하여금 데드락이 발생했는지, 안했는지를 판별하고 회복하도록 만들어주는 알고리즘을 사용하게 됩니다. 이때 사용되는 알고리즘은 뱅커스알고리즘과 매우 유사하지만 약간 다르더군요. 3번처럼 배째는 시스템에서는 당연히 데드락이 발생하게 되고 시스템 리소스가 소모되면서 시스템이 점점 느려지고, 실행되지 못하는 프로세스가 발생하게되죠. 결국은 폭탄맞게 됩니다. 먼저 데드락방지(deadlock prevention) 기법을 살펴봅시다. 조건1 은 뮤텍스인데, 이는 리소스의 원래 특성상 절대 공유를 할 수 없는 리소스가 존재해야만 하기에 뮤텍스를 제거하는것은 일찌감치 포기합니다. 결론은 조건1 깰수 없다 입니다. 조건2는 쥐고기다리기인데 이를 깨기 위하여 모든 리소스를 한꺼번에 쥐고 프로세스의 실행을 시작 하거나, 프로세스가 어떤 리소스를 요구할시에는 자신이 절대로 다른 리소스를 쥐고 있지 못하게 하는것이죠. 이 방법의 단점은 리소스의 활용도가 확~ 떨어짐으로써 본질적인 오에스의 목적을 위배하게 되고 특정 프로세스가 배고픔(starvation)에 시달릴 가능성에 놓인다는 것입니다. 조건3은 선점형을 적용함으로써 깰수 있는데, 이는 한 프로세스가 필요로하는 리소스를 다른 프로세스가 다른 리소스를 기다리면서 쥐고 있다면 그 리소스를 선점함으로써 빼앗아 오게 됩니다. 즉, '기다리는 자여 리소스 가질 자격 없다'라는 모토로 데드락을 방지하는것이죠. 이는 한가지 큰 단점을 가지고 있는데, 바로 모든 리소스에 적용할수는 없다는 사실입니다. 프린터같은 리소스에 적용했다가는 몸은 이승희인데 얼굴은 찍찍이 따위의 깨는 그림 나오죠. 마지막으로 조건4 원형순환기다림을 깨기 위하여 모든 리소스에 번호를 부여하고, 한 프로세스가 다음 리소스를 할당할때에는 반드시 리소스 번호가 전 리소스보다 클때에만 할당이 가능하도록 규약을 맺게됩니다. 그런데 효율성을 위해 리소스마다 사용되는 순서를 고려하여 번호 부여하는 작업이 매우 난해합니다. 다음으로 데드락피하기(deadlock avidance) 기법을 위해서는 또한가지 중요한 개념을 제시해야 하는군요. 바로 안전상태(Safe State)라고 불리우는 상태인데, 이는 똑같은 전제(같은 종류의 프로세스와 같은 갯수의 리소스)에서도 특정 순서로 프로세스가 리소스를 점유하게 되면 데드락이 발생하지 않는 안전순서(Safe Sequence)가 존재하게 되고, 바로 그 안전순서가 존재하는 상황을 바로 안전상태라고 정의하는 것이죠. 이것을 직관적으로 생각한다면, 프로세스는 리소스를 점유!하는 행위 뿐만 아니라 리소스를 놔!주는 행위도 한다는 사실을 상기했을때 분명이 리소스의 할당 순서에 따라 데드락이 발생하기도 안하기도 한다는 사실을 느낄수 있을겁니다. 데드락상태는 비안전상태의 부분집합입니다. 고로 안전상태에서는 절대로 데드락이 일어나지 않는다는 보장을 받는다는 전제를 할수 있게되죠. 그럼 도데체 안전순서란? (What is the Safe Sequence?) 만일 프로세스의 집합 {P1, P2,..., Pn}이 있다고 할때, 임의의 Pi가 요구하는 타입의 리소스 인스턴트의 수가 임의의 Pj(이때 j<i)에 이미 할당된 수와 아직 제공 가능한 같은 타입의 리소스 인스탄트의 수의 합보다 작다!면 프로세스가 처리되는 순서<P1, P2,..., Pn>은 안전순서이다. 위의 말을 토대로 분배된 리소스의 수및 남은 리소스의 수를 타입별로 트래킹하고 과연 안전순서가 존재하는지를 확인한 뒤에야 리소스를 분배하려면 각 프로세스가 앞으로 사용할 최대한의 리소스의 수를 타입별로 선언해줘야 합니다. 그렇기에 본 방법은 추가적인 정보를 프로세스가 오에스에게 넘겨주어야 구현이 가능한 것이죠. 이것을 알고리즘화 한것을 우리는 뱅커즈알고리즘(Banker's Algorithm)이라고 하고, 그 이유는 은행이 돈을 대출해줄때 위의 방법대로 해야 은행이 파산하지 않게 되기 때문이죠. 돈은 한정된 리소스, 은행은 오에스, 대출하는 사람은 프로세스, 파산은 데드락에 각각 대응되겠죠? 뱅커즈알고리즘 또한 꽤 유명한 알고리즘입니다. 제가 본 문서에는 구체적으로 기술하지는 않지만, 한번쯤 책 p.221~p.222에 나온 알고리즘의 흐름을 주욱 따라가보길 강력하게 권유합니다. 여기서는 2차원 배열들을 남발하는 경향이 있기에 극심한 계산량과 대량의 메모리를 요구하게 되지요. 이런 알고리즘을 비싼 알고리즘(expensive algorithm)이라고 일컫습니다. 그래서 일반적인 오에스에서는 채택이 꺼려지는듯 해요. 배보다 배꼽이 더 큰데 누가 쓰남,,, 데드락을 해결하는 두번째 방법(먼저 데드락 발생하라고 허고 후에 잡아내자)은 크게 두단계로 그 과정이 진행되지요. 첫째로 먼저 특정 알고리즘이 데드락이 과연 발생했는가를 판단하고, 만일 발생했음을 검출하면, 두번째로 데드락을 회복시키게 됩니다. 좀 당연한 순서였나?,,,하지만, 설명에서 이렇게 두단계로 구지 나눈 이유가 있습니다. 먼저 첫단계를 살펴보면, 만일 각 리소스가 한개의 인스턴스만을 갖는경우라면 그냥 그들사이의 원형순환을 검출하면 간단하게 해결되겠지만, 각 타입의 리소스가 여러개일때의 데드락을 검출할때에는 위의 뱅커스알고리즘과 동일한 데이터 스트럭쳐의 알고리즘을 사용하게 되지요. 그래서 한번 검출을 시도할때마다 씨피유에 대량의 오버헤드가 요구됩니다. 고로 이 검출시도를 자주하자니 구더기 무셔워서 장못담그는 격이고, 가끔씩만 하자니, 뭐 안하는거나 매한가지고,,,바로 첫단계에서 부터 우리는 골때리는 딜레마에 빠져버리게 되는 것이죠. 또한 데드락을 첫단계에서 발견한다고 해도 이거 또 문제가 발생해요. 데드락이 발생했다는것은 알겄는데, 도데체 어느 프로세스놈이 바로 데드락을 유발했는지를 톡~ 찝어내기가 불가능하다는 것이죠. 그래서 또 이때 두가지의 선택의 기로에 놓이게 되는데, 첫째는 한다는 짓이 맘편하게 데드락에 연루된 모든 프로세스를 싸그리 숙청해버리거나, 둘째는 세월아 내월아 프로세스 하나하나를 없애면서 과연 이 데드락 상태가 풀리는지를 관찰하는것이죠. 이거 아주 골치아픕니다. 생각해보시길, 모든 프로세스를 없애자니 여태 각 프로세스 나름대로 그동안 노가다해서 이루어놓은 성과를 한순간에 날려버리는 것이고, 그렇다고 하나 없에고 데드락 검출시도하고, 또하나 없애고 데드락 검출시도 하고,,,만일 백개의 프로세스가 연루되었다면, 아마 데드락 어떤놈이 유발했는지 찾으려다 날샙니다. 자, 이제는 여러분이 왜 그 위대하가고 입을모아 찬양하는 유닉스조차 이 데드락 해결사들을 외면했는지가 이해가 되시는지요? 그래서 이방면을 어떻게 해결해보겠다고 모인 자칭 박사들이 내놓은 대안이란, 다름아닌 그냥 '저것들 섞어서 쓰자'입니다. 말그대로 리소스를 타입별로 분류하여 각 리소스마다 나름대로 효과적이라고 여겨지는 데드락 해법을 적용하자는 이야기이죠. 오에스에 대한 불타는 호기심으로 여기까지 제대로 이해하시고 오신분들은 이제 어느정도 오에스를 바라보는 새로운 눈이 생기셨을겁니다. 제가 기획한 오에스개론의 분량의 2/3정도가 끝났으니까요. 컴퓨터에 우리는 무엇인가 정확한 수치를 입력하고 칼로잰 잰 답을 출력받듯, 컴퓨터의 밑바탕인 오에스도 이러한 성격의 연장선에서 완벽한 조각으로 이루어져 있을것이라고 믿고 있는사람들이 의외로 많죠. 하지만, 어찌보면 오히려 오에스야말로 정말 대책없는 컴퓨터의 절대필요 요소였던 것입니다. 다음장에서는 후반부의 꽃,,,바로 메모리 메니지먼트를 다룰예정입니다. 여기에서도 여러분들이 평소에 많이 말하고 듣는 버쳐메모리, 세그먼트, 그리고 페이징등의 보스급 단어들이 버라이어티쇼를 펼칠예정이니 다음프로,,,기대해주셔요. -duffer 경준 (http://vorlon.cwru.edu/~kxm73)
|