Between the CA and the OS - CAOS?
컴퓨터를 전공하는 학생들에게 있어서 학부 수준에서 가장 중요한 과목중의 하나라면 단연 OS가 빠지지 않을 것입니다. 그러나 OS라는 과목이 공략하기에 쉽지 않은 과목입니다. OS를 제대로 이해하기 위해서는 Computer Architecture에 대한 충분한 이해와 컴퓨터에 대한 상당한 제반 지식이 필요한 것입니다. 그러한 이유로 이 글은 CA를 기반으로해서 OS를 이해하기 위한 basic들과 OS의 개괄적인 동작을 중점적으로 엮어보려 합니다. 아마 이 글을 읽기에 최적의 독자는 XT나 AT시절에 프로그래밍을 시작한 독자나 혹은 DOS시절 PC의 HW를 조금씩 다루기 시작한 사람이 될 것입니다. 다른 OS서적과 함께 읽는다면 도움이 되리라 생각됩니다. 어줍잖은 지식으로 제 자신의 지식 또한 시험하기 위함이오니 혹 잘못된 내용이 있다면 바로 지적해주시기 바랍니다.
저는 처음 컴퓨터를 접하면서 BASIC을 배웠고, C를 배웠습니다. C를 배웠던 책이 임인건님의 "터보C정복"이라는 책이었는데, 이런 훌륭한 책 덕분에 곧 C의 아름다움에 매료될 수 있었고, 프로그래밍의 재미에 빠져볼 수 있었습니다. 개인적으로 C에 관한한, 아니 컴퓨터에 관련된 국내서 중에서 이보다 더 훌륭한 책을 아직까지도 알지 못합니다. 그 이후에 보았던 숱한 컴퓨터 관련 국내서들이 엉터리 번역, 성의없는 번역등으로 실망만을 주었고, 우리말로 직접 집필하였다는 책도 베끼기 수준을 벗어나지 못하거나 성의없는 설명으로 일관하는등 국내서에 대한 실망감이 컸습니다. Stevens라든지 Knuth등 저자 이름이나 표지 그림 정도만으로도 "아, 그책"이라고 모두가 알고 있는 bible과 같은 위상을 차지하는 원서와 같은 책이 하나 정도 밖에 없다는 것이 (이 하나는 물론 임인건님의 책입니다.) 아쉬웠고, 제 작은 바램이 있다면, 이 작은 책이 제가 임인건님의 책을 통해 C를 쉽게 접하게 되었듯이 다른 사람들이 OS를 쉽게 이해할 수 있게 되는 매개체가 되었으면 하는 것입니다.
이 책을 읽으시면서 주의하실 점은, 용어의 혼란입니다. 하나의 용어가 여러 가지 경우에 서로 다른 개념을 가리키는 경우가 많기 때문에, 정확한 이해가 요구됩니다. 예로, segment라는 개념은 여러곳에서 나오지만, 어느것도 정확히 같은 것을 가리키고 있지는 않습니다. 어떤 것은 하드웨어적인 메모리의 범위를 나타내기도 하고, (intel CPU의 segment) 어떤 것은 소프트웨어적으로 구현된 level의 메모리 범위를 나타내기도 합니다. (linux의 VMA등) 또는 interrupt라는 용어도 주의가 요구됩니다. 어떤 책에서는 Hardware interrupt와 software interrupt(Exception)을 interrupt라고 통칭하기도 하고 다른 책에서는 엄밀히 구분하기도 합니다. buffer라는 말도 각 문맥에 따라서 구현된 level이 다른 경우가 많죠. 페이지라는 말도 physical page frame을 말하거나 혹은 virtual page를 말하기도 합니다. Thread역시 여러 레벨에서 다른 개념을 가리키는 경우가 흔합니다. 혼란의 여지가 있는 이러한 용어들의 경우 최대한 구체적으로 용어를 표현하겠지만 문맥에 따라 미묘한 차이를 가지고 있으니 이에 유의하시기 바랍니다.
또한 이책은 간간히 update되고 있기 때문에 통일성을 지키기 힘들 것같습니다. 때가 되면 정리할 수도 있겠지만 그전까지는 각 부분들의 내용들이 유기적으로 연결된 흐름을 가지기 어려울 것같습니다. 어떠한 챕터들은 그냥 비워져있거나 충분한 내용이 없습니다. 아마 그런 부분들을 다 채워넣으려면 한 백만년쯤 걸릴것같습니다. 완성되기를 기대하는것은 무리일듯합니다. 더 심각한 것은 내용의 수준이 basic에서부터 advanced까지 마구 섞여있다는 점입니다. -_-; 점점 저의 작업장 수준이 되어가고 있습니다. 이런 부분은 적당히 건너뛰시면서 읽거나 더 깊은 내용은 주어진 link들을 찾아 읽으시는게 좋을 것 같습니다.
이 책의 가장 최신판은 http://osinside.net/ 이나 혹은 제 개인 페이지인 http://abraxsus.pe.kr/ 에서 찾아보실수 있습니다.
이 문서를 개인적인 학습의 용도 이외의 용도로 사용하실 때에는 연락해주시기 바랍니다.
이 프로젝트는 OS(커널)를 중심으로 시스템 전반에 대한 입문서를 작성하는 저의 개인프로젝트입니다. 이 프로젝트의 최종 목표는 책으로의 출판이며, 그 세부 목표는 깊이 있는 내용, 정확한 내용, 최신 정보, 상세한 설명, 지속적인 관리와 보완입니다. (가능할까? -_-;;) 이 책은 학부와 대학원의 중간정도의 level을 목표로 하며, 그 내용은 OS, CA를 중심으로 시스템 전반을 다루고자 합니다. 이 책의 목표는 모든 내용을 다 담는것이 아닙니다. 그럴수도 없고 그럴 필요도 없기에, 방대한 내용들을 모두 담는것이 아니며, 단지 기초적인 이해를 도와주고, 더욱 자세한 내용이 있는곳을 향해갈수 있는 길잡이가 되고자합니다. 대부분의 학문이 그러하듯이, 현재 가장 최근의 내용, 가장 정확한 내용등은 모두 영어로된 책이나 논문등의 형태로 존재합니다. 따라서 이 작은 책은 독자가 그러한 고급정보를 접하기 위한 기초를 제공하고자 합니다. 독자는 더 자세한 내용은 직접 원문을 찾아보며 공부하셔야 합니다.
이 프로젝트를 함께 하시거나 도와주실분을 찾습니다. 단순한 comment에서부터 직접 집필하시고자하시는분까지, 참여를 원하신다면 연락주시기 바랍니다. 기본적으로 다음과 같은 도움을 주실분을 찾습니다.
1) reader -> 힘내라거나-_-; 밥을 사주겠다거나(응??)하는 단순한 comment, 혹은 틀린 철자/문법를 지적해주신다거나, 문서를 예쁘게 정리해주신다거나 해주실분.
2) reviewer -> 잘못된 내용에 대한 지적이나, 내용의 구성/깊이에 대한 조언등, 혹은 서로간의 내용에 대한 토론을 통해 문서를 발전시켜주실분.
3) coauthor -> 자신이 직접 집필한 내용을 추가해넣고 싶으신분. 한 섹션이나 혹은 이미 있는 세션에 상세한 설명을 덧붙여주실분을 찾습니다. 물론 자신이 집필한 부분에 대한 credit은 드립니다. :-)
그외의 어떤 형태든 함께 참여하고자 하시는분을 기다립니다.
저자 이 민
email : abraxsus (at) yonsei.ac.kr
Copyright(C) 2003 Min Lee
Last updated date : 2008 October
현재의 목차 구성은 임시적입니다.
Topics
OS란 결국, 하드웨어를 총괄하면서 하드웨어간의 이질성을 끌어 안아 소프트웨어가 좀더 추상적이 될 수 있는 환경을 제공하는 근본 소프트웨어라고 할 수 있습니다. 또는 평상시에는 잠들어 있다가 Application이 필요로 하는 서비스를 제공해주는 데몬(daemon)이라고 볼수도 있습니다. (이것은 정확한 이해는 아닙니다.데몬이라고 할수는 없죠. 하지만 Application이 필요로하는 서비스를 제공하는 코드라는점은 중요합니다.) OS를 이해하기 위한 가장 핵심중의 하나는, OS가 HW위에서 application을 위한 추상 계층(layer)를 제공한다는 것입니다. 이것은 상이한 H/W들위에서 동일한 프로그램을 돌릴 수 있도록 해주는 것입니다. 이것이 당연하게 생각될 수도 있겠지만, 실제로 초창기에는 IBM등의 기업에서 H/W를 팔기위해서 해당 H/W만을 위한 S/W를, 즉 OS를 제작해주었다는 점을 생각한다면 OS와 H/W의 분리는 역사적으로 획기적인 발전이었다고 할 수 있습니다. 즉 초창기의 H/W를 팔기위해 S/W가 제작되어지는 상황이었다면 근래에는 S/W의 중요성이 날로 커지고 S/W와 H/W의 분리가 가속화되면서 S/W를 위한 H/W를 제작한다고 할 수 있습니다. 이러한 S/W중에서 그 꽃이라 할 수 있는 것이 이 OS 와 compiler입니다.
OS 는 또한 자원관리자(resource manager)라는 관점으로 파악되기도 합니다. 이것은 모든 H/W로의 접근과 그 사용권한이 커널을 통해서만 이루어지기 때문이죠. Resource라는것은 사실상 H/W로 할수 있는 모든것을 의미합니다. CPU와 메모리부터 시작해서 H/W가 추상화되어 쓰일수 있는 모든 개념입니다. 디스크나 화일, 네트워크 등이 모두 resource로 취급되며, 이들을 잘 분배해서 나누어주는것이 커널의 일이라고 할수 있습니다. 이러한 관점에서 resource manager라고도 볼 수 있습니다.
이러한 철저한 계층화(layered structure)는 system call이라는 것을 이용하여 구현되어 있습니다. 즉, Application은 H/W에 접근하기 위해서는 항상 OS가 제공하는 system call이라는 것을 통해야만 가능하다는 것입니다. 기존의 DOS같은 경우 이렇게 철저하게 분리되어 있지는 않았습니다. application은 BIOS 서비스와 OS가 제공하는 서비스를 모두 쓰는등 layed structure가 완전하지 못했습니다. 그러나 이제 386이후로 본격적인 OS들은 모두 이러한 계층화를 완전하게 이루고 있습니다.
모든 SW가 그렇듯이 OS역시 need에 맞춰져서 디자인됩니다. PC와같은 환경에서는 사용자의 편의를 위해서 performance가 중요시되나 resource utilization은 곧잘 무시되죠. 반면 server환경에서는 throughput혹은 resource utilization이 중시됩니다. 최근에는 mobile환경등에서는 energy efficiency가 매우 중시됩니다. 이와같이 목적에 따라 OS디자인과 철학은 달라집니다. 또한 CA와 OS는 뗄수없는 밀접한 관계에 있습니다. SW와 HW가 서로 영향을 주고받으며 발전해온 대표적인 경우죠.
본격적인 이야기를 하기 이전에 먼저 컴퓨터라는 것에 대해서 생각해보고자 합니다. 컴퓨터는 결국 다음과 같은 간단한 모델이라고 생각할 수 있습니다.
I/O란 모니터나 키보드등의 모든 입출력과 관련된 부분이기 때문에 실제로는 CPU와 메모리만 있으면 컴퓨터라고 부를 수 있는 형태가 됩니다. 간단하지요. 이러한 모델을 computational model이라고 부릅니다. (네, 바로 튜링머신입니다. ^^;) 본질적으로 이러한 컴퓨터의 기본 구조를 폰노이만 구조라고 부르며 아시다시피 CPU는 명령이 주어지면 주어진 명령을 수행하는 프로세서의 역할을 하고, 메모리는 그러한 명령이나 연산결과등이 담기는 말 그대로의 메모리의 역할을 합니다. (CPU는 레지스터라고 하는 간단한 임시 메모리를 가지지만 이런 모델에서는 CPU는 메모리를 가지지 않는다고 가정합시다. 단순화하는거죠.) 메모리는 단순한 array라고 생각하시면 되고, 이제 실제로 이러한 모델이 어떻게 동작하는지 간단하게 살펴보면,
ADD 80번지, 20번지, 10번지
이와 같은 명령이 수행된다고 생각해보죠. 물론 ADD와 같은 instruction은 코드화되어서 메모리에 저장되어 있을 것이고, 이러한 명령들의 집합과 그 행동등은 이미 잘 정의되어 있고 CPU는 그러한 정의에 따라서 충실히 일을 수행하게끔 구현되어있습니다. 이러한 명령집합(instruction set)과 그 구체적인 행동등의 잘 정의된 내용들을 CPU Architecture라고 부릅니다. 우리가 흔히 부르는 x86이나 ARM등의 아키텍쳐가 이러한 CPU architecture의 예라고 할 수 있습니다.
주의하실 것은 이러한 아키텍쳐는 하드웨어가 아닌 단지 definition이라는 것입니다. 이러한 Architecture들은 책등으로 publish되어 있는 것뿐이고 이것을 실제 구현한 CPU는 얼마든지 다른 회사에서 만들어낼 수 있습니다. (라이센스 문제가 해결된다면 말이죠) x86이라는 아키텍쳐는 인텔에서 만들었지만 x86호환되는 CPU들은 많은 회사에서 독립적으로 만들어낸다는 얘기입니다.
위의 ADD명령의 의미가 80번지의 내용과 20번지의 내용을 더해서 10번지에 쓰는 것이라고 해봅시다. 아마 다음과 같은 동작을 하게 될 것입니다.
1) 80번지의 내용을 CPU안으로 읽어오고
2) 20번지의 내용을 CPU안으로 읽어오고
3) 둘을 더한 결과를 만들어내고
4) 10번지에서 그 결과를 써넣습니다.
사실 아무리 복잡한 현대의 컴퓨터라고 하더라도 폰노이만 형식의 컴퓨터구조는 본질적으로 위의 모델을 벗어나지 않습니다. 사실 현재의 많은 Embedded 기기들이나 오래된 구식 컴퓨터들은 거의 정확하게 이러한 모델을 따르고 있었습니다. 다만 현대의 컴퓨터들은 이러한 모델이 여러번의 추상화를 거쳐 virtualization을 제공한다는 것 때문에 복잡하게 느껴지는 것일뿐 application level에서는 아직도 여전히 이런 간단한 computer model을 제공합니다. 예를 들어 hello.c를 컴파일하고 실행하는 것은 여전히 위의 모델로 쉽게 이해되어질 수 있습니다. 그러나 application level의 프로그래밍과 달리 OS level에서의 프로그래밍이 어려운 이유는 OS가 제공하는 virtualization들을 모두 이해하고 그 메카니즘을 알아야 하기 때문입니다.
현재 가장 중요한 virtualization은 밑의 4가지정도로 생각할 수 있습니다.
1) Virtual CPU
2) Virtual Memory
3) Virtual File System
4) Virtual Machine
4번 Virtual machine을 제외한 3가지 virtualization은 모두 OS가 제공하는 것들이고 이러한 virtualization위에서 application level은 마치 위의 간단했던 computer model을 자신이 하나 가지고 있는 것처럼 편하게 프로그램되고 수행될수 있는 것입니다. 간단하게 설명하자면 Virtual CPU란 1개의 CPU를 마치 여러개의 CPU가 있는 것처럼 쓸 수 있다는 것입니다. 즉 multitasking을 말합니다. 우리가 가진 컴퓨터가 여러개의 창을 띄우고 여러개의 process가 수행될수 있는 것은 이 기능 때문입니다. 즉 개개의 프로그램은 마치 자신이 CPU를 모두 독점하고 있다고 생각할 수 있고 그런 가정에서 프로그램될 수 있는 것입니다. 이런 기능이 없다면 application을 짜는 사람은 얼만큼 실행한후 다음 프로세스에게 CPU를 넘겨준다라고 하는 일들을 손수 해주었어야 할 것입니다. 여기에 Virtual Memory는 프로세스가 마치 메모리 전체를 자기가 혼자 쓰고 있다고 생각할 수 있게끔 만들어줍니다. 만약 이런 Virtual Memory가 없었다면 역시 Application을 프로그램할 때는 어디서 어디까지의 구역은 자신이 쓸테니 그외의 다른 구역은 침범하지 않아야 한다는등의 규칙들을 지켜주어야 할 것입니다. 이런 복잡함을 Application이 신경쓰지 않고도 프로그램할 수 있게된 것이 이런 Virtualization의 목적입니다. 결국 CPU와 Memory에 대해서 프로세스는 위의 모델을 그대로 유지할 수 있게되고 Application은 마치 자신이 독립적인 하나의 컴퓨터 위에서 실행되고 있다고 생각할 수 있는 것입니다.
그러나 I/O의 경우는 좀 문제가 될 수 있습니다. CPU와 메모리는 간단하고 그 특성이 정해져있는 간단한 component라고 할 수 있지만 I/O는 그 특성상 복잡하고 미묘한 문제들이 많이 섞여있어서 다른 방식으로 추상화합니다. 물론 역시 OS가 이러한 추상화를 제공하며 모든 I/O들은 커널을 통해서만이 이루어지게 됩니다. 이것은 이후에 자세하게 다룰 것입니다.
이와 같이 실행의 단위인 process는 OS가 제공하는 virtualization을 통해서 여전히 위와 같은 간단한 모델을 유지할 수 있게 되고 이로써 프로그램이 단순해집니다. 이 모든 서비스를 process에게 제공해주는 것이 바로 OS입니다. 그러한 OS중에서도 핵심적인 부분들을 커널(kernel)이라고 부릅니다.
VM이라는 기법은 아마도 Computer Architecture에 있어서 기념비적인 혁신일 것입니다. OS를 공부하기 앞서서 VM에 대한 충분한 이해가 필수적입니다. 만일 아직도 DOS시절의 XMS, EMS등의 메모리 관리자가 이제 더 이상 쓰이지 않는 이유를 모르신다면, 또는 Vitrual address space와 Physical address space를 구별할 줄 모르신다면 아직 OS책을 펼치기에는 부족합니다. 따라서 이 문서에서는 VM이전과 VM이후에 대한 비교를 자주 하게 될 것입니다. 주로 intel과 linux를 대상으로 설명할 것이기 때문에, "VM이전"은 "386이전" 이라는 말로, "VM이후"는 "386이후"라고 표현될 것입니다. VM이전과 이후를 이렇게 구분하는 이유는, 사실상 VM의 도입 여부가 현대적 CPU인가 아닌가의 판단 기준이 되기 때문입니다. 따라서, "386이후"라는 표현은 "VM이후", 즉 현대적CPU라는 뜻으로 이해될 수 있습니다.
VM은 1950년대 메모리의 부족, 즉 실행 화일이 메모리보다 더 큰 문제,(이를 해결하기 위해 overlay가 등장하지만 문제가 많았습니다.) 그리고 multiprogramming에 따르는 job들간의 protection의 문제등을 해결하기 위해서 등장했습니다. VM은 이러한 문제에 대한 훌륭한 해법이 되었고, 1960년대에 상업용 OS들 사이에서 널리 쓰이게 됩니다. 이후 thrashing이라는 문제점에 대해서 1970년대 후반 working-set을 이용한 해결책이 나오게 됩니다. 또한 캐쉬가 개발되면서 VM은 CA에 있어서 표준으로 자리잡게 됩니다. (Peter J. Denning 의 "Before memory was virtual" 참조)
VM의 기본적인 concept는 "virtual address"와 "physical address"의 분리입니다. 즉, 10번지의 내용물과 20번지의 내용물을 더해서 30번지에 넣으라는 instruction에 대해서 기존에는 10,20,30이라는 주소는 메모리의 실제 주소(physical address)였다면, VM은 10,20,30이 가상 주소(virtual address)입니다. 따라서 실제로 메모리의 어느 지점의 내용물들이 사용될런지는 이것만으로는 알 길이 없습니다. 따라서 VM을 구현하기 위해서는 MMU(Memory management unit)이라는 CPU내의 특수한 하드웨어가 필요합니다. 이 unit에 의해서 10,20,30이라는 physical address는 100,200,300 따위의 실제 주소(physical address)로 변환됩니다. 이러한 변환과정(mapping)은 매우 중요합니다. 아시다시피, 그렇지 않아도 빠른 CPU를 따라오지 못하는 Memory의 속도가 문제가 되는 시점(Von Neuman bottleneck)에서, 1번의 메모리 참조(reference)를 매번 이와 같은 변환 과정을 거쳐서 참조해야 한다는 것은 막대한 성능의 저하를 초래할 것이기 때문입니다. 그렇다면 이러한 성능의 저하를 감수하고라도 VM기능을 이용할 필요가 있는 것인가? 그렇습니다. 그에 따르는 수많은 장점들이 있기에 현대 CPU가 대부분 이를 사용하겠지요. 그렇다면, 이러한 mapping과정의 부하를 최대한으로 줄이는 것이 관건이 됩니다. 이를 위해 사용되는 것이 TLB(Translation Look-aside Buffer)입니다.
이러한 VM의 강력함은 그 부수적인 효과에서도 대단한 변화를 몰고 왔습니다. 즉, VM으로 인하여 각 process는 자신만의 4GB라는 거대한 address space를 가지게 된 것입니다. 이 space는 다른 process에게서는 보이지 않기 때문에 자신만의 공간이며, 4GB라는 풍족한 address space를 십분 활용하여 이전에는 생각하지 못했던 일들을 할 수 있습니다. 즉 남는 address space를 어떻게 physical space에 연결(mapping)시키느냐에 따라서 다양한 활용이 가능한것입니다.
Linux에서 init process의 memory map입니다. 첫 번째 컬럼의 0804800지점에 init 의 실행화일이 올라와 있는 것을 볼 수 있습니다. 그외에도 ld-2.3.2.so 나 libc-2.3.2.so 같은 image(실행화일)들이 올라와 있습니다. 이와 같이 4G라는 주소공간(address space)가 바로 virtual memory address입니다. 제가 실제 메모리를 4GB씩이나 가지고 있을 리가 없으니 말입니다. :-P 이것으로부터 알 수 있는 것이 init이라는 image는 ld 와 libc라는 또 다른 image들을 사용하고 있다는 점입니다. ld는 dynamic linker입니다. 즉, 공통으로 사용되는 libc를 init에서 사용하는데, 이 library를 동적으로 loading해주는 것이 ld라는 linker입니다. 이 ld 는 일반적으로 compiling에 사용되는 static linker이기도 하지만, 동시에 dynamic linker로도 쓰입니다. 여기서 알 수 있는 것이 dynamic library라는 또 다른 특징입니다. 이 간단한 화면으로도 많은 것을 이야기할 수 있습니다. 뒷부분에서 다시 살펴보게 될 것입니다.
(From intel manual)
위의 그림은 intel에서의 virtual address (intel architecture에서는 linear address라고 부릅니다)를 physical address로 변환하는 과정을 보여주는 그림입니다. virtual address는 3부분으로 나뉘는데, 가장 뒤 12비트는 offset으로서 아무런 변환도 거치지 않습니다. 앞의 10비트는 page directory에서의 index를 나타내는 부분으로 쓰이고, 중간의 10비트는 page table에서의 index를 나타내는 부분으로 쓰입니다. 또한, CPU내에는 page directory를 가리킬 하나의 레지스터가 필요합니다. intel에서는 CR3라는 레지스터가 있어, 이 레지스터가 Page directory의 주소를 가지고 있게 됩니다. context switching이 일어나서 다른 process의 virtual address space로 전환하려면 이 CR3의 내용을 해당 process의 page directory의 주소로 넣어줌으로써 각 virtual address space간의 전환을 하게 됩니다.
아시다피시, physical memory는 모두 4KB의 단위의 page로 구성되었다고 생각하고, 이러한 page단위로 접근하기 때문에, 모든 단위는 page로 이루어지는 것이 좋습니다. 따라서 위의 page table과 page directory는 모두 1 page를 차지하게 됩니다. 또한 각 entry는 4byte로 이루어지기 때문에, 자연히 1개의 page는 (위에서 각 page directory와 page table은) 1024개의 entry를 가지게 됩니다. offset은 변환이 완료된 physical page안에서의 offset만을 나타내기 때문에 아무런 변환이 없이 사용될 수 있습니다. 이제 하나의 메모리 참조를 하기 위해서는 CR3가 가리키는 페이지에서 virtual address의 앞 10비트를 index로서 사용해서 해당하는 entry를 참조합니다. 10비트이기 때문에 정확히 1024개의 entry를 cover하게 되는 것입니다. 이렇게 얻은 4byte자리 entry는 다시 다음 page table로의 base address를 제공하게 됩니다. 이때 다시 중간의 10bit를 index로서 사용하여, 역시 10bit이기 때문에 1024개의 entry를 cover하게 되고, 이제 page-table entry를 얻게 됩니다. 이때 나오는 page-table entry가 비로소 physical page의 물리적 주소를 제공하게 됩니다. 이제 이 주소에 원래 virtual address의 마지막 12bit를 합쳐주면 최종적인 physical address를 얻게 됩니다. 이러한 과정은 다음과 같은 2-level tree로서 구성해서 이해할 수 있습니다.
이 그림에서 보듯이 CR3를 root로 해서 tree구조를 형성하고 있습니다. CR3를 제외한 하나의 사각형은 모두 4KB짜리 페이지를 나타냅니다. 따라서 하나의 사각형당 최대 1024개의 화살표를 가질 수 있습니다. 위의 그림에서 page directory에서부터 각 level에서 virtual address의 각 10비트씩을 index로 사용하여 최종 단계에 이르러 (여기서는 page table) 실제 physical page의 주소를 얻게 됩니다. 이렇게 얻은 주소에 12bit의 offset을 합치면 physical address가 됩니다. 여기서 사각형 안에 있는 번호는 physical page number임을 주의하시기 바랍니다. 실제 개념도는 tree일지라도 page directory와 page table등은 모두 실제 메모리를 차지하는 하나의 page이기 때문에 실제로는 각 번호대로 일렬로 그려야 할 것입니다. 이러한 실제 메모리에 대한 그림을 뒤에 넣었으니 참조하시기 바랍니다.
계산을 좀 해보면, 하나의 page table은 1024개의 entry를 가지고, 한 개의 entry가 한 개의 page를 가리키기 때문에, 하나의 page table은 1024개의 page를 가리킬 수 있습니다. 역시 한 개의 page directory에 의해서 1024개의 page table을 가리키기 때문에, 하나의 page directory는 총 1024*1024개의 page를 가리킬 수 있게 됩니다. 이는 곧 4GB의 공간을 나타낼 수 있다는 것입니다. 그러나, 실제로 이 모든 mapping을 한다면, page directory와 page table을 위해서 1025개의 page를 소모하는 꼴이 됩니다. 이것은 대략 4MB의 용량입니다. 하나의 process가 이 mapping을 위해서 4MB씩을 소모할 수는 없는 노릇입니다. 당연히 이 mapping은 필요로 하는 부분만을 mapping하여 사용하게 됩니다. 위의 예에서 12번 물리 페이지를 사용하는 page directory는 4개의 화살표만을 가지고 있습니다. 이것은 곧, 5번째 이후의 entry들은 null일테고, mapping이 존재하지 않는다는 뜻입니다. 이말은 즉, 해당 virtual address에 대한 virtual address space가 존재하지 않는다는 것입니다. 한 개의 page directory entry는 1개의 page table에 대응하고, 하나의 page table은 4MB를 커버하기 때문에, 4개의 화살표는 0~16MB의 공간을 뜻합니다. 따라서, 위의 mapping에서는 16MB까지만의 virtual address가 valid한 것입니다. 사실, 좀더 정확히 얘기하자면, page table에서도 모든 화살표가 있는 것이 아니기 때문에, 화살표가 있는 부분만이 valid한 address space라고 할 수 있습니다. 그렇다면 invalid한 address space로 접근하게 되면 어떻게 될까요? 이런 경우에 page fault가 발생합니다.
또한 page table에서 실제 page로의 mapping이 임의의 방식대로 이루어질 수 있음에 주목하시기 바랍니다. 즉, 화살표가 아무런(임의의) physical page를 가리킬 수 있습니다. 이는 곧, contiguous한 virtual memory space가 실제로 physical memory에서는 아무렇게나 흩어질 수 있음을 뜻합니다. 반대로 physical memory에서 continuous한 영역이 virtual memory에서는 아무렇게나 흩어져있을 수 있습니다.
이와 같이 virtual address와 physical address를 mapping하는 작업은 공짜가 아닙니다. mapping이 많아질수록 물리 메모리를 많이 소비하게 되는 것입니다. 위에서는 8번 page가 현재 free page이기 때문에, 만약 process가 더 많은 virtual address를 요구하면, 커널은 이 8번 page를 추가적인 page table로 할당하여 mapping을 늘릴 수 있습니다. (brk와 sbrk시스템콜관련) 이와 같이, 커널은 전체적인 비어있는 페이지들을 관리하고, 할당할 필요가 있습니다. 이러한 것을 physical memory management라고 할 수 있습니다. linux에서는 대표적으로 이러한 관리를 buddy system을 이용해서 하고 있습니다.
물론 이러한 mapping을 각 process마다 하나씩 가지고 있습니다. 즉, 각 process는 독립적인 virtual address space를 가집니다. 예를 들어 위처럼 또하나의 process가 20,22,23,24번 page를 이용한 또다른 virtual address space를 가질 때, 하나의 physical page는 이 process들간에서 공유될 수도 있습니다. 위에서 1,6,7번 page는 공유되고 있는 page입니다. 이러한 shared memory는 IPC의 주요한 기법중의 하나로 활용될 수 있습니다.
옆의 그림에 이러한 가상주소공간의 실제적인 메모리안에서의 위치와 link관계를 나타내었습니다. page table과 page directory는 색깔로 구별하였으니, 그 의미의 차이를 꼭 구별하시기 바랍니다.
꼭 염두에 두어할 사항중 하나는, 이러한 mapping과정은 모두 옆의 그림처럼 linear한 형태의 메모리에서 일어나고 있는 과정이라는 것입니다. 앞으로 이러한 사항에 대한 구체적인 언급이 없이 "가상 주소를 mapping한다", "주소 공간을 새로 만든다/제거한다", "두 주소공간에서 하나의 physical page를 공유한다"등으로 표현하게 될 것입니다. 이러한 추상적인 표현뒤에 숨어있는 아키텍쳐의 동작을 항상 염두에 두시기 바랍니다.
한가지 더 살펴보고자하는 것은, CR3의 역할입니다. 이 CR3는 현재 그림에서 12를 가리키고 있지만, 물론, 다른 페이지(이를테면 24번 페이지)를 가리킬 수도 있습니다. 매 instruction에서 memory reference가 일어날 때마다 MMU는 이 CR3의 내용에서부터 메모리를 찾아가기 때문에, 즉, 위의 tree구조에서 이 CR3가 root에 해당하기 때문에, 이 CR3의 값이 바뀐다는 것은 다시 말해 "가상주소공간(virtual address space)"를 변경한다는 말이 됩니다. 이것은 context switching때 반드시 이루어져야할 일중의 하나로서, 당연히 서로 다른 프로세스들은 서로 다른 주소공간을 가집니다. 즉, 현재 12번 페이지를 page directory로 가지는 A process의 10번지와 24번 페이지를 page directory로 가지는 B process의 10번지는 엄연히 실제로는 다른 공간인 것입니다. 이와 같이 CR3를 프로세스마다 하나씩 가지고 있는 page directory들 사이를 context switching때마다 multiplexing해가면서 각 process들이 서로간의 독립적인 주소공간을 소유할 수 있게 되는 것입니다.
그러한 이유로 프로세스 입장에서는 다른 프로세스의 주소공간은 구경도 못하게 되는꼴입니다. 이렇게 프로세스들을 서로간에 보호해주는 것을 "protection"이라고 합니다. 그렇다면 프로세스가 CR3를 바꾸면 되지 않느냐고요? 이 CR3는 그 중요성 때문에 kernel mode에서만 loading이 가능한 register입니다. 따라서 유저모드에서는 꼼짝없이 자신의 process공간에 갇혀있는 셈입니다.
여기서 Thread를 생각해 봅시다. 뒤에서 보겠지만, Thread는 일반적으로 주소공간을 공유하는 process들이라고 생각할 수 있습니다. 즉, 같은 process에 속한 A라는 thread와 B라는 thread의 10번지는 동일한!! 공간인 것입니다. 이것은, context switching때 이 주소공간을 switching할 필요가 없다는 것을 뜻합니다. 즉, CR3의 값이 변할 필요는 없는 것입니다. 이러한 이유등으로 thread는 process보다 가볍다(light)고 이야기 합니다. context switching이 보다 빠르다는 이야기입니다.
또한 주소공간을 공유함으로써 얻는 큰 이득중 하나는, TLB를 flush할 필요가 없다는 것입니다. TLB란 이러한 virtual address와 physical address간의 변환을 빠르게 하기 위한 하드웨어 캐쉬입니다. 그러므로 당연히 주소공간이 바뀐다면 그 mapping이 전혀 달라지므로 TLB는 flush되어야 합니다. 그렇게 되면 context switching이후의 한동안의 memory reference는 계속 miss가 나게 되고, 이것은 상당한 성능의 감소를 가져오게 됩니다. 이와 같은 이유로도 thread가 process보다 선호될 수 있는 것입니다.
물론, 주소공간이 공유된다면 문제점도 발생합니다. synchronization이 그것입니다. 어떤 data가 두 개 이상의 실행 context에 의해서 공유된다면, 우리는 항상 그 synchronization을 고려해야 합니다. 이와 관련된 내용은 뒤에서 설명하겠습니다.
이와 같이 VM은 사실 현대 OS의 이해의 첫걸음이라고 할 수 있습니다. 계속되는 이후의 장에서 이해가 되지 않는 부분이 있거나 세부적인 동작을 읽기 어려울 때는 이 부분으로 돌아와서 다시 한번 읽어보시기 바랍니다.
i386에서의 VM에 대해서 여기 좋은 자료가 있네요. 참고하세요
http://liebmona.net/docs/kernel/memory_management.pdf
VM의 페이지 매핑을 구현하는데에는 보통 위와같이 tree구조를 사용합니다. (다른 많은 방식들도 있습니다. 공룡책보면 잘나오죠.) 이 tree구조의 문제는, reverse mapping을 구하기 어렵다는점입니다. 즉 특정한 물리 페이지가 매핑되어있는 주소공간들을 찾아내는일이 쉽지 않다는 것입니다. 이를 위해서는 별 수 없이 모든 페이지 테이블을 뒤져서 해당 물리 페이지에 매핑되어있는 entry들을 모두 찾아내야 합니다. 이것은 엄청난 overhead를 가지게 되죠. 이게 문제가 되는 것은 실제 OS에서 이런일을 해야할 필요성이 있다는 것입니다. 특정 물리 페이지를 할당해제할 때, 즉 memory allocator에게 돌려주기 위해서, (swapping을 할 때가 대표적인 예가 되겠습니다) 해당 물리 페이지의 매핑을 모두 끊어야하는 것입니다. 평소에는 문제가 없지만 메모리가 모자라 swap이 활발하게 사용되기 시작하면, swapping을 위해서 커널은 이렇게 매핑을 모조리 scan해야하고, 그렇지 않아도 시스템이 바쁜와중에 이 작업은 bursty하게 들어오게 됩니다. 이는 thrashing처럼 performance를 급격히 떨어뜨릴 수 있습니다. 이런 현상을 swapping storm이라고 합니다. 실제 이 문제는 리눅스에서 골치거리여서, 2.5대에서 이 문제를 해결하기 위한 방법들이 도입됩니다. 이를 reverse mapping (rmap)이라고 합니다.
더 자세한 내용은 다음을 참고하세요
http://www-128.ibm.com/developerworks/library/l-mem26/
http://www.uwsg.iu.edu/hypermail/linux/kernel/0306.3/1647.html
intel 의 x86계열은 애초에 kernel mode와 user mode의 구분이 없는 형태로 시작한 CPU입니다. 즉, DOS시절에 사용되던 CPU인 것입니다. VM이 없으므로 모든 memory에 직접적으로 접근할 수 있고, instruction의 실행에 아무런 제한이 없었던 것입니다. 그러나 PC가 발전하면서 다른 현대적 CPU가 모두 갖추고 있는 기능인 kernel mode와 user mode의 구분, 그리고 VM마저도 PC가 가질 필요가 생기게 되고,(memory의 빠른 증가와 낮은 CPU의 활용도(utility)등) intel에서도 이러한 기능들을 도입하게 됩니다. 286에서 부분적으로 도입된 이 기능들이 386에서 비로소 완전하게 구현되기에 이릅니다. 그러나 여전히 수많은 application과 게임들이 real mode에서 동작하고 있었고, 유저들을 놓치지 않으면서 앞으로의 발전을 보장할 수 있는 이러한 기능의 도입을 추진하기 위해서 고육지책으로 도입된 것이 real mode와 protected mode입니다. 즉, real mode란 386이전의 DOS시절의, 단지 빠르기만한 8086으로서 동작하는 모드라면, protected mode란 VM와 kernel/user mode등의 기능들이 작동하는 mode인 것입니다. 이러한 기형적인 형태로의 발전으로 인해서 역설적으로 intel 계열 CPU가 공부하기에는 가장 이상적인 CPU가 되었습니다. 즉, real mode와 protected mode의 구분은 intel계열에서만 존재하는 것이며, 이 문서에서 얘기하는 VM 따위의 모든 현대적 기능들은 protected mode에 해당하는 이야기들입니다. 즉 protected mode로 변환한 후에야 kernel mode와 user mode라는 기능이 쓰이기 시작하는 것입니다. Intel 계열의 CPU는 부팅시에는 real mode로서 부팅하지만, 어느 시점에서 OS는 protected mode로 전환합니다. 이 전환 과정을 이해하는 것 역시 VM을 이해하기 위한 훌륭한 과정일 수 있습니다.
또 하나, intel에서는 segment라는 것을 지원합니다. DOS시절 프로그래밍을 해보신 분이라면, 64KB의 한계라든지, memory model(COM과 EXE의 차이등)에 관해서 아실 것입니다. 이러한 것들이 intel이 가진 (real mode에서의) segment방식에 의해서 나타나는 것들입니다. 그러나 protected mode에서는 여전히 segment방식을 지원하지만, 전혀 다른 방식으로 지원합니다. 따라서 이전의 segment를 표현하기 위한 segment/offset방식이 selector/descriptor라는 방식으로 바뀌었으며, 레지스터의 크기는 변하지 않았지만 의미는 전혀 달라졌습니다. 자세한 내용은 intel manual을 참조하시기 바랍니다.
이러한 segment방식은 VM이전에 유용하게 쓰이던 방식이었지만, VM으로 인해서 필요성이 거의 없어진 기능입니다. 따라서 현대의 UNIX들에서는 이 segment기능을 이용하지 않습니다. (앞서 "When memory was Not virtual 참조") 이에 따라서 Linux역시 이 기능을 사용하지 않습니다. 이것은 segment를 사용하지 않는 다른 platform과의 portability라는 측면에서도 사용하지 않는 것이 좋을 것입니다. 이와 유사하게, intel은 VM의 구현을 위해 2-level mapping을 사용하지만, 실제 linux는 3-level mapping을 위한 코드를 사용하고 있습니다. 이중 하나의 level을 아무 의미없이 사용함으로써 x86에서 사용할 수 있게 되어있습니다. 이것 역시 다른 platform을 위한 고려라고 할 수 있습니다. AMD가 x86-64에서 이 segmentation을 제거해버렸죠. 그만큼 인기가 없었던거죠.
VM의 기본적인 동작법을 살펴보았으니, 이제는 옛날 얘기가 되어 버린 VM이 없던 시절 기법을 좀 설명하겠습니다. 이를 통해서 VM의 등장 이유와 그 동기에 대해서 더 잘 이해하실수 있을 것입니다. 또한 사실상 지금은 의미없는 이야기일 수 있지만, CA를 배우는 과정으로서, 혹은 Embedded환경에서 아직도 쓰이고 있는 기법들이므로 도움이 될 수도 있을 것이라 생각합니다. 이와 더불어 old user들에게는 과거에 대한 향수를 일으킬지도 모르겠습니다. ( :-P ) 지금도 intel은 real mode에서는 여전히 메모리가 virtual이 아니기 때문에, 이러한 기법이 적용될 수 있습니다. 또한 VM가 없는 가벼운 embedded환경에서도 유용할 수 있습니다. 그럼 VM이전에는 어떻게 현재 VM로 해결하는 문제점들을 해결하였는지 살펴보겠습니다.
기본적으로 VM이 없이는 실제 메모리보다 큰 실행화일은 실행할 수 없습니다. 이것을 해결하기 위한 방법중 하나가 overlay라는 기법입니다. 고전 게임을 즐기셨던 분들이라면 디스크 1장정도에 파일하나만 들어가있는, ".ovl" 이라는 확장자의 파일을 기억하시는 분들이 있으실 것입니다. 이 파일이 overlay되는 파일들입니다. 실제 실행화일의 일부이지만, 적당한 크기대로 잘려져있는 파일입니다. overlay란 기본적으로 실행의 단계를 몇 개의 phase로 나누고, 각 phase가 진행될 때마다 메모리에 올려진 실행이미지의 일부를 바꾸어가는 방식입니다.
위와 같이 최초 실행시에는 common code와 phase1.ovl를 로딩합니다. common code는 두 phase모두에서 쓰일 코드와, overlay를 관리할, 즉, 각 phase에 맞춰서 해당 ovl화일을 load하는 driver가 존재하고, 이 driver에 의해서 phase간의 이동을 하게 됩니다. 최초에 phase1.ovl로 실행하다가 어느 시점에서 phase2 가 필요할 때 이제는 필요없어진 메모리상의 phase1.ovl 위치에 phase2.ovl을 올려서 사용합니다. 물론 이와 같은 실행을 위해서는 phase간의 구분과 한 phase에서 충분히 사용자가 오랫동안 머무른다는 등의 가정이 있어야 할 것입니다. 이러한 overlay기법은 사실 VM이냐 아니냐와는 상관없이 VM상에서도 쓸 수는 있는 기법입니다. (쓸 이유는 없겠지만 말입니다)
DOS를 써보셨다면, A드라이브로 부팅시 귀찮게도 무엇인가를 실행하고 나면 꼭 A드라이브에 command.com 이 담긴 디스크를 넣으라는 메시지를 만나보셨을 것입니다. 640KB의 한계가 있기 때문에, 어떤 파일을 실행할 때 용량이 꽤 큰 command.com (DOS에서의 command interpreter이지요)을 메모리에 여전히 남겨놓는 것은 상당한 메모리의 낭비입니다. 그만큼 실행가능한 이미지의 크기가 제한을 받기 때문입니다. 이러한 이유로, command.com 에 대한 메모리를 해제하고 application이 더 많은 메모리를 점유할 수 있도록 해줍니다. (지금의 관점에서 보면 별거 아닌 이득이지만.) 이러한 기법도 일종의 overlay기법이라고 할 수 있을 것입니다.(제 생각!)
VM이전에도 multi-programming은 존재하였습니다. (VM이후엔 주로 multitasking이라고 불리우죠) 즉 여러개의 program을 실행하는 것인데, 이때 문제는 process간 protection입니다. 서로간에 침범하여 다른 process를 망가뜨리는 일을 방지해야 합니다. VM은 각 process의 주소공간을 완전히 분리함으로써 이 문제를 해결하지만, 그렇다면 그 이전에는 어떤 방법을 썼을까요? 기본적으로 메모리를 각 process에게 나누어서 할당하는 방식을 생각할 수 있습니다. 이를 위해 고안된 것이 메모리의 특정 block을 segment로 만들어서 이 segment를 관리하는 방식입니다.
만일 2개의 editor process가 돌고 있다면, (process A, process B) 위와 같은 구성이 될 수 있습니다. 3개의 segment가 정의되고, 그중 code segment는 둘 사이에서 공유되면서, data segment만이 서로 다른 구조입니다. 각 segment는 base address라는 것이 있고, limit address가 있습니다.(limit은 segment의 크기값을 가질수도, 마지막 주소값을 가질 수도 있습니다. - intel같은 경우 크기값이 쓰입니다.) 이러한 주소값들은 각 레지스터에 저장되어 있으며, process의 전환시에 적합한 값들로 loading됩니다. 즉, 이 경우 process A에서 process B로 바뀐다면 data segment에 대한 register의 내용들이 (1500, 2000)에서 (2500,3000)으로 바뀔 것입니다. 공유되는 code segment에 대한 레지스터값들은 안 바뀌더라도 말입니다. 이러한 segmentation을 사용할 때 주소 지정방식은 단순히 linear address(즉 그냥 physical address)를 쓰는 것이 아니라, segment:offset 의 모양새로 쓰입니다. 즉, 먼저 사용될 segment를 지정한후, 해당 segment에서의 상대적인 주소(이것을 offset이라고 부릅니다.)를 이용하여 실제 주소를 만들어 냅니다. 예를 들어, 위의 code segment에서 실제 물리 주소 50번지를 가리키기 위해서는 CS:40 처럼 써야 합니다. CS는 code segment register를 의미하는 것으로, base address를 담고 있는 register입니다. 이 경우 CS는 10의 값을 가집니다. 그러면 10과 40을 더해서 50이라는 최종적인 physical address를 얻게 됩니다. 물론, code내에서 모든 주소는 offset만을 사용합니다. 프로그램의 처음에 CS 레지스터를 10으로 설정한 이후에, 예를 들어 20번지의 값과 30번지의 값을 더하여 40번지에 넣으라는 명령은, 실제로는 30번지의 값과 40번지의 값을 더해서 50번지에 넣는 행동을 합니다. 이렇듯 앞서서의 code안에 있는 주소는 offset만을 넣고, 실제로는 segment의 base address가 더하여져서 실행됩니다.
(from intel manual)
인텔에서의 방식입니다. 보다시피 segment descriptor라는 것이 있어서 이곳에 각 세그먼트의 정보가 들어있습니다. 여기에서 각 segment의 base address를 얻을 수 있고, 이 값이 offset (즉 프로그램에서는 그저 주소라고 생각되는)에 더해져서 최종적인 linear address가 얻어지는 것입니다.
이렇게 segment:offset의 형태로 쓰는 중요한 이유가 있습니다. 이것은 주소 바인딩(address binding)의 문제를 해결하기 위함입니다. 만일 이렇게 offset을 이용하지 않는다면, 현재 10번지에 load된 image는 process A와 B를 오갈 때마다 같은 변수에 대한 주소를 바꾸어 주어야 하는 문제가 생깁니다. 즉, A라는 변수가 process A의 변수라면 "1500+얼마" 의 위치에 있을테니, 이것을 수정하면 되지만, 이제 process B로 switch되어 다시 A라는 변수가 쓰일 때, 이것은 "process B의 변수 A"이기 때문에 실제 위치는 "2500+얼마"가 되는 것입니다. (여기서 '얼마'가 offset에 해당합니다.) 이처럼 변수A 라는 하나의 name에 process A냐 process B냐에 따라서 2개의 위치(location)이 대응되고 있습니다. 이중 어느것과 연결하느냐를 주소 바인딩(address binding)이라고 부릅니다. 이러한 binding이라는 개념은 비슷한 모습으로 여러곳에서 등장하는데, 뒷부분에서 설명하겠습니다. 여기서 이러한 문제를 '얼마'라고 하는 offset이 동일하다는 점을 이용해 1500,2500 이라는 base address만을 바꾸어 줌으로써 해결합니다. 이 base address를 register에 놓고, process에 따라서 (사실은 segment에 따라서) 변경만 해주면 각 경우에 따라 올바른 위치를 찾아갈 수 있게 되는 것입니다.
또 하나의 이점은, 메모리내에서 segment를 이동할 수도 있다는 것입니다. 즉, address binding이 base address를 사용하기 때문에 offset이 동일하게 유지되는 이상 실행도중이라도 segment를 메모리의 다른 위치로 이동할 수도 있는 것입니다. 이와 관련하여 relocatable 이라는 개념이 등장하는데, 이후에 설명하겠습니다.
또한 protection을 위해서 각 segment는 limit값을 가집니다. segment의 범위를 벗어나는 메모리 참조를 차단하기 위함입니다. 이렇게 함으로써 segment간의 침범을 차단합니다. 위의 그림처럼, offset과 base address를 더한후에 그 값이 정당한 참조인지, 즉 segment내부에 대한 참조인지를 검사합니다. 만일 그렇지 못하다면 이것은 잘못된 참조로 exception을 발생시킵니다. (뒤에 나옵니다. 즉, 에러처리 됩니다.) 이렇게 함으로써 protection을 달성합니다. (위의 그림은 limit가 physical address일 때입니다. limit가 segment의 크기로 쓰일 때는 검사를 offset에 대하여 미리 해주는 방식이 되어야 하겠습니다.)
다음은 intel CPU에서 어떻게 segmentation이 쓰일 수 있는지를 보여주는 예입니다.
(from intel manual)
Segmentation을 사용할 때의 문제점은, 각 segmentation의 배열입니다. 이른 바 외부 단편화(external fragmentation)이라는 것이 발생하는데, 이것은 segment들간의 위치의 문제입니다. 여러개의 segment가 physical memory에서 띄엄띄엄 위치하게 될 경우, 남는 메모리가 상당함에도 불구하고, 개개의 메모리 구간들이 너무 작아 충분히 크기가 큰 segment를 잡지 못하게 되는 상황이 벌어질 수 있습니다. 이런 경우 각 segmentation을 이동하여 가까이 붙임으로써 빈공간을 만들 수 있지만, (이런 과정을 compaction이라고 합니다.) 그 과정의 overhead도 문제가 되고, 스택과 같은 경우 segment가 자라나야 하는데, 이런 경우 문제가 더욱 심각해 집니다.
Multiprogramming에서 요구되는 protection을 제공하기 위해서 Segmentation이 쓰이고, protection도 이루어지지만, 여전히 실메모리보다 큰 이미지를 실행할 수는 없었고, 이를 위한 편법인 overlay는 사용이 가능한 제한적인 상황과 구현의 복잡성등으로 여전히 충분한 해결책이 되지는 못했습니다. 이 모든 문제점들을 해결하기 위한 멋진 해결책으로 나온 것이 VM인 것입니다.
현대 CPU는 대부분 CPU의 동작 모드를 Kernel mode와 user mode로 구분합니다. 혹은 이러한 모드들을 ring이라고 부릅니다. (real mode와 protected mode와는 혼동하지 마시기 바랍니다.) 386이전에는 그저 부팅후 모든 instruction에 대해서 CPU는 실행을 할 뿐이지만, 386이후부터는 kernel mode인지 user mode인지에 따라서 실행될 수 있는 명령이 있고, 그렇지 않은 명령이 있습니다. kernel mode에서는 모든 instruction의 실행에 제한이 없지만, user mode에서는 특정 instruction들 (중요한 register에 값을 load하는, 혹은 I/O에 관련된 instruction 등)은 수행될수 없습니다. 이러한 명령들을 priviledged instruction이라고 합니다. 또는 조금 유연하게 특정 조건이 만족해야만 수행됩니다. (I/O관련된 이러한 sensitive instructions은 지정된 ring이상의 권한을 요구합니다.) 이처럼 kernel mode에서는 막강한 권한을 가지기 때문에 특권 모드(privileged mode)라고도 합니다. 이러한 기법으로 protection을 달성하게 됩니다. 아시다시피, OS의 커널은 kernel모드에서 실행되고, 일반 process들은 user mode에서 실행됩니다. 그렇다면 kernel mode에서 user mode로의 전환는 쉽게 할 수 있겠지만, user mode에서 kernel mode로의 전환은 민감한 부분이겠지요? 그렇습니다. kernel mode로의 진입은 시스템을 완전히 장악할 수 있는 능력을 획득한다는 의미이기 때문에, 흔히들 말하는 hacking의 중요한 목적이 되는 것입니다. 그렇기 때문에 OS는 user mode에서 kernel mode로의 진입을 엄격하게 제한해야 합니다. 이런 제약에 따라서 user mode에서 실행중인 process가 kernel mode로 진입할 수 있는 유일한 길이 system call입니다.
유저모드에서도 system call과 같은 software interrupt를 일으킬수 있습니다. 이게 유일한 kernel 진입과정이니까요. 그러나 유저가 interrupt vector table을 수정한다면? 혹은 page table을 수정한다면? 문제가 됩니다. 따라서 메모리 보호가 먼저 선행되어야 함을 알수 있습니다. 즉 memory protection은 ring이전에 필요한거죠.
이렇게 CPU의 동작모드를 여러단계로 나누어서 각 모드마다 권한이 제한되게 됩니다. 이런 모드들을 ring이라고도 부릅니다. 인텔에서는 4개의 ring을 제공합니다. 즉 ring 0 가 kernel mode이고, ring 3이 user mode입니다. 때로는 Ring1에서 device driver가 돌기도 합니다. Intel 386의 I/O관련 sensitive instruction들은 각 포트들에 대해서 지정된 ring이상이면 수행될수 있는데, 이는 device driver제작을 위해 구현된 사항인듯합니다. 즉 각 device driver들에게 port를 할당하고 이들을 ring1과 같은 non-kernel mode에서 실행할수 있습니다. (물론 이건 너무 intel-specific이긴합니다만) 또는 Xen과 같은 VMM을 이용하면 Application이 ring 3에서, OS는 ring 1에서, VMM이 ring 0에서 돌게됩니다.
그러나 AMD가 x86-64를 설계하면서 segmentation과 함께 거의 쓰이지않던 두개의 ring을 제거해버려 xen의 경우 문제가 되었습니다. 그외에도 IA64등과 같은 아키텍쳐에서 ring이 2개밖에 없어서 이런 경우엔 OS는 application과 같은 ring에서 수행되며 paging과 같은 memory protection에 의해서 보호받게 됩니다.
일반적으로 주소공간을 kernel space와 user space로 나눕니다. 이러한 kernel space는 모든 process가 공유하는 주소공간이 되는 것입니다. (리눅스의 경우 일반적으로 상위 1G를 kernel space로, 하위 3G를 user space로 나눕니다. 윈도우의 경우는 각각 2G/2G씩으로 나눕니다.) 즉, linux의 경우 상위 1G의 범위에 해당하는 address mapping을 공유하는 것입니다. 이러한 구조로 시스템이 kernel mode일 때는 두 space모두를 넘나들 수 있지만, user mode에서는 kernel space에 접근할 수 없게 됩니다. 이렇게 함으로써, system call이 일어날 때 context switch가 필요 없게 되며, kernel에서는 system call을 부른 process의 공간에 마음대로 접근할 수 있게 됩니다. 이러한 장점 외에도 context switch할 때 kernel space에 해당하는 영역에 대한 TLB는 flush할 필요가 없다는 점 때문에 TLB의 성능이 증대될 수 있다는 점도 있습니다.
이러한 방식을 3/1 split이라고 합니다. 이것은 커널 컴파일시 option을 통해서 2/2 split등으로 바꿀수가 있습니다.
혹은 이러한 방식이 아니라 아예 kernel space를 독립적인 address space로 만들수도 있습니다. 이것을 separate address space 혹은 4/4 split이라고 하는데, system call때마다 TLB를 flush하며 switching을 해야하는 부담이 있습니다. 이런 큰 부담에도 불구하고 이것을 쓰는 이유는 큰 양의 메모리를 제대로 활용하기 위해서입니다.
이런 가상주소공간은 현재 부족한 형편입니다. 3G의 user space도 shared library나 스택등으로 채워놓으면 큰 프로그램의 경우 부족해지기 일수이고, 특히 윈도우의 경우 2G의 좁은 공간안에 많은 구조들이 들어가기 때문에 이미 user space의 부족함은 일상적인 투정이 되어있습니다. (게임 엔진을 만드시는분들이 당장 부족하다며 아우성이더군요) 그러나 정작 더 큰 문제는 kernel space의 부족입니다. 불과 1G밖에 안되는 공간 때문에 실제 물리 메모리를 제대로 활용할 수 없는 상황입니다. kernel space 1G가 왜 부족할까요? 그것은 (리눅스에서) 기본적으로 이 1G안에 모든 물리 메모리들이 매핑되어 들어가야하기 때문입니다. 이것은 linux가 real mode에서 protected mode로 전환하기전에 반드시 하는 매핑인데, 이를 PAGE_OFFSET mapping이라고 합니다. (Linux 참조) Linux에서는 모든 물리 페이지들을 kernel space에 일렬로 쭉 매핑해놓고 원하는 물리 페이지에 접근하고 싶을 때엔 이 매핑을 이용해서 접근합니다. 이로써 메모리 관리가 편리해집니다. 그러나 문제는 1G라는 kernel space의 한계 때문에, 그리고 kernel space는 다른 용도로도 사용되기 때문에 실제 메모리중 대략 하위 896MB정도만이 이 매핑으로 커버됩니다. (이를 low memory라고 부릅니다.) 그 이상의 메모리는 high memory라고 부르며 이들에 접근하기 위해서는 그때그때 mapping을 만들어줘야하는 번거로움이 생기게 됩니다.
이런 문제들의 제대로된 해결책은 두말할 것도 없이 64bit으로의 이전이죠.
kernel space와 user space의 분리는 효과적인 방법이지만, 둘간의 데이터의 전송이 문제가 됩니다. 특히 network에서 문제가 되는데, copy_to_user / copy_from_user를 써서 kernel buffer와 user buffer사이의 복사가 이루어지는 것입니다. (부연 설명)
아시다시피 386이후부터는 모든 I/O와 시스템에 민감한 부분들은 모두 커널이 장악하게 있습니다. 이런 환경에서 process는 사소한 IO라도 하기위해서는 반드시 커널에게 부탁(?)을 해야 하는 입장입니다. 이러한 user mode process의 kernel에 대한 특정 서비스 요청이 시스템콜이라고 할 수 있습니다. 시스템콜은 user mode process에서 특정 인터럽트를 거는 행위로 나타납니다. 각 서비스에 대해서 미리 준비된 번호가 있고, 이 번호를 레지스터등(linux에서는 eax)에 올린후 특정한 인터럽트를 걸 게 되면, 인터럽트 매커니즘에 따라서 kernel mode로 진입하여 해당 서비스를 제공해주게 됩니다. DOS에서는 이런 경우 INT 21h를 사용하였고,(사실 DOS에서는 BIOS call과 시스템콜이 불분명하게 섞여있었죠. 리눅스에서는 BIOS콜은 생각안하셔도 됩니다.) linux에서는 인터럽트 0x80을 시스템콜을 위한 인터럽트로 사용합니다.
이러한 시스템콜은 일반적으로 C함수에서는 wrapper function에 의해서 표현됩니다. 즉, read라는 시스템콜이 있다면, 보통 거기에 대응하는 read() 함수를 C library에서 제공하고 있습니다. 따라서 C 프로그래머는 단지 이러한 wrapper function을 사용함으로써 시스템콜을 사용할 수 있게 됩니다. 그러나 반드시 이렇게 1:1로 대응하지는 않습니다. 예로, malloc(), calloc(), free() 등의 API에서 정의되고 있는 함수는 brk()등의 시스템콜을 사용하여 구현되고 있습니다. 즉, API는 여러 system call을 이용하여 더 기능을 덧붙이는 등의 과정을 거쳐서 만들어지게 됩니다. 물론 strcpy()같은 어떤 API는 시스템콜을 이용하지 않고도 구현되기도 합니다. (시스템콜을 쓰지 않기 때문에 이러한 함수들은 아무리 많이 이용해도 CPU는 커널모드가 아닌 유저모드에서만 동작하게 됩니다.) 이러한 API층은 system call 계층의 위에서 user program에게 제공되는 또다른 층이 되는 것입니다.
이 그림에서 각 계층의 모습을 잘 보여주고 있습니다. API와 system call의 차이를 좀더 잘 알기 위해서 C에서 다음과 같은 비교를 해볼 수 있을 것입니다.
|
API |
System call |
|
FILE structure |
fd (file descriptor) |
|
stdin |
STDIN_FILENO |
|
stdout |
STDOUT_FILENO |
|
fread()/fwrite() |
read()/write() |
|
malloc()/free() |
brk() |
|
Buffered I/O |
Unbuffered I/O |
API와 같은 계층이 더 있음으로 해서 program입장에서는 자세한 H/W spec에 신경쓰지 않으면서도 훨씬 효율적인 I/O를 쓸 수 있게 됩니다. 예로, 화일 입출력을 위해서는 struct FILE 구조체를 이용하고 있는데, 이것은 system call과는 무관한 것입니다. 물론 내부적으로는 모두 read()나 write()를 쓰겠지만, 사용자로서는 더 편리한 fread()/fwrite()를 쓸수 있게 되는 것입니다. 그렇기 때문에 system call에서 쓰는 file descriptor는 C 의 API에서는 FILE 구조체에 해당하는 것이라고 할 수 있겠습니다. 이러한 계층이 사용자에게 편리함과 효율성을 제공하지만, 또한 가끔 이런 계층의 buffering 현상 때문에 예상하지 못했던 현상들이 나타나기도 합니다. 자세한 내용은 Stevens의 APUE를 참고하시기 바랍니다.
Linux에서 시스템콜에 대해서 자세히 알기 위해서 man syscalls를 해보십시오. 또한 소스화일의 include/asm/unistd.h 를 참고하세요.
컴퓨터 시스템의 성능을 높이려면 일반적으로 세가지를 생각할 수 있습니다. 빠른 clock speed의 CPU, 또 빠른 access time의 메모리, 또한 빠른 전송 속도의 I/O system입니다. 그러나 이러한 요소들은 갈수록 성능을 올리기가 어려워지고 있고, 성능 향상에 대한 비용이 높아져 가고 있습니다. 이러한 이유로, 비교적 어렵지 않게 성능의 큰 향상을 꾀할 수 있는 방법들이 강구되는데, 그 대표적인 예가 cache라고 할 수 있습니다. 캐쉬는 memory hierarchy의 각종 메모리 계층간에서 사용될 수 있지만, 이중 CPU와 관련된 캐쉬로, TLB(Translation Lookaside buffer)와 L1 cache(onchip cahce 혹은 internal cache), L2 cache(external cache)가 있습니다. (요즘은 L3캐시까지도 있죠)
캐쉬는 참조의 지역성(locality of referece)를 활용하는 기법으로서, 기본 idea는 프로세스가 현재 직접 사용중인 부분들, 즉 current working set만을 메모리보다 빠른 캐쉬에 저장해둠으로써 메모리로의 실제 접근을 줄이려는 시도입니다.
Memory hierarchy
이러한 구조가 성립하는 이유는 가격과 속도 때문입니다. 상위의 메모리(캐시)는 비싸고 빠른 메모리이며, 하위의 메모리는 느리고 싼 메모리인 것입니다. 이 캐쉬는 DRAM보다 빠르고 비싼 SRAM을 사용해서 구현됩니다.
일반적으로 캐시는 inclusion property가 성립합니다. 이는 하위의 메모리의 내용중 같은 내용을 캐시가 가지고 있다는 것입니다. 당연하게 들리겠지만, L1캐시의 내용을 레지스터로 가져오는 것이고, L2캐시의 내용을 L1캐시로 가져오는 것이고, main memory의 내용을 L2캐시로 가져오는 것입니다. 따라서 캐시는 바로 밑의 층의 내용을 중복해서 가지게 됩니다. 이를 캐시의 inclusion property라고 합니다.
재미있는 것은 CPU내에서의 L1캐시와 L2캐시의 관계입니다. Intel의 경우 이런 일반적인 구조를 가져서 이 둘간에 inclusion property를 가지게 됩니다만, AMD의 경우 다른 방식을 도입했습니다. 거꾸로 AMD의 L1캐시와 L2캐시는 exclusion property를 가지게 됩니다. 이는 두 캐시간에 공유되는 데이터가 없다는 특징으로, 위의 hierarchy와는 다르게 L1캐시와 L2캐시가 disjoint한 관계가 됩니다. Intel의 경우 inclusion property를 지키고 있기 때문에 실제 L1&L2캐시로 인해 캐시가 가능한 용량은 L1 size+L2 size-L1 size, 즉 L2의 크기만큼만이 됩니다. 또한 L1은 L2보다 커질 수 없으며, L1와 L2간의 크기는 일정한 비율을 지키는 것이 효율성의 극대화를 위해서 좋습니다. Intel의 캐시에는 이러한 제한들이 적용되는 것입니다. 반대로 AMD의 경우 실제로 캐시가 가능한 용량은 L1+L2의 크기가 되고, 이러한 크기에서의 제약이 없게 됩니다. 반면에 exclusive cache의 경우 이러한 exclusion을 만들기 위해 추가적인 조치가 필요하기 때문에 L2의 성능이 저하될 수 있습니다. 이와같이 inclusive cache와 exclusive cache는 각각 장단점이 존재하고, Intel과 AMD가 각각 대표적인 경우라고 할 수 있습니다. (인텔과 AMD, 볼수록 흥미롭게도 서로 다른 디자인 결정을 내리죠? ^^; )
여기에 대한 자세한 내용은 http://www.cpuid.com/reviews/K8/index.php 를 참조하세요.
이 TLB는 VM의 핵심부분인 virtual address와 physical address의 변환과정을 빠르게 하기 위해서 도입되었습니다. TLB는 일반적으로 associative memory, 혹은 contents-addressable memory 라고 하는 특수한 메모리를 사용합니다. 이 메모리의 특성은 주소가 아닌 내용물을 입력으로 주면 해당 내용물이 들어있는 주소가 그 결과로 나온다는 것입니다. 이는 매핑을 캐시하기에 좋은 구조이기 때문에 TLB에 사용됩니다. 일반적인 2-level translation에서는 1번의 메모리 참조를 위해서 무려 3번의 참조가 필요하게 됩니다. 아무리 VM의 장점이 많다고하더라도 이러한 막대한 비용은 결국 VM을 쓰지 못하게 만들 것입니다. 이런 이유로 TLB의 성능은 컴퓨터 전체 성능에 결정적인 역할을 하게 됩니다. 이 TLB의 도움으로 3번의 참조라는 비용이 1.2번의 참조정도로, 즉 20%정도의 부하정도만으로 VM을 구현할 수 있게 됩니다. TLB와 캐시를 혼동하지 마시기 바랍니다. 캐시는 메모리 hierarchy에서 아랫단계에 있는 메모리의 내용물들을 똑같이 담고 있는 메모리이지만, TLB는 메모리의 내용들이 아닌 VM의 매핑관계를 담고 있는 메모리라는 것입니다. 즉 매핑관계를 캐싱하고 있는 것이 TLB입니다.
현대 컴퓨터들은 대부분 Interrupt-driven방식입니다. 이것은 정상적인 프로그램의 실행 도중 발생한 사건을 해결하기 위해 잠깐 다른 부분을 실행한 이후에 다시 원래 실행하던 것을 계속해서 실행해 나가는 방식을 이야기합니다. 대표적으로 I/O처리를 들 수 있습니다. 즉, 외부 장치들과 의사소통하기 위해서 Interrupt라는 방식을 사용합니다. 이 Interrupt는 CPU가 정신없이 일하고 있을 때, IO장비들이 뭔가 할 이야기(IO처리가 끝났다는등)가 있을 때 Interrupt라는 신호를 줌으로써 CPU에게 알 리는 것입니다. 이와 대조적으로 예전 Apple같은 경우 Polling이라는 방식을 썼었습니다. 이 방식은 CPU가 한 instruction이 끝날 때마다 IO장비들을 검색하여 자신에게 할 이야기를 가진 IO장비가 있는지를 살펴보는 방식이었습니다. 매우 비효율적이라고 할 수 있습니다. 당연히 Interrupt방식이 효율적입니다. 그 반대급부로 Interrupt는 구현이 복잡하다는 단점이 있습니다. 구현이 간단한 Polling의 경우, 먼저 scan하는 IO slot이 자연히 높은 우선 순위를 가지게 됩니다. Interrupt의 경우 우선순위는 HW적으로 어떻게 Interrupt를 구현하느냐에 달려있습니다.
CPU의 pin들중에 하나에 INTR pin이(interrupt request) 있습니다. I/O장비들중에서 interrupt를 걸게되면 이 line에 신호가 걸리게 되고, CPU는 machine cycle을 돌던중에 마지막에 이러한 신호를 체크하게 됩니다. 이때 interrupt신호가 있다면 interrupt handler로 제어를 옮깁니다.
어느 interrupt가 들어왔을 때, 이 interrupt를 처리해주는 코드를 interrupt handler라고 합니다. CPU는 interrupt가 들어오면 이 interrupt handler를 실행한후에 언제 그랬냐는 듯이 다시 이전 프로그램을 실행합니다. 이렇게 함으로써 현재 실행중인 프로그램을 방해하지 않으면서 (사실 속이면서?) 효과적인 IO를 달성합니다. real mode에서는 상대적으로 이러한 interrupt의 처리가 간단하였습니다. CPU는 interrupt가 오면 주소 0번에서부터 시작하는 interrupt vector table을 참조하여 해당 주소로 jump하기만 하면 되었습니다.(real mode에서 보통 메모리 0번부터 시작하는 주소는 그래서 금지된 주소입니다. NULL pointer가 항상 invalid하다는 것이죠.) 그러나 protected mode에서는, 훨씬 복잡해집니다. 인텔의 경우 IDT를 통하는데........
이와같이 IO device가 필요할 때 CPU에게 interrupt를 걸 수 있지만, 때로는 이러한 interrupt들을 무시해야할 때가 있습니다. 이럴 때 cli 와 같은 instruction을 사용하면 IO장비들로부터 오는 interrupt를 무시할 수 있습니다. 이것을 interrupt disable한다고 합니다. 반대로 sti instruction에 의해서 다시 interrupt enable할 수 있습니다. 그러나 이 명령들이 모든 종류의 interrupt들을 무시하게 해주는 것은 아닙니다. 이러한 instruction에 의해서 무시될 수 있는 interrupt들을 maskable interrupt라고 하고, 그렇지 않는 것들을 non-maskable interrupt라고 합니다.
intel CPU에는 INTR pin말고도 NMI pin이 있습니다. 이것은 nonmaskable interrupt의 신호가 들어오는 pin입니다. power failure같은 interrupt는 매우 중요한 interrupt이기 때문에 NMI에 속합니다. 즉, 무시할 수 없는, cli/sti instruction에 영향을 받지 않는 interrupt입니다.
이러한 maskable interrupt와 NMI외에도 CPU내부에서 발생하는 exception이 있습니다. 이 exception은 외부에서 발생하는 interrupt들과는 달리 CPU내부에서 발생하는 신호들입니다. 즉 instruction을 실행하다가 만나게 되는 문제점들 (0으로 나눈다던지, page fault등)에 대해서 CPU가 스스로 발생시키는 신호인 것입니다. 이런 이유로, 즉 exception이 항상 instruction과 동기화(synchronized)되어서 발생한다는 점 때문에 synchronous interrupt 라고 부르기도 하고, 반대로 NMI와 maskable interrupt를 IO장비에서 아무때나 전달되어오는 신호이기 때문에 asynchronous interrrupt라고 부르기도 합니다.
|
Asynchronous interrupt |
Maskable interrupt |
INTR pin으로 들어옴. cli/sti 로 금지시킬 수 있다. IO장비에서 오는 모든 인터럽트들. |
NMI |
NMI pin으로 들어옴. |
|
|
Synchronous interrupt |
exception |
CPU내부에서 발생. page fault등. |
interrupt라는 용어가 어떤 경우에는 이 3가지 종류의 신호들을 모두 가리키기도 하고, (왜냐하면 exception도 interrupt과 똑같이 처리되기 때문입니다.) 때로는 exception을 강조하여 interrupt는 maskable interrupt와 NMI만을 뜻하기도 합니다. 주로 과거에 interrupt라는 단일 용어로 쓰였었는데, 386이후부터는 VM등의 영향으로 CPU의 control unit이 내부적으로 처리해야할 상황이 많아지면서 (각종 fault들) 최근에는 exception과 interrupt를 구분해서 쓰이는 경향이 있습니다. 이 책에서도 exception와 interrupt를 구분하여 쓰도록 하겠습니다만, 가끔 그렇지 못한 경우도 있을 것입니다. 그리 어렵진 않으니 문맥에서 잘 판단하시기 바랍니다.
예외나 인터럽트가 걸리면 기본적으로 CPU는 자신이 현재 실행중이던 곳의 주소인 EIP를 스택 (커널 모드 스택)에 저장하고, 해당 인터럽트나 예외를 처리합니다. 인텔 매뉴얼에서는 exception을 이 저장되는 EIP의 값에 따라서 다음과 같이 나누고 있습니다.
이외에 INT instruction에 대해서도 알 필요가 있습니다. INT(interrupt)라는 instruction은 S/W에서 직접 exception이나 interrupt를 일으킬 수 있게 해주는 명령입니다. 이것은 system call을 구현할 때와 같은 경우에 필수적으로 필요한 기능입니다. 이런 경우를 인텔 매뉴얼에서는 Software-generated interrupts라고 하고 있습니다. 이 부분에 대해서는 뒤에서 좀더 자세히 살펴보도록 하겠습니다.
PC에서는 interrupt의 구현을 위해서 intel 8259A 칩을 사용합니다. 이러한 칩을 PIC (programmable interrupt controller) 라고 하는데, 이 PIC의 역할은 다른 device controller로부터 interrupt신호를 받아서 (이러한 선을 IRQ선이라고 합니다) 그중 priority가 높은 신호를 CPU에게로 전달해주는 (CPU의 INTR선을 통해서) 것입니다.
(from 8259A data sheet - 8259A interface to standard system bus)
original PC나 XT에서는 하나의 8259칩을 사용하였는데, 위의 그림에서 보시다시피, 최대 8개까지의 장치를 연결할 수 있었습니다. 8259A 는 이들을 직렬연결(cascade)을 통해 최대 64개의 장치까지를 연결할 수 있게 되어있습니다. AT이후부터는 이 8259A 2개를 연결하여 총 16개의 interrupt를 처리하고 있습니다. 여기서 눈여겨볼 pin은 IRQ0부터 IRQ7까지의 외부 device controller와 연결되는 IRQ선과, CPU의 INTR pin에 연결되어 interrupt를 요청하는 INT선, 그리고 CPU로부터 interrupt에 대한 ack를 받는 INTA pin입니다. 개념적으로 나타내면 다음과 같이 그릴 수 있습니다.
위에서 PIC 2개를 직렬연결(cascade)하였음을 볼 수 있습니다. 8259A 칩은 priority에 따라서 IRQ선으로 오는 신호를 처리하기 때문에, 위의 예에서의 priority는 0,1,8,9,10,..14,15,3,4,5,6,7 임을 알 수 있습니다. 또다른 NMI pin은 nonmaskable interrupt를 받는 pin입니다. PIC은 또한 CPU에게 어느 장치가 interrupt를 일으켰는지를 알려줄 interrupt vector를 넘겨주어야 합니다. 이것을 위해서 PIC는 들어온 선의 신호를 미리 지정된 번호(interrupt vector)로 바꾸어 IO공간에 써넣게 됩니다. 기본적으로 intel에서는 IRQ선 번호+32 를 씁니다. 즉, IRQ0번은 32번 interrupt vector에 해당합니다. 이러한 IRQ와 vector간의 mapping은 PIC에 입출력 명령을 써서 programming할 수 있습니다.
이제 8259A의 동작을 살펴봅시다. 8259A는 IRR(Interrupt Request Register) 라는 레지스터를 가지고 있습니다. 이 레지스터는 8bit로 이루어져있으며, 각 bit는 각 IRQ선에 대응됩니다. 어느 한 IRQ선에서 신호가 들어올 때, 정확히는 신호의 rising edge가 파악되었을 때 해당 bit는 1이 됩니다. 또다른 8bit의 IMR(Interrupt Mask Register) 라는 레지스터는 각 IRQ선에 대해서 개별적으로 masking을 할 때 사용됩니다. IRR과 not(IMR)을 AND시킴으로써 masking이 이루어 집니다. 또한 ISR(In Service Register)라는 8bit의 레지스터가 있습니다. 이 register는 들어온 interrupt가 CPU에게 전달되었을 때 (CPU에서 INTA선을 타고 ack가 왔을 때) 1이 되고, CPU가 EOI (End of Interrupt)신호를 보내올 때 0이 됩니다. 즉, ISR에 있는 '1'은 해당 interrupt를 CPU가 처리중임을 표시합니다. 따라서 우선순위가 낮은 IRQ선에서 신호가 들어올 때, ISR의 그보다 높은 bit들중 '1'이 있을 때 그 interrupt의 처리는 미루어집니다.
이때 PIC에서 이루어지는 masking은 각 IRQ선에 대해서 개별적으로 이루어질 수 있습니다. 이 masking은 cli에 의한 interrupt disable과는 다릅니다.
더 자세한 내용은 8259A data sheet를 참조하시기 바랍니다.
이러한 모든 interrupt나 exception들은 0에서 255까지의 숫자로 구분됩니다. (할당됩니다.) 이러한 숫자를 interrupt vector라고 부릅니다. PC에는 interrupt vector table이 있어서 이 table에서 각 interrupt가 들어올 때 그것들에 대한 vector번호를 가지고 처리할 handler의 주소를 얻을 수 있게 되어있습니다. (386이후에는 기본적으로 같지만 좀더 복잡합니다.) 따라서 모든 interrupt나 exception들은 vector값을 가지고 있으면서, 해당 interrupt나 exception이 발생하면 vector table에서 handler의 주소를 찾아서 실행하게 되는 것입니다. 다음 테이블은 각 interrupt나 exception에 vector번호가 어떻게 할당되어있는지를 보여줍니다.
(from intel manual)
여기서 0부터 31번까지의 vector 번호가 예약되어 있음을 볼 수 있습니다. 이중 2번에 NMI가 할당되어 있음을 알 수 있습니다. 즉 NM와 exception은 0~31번에 할당되어 있습니다. 따라서 maskable interrupt들은 32번 이후로 매핑이 가능합니다. 이러한 매핑은 APIC을 통해서 변경할 수 있게 됩니다. 따라서 OS에 따라서 매핑은 차이가 날 수도 있는 것입니다. Linux의 경우 IRQ번호+32번 vector에 각 IRQ들을 할당하고 있습니다. 즉 32번은 IRQ 0 번에 할당되어있는 것입니다.
x86에서는 예외를 20여개정도 일으키는데, 각 경우마다 CPU의 동작이 조금씩 차이가 나기도 합니다. 이를 좀 살펴보면,
|
Vector no. |
Mnemonic |
Linux의 handler |
설명 |
Signal |
|
0 |
#DE |
divide_error() |
DIV나 IDIV가 0으로 나누려고 하거나 결과값이 표현하기에 너무 클 때 발생 |
SIGFPE |
|
1 |
#DB |
debug() |
eflags의 T 플래그가 설정되는등의 디버깅을 위한 exception조건들이 있을 때 발생합니다. |
SIGTRAP |
|
2 |
|
nmi() |
NMI |
|
|
3 |
#BP |
int3() |
INT3 명령으로 발생하는데, 보통 디버거가 breakpoint를 만들기 위해 삽입해 넣습니다. |
SIGTRAP |
|
4 |
#OF |
overflow() |
INTO명령은 EFLAGS의 OF플래그가 켜져있을 때 overflow가 발생하면 이 exception을 발생시킵니다. |
SIGSEGV |
|
5 |
#BR |
bounds() |
BOUND명령이 operand가 주소 범위를 벗어났을 때 발생시킵니다. |
SIGSEGV |
|
6 |
#UD |
invalid_op() |
잘못된 op-code일때. |
SIGILL |
|
7 |
#NM |
device_not_available() |
x87 FPU, MMX,등의 장비가 사용준비가 되지 않았을때 |
SIGSEGV |
|
8 |
#DF |
double_fault() |
CPU가 예외를 처리하는 중인데 예외가 다시 발생했을 경우. 보통 이런 경우 둘을 serial하게 처리할 수 있지만, 간혹 그럴 수 없는 경우가 발생하는데, 이런 경우에 발생. |
SIGSEGV |
|
9 |
|
coprocessor_segment_overrun() |
최근 인텔의 프로세서에서는 발생하지 않지만, 예전 386에서만 387에서 문제가 발생했을 때 발생 |
SIGFPE |
|
10 |
#TS |
invalid_tss() |
TSS가 잘못되었을 때. |
SIGSEGV |
|
11 |
#NP |
segment_not_present |
segment descriptor나 gate descriptor의 present flag가 꺼져있는 경우. 즉 존재하지 않는 세그먼트를 참조하는 경우에 발생 |
SIGBUS |
|
12 |
#SS |
stack_segment() |
존재하지 않는 stack segment를 SS레지스터에 load하려는 경우거나 스택 세그먼트의 한계를 넘어서는 경우. |
SIGBUS |
|
13 |
#GP |
general_protection() |
보호모드에서 보호 규약을 어겼을때. |
SIGSEGV |
|
14 |
#PF |
page_fault() |
주로 참조하는 주소에 대한 페이지가 없거나 하는등의 paging 매커니즘의 규약을 어겼을때 |
SIGSEGV |
|
15 |
|
|
(인텔이 예약) |
|
|
16 |
#MF |
coprocessor_error() |
CR0의 NE flag가 켜져있을 때 발생하는데, x87 FPU가 에러를 발견했을 때 발생. |
SIGFPE |
|
17 |
#AC |
alignment_check() |
operand의 주소가 정렬되어 있지 않을때 |
SIGSEGV |
|
18 - 31 |
|
|
(인텔이 예약) |
|
위의 표에서 알아두어야할 주요 exception은 #SS, #GP, #PF 정도입니다. 13번 #GP의 경우 intel의 protected mode에서의 보호정책을 위반하였을 때 일어나는 exception입니다. 윈도우에서 자주보던 General Protection Violation입니다. :-P 또 14번 #PF는 우리 눈에 익은 page fault입니다. VM에 관련하여 이 page fault와 그 handler를 잘 이해하는 것이 중요합니다. #SS는 자라나는 스택에 대한 exception인데 이를 통해서 VMA를 더 잘 이해할 수 있을 것입니다.
이러한 exception들은 Linux등 unix system에서는 보통 현재 process에게로 전달됩니다. exception의 경우 현재 실행중이던 process에서 발생한 것이기 때문에 interrupt와 달리 현재 process에게 signal을 보내는 것으로 처리할 수 있습니다. 그렇게 함으로써 해당 process가 처리하도록 하기 때문에 커널입장에서는 exception은 손쉽고 빠르게 처리할 수 있습니다. 이처럼 예외의 경우, 커널은 signal로 해당 process에게 전달해주기 때문에 상대적으로 쉽고 빠르게 처리할 수 있지만, interrupt의 경우는 그렇지 않습니다. 왜냐하면 exception과는 달리 interrupt는 일어난 시점의 실행중이던 process와 아무런 관련이 없고, 전달된 interrupt를 해당 process에게 전달해주어야 하기 때문입니다. 이런 이유로 interrupt처리는 좀 더 복잡해집니다. 이에 대한 자세한 내용은 "Nested kernel control path"에서 살펴보도록 하겠습니다.
이러한 인터럽트중에서 중요한 것으로 timer interrupt가 있습니다. timer정도가 뭐가 중요하냐고 반문하실지 모르겠지만, 이 timer interrupt 기능은 multitasking을 위한 기본적인 조건으로 HW는 일정한 시간간격마다 interrupt를 발생시킬 수 있어야 합니다. 그래야만 time sharing system 을 구현할 수 있기 때문입니다. 즉 우리는 OS가 항상 control 을 가질수 있게끔해야하는데, 그래야 user가 무한루프에 빠졌을때도 OS가 시스템을 유지할수 있으니까요, 이를 위해 필요한것이 timer 입니다. 이를 통해 CPU를 보호하는거죠. 당연히 타이머를 조작하는 명령도 priviledged입니다.
현대의 S/W는 Multithreading을 기본으로 하고 있습니다. 즉 parallelism을 얻으려는 것입니다. 어째서 parallelism이 좋은 것일까요? 첫 번째, HW의 능력을 십분 활용할 수 있습니다. 즉 utilization이 좋아집니다. multicore나 SMP환경등 시스템들이 직렬 연산의 한계를 병렬성을 통하여 극복하고자하고 있기 때문에 S/W가 이러한 풍부한 H/W를 활용하기 위해서는 parallelism을 추구해야하겠습니다. 즉 단순히 빠른 직렬연산을 추구하는 방식의 한계에 다다르는 것입니다. 두 번째로는 I/O에 적합하다는 점입니다. S/W의 기본 동작을 계산+I/O라고 볼 때 계산의 부분은 직렬성이 적합하다고 할 수 있지만, I/O의 부분은 병렬성을 필요로 하는 부분입니다. 대표적인 경우로 GUI등 사용자입력을 위한 시스템을 들 수 있습니다. I/O의 특성상 blocking이 많기 때문에 이것을 위해서 여러 쓰레드를 사용하는 것이 프로그래밍에 편리하다고 할 수 있습니다. responsiveness가 좋아진다고 할수 있겠습니다. 그외에 쓰레딩에 대해서 one-to-one이니 many-to-one이니 many-to-many니 하는것들이 있는데, 말장난입니다. 쓰레딩에 대해서는 몇가지 고려사항들이있는데, (1) fork에 대해서는 어떻게 할지? 또는 exec때는? exec때는 보통 모든 쓰레드를, 즉 프로세스 전체를 죽입니다. 그러면 fork때 만약 모든 쓰레드들을 복제했다면 exec가 연달아올때 쓸데없는짓을 한것이 되죠. (2) thread cancellation때는? 프로세스와 달리 (사실 프로세스도 마찬가지지만) thread의 cancel은 좀 어려운 구석이 많습니다. 공유되기 때문인데, 예를들어 lock을 쥐고있는채로 죽이면 무척 곤란해지죠. 또는 여러 thread들이 결과를 찾다가 한 thread가 결과를 찾았을때 다른 쓰레드들은 멈춰버릴 필요가 있다든가, 그럴때 스레드를 취소해야합니다. 그래서 즉시 죽일수도 있겠지만, 그보다 해당 쓰레드가 주기적으로 끝내야할지를 체크해서 스스로 끝내는 방식을 쓸수 있습니다. 이런 지점들을 cancellation points 라고 하고 이런 방식을 deferred cancellation이라고 합니다. 이것말고도 signal의 처리가 애매해집니다. 시그널이 thread때문에 발생한 경우(synchronous signal)에는 어느 쓰레드가 받아야할지가 명확하지만 그외에 외부적인 시그널(asynchronous signal)은 누가 받을지가 불분명합니다. 예를들어 Ctrl-C를 누를때같은 경우죠. 어떤 OS는 모두에게 전달하되 각 thread가 signal mask를 써서 받을지 안받을지를 결정하는 방식을 쓰기도 하지만, 이런 asynchronous signal은 단 한번만 처리되어야 하기때문에 시그널을 막지 않는 첫번째 쓰레드로 전달됩니다. Windows 2000의 경우엔 APC(Asynchronous Procedure calls)를 이용해 시그널과 비슷한 효과를 내는데, APC는 받은 notification에 대해서 어떤 함수를 호출할지를 지정해주게 됩니다. 이런 경우 어느 쓰레드가 받을지에 대한 혼란이 없지요.
보통의 경우 thread pool을 유지합니다. 이건 thread creation 오버헤드때문이기도하고, 요청이 들어오는대로 thread를 만들면 무한대의 쓰레드를 만들게될수도 있기에 pool로 관리를 합니다. 그리고 thread-specific data가 있습니다. 예를들어 UNIX의 errno와 같은 경우 새롭게 구현되었는데......(생략)
쓰레딩을 지원하기 위해서는 커널 내부에서도 적지않은 변화가 필요합니다. 대표적으로 PCB에 TCB(Thread control block)을 달아야하는등의 변화죠. Linux에서는 독특한 방식으로 이것을 처리하는데, 리눅스에서는 프로세스와 쓰레드의 구별이 없이 task라는 이름으로 불리웁니다. 그리고 fork()는 clone()이라는 함수를 콜하는 wrapper일뿐입니다. clone()은 새로운 task를 생성하는데 부모task와 어떤 부분들을 공유할지를 결정합니다. 여기서 주소공간을 공유할지 안할지가 결정되는데 이와같은 flag들에 의해서 어느정도 공유가 될지가 결정됩니다. 따라서 여기에 따라서 쓰레드인지의 여부가 결정되죠.
자바는 언어가 threading을 지원하는 몇안되는 케이스중에 하납니다. 그리고 JVM이 쓰레딩을 구현하기때문에 기본적으로 user level쓰레딩이라고 할수 있겠지요. 그러나 보통 one-on-one으로 커널쓰레드에 매핑시키는것 같습니다.
그러나 쓰레딩 구조에 대한 비판도 많습니다. 대표적인 대안으로 event-driven방식의 프로그래밍을 제안하기도 하는데, GUI등을 이와같은 event-driven형식으로 설계할 수도 있겠습니다.
Program을 실행하면, 커널은 그 image를 메모리에 올리고(load) 실행을 시작합니다. 이렇게 프로그램이 실행중인 상태에 있을 때 그 실행환경(context)과 메모리에 올라온 이미지를 process라고 부릅니다. (Linux에서는 task라고 부릅니다) 이 process는 UNIX에서 전통적으로 쓰이는 실행단위입니다.
multitasking이란 이러한 여러 process들을 동시에 실행시킬 수 있다는 의미로서, 실제로는 위의 그림과 같이 여러 process가 번갈아 가며 실행되는 환경입니다.
그러나 context switch가 너무 무겁고(즉 cost가 크고), fork의 비용이 크다는등의 단점을 보완하기 위해서 thread가 만들어졌는데, thread란 간단히 말해서 하나의 프로세스의 주소공간(address space)를 공유하는 여러 실행 단위들이라고 할 수 있습니다. 즉, 하나의 프로세스는 하나의 thread로서도 볼 수 있으며, 하나의 프로세스는 여러개의 thread로 이루어 질 수도 있습니다. 이러한 thread들은 data와 code를 공유하는 것입니다. 이러한 thread는 process에 비해서 context switch가 빠르며, 빠르게 만들어질 수 있다는 장점이 있습니다. (앞서서의 VM장을 참조하시기 바랍니다.)
context switch가 무거운 이유는 주로 TLB의 flush 때문입니다. 즉 address space의 전환입니다. TLB flush후엔 한동안 매 memory reference가 각각 3번씩의 메모리 참조를 하게되기 때문입니다. (보통 이때는 page table의 내용은 캐시에서 사라진 후겠죠.) 거기에 locality의 변화가 생기기 때문에 cache미스가 마구 일어나는 것이 또한 context switching을 무겁게 만들 게 됩니다. 사실 몇 instruction되지 않는 state의 save/restore는 그 자체로는 큰 부담이 되지는 않습니다. 시스템콜보다 context switch가 훨씬 무거운 이유입니다. 따라서 threading간의 switch는 이와같은 address space의 전환이 없기 때문에 훨씬 가볍습니다. 그래도 locality의 변화만을 좀 겪겠지요. 따라서 따져보면 오버헤드는 context switch(address space switch) >> system call > thread swtich 가 될 것입니다.
thread에는 크게 2가지 종류의 thread가 있습니다. 첫 번째는 kernel-level thread이고, 두 번째는 user-level thread입니다. 이 둘간의 차이는 커널의 scheduler에 등록이 되어있느냐 아니냐입니다. 즉, 등록되어있을 때 kernel-level thread라고 하고, 그렇지 못할 때 user level thread라고 합니다. 즉, 커널이 그 존재를 인식하고 있을 때 kernel level thread인 것입니다. kernel level thread는 커널이 thread단위로 스케쥴링하기 때문에 각 thread들간이 독립적입니다. 이것은, I/O장비등에 의해서 하나의 thread가 block되었을 때도 다른 thread의 실행에 영향을 미치지 않는다는 것을 뜻합니다. 또한 당연히 다른 thread들과 공평한 CPU자원을 분배받을 수 있습니다. 스케쥴러에 의해서 하나의 동등한 단위로 인식되기 때문입니다. 그러나 user level thread에서는 어느 한 thread가 block되었다면, 모든 thread가 함께 block되어 버립니다. 스케쥴러는 그것을 하나의 실행단위로 인식하기 때문입니다. 즉, user level thread란 application level에서 직접 threading을 구현한 것입니다. 따라서 CPU자원은 하나의 process에 오는 양만큼의 자원을 가지고 각 thread가 나누어 가지게 되는 것입니다.
user-level thread는 하나의 thread가 blocking system call을 하게되면 모든 thread들이 block되기 때문에, 이를 해결하기 위해서 다음과 같은 두가지 방법을 생각할 수 있습니다. 하나는 그러한 systsem call을 thread library로 통하게 하고 library는 blocking될 system call을 defer하는 것입니다. 그후 다른 모든 thread가 block되어도 좋을 지점에서 비로소 system call을 부릅니다. (물론 안좋겠죠) 두 번째는, 커널이 프로세스가 multi-threaded라는 것을 인식하고 있다가 blocking system call이 와서 block되면 library에서 upcall로 그 사실을 알려주는 것입니다. (이것도 별로 마음에 안드네요.:-) )
thread라 하면 일반적으로 kernel-level에서의 thread를 뜻합니다.
커널 자체는 process가 아닙니다. 커널은 실행되는 user process에 의해서 system call을 통해서 불리워지는 코드입니다. 이에 반해서 사용자 process외에 kernel thread라고 하는 process가 있습니다. 이 process들은 커널의 부팅 과정에서 만들어지는 process들로서 커널 모드에서 실행되는 process들입니다. kswapd 등의 process들이 이러한 kernel thread들입니다. 이들은 터미널을 가지지 않으며 시스템이 종료할 때까지 살아있는 process들입니다.
커널은 process가 아니라면, 커널은 언제 실행되는 것일까요? 첫 번째, 가장 흔하게 시스템콜이 호출된 경우입니다. 위의 그림에서 user process에 의해서 system call이 불리우면 커널코드가 실행되는 것입니다. 또한 각종 interrupt가 걸렸을 경우입니다. 당연히 모든 interrupt는 먼저 커널에 의해서 처리됩니다. 이러한 interrupt중 timer interrupt의 경우 context switching에 의해서 사용되기 때문에 scheduler가 실행되도록 되어 있습니다. 그외의 다른 I/O장비들로부터 오는 온갖 interrupt를 처리하기 위해서 위의 그림에서처럼 process B가 멈추고 커널코드가 실행됩니다. 또한 scheduler에 의해서 kernel thread가 선택된 경우, 이 kernel thread역시 커널 코드의 일부분이기 때문에 커널이 실행되는 경우입니다.
여러개의 process들이 있을 때 CPU는 각 process들을 조금씩 번갈아 실행시켜가며 마치 사용자에게 모든 프로그램이 동시에 수행되는 것처럼 보이게 합니다. 이러한 방식을 time-sharing 시분할 방식이라고 합니다. 이때 하나의 process에게 주어지는 짧은 수행 시간을 time slice 혹은 time quantum이라고 합니다. 하나의 process의 수행을 마칠 때, 다음 process를 수행하기 위해서 현재 process의 context를 어떤 장소에 보존하고, 다음 process의 context를 올려오는 과정을 context switch라고 합니다. 여기서 context란 일반적으로 한 process가 실행되는 machine state를 말합니다. 즉, 해당 process를 둘러싼 실행 환경이라고 할 수 있습니다. 이 환경이란 다음 instruction의 주소를 가리키는 IP, 각종 레지스터값들, 해당 process의 virtual address space의 page directory의 주소(CR3로 load됩니다), SP (stack pointer), 등의 process가 실행되는데 필수적이고 개개의 process마다 존재해야 하는 모든 정보들입니다. 일반적으로 이러한 정보들은 모두 PCB(process control block) 이라는 구조체에 저장되어 있습니다. 커널은 하나의 process마다 이러한 PCB를 가지고 있으며, linked list같은 형태로 관리합니다. 따라서 context switch때 커널은 방금전에 실행중이던 process의 환경(context)를 그 process의 PCB에 저장하고, 다음 실행된 process의 PCB에서 context를 꺼내어 레지스터등의 적절한 위치에 넣습니다. 이러한 준비로 인해, process입장에서는 자신이 실행될 때 그사이에 어떤 일이 벌어졌는지 모르게 되고 마치 자신이 계속해서 CPU를 사용한 것과 같이 느끼게 됩니다. multitasking을 위한 이러한 작업(context switching)은 매우 비싼편(컴퓨터가 해야할 작업이 많죠)이기 때문에 time quantum의 길이를 길게해서 context switch를 덜 빈번하게 일어나게끔 하는 것이 좋겠지만, 그렇게 되면 process 입장에서는 외부의 입력에 대한 반응이 느려질수밖에 없습니다. 즉, response time이 길어지게 됩니다. 따라서 적절한 time quantum의 길이를 정하는 것이 중요합니다.
이러한 context switch를 가능케 하는 것이 timer interrupt입니다. 이 timer에 의해서 일정한 시간 간격때마다 interrupt가 걸리게 되고, 이것이 context switch를 일으키게 되는 것입니다. 이러한 timer interrupt는 리눅스에서는 틱(tick)이라는 이름으로 부릅니다. 이 틱이 발생하는 고정된 길이의 시간이 해당 시스템에서의 시간을 잴 수 있는 최소단위가 됩니다. 즉 time의 resolution이 되는 것입니다. 예를 들어 Linux 2.6에서는 x86에서 1/1000초 즉 1ms마다 tick이 발생합니다. 이것은 다른 시스템에 비해서 매우 짧은 편입니다. 1초에 천번씩이나 interrupt가 발생하게 되므로 이것은 시스템에 부담을 주게 되는 반면 마우스의 감도등 I/O처리등에 있어서 빠른 반응을 할 수 있게되기 때문에 반응성(responsiveness)가 좋아지게 됩니다. 밑의 그림들에서는 간단히 박스 하나로 처리된 time slice들이 사실은 여러개의 tick으로 구성되었다는 점에 유의하시기 바랍니다. 즉 time slice는 여러개의 tick들로 모여져서 이루어지는 것입니다. time slice 한 개의 길이는 가변적 (즉 tick의 수로 나타나죠) 이고 이것은 스케쥴러가 해당 process에게 얼마나 길 게 CPU를 사용하게 해줄 것인지를 결정하는 것입니다. 리눅스에서는 디볼트로 100ms의 길이가 정해져있습니다. 즉 이런 길이의 time slice동안 여러번의 tick이 발생하게 되고 이런 tick중에서 보다 중요한일이 있다면 이 프로세스는 preemption되고 남은 time slice는 나중에 다시 실행되게 됩니다. 그러나 tick의 발생시에 별다른일이 없다면 tick, 즉 timer handler는 간단한 accounting만을 하고 (매 tick마다 timer handler는 해당 process가 CPU를 1틱동안 썼다는 것을 accounting합니다) 마치 아무일 없었다는 듯이 종료하게 됩니다. 여기서도 알 수 있듯이 tick은 preemption을 위한 전제조건이며 preemption을 할 것인지의 여부를 매번 체크하는곳이 이 timer handler입니다. 동시에 tick은 preemption이 될 수 있는 최소의 단위이자 컴퓨터가 시간을 잴 수 있는 최소의 단위이기도 합니다. 즉 1개의 틱내에서는 당연히! 죽었다 깨어나도 preemption이 되지 않습니다. 그냥 CPU가 수행될뿐이니까요. 아, 물론, 인터럽트나 예외가 발생하는 경우엔 때에 따라 preemption하기도 합니다.
다만, 실행중이던 process가 CPU를 자발적으로 내놓을 수는 있습니다. I/O등의 작업을 하기 위해서 sleep하는 경우가 대표적인데요, 이런 경우 언제든지 CPU는 스케쥴러에 의해서 다른 프로세스에게 넘겨지게 됩니다. 이것을 yield()한다고 합니다.
스케쥴러를 잘 이해하기 위해서는 time slice보다는 tick을 기준으로 이해하시기를 권합니다. tick의 개념은 거의 모든 OS에 동일하게 쓰이는 반면 time slice혹은 time quantum이라는 용어는 다른 책에서는 지금 설명한 tick의 개념으로 쓰이기도 하며 스케쥴러마다 조금씩 다를 수 있기 때문입니다. 또한 time slice라는 것이 preemption이 되면 나머지 길이만큼은 나중에 다시 스케쥴러에 의해서 수행되기 때문에 각 process의 time slice조각들이 섞이기도 하는등 처음 접해서 이해하기 난감한 측면이 있습니다. 이제 이러한 time slice를 모두 써서 그 값이 0이 되면 expired되었다고 하며 스케쥴러는 새로운 값을 주게 됩니다...(생략)
이러한 tick은 시스템설계를 간단하게 해주지만 역시 그 부담이 적잖이 있습니다. 이를 해결하기 위해서 tickless system이라는 것도 많이 이야기되던 주제였습니다. tick을 없애고자 하는 시도인데요, ...(생략)
preemption되어서 context switching할 때 다음번에 어떤 process가 선택되어야 하는지를 결정하는 것을 scheduling이라고 합니다.
process는 어느 특정 시점에 user mode에 있거나 혹은 system call에 의해 kernel mode에 있을 수가 있습니다. 이때 time slice가 다해서 타이머에 의해 인터럽트가 발생했을 때(엄밀히 말해서는 타이머에 의해 time slice값이 줄어들었는데 그때 이 값이 0이되었을때) 해당 process가 user mode에 있다면 선점(preempt)될 것입니다. 즉 스케쥴러가 실행되어서 다른 프로세스가 실행될 것입니다. (앞서 "process and thread"편의 그림 참조) 그러나 process가 시스템콜로 kernel mode에서 수행중이었다면, time slice가 다되었음에도 불구하고 제어권을 내놓지 않을 수 있습니다. 이것을 커널이 preemptible하지 않다고 이야기합니다. 이것은 커널의 자료구조의 동기화 문제 때문인데, 이는 일반 프로세스와 달리 커널의 data structure들은 모든 프로세스들에 대해서 공유되고 있는 데이터들이기 때문입니다. 만일 커널이 preemptible하다면, 즉, 커널의 자료구조들이 동기화 되어 있다면 kernel mode에서도 선점될 수(preemptible) 있습니다. 이러한 커널 자료구조들의 동기화는 쉽지 않은 작업으로, Solaris의 경우 이러한 preemptible kernel이었지만 Linux는 이제 2.6에서부터 지원되기 시작했습니다. 이 부분은 곧 다시 살펴볼 것입니다.
특기할 만한 사항으로는, CPU가 어떤 process를 실행중일 때, context를 가지지만 예외적으로 몇가지 특수한 경우에 context를 가지지 않는다고 할 수 있다는 점입니다. 바로 인터럽트의 경우인데, interrupt handler같은 경우 실행 context가 없다고 볼 수 있습니다. 또는 streams service의 경우에 실행 context가 없다고 볼 수 있습니다. ("Unix Systems for Modern Architecture"참고)
다음과 같이 정리해 볼 수 있습니다. 시스템은 어느 특정한 주어진 순간에 다음과 같은 3가지 경우의 context중에 하나의 경우에 놓여있게 됩니다.
("Linux Kernel Development by Robert Love" 참조)
CPU는 결국 모든 경우에서 위의 3가지 경우들중에서 한가지 경우에 있다는 것을 항상 염두에 두시기 바랍니다.
"Processes and thread"편의 그림에서 살펴본 실행 흐름은 가장 간단한 편에 속합니다. 이제 좀 더 복잡한 경우를 살펴보겠습니다. 앞서와 같이 kernel mode에서 실행되는 제어 흐름을 kernel control path라고 하는데, 이 kernel control path는 여러 이유로 중첩(nested)될 수도 있습니다. 이것은 곧, kernel mode에 있을 때 인터럽트나 exception에 어떻게 대처하느냐 하는 문제입니다.
kernel control path가 어떻게 끝나거나 nested되는지 생각해 봅시다. 가장 간단하게, system call등으로 생긴 kernel control path가 자발적으로 CPU를 내놓을 수 있습니다. 이 경우는 I/O등에게 일을 시켜놓고 결과를 기다리는 것(blocking)과 같은 경우입니다. 이런때 커널은 스케쥴러를 실행하여 context switching을 하게 됩니다. 이런 경우는 nested된 경우가 아닙니다. 이 경우 그저 system call은 자발적으로 CPU를 반납했을뿐이지 여전히 이 kernel control path는 해당 process의 실행과정중 일부분입니다.(즉 해당 process의 context내에서 실행되고 있는 것입니다.) 이런 경우, 이 kernel control path는 다른 kernel control path가 공유되는 커널 자료를 수정할수 있음에 유의해야 합니다. 즉, 실행이 되돌아왔을 때, 자료가 변경되어 있을 수 있다는 것입니다.
즉, 이렇게 여러 kernel control path가 실행 context에 있을 때, 서로간에 kernel data를 변경시킬 수가 있습니다. 따라서 CPU를 내놓은 후에 data가 변하지 않았는지 검사할 필요가 있게 됩니다.
이제 nested되는 경우를 살펴보기 위해서, 먼저 두가지 사항을 알아야 합니다.
이것을 염두에 두고 생각해봅시다. 이제 kernel control path가 nested되는 경우를 살펴보면, exception과 interrupt의 경우가 될 수 있습니다. exception이 발생한 경우, 예를 들어 page fault가 발생한 경우, 페이지를 할당받고 이 페이지를 virtual address space에 연결하게 됩니다. 여전히 이 작업은 해당 process의 context내에서 실행되는 것입니다. 그렇다면 이러한 exception이 여러번 중첩되어 일어날 수 있을까요? 그렇지는 않습니다. 1번 조건에 의해 대부분의 exception은 user mode에서 일어나며, (kernel에 버그가 없다면) kernel mode에서 일어날 수 있는 유일한 exception은 page fault뿐입니다. 또한 이 page fault handler내에서 exception이 일어나지 않으므로, 따라서 exception에만 국한해서 생각해본다면,(즉 interrupt가 안일어난다면) kernel control path는 최대 한번밖에 nested될 수 없습니다. (즉 두 개의 kernel control path가 중첩) 이런 경우에 두 개의 kernel control path는 모두 해당 process의 context에서 실행되는 것입니다.
그런데 이러한 page fault handler는 페이지를 disk로부터 읽어올 때 context switching이 일어날 수도 있습니다. 이런 경우에 다음과 같은 시나리오를 생각할 수 있습니다.
반면, interrupt는 얼마든지 중첩될 수 있습니다. (물론, kernel에는 interrupt를 disable한 영역이 있습니다. 이 영역을 제외하고 말입니다. ) 즉, IO장비에서 오는 interrupt에 대해서는 interrupt handler의 실행이 여러번 nested될 수 있습니다. 이러한 경우, interrupt에 의해서 새로이 시작되는 kernel control path는 해당 process의 context와는 무관합니다. (당연하죠. IO장비는 아무때던지 interrupt를 걸기 때문이죠 - accounting과 관련하여서는 이렇게 interrupt에 의한 kernel control path가 해당 process와는 무관함에도 불구하고, 사용된 CPU양은 해당 process가 사용한 것으로 계산(accounting)됩니다.) interrupt에 관련되어서 kernel control path가 얼마든지 중첩될 수 있지만, timer interrupt에 따르는 context switching은 일어나지 않습니다. 즉, interrupt handler를 처리중인 Linux kernel은 time quantum이 다 소모되더라도 context switching을 하지 않는 non-preemptible kernel입니다. 이것은 만일 이를 허용했을 때 나타나는 kernel data들의 동기화문제를 피해가기 위해서입니다. Linux에서 Interrupt handler가 non-preemptible이라는 것은 조건2)에서 보다시피 interrupt handler는 page fault를 일으키지 않기 때문에, 즉, context switching을 일으킬 수 있는 page fault가 일어나지 않기 때문입니다. 이처럼 kernel mode에서 interrupt handler가 non-preemptible이고, timer interrupt에 의해 context switching하지 않기 때문에 결국 Linux kernel은 스스로 CPU를 내놓지 않는 이상 context switching이 일어나지 않게 됩니다. 이러한 kernel preemption은 Solaris등에서 구현되었었는데, 이것은 kernel data들을 동기화시켜야 함을 의미합니다. 이럴 때 커널은 preemptible kernel이 될 수 있고, Linux에서는 이번 2.6대에 들어서면서 지원되기 시작했습니다.
( Interrupt handler는 얼마든지 중첩될 수 있다.)
** 그런데 page fault 로 일어난 kernel control path에서 다시 interrupt가 걸리면 어떻게 되는걸까?) **
모든 Unix 커널은 reentrant(재진입 가능)합니다. 따라서 linux kernel 역시 reentrant합니다. 이것은 즉, 여러개의 process가 동시에 커널 모드에서 실행중일 수 있다는 표현입니다. 예를 들어 Process A가 IO장비의 일이 끝나기를 기다리고 있고, 그때 Process B가 system call을 호출하여 커널 모드로 진입할 수 있습니다. 이렇게 reentrant하기 위해서는 일단 해당코드(여기서는 커널)이 self-modify하지 않아야 합니다. 어떤 코드는 때론 자기 자신의 코드를 스스로 고치기도 하는데, 이런 코드는 reentrant하지 않은 코드입니다. (386이전에 도스같이 모든 system을 하나의 process가 장악하고 있을 때는 이런 기법이 쓰일 수 있었고 문제가 없었겠지만 지금은 하나의 image에 여러개의 process가 뜰 수 있기 때문에 기본적으로 모든 프로그램은 self-modify하지 않아야 합니다.) 요즘 같은 시절엔 너무 당연한 얘기로 들리기도 합니다. 사실 진짜 문제는 데이터입니다. reentrant하기 위해서 코드가 아닌 데이터에 있어서의 문제점은, 각자의 스택에 있는 local variables들은 문제가 안되지만, 모든 공유하는 global data의 경우에는 동기화(synchronization)가 이루어져야 한다는 점입니다. 즉 모든 커널 데이터를 서로에 대해서 보호해야합니다. Linux 2.4까지만해도 이것은 어려운 문제였기 때문에 한 시점에 하나의 프로세스만이 커널 모드에 진입해있을수 있도록 함으로써 커널을 reentrant하게 했었습니다. 즉 한 프로세스가 커널에 진입했을때 스스로 yield하거나 커널을 나가지 않는 이상 다른 프로세스는 커널로 진입할수 없었던 것입니다! 따라서 이런 커널을 non-preemptible kernel이라고 부릅니다. 즉 한 프로세스가 이미 다른 프로세스에 의해 수행중인 커널을 preemption할수 없었다는 것입니다. 다른 관점에서 말한다면 커널만큼은 cooperative scheduling을 한다는것입니다. (또는 커널 전체가 critical section이라고도 할수 있겠습니다.) 가장 간단한 해법이죠.
이와 같이 버전 2.6이전까지의 linux kernel은 non-preemptible kernel입니다. 이것은 linux뿐만이 아니라 고전적인 unix kernel이 커널 동기화(kernel synchronization)을 위해서 채택하는 방식입니다. 이번 linux 2.6대에 이르러 preemptible kernel을 지원하게 되었습니다. 이것은, 즉, 커널코드들도 다른 process에 의해서 선점될 수 있다는 의미입니다. 이전 커널에서는 다른 프로세스가 커널로 진입하고자할때 인터럽트 핸들러들이 단지 need_schedule flag를 켜놓아서 커널이 다음 user mode로 들어갈 때 스케쥴러가 호출되어 적절한 process가 CPU를 차지할수 있도록 하는 것이었습니다. ( 이러한 Linux 커널은 kernel mode에서 user mode로 돌아갈 때 need_schedule flag를 살펴보아서 켜있을 때 context switching을 일으킵니다. )
장점은 synchronization을 피할수 있다는것 정도라고 할까요. (그러나 물론, 이런 경우에서조차 interrupt나 exception등의 쓰레드는 언제든지 CPU를 차지할수 있기때문에 반드시 커널과의 synchronization을 해줘야합니다. 다시한번 interrupt 의 특수성을 알수 있습니다.) UP환경이라면, 아마 큰 성능의 저하없이 latency의 희생정도로 끝날수도 있겠습니다만, MP환경에서는 심각한 문제를 발생시킵니다. 즉, 오로지 한 CPU만이 커널모드로 진입할수 있다는것이죠. 따라서 우리는 보다 적극적으로 모든 CPU혹은 프로세스가 커널모드에 있을수 있도록 해야할것입니다. 즉, 이를 위해 공유하는 모든 data structure를 보호하기 위해서 locking 매커니즘을 사용하여 커널을 reentrant하게 만들 게 됩니다. 이러한 locking 매커니즘은 간단히 말해서 kernel의 특정 구간(reentrant하지 않은 부분, 즉 공유 data를 수정하는 부분)을 critical section으로 묶어 이 구간에는 하나의 프로세스만이 진입할 수 있도록 만드는 기법입니다. 따라서 MP