Memory Management
이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.
http://kocw.net/home/cview.do?cid=3646706b4347ef09
운영체제
운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각
www.kocw.net
Memory
프로그램이 실행되면 갖게 되는 자원으로, 주소로 접근한다.
Address
주소는 두 가지 유형이 존재한다.
- Logical Address (=Virtual Address, 논리적 주소): 실제 물리 메모리의 위치가 아닌 프로세스에게 가상으로 할당된 독립적인 메모리 공간을 가리키는 위치. 0번지부터 시작하며, CPU에서 메모리에 접근할 때 사용하는 주소는 logical address이다.
- Physical Address (물리적 주소): 실제 물리 메모리 상에서의 위치
결국 프로세스가 메모리에 올라가는 물리적인 위치(물리적 주소)를 결정해야 하는데, 이를 Address Binding(주소 바인딩)이라 한다.
*Symbolic Address: 프로그래머는 특정 함수나 변수에 접근할 때 숫자로 구성된 logical address를 사용하지 않고, 변수나 함수의 이름을 이용하여 접근하는데, 이때의 이름을 Symbolic Address라 한다. 주소 바인딩에는 symbolic address를 logical address로 변환하는 과정을 포함하는데, compile time에서 symbolic address의 logical address가 결정된다.
Address Binding
주소 바인딩의 방식에 따라 주소의 결정 시점이 다양한데, 아래와 같은 방식이 존재한다.
- Compile Time Binding: 물리적 주소가 컴파일 시 결정된다. 따라서 재컴파일을 하지 않는 한 시작 위치는 바뀌지 않는다. 이때 컴파일 타임에서 심볼릭 주소가 논리적 주소로 바뀌므로, 결국 논리적 주소는 물리적 주소와 동일한 것을 알 수 있다. 따라서 컴파일 타임에 결정되는 주소는 메모리에 load되어도 변하지 않기 때문에, 이 바인딩 방식으로 컴파일 된 코드를 Absolute Code(절대 코드)라고 한다. 현 시스템에서는 사용하지 않는 방식이다.
- Load Time Binding: Loader가 실행을 시작한 프로세스를 메모리에 배치할 때 물리적 메모리를 부여한다. 따라서 컴파일 되어 결정된 주소(논리적 주소)는 load시에 새로운 위치(물리적 주소)로 배치될 수 있으므로, 이 바인딩 방식으로 컴파일 된 코드를 Relocatable Code(재배치가능 코드)라고 한다.
- Execution Time Binding (=Run Time Binding): 프로세스가 실행하는 도중에 물리 메모리 상 위치가 변동되어 물리적 주소가 바뀐다. 따라서 CPU가 메모리에 접근할 때 주소 바인딩 정보(address mapping table)를 참조하며, 하드웨어적 지원(MMU, base/limit register)이 필요한 방식이다.
MMU (Memory-Management Unit)
logical address를 physical address로 매핑하는 하드웨어 장치로, CPU가 logical address만으로 메모리 접근이 가능하도록 한다. 이 하드웨어는 base register(=relocation register)과 limit register을 사용한다.
위 그림은 relocation register의 용도를 나타낸 것이다. Relocation Register는 물리 메모리에 load된 프로세스의 시작 위치의 물리적 주소가 저장되는데, 예를 들어 위 그림에서는 특정 프로세스의 시작 부분이 위치(논리적 주소로 0번지)한 물리적 주소는 14000번지이다. 그리고 이 레지스터의 값을 이용하여 물리적 주소를 구하는데, 논리적 주소에 relocation register의 값을 더한다. 다시 그림을 보면 논리적 주소 346의 위치는, 시작 위치인 0에서 346만큼 떨어진 것인데, 실제 메모리상에 올라간 시작 위치가 14000이므로, 14000에 346을 더한 14346이 물리적 주소가 되는 것이다.
하지만 오동작 등으로 CPU가 프로세스가 할당한 영역의 범위를 벗어나는 위치를 요구할 때 이를 확인하고 막는 것이 Limit Register이다1. limit register에는 프로세스가 할당 받은 크기, 즉 논리적 주소의 범위가 저장된다. 위 그림에서 동작하는 프로세스의 크기가 3000이라고 가정하면, limit register에는 3000이 저장되는 것이다. 이때 CPU가 논리적 주소 4000번지에 접근하려 하면, 해당 주소 값은 할당된 범위의 마지노선 3000을 벗어나므로 MMU는 해당 위치의 접근을 막는다.
위 그림은 MMU의 동작을 정리한 것이다. CPU에서 logical address에 접근하려 하면, 먼저 limit register로 허용된 위치를 접근하는지 확인하고, 범위 밖의 접근일 경우 trap2을 발생시킨다. 정상적인 접근일 경우 논리적 주소에 relocation register의 값을 더하여 물리적 주소로 변환하고 메모리에 접근한다.
Dynamic Loading
프로세스 전체를 메모리에 load하지 않고, 특정 루틴이 발생했을 경우에만 해당 부분만 메모리에 올리는 것이다. 보통 프로그램들은 지속적으로 사용하는 코드와 데이터들이 있지만, 이들이 점유하는 메모리 크기는 작다. 오히려 가끔씩 호출되거나 사용되는 오류 처리 루틴과 같은 거의 사용하지 않는 코드와 데이터들이 프로세스의 상당 부분을 차지하는데, 이렇게 사용 빈도가 낮은 데이터들을 같이 메모리에 적재하는 것은 비효율적이다. 따라서 필요할 때만 특정 데이터를 메모리에 load하게 되면 memory utilization이 증가한다. 중요한 점은, 이렇게 동작하도록 구현하는 것은 프로그래머의 몫으로, 구현에 도움을 주도록 OS에서 라이브러리로 제공하고 있다는 것이다.
*Dynamic Linking의 개념은 프로그래머가 직접 필요한 시점에 데이터를 load하도록 구현하는 것이다. 운영체제에서 별도로 관리하는 Paging System과는 별개의 개념이다.
Overlays
초창기 시스템에서의 dynamic loading과 유사한 개념으로, 프로그램 1개를 모두 올리지 못했던 그때 당시의 시스템을 위해 메모리에 필요한 부분만 load하는 것이다. 이 개념도 마찬가지로 사용자가 직접 구현해야 하지만, dynamic loading과 달리 OS에서 별도의 지원 없이 오직 프로그래머가 직접 구현해야 했으므로(Manual Overlay) 상당히 어렵고 복잡하다.
Dynamic Linking
link는 여러 목적 파일을 결합하여 하나의 실행 파일을 만드는 것으로, 두 가지 방식이 존재한다.
- Static Linking: 프로그램이 사용하는 모든 라이브러리 코드를 결합하여 하나의 실행 파일로 만드는 방식이다. 실행 파일의 크기가 커지며, 메모리에 적재될 때 해당 라이브러리 코드도 적재되므로, 메모리를 많이 점유하게 된다. 또한 다른 프로그램들이 같은 라이브러리를 사용하더라도 독립적인 메모리 공간을 할당받아, 동일한 라이브러리 코드가 메모리에 중복으로 적재되므로 메모리 관리 측면에서 비효율적이다.
- Dynamic Linking: 프로그램이 사용하는 라이브러리 코드를 실행 도중에 linking하는 방식이다. 해당 라이브러리 코드를 호출하는 위치에 stub 코드를 두어 호출 시 stub를 통해 위치를 찾는데, 만약 라이브러리가 메모리에 이미 존재하면 그 주소로 jump하고, 그렇지 않으면 디스크에서 load한다. 이 방식은 OS의 도움을 필요로 한다.
Swapping
프로세스를 일시적으로 메모리에서 디스크에 있는 swap area(backing store)로 쫓아내는 것을 말한다. 중기 스케쥴러(Swapper)에 의해 메모리에서 swap-out할 프로세스를 선택하는데, 우선순위 기반 CPU 스케쥴링 알고리즘에서는 보통 CPU 우선순위가 낮은 프로세스를 선택하고, 우선순위가 높은 프로세스는 swap-in한다. compile time binding이나 load time binding에는 다시 swap-in될 때 원래의 메모리 위치로 복귀되어야 하므로, swapping 시스템은 run time binding에서 효율적이다. swapping에서 디스크와 주고 받는 데이터의 양은 크기 때문에, swap time은 transfer time3이고, swap하는 크기에 비례한다.
*원칙적으로 Swapping은 프로세스 전체가 swap되는 개념이지만, 현대의 Paging System에서 프로세스의 page가 swap되는 경우 또한 Swapping으로 볼 수 있다.
Allocation of Physical Memory
물리 메모리에서 하위 주소 공간은 OS가 상주하고, 나머지 높은 주소의 영역은 사용자 프로세스가 사용한다. 이때 사용자 프로세스 영역을 할당하는 방식은 2가지로 나뉜다.
- Contiguous Allocation (연속 할당): 각각의 프로세스가 연속적인 공간에 적재되는 방식
- Fixed Partition Allocation (고정 분할 할당)
- Variable Partition Allocation (가변 분할 할당)
- Noncontiguous Allocation (불연속 할당): 프로세스 하나가 여러 단위로 분산되어 메모리에 올라가는 방식. 현재 시스템에서 사용한다.
- Paging
- Segmentation
- Paged Segmentation
Contiguous Allocation
contiguous allocation에서는 2가지의 Fragmentation이 발생한다.
- External Fragmentation (외부 조각): 프로그램의 크기가 분할 크기보다 커서 프로그램이 적재되지 않는 분할 공간을 말한다. 해당 분할 공간보다 작은 프로세스가 없을 경우 그 공간은 사용되지 않는다.
- Internal Fragmentation (내부 조각): 프로그램의 크기가 분할 크기보다 작을 경우 적재 이후에 남는 여분의 공간을 말한다. 이 공간은 특정 프로세스에게 할당받은 공간이지만 실제로 프로세스가 사용하지 않는다.
Fixed Partition Allocation은 물리 메모리 공간을 영구적으로 분할하여 하나의 프로그램을 적재하는 방법이다. 분할 크기의 통일 여부에 따라 2가지 방식으로 나뉘며, 분할된 크기보다 작은 프로그램이 적재되면 해당 분할 공간에서 Internal Fragmentation이 발생한다. 또한 프로세스의 크기가 분할 공간보다 커서 적재가 안 되면 External Framentation이 발생한다. 이 방법은 공간을 영구적으로 분할하므로 동시에 load되는 프로세스의 최대 개수와 프로그램이 적재될 수 있는 최대 크기가 한정되어 있다.
Variable Partition Allocaion은 프로세스의 크기를 고려해 분할하여, 프로세스를 실행 순서대로 쌓는 방식이다. 위 그림에서 프로세스 5, 8, 2가 순서대로 실행되어 적재된 상태에서, process 8이 종료하여 External Fragmentation이 발생했다. 하지만 이 공간에 process 9가 적재되고, 다시 process 5가 종료되어 외부 조각이 생성됐음을 볼 수 있다. 이처럼 분할 크기와 개수가 계속 변하며, 중간에 발생하는 외부 조각을 Hole이라고 하는데, 이것들을 관리하는 기술적 기법이 필요하다.
Hole
Variable Partition Allocation에서 물리 메모리 곳곳에 생기는 가용 메모리 공간을 Hole이라 한다. 임의의 프로세스가 실행되면 해당 공간들 중 프로세스가 적재할 수 있는 공간을 할당하는데, 이 때문에 운영체제는 Hole과 할당 공간에 대한 정보를 갖고 있어야 한다.
Dynamic Storage-Allocation Problem
앞서 기술한 Hole에 새로 실행되는 프로세스를 적재해야 하는데, 프로세스마다 크기 n이 다양하므로 n에 적절한 Hole을 찾아야 한다. 이 문제를 해결하는 방법은 아래 3가지가 존재한다.
- First-Fit: n 이상의 Hole 중 최초로 발견한 Hole에 할당한다.
- Best-Fit: n 이상의 Hole 중 가장 작은 Hole에 할당한다. 모든 Hole의 정보가 담긴 리스트가 정렬이 안 되어 있다면, 해당 리스트 전체를 탐색해야 한다. 이 방법은 아주 작은 Hole을 많이 생성한다.
- Worst-Fit: 가장 큰 Hole에 할당한다. Best-Fit과 마찬가지로 리스트 전체를 탐색하며, 상대적으로 큰 Hole을 많이 생성한다.
직관적, 실험적으로 First-Fit과 Best-Fit은 Worst-Fit보다 속도, 공간 효율 측면에서 효과적이다.
Compaction
메모리에 존재하는 Hole을 한 곳으로 몰아 하나의 block을 만드는 방법으로, External Fragmentation을 해결하는 방법 중 하나이다. 전체적으로 메모리에 할당된 전체 데이터들의 위치를 바꾸므로 비용이 매우 많이 든다. 또한 메모리 위치가 실행 도중에 변경되므로, run-time binding이 지원되어야 한다.
Noncontiguous Allocation
noncontiguous allocation은 대표적으로 Paging, Segmentation 기법이 있으며, 이 둘을 혼합한 Paged Segmentation 기법이 있다. 이 불연속 할당 방법은 프로세스의 데이터들이 여러 조각으로 나뉘어 물리 메모리에 저장되므로, MMU에 의한 주소 변환 과정이 복잡해진다.
Paging
가상 메모리와 물리 메모리 공간을 동일한 크기로 나누어, 가상 메모리의 내용을 Page단위로 물리 메모리 상에 불연속적으로 할당하는 방법이다. 이때 물리 메모리에서 동일한 크기로 나뉜 단위를 Page Frame이라 하고, 가상 메모리의 page와 크기가 동일하다. 또한 가상 메모리의 일부 page는 물리 메모리에 page frame에 저장되고, 나머지는 backing storage(swap area)에 저장된다.
위 그림에서, 가상 메모리의 page 0~3이 물리 메모리 상에서 page frame 1, 3, 4, 7에 저장되는 것을 볼 수 있다. 이때 가상 메모리에의 page에 접근할 때 실제 물리 메모리에서의 그 page에 해당하는 page frame에 접근해야 하는데, Page Table을 이용하여 특정 page가 저장된 page frame number를 알아낼 수 있다. 이 page table에서 index는 가상 메모리의 page number을 의미하고, 각 index에 해당하는 entry에 저장된 번호는 page frame number이다. page 2를 예를 들어, table의 index 2의 entry에 저장된 3을 통해, page 2는 page frame 3에 저장된 것을 알 수 있다.
Paging: Address Translation Architecture
page table에는 page에 해당하는 page frame number가 존재하므로, 특정 데이터가 페이지의 시작에서 얼만큼 떨어져있는지에 대한 offset만 안다면 해당 데이터의 정확한 물리 주소를 알아낼 수 있다.
CPU에서 사용하는 주소는 논리 주소로, 앞의 비트들은 page number(p)로, 뒤의 비트들은 접근하고자 하는 데이터의 offset(d)로 구성돼 있다. 먼저 p와 table을 이용하여 p에 해당하는 frame의 number(f)를 얻어 온다. 그리고 f에 offset인 d를 더하여 원하는 물리 메모리에서 데이터를 접근할 수 있는데, 이때 물리 주소는 {f:d}로, 앞의 비트들은 page frame number(f), 뒤의 비트들은 오프셋(d)로 구성돼 있다. 이러한 방식으로 논리 주소 {p:d}를 물리 주소 {f:d}로 변환할 수 있다.
Paging: Implementation of Page Table
주소 변환에서 사용되는 page table은 물리 메모리에 상주한다. 그런데 가상 메모리 상 특정 데이터의 실제 물리 주소를 모르기 때문에 table을 사용하여 논리 주소를 물리 주소로 변환하는 것인데, 그럼 page table의 물리 주소는 어떻게 알 수 있을까? 이 문제는 MMU에서 page table의 정보를 저장하고 있기에 해결 가능하다. MMU는 아래 두 개의 레지스터를 사용한다.
- Page Table Base Register(PTBR): page table의 시작 위치의 물리 메모리 주소를 저장한다. 초반에 설명한 MMU의 Base Register과 동일하다.
- Page Table Length Register(PTLR): page table의 크기를 저장한다. 초반에 설명한 MMU의 Limit Register과 동일하다.
따라서 어떤 데이터를 접근하기 위해서는, MMU를 통한 물리 메모리 상 table 접근 및 주소 변환, 변환된 물리 주소를 이용한 데이터 접근, 총 2번의 메모리 접근이 필요하다. 그러나 데이터를 읽거나 쓰기 위해 메모리를 2번 접근하는 것은 비용이 큰 동작이므로, 속도 향상을 위해 Cache 하드웨어를 사용하는데, Translation Look-aside Buffer(TLB) (Associative Register)를 사용한다.
TLB는 page number에 해당하는 frame number을 저장하는 Cache Memory로, 먼저 table에 접근하기 전에 TLB를 확인한다. 만약 Cache Hit라면 table을 접근할 필요 없이 물리 주소로 변환이 가능하다. 하지만 TLB는 모든 page의 frame number를 저장하고 있지 않으므로 Cache Miss가 발생할 수 있는데,이 경우에는 물리 메모리에 존재하는 page table에 접근한다. 따라서 TLB에 원하는 page 정보가 저장되어 있는지 탐색을 해야 하는데4, 이 탐색 시간을 줄이기 위해 Parallel Searching이 가능한 Associative Register를 이용하여 구현하므로 한번에 모든 entry를 탐색할 수 있다.
Effective Access Time
EAT = (1 + ɛ)ɑ + (2 + ɛ)(1 - ɑ) = 2 + ɛ - ɑ
Associative Register lookup time = ɛ
Hit ratio = ɑ
※ TLB의 탐색 시간이 작고, Hit Ratio가 높을수록, 메모리 두 번 접근하는 시간(2)보다 더 단축할 수 있다.
위에서 충분히 논의했듯이, page table은 가상 메모리에서의 특정 page에 대한 frame의 정보를 저장한다. 이때 page는 가상 메모리 공간 상에서 존재하고, 또 가상 메모리 공간은 프로세스마다 별도로 할당되므로, 결국 가상 메모리의 page 정보를 담는 page table 또한 프로세스마다 별도로 존재한다. 따라서 TLB에 저장되는 내용들도 어느 프로세스가 CPU를 사용하는지에 따라 달라지는데, context switching이 발생하여 CPU를 점유하는 프로세스가 바뀔 경우 TLB는 flush된다.
Paging: Two Level Page Table
32bit 컴퓨터 시스템은 주소를 32bit만큼 가지므로, 가상 메모리를 2^32Byte = 4GB만큼 할당한다. 이 가상 메모리 공간을 4KB인 page 크기만큼 분할하면, 1M(2^20)만큼의 page가 만들어진다. 따라서 page table는 각 page들에 해당하는 entry를 가져야 하는데, 각 entry의 크기를 4Byte라고 하면 table의 크기는 page 개수 x entry 크기 = 4MB가 되므로, 결국 프로세스마다 4MB의 table이 필요하다. 그러나 실제로 1M개의 page들 중에서 실제로 사용하는 page는 일부이므로, 나머지 사용하지 않는 page들을 위해 table에 entry를 할당하는 것은 공간적으로 매우 비효율적이다5.따라서 이 문제를 개선하기 위해 Two Level Page Table을 사용한다.
Two Level Page Table은 여러 개의 page table 각각을 하나의 page화하고, 이 table들을 구성하는 page들을 outer page table이 가리키는 방법이다. 위 그림에서 outer page table의 entry가 inner page table을 가리키는 것을 볼 수 있다. 가운데에 있는 inner page table들은 각각 하나의 page로 구성되어 있다. 예를 들어, frame number 929...900을 저장하는 table은 하나의 page로, 100...708을 저장하는 table은 또 다른 page로 구성되어 있다. 따라서, 앞서 언급했다시피 entry 하나의 크기는 4Byte이고, page로 구성된 table 1개의 크기는 page 크기인 4KB이므로, 해당 table의 entry 수는 1K개가 된다. Two Level Page Table 방식을 사용하면, outer page table이 논리적인 메모리 크기만큼 만들어 지지만, 사용되지 않는 page들에 대해 inner page table들이 만들어지지 않고, outer page table의 entry를 NULL로 두게 된다. 게다가 실제로 사용되지 않은 page들이 많아, 그만큼 inner page table들이 만들어지지 않으므로 공간의 효율성을 높일 수 있다.
Two Level Page Table을 이용할 경우 논리 주소는 3개의 구역으로 나뉜다. p1을 outer page에서의 index로 접근하는데, 해당 outer table의 entry에는 inner page table를 구성한 page number가 있다. 이 번호를 통해 inner page table의 page에 접근하고, p2를 해당 page table의 index로 하여 해당하는 entry 내부의 page frame을 얻는다. 그리고 해당 page frame에서 d page frame의 offset으로 동작하여 최종적으로 물리 메모리에 접근할 수 있게 된다.
32bit에서 p1, p2, d의 할당 bit 수는 아래의 이유로 정해질 수 있다.
- d는 하나의 page frame의 시작 지점인 0으로부터 끝 지점까지 모두 가리킬 수 있어야 한다. 그런데 page frame의 크기는 page 크기와 동일한 4KB = 2^12B이다. offset d가 이 범위의 바이트를 모두 가리키기 위해서는 12bit여야 한다. 따라서 b는 12bit이다.
- p2는 inner page table에서의 index를 의미한다. inner page table의 크기는 page의 크기인 4KB이고, 해당 테이블의 entry 크기가 4B이므로, entry 개수는 1K개가 된다. 따라서 p2는 1K=2^10개의 테이블을 가리킬 수 있어야 하므로 10bit여야 한다. 따라서 p2는 10bit이다.
- p1에는 32bit에서 d와 p2를 위한 영역을 제외한 나머지 10bit가 할당된다.
이와 같은 이유로, page 크기가 4KB일 때 64bit에서의 주소 체계도 위 그림과 같이 표현할 수 있다.
Paging: Multi Level Page Table
주소 공간이 확장될 경우 3단계 이상의 page table을 사용해야 한다. 그러나 page table은 물리 메모리에 존재하므로 접근해야 하는 table의 수가 많을수록 물리 메모리에 접근해야 하는 횟수가 증가한다. 이 횟수는 앞에서 기술한 TLB를 통해 줄일 수 있다.
Performance of 4 Level Page Table
Effective Memory Access Time = 0.98 × 120ns + 0.02 × 520ns = 128ns
- TLB Hit: 1(TLB access) × 20ns + 1(data access) × 100ns = 120ns
- TLB Miss: 4(table access) × 100ns + 1(data access) × 100ns = 500ns
TLB Acess Time = 20ns, Memory Access Tme = 100ns, Hit Ratio = 98%
※ 128ns에서 메모리 접근은 100ns이므로, 나머지 28ns는 주소 변환에서 소요되었다.
Paging:Memory Protection in Page Table
Page Table에는 frame의 잘못된 접근을 막기 위해 Valid/Invalid Bit와 Protection Bit을 설정한다.
Paging: Valid/Invalid Bit
page table에는 entry에 존재하는 number가 유효한 값인지 valid/invalid bit을 통해 알 수 있다. 만약 해당 bit가 valid라면, number에 해당하는 page frame이 유효하고, 반대로 invalid bit으로 설정되어 있으면 해당 entry 값은 page frame number로써 유효하지 않는 것이다. 위 그림에서 i(invalid) bit으로 설정된 table entry는 0을 저장하고 있지만, 이 값은 frame number로써 frame 0을 가리키는 것이 아님을 알 수 있다. 이 경우는 프로세스가 해당 page 주소 공간을 사용하지 않거나, page frame이 물리 메모리에 있지 않고 swap area에 있는 경우이다.
Paging: Protection Bit
table에는 valid/invalid bit 뿐만 아니라 Protection bit도 저장하고 있다. 이 bit는 entry에 저장된 number에 해당하는 frame의 연산 권한을 의미한다. 권한은 Read, Write, Read-Only가 있는데, 만약 protection bit가 Read-Only로 설정되어 있다면 write가 불가능하다.
* Protection bit에서의 Protection은 '인가되지 않은 제 3의 프로세스로부터의 접근 제한'을 의미하지 않는다. 즉, 특정 프로세스가 다른 프로세스의 page frame에 접근하는 것을 막기 위해 Protection bit를 사용하는 것이 아닌6, 해당 frame의 연산 권한(Read/Write)을 설정하는 것에 목적을 둔다.
Paging: Inverted Page Table
시스템 내부에 page table을 1개만 두어, 모든 프로세스들의 page에 대한 page entry를 관리하는 방식이다. 이 때문에 어느 프로세스의 entry인지 구분해야 하므로, table의 각 entry에는 page를 사용하는 프로세스의 pid를 저장하고 있으며, 해당 page number도 있다. 또한 page frame number는 각 entry의 index로써 동작하는데7, 그 entry는 찾고자 하는 frame에 해당하는 page number와 pid를 이용하여 찾는다. 따라서 논리 주소는 pid와 page number(p), page 내에서의 offset(d)로 구성된다.
논리 주소를 물리 주소로 변환하는 과정을 표현한 그림이다. 먼저 논리 주소 {pid:p:d}에서 pid와 p를 이용하여 table에서 해당하는 entry를 찾는다. 그리고 해당 entry의 table상의 index 값을 frame number로 동작하여 물리 주소 {i:d}로 변환한다. 이 주소 값을 통해, i번 page frame의 시작 위치에서 d만큼 이동하여 원하는 데이터를 찾을 수 있다. 이 inverted page table에서, pid와 page number가 일치하는 table entry를 일일이 탐색하므로 비교적 탐색 시간에서 오버헤드의 단점이 있지만, associative register를 사용하여 entry를 병렬적으로 탐색함으로써 해결할 수 있다.
그런데 Inverted page table인 이유는 page frame number가 table의 index로 동작한다는 사실에서 짐작할 수 있다. 만약 물리 주소를 논리 주소로 변환한다면, 물리 주소 {i:d}에서 i를 이용하여 table entry를 찾고, 해당 entry에서 page number와 그 프로세스의 pid를 얻을 수 있다. 또한 offset인 d는 page나 frame에서 동일하게 동작하므로, 이 역(Inversion)의 과정을 통해 논리 주소 {pid:p:d}로 변환할 수 있다.
Paging: Shared Page
여러 프로세스가 동일한 code를 공유하기 위해 같은 page frame을 table에 맵핑하여 사용하는 방법을 Shared Page라고 한다. 위 그림에서 C library 코드를 물리 메모리 상의 frame에 올린 후, 이 코드를 사용하는 프로세스 수만큼 복제하지 않고, table entry에 해당 frame number(3, 4, 6, 1)을 매핑하여 공유하는 것을 볼 수 있다. Re-Entrant Code 혹은 Pure Code라고도 한다. 반대로 Private한 code와 data는 물리 메모리에 별도의 frame으로 관리한다.
shared page 기법을 사용할 경우 다음과 같은 주의점이 있다.
- Set Protection Bit to Read-Only: protection bit을 read-only로 설정하여, 해당 page frame을 공유할 때 frame 내부의 코드가 변경되지 않도록 한다.
- Fixed Logical Address Space: 각 프로세스에서 실행되는 shared code의 논리 주소 공간이 동일해야 한다. 코드가 가상 메모리에서 저장되는 논리 주소(위치)는 compile time에서 결정되고, 실행 도중에는 정해진 위치 그대로 고정된다. 따라서 정해지지 않은 가상 메모리 위치에서 해당 코드를 실행할 수 없으므로, 공유되는 코드 또한 정해진 논리적 위치에서 실행되어야 한다. 위 그림을 예로 들면, 가상 메모리에 올라간 libc 4개의 page들의 page number가 바뀌면, p논리적인 주소(위치) 또한 바뀌므로, 반드시 libc 코드에 정해진 논리 주소에 배치되어야 한다.
* Shared Page는 IPC와 목적이 다르다. 둘 다 같은 page를 맵핑하는 것은 동일하나, IPC는 프로세스 간 Communication을 위해 사용하므로 read와 write가 가능하다. 그러나 Shared Page는 하나의 code만 올려 그것을 공유하는 것이 목적이므로 read-only만 가능하다.
Segmentation
Paging은 메모리를 동일한 크기로 나누어 관리하지만, Segmentaion은 메모리를 의미 단위로 나누어 관리한다. 여기서 의미 단위란, code, data, stack과 같은 저장하고자 하는 데이터의 목적과 논리적 동작에 따라 나누는 단위를 말한다. 예를 들어, code 영역에는 code를 저장하고, data 영역에는 전역 변수와 상수를, stack에는 함수 호출 정보와 인자 및 지역 변수를 저장한다. 이렇게 의미 단위로 나뉜 각 공간을 Segment라고 한다.
Segmentation: Hardware
paging 기법에서 각 page마다 번호를 부여했듯이, segment 또한 각각의 segment number가 있고, segment의 물리적 주소로 변환하기 위한 segment table가 있으며, 각 table entry에는 segment 시작 위치의 물리 주소인 limit, segment의 크기인 base가 저장돼 있다.
segmentation에서 논리 주소는 segment number(s)와 offset(d)로 구성되어 있고, segment table도 마찬가지로 물리 주소에 저장한다. 따라서 특정 논리 주소를 물리 주소로 변환할 때 다음 register 정보를 이용한다.
- Segment Table Base Register(STBR): segment table의 물리 주소
- Segment Table Length Register(STLR): 프로세스가 사용하는 segment의 수. 즉 segment table의 entry 수를 의미한다.
먼저 주소 변환을 위한 Table을 STBR을 통해 접근한다. 그 다음 segment number(s)를 통해 Table에 entry에 접근하는데 이때 s와 STLR을 비교하여, 만약 s가 STLR보다 같거나 크다면 유효하지 않는 segment number를 이용하여 접근하려 했으므로 Trap을 발생시킨다. 그러나 s가 STLR보다 작다면, 해당 entry에서 limit와 base를 가져와 물리 메모리에 접근한다. 이 경우에도 offset(d)가 유효한지 검사해야 하는데, d가 segment의 길이인 limit보다 크다면 이 역시 Trap을 발생시킨다. 만약 d가 유효하다면, 물리 메모리에서 segment의 시작 위치(base)에서 offset(d)만큼 더하여 원하는 데이터에 접근한다.
* paging에서, 논리 주소를 나눌 때 offset d의 bit를 page frame의 크기만큼 정했다. 이와 유사하게, segmentation에서는 d의 bit수가 접근하고자 하는 segment의 크기만큼 결정되는데, 여기서 주의할 점은 segment에 따라 d의 bit수가 달라진다는 것이다.
Segmentation: Architecture
- Protection: 각 segment별로 valid/invalid bit이 있다. 게다가 Read/Write/Execution 권한도 설정하는 bit도 존재한다.
- Sharing: segment 또한 sharing이 가능하며, 이 경우 물리 메모리 상에서의 같은 segment로 맵핑한다.
* page와 달리, segment는 의미 단위로 나뉘어져 있으므로 공유(share) 및 보안(Protection) 관리가 더욱 효율적이다.
Segmentation: Allocation
segment는 그 크기가 다르므로, 할당과 해제를 반복하면 Hole이 생길 수 있다. 따라서 segment를 할당할 때 앞서 논의했던 Dynamic Storage-Allocation Problem이 발생하는데, 보통 first-fit 또는 best-fit을 사용한다.
Segmentation with Paging
segmentation과 paging을 혼합한 관리 기법으로, segment를 물리 메모리에 올릴 때 page frame으로 쪼개어 올린다. 따라서 segment table entry에는 segment의 길이와, 해당 segment를 구성한 page 정보가 담긴 page table의 시작 주소인 page table base가 있다. 결국 두 개의 table을 이용하여 주소 변환을 2번 거쳐야 된다.
{s:d}인 논리 주소에서, STBR을 통해 segment table에 접근하여 segment number(s)에 해당하는 entry를 찾아, 저장된 segment의 길이와 해당 segment의 page table base를 얻는다. 그리고 offset(d)이 segment 길이보다 작은지 확인하고, 크다면 trap을 발생시킨다. 만약 유효한 offset이라면 해당 d값을 page number(p)와 page offset(d')로 나누고, page table base로 page table에 접근한 후 p를 이용해 page number에 해당하는 entry를 찾는다. 그 entry에는 page frame number(f)가 있는데, 이 f를 통해 물리 메모리 상의 frame을 찾고, d'를 이용해 데이터의 정확한 위치를 찾는다. 이 과정을 통해, 논리 주소인{s:d}가 물리 주소인 {f:d'}로 변환되었다.
Role of OS in Memory Management
지금까지 물리 메모리를 관리하는 기법을 공부했지만, 사실 물리 메모리를 관리하는 주체는 OS가 아닌 하드웨어이다. 지금까지 설명한 주소 변환 과정은 모두 하드웨어가 담당하며, OS는 이 과정에 개입하지 않는다. 만약 프로세스가 메모리에 접근할 때마다 OS의 관리한다고 가정하면, user mode에서 kernel mode로 바뀌는 동작이 필요하다. 그런데 CPU가 메모리에서 필요한 데이터를 load하여 명령을 실행하는 동작에는 주소 변환 과정이 포함되는데, 그럴 때마다 매번 OS가 개입하여 kernel mode로 동작하는 것은 불필요하고 비효율적이다. 이러한 이유로 물리 메모리는 하드웨어가 관리하고, 가상 메모리는 OS가 관리한다.
참고한 자료
>> book
Abraham Silberschatz, Operating System Concepts 10th edition
Abraham Silberschatz, Operating System Concepts 8th edition
>> physiclal memory
https://samypesse.gitbook.io/how-to-create-an-operating-system/chapter9
>> Physical Memory Allocation
https://cstaleem.com/fixed-partitioning
- 그림에 표기되어 있지 않다. [본문으로]
- software interrupt [본문으로]
- disk management에서 공부한다. [본문으로]
- page table과 비교하자면, page number가 곧 page frame의 index로 동작하여, 해당 index의 entry가 frame number이므로 별도의 searching이 필요 없이 index로 바로 접근 가능하다. [본문으로]
- 기존 page table에서는 page number을 index로 접근하여 frame number을 파악하므로, 연속된 page number 중간에 사용하지 않는 page가 있다 하더라도 entry 할당을 생략해서는 안된다. [본문으로]
- 애초에 프로세스가 다른 프로세스의 page frame에 접근할 일은 없다. [본문으로]
- 이 이유로 연속된 page들 중간에 사용하지 않는 page가 없더라도 entry를 할당해야 한다. [본문으로]