Memory Management (2)

Page Table Structure

Paging을 위해서는 Paging Table을 효율적으로 관리하는 방법이 필요하다.

Hierarchical Paging

하나의 Page Table을 여러개의 계층적인 Page Table로 쪼개는 것.

Two-level Page Table방식을 사용한다. Ex. 책의 목차.

Two-Level Paging Table Example

Logical Address가 32bit로 구성이 되고, 페이지가 4K크기일 때

page number는 20bit → 한 테이블에 100만개의 항이 있음. → 메모리로 올라올 때 공간을 많이 차지한다. → p1 = 10bit, p2 = 10bit로 쪼갬.

page offset 은 12bit → 4K크기를 위해 12비트가 필요.

(p,d) → (p1,p2,d)로 바꿈

 

p1을 사용하여 하나의 outer table에서 p2값을 찾고,

p2를 사용하여 다른 하나의 outer table에서 Frame의 값을 찾는다. (메모리의 실제 주소를 찾음)

그 Frame에서 d(offset)값 만큼을 읽는다.

Hashed Page Tables

Hash Function을 사용하여 Logical Address를 Physical Address로 바꾸는 것.

다양한 Hash Function을 사용할 수 있다.

Hash Function에 따라서 같은 Hash값이 나오는 경우가 있고, 같은 Hash값에 대해서는 포인터를 사용하여 Hash Chain을 만들어준다.

Hashed Page Table방식을 사용하여 원하는 Frame Number를 찾아갈 수 있다.

Page Table을 탐색하지 않기 때문에 효율적인 방식이다.

 

Inverted Page Table

프로세스가 사용하는 Page Table이 있다. → 이 Page Table들은 메모리에 올라와 있음

프로세스가 100개이면 Page Table 100개 → 비효율적이다.

 

Physical Memory 전체를 관리하는 하나의 Page Table이 있고, 이 Page Table을 탐색하여 Physical Memory 공간을 찾는다.

이 Page Table은 (pid, p)의 쌍으로 구성되어있다.

탐색을 통해 CPU가 생성한 pid와 p에 맞는 항을 찾은 뒤, 그 인덱스 i를 돌려준다.

전체 Frame을 관리하는 Page Table은 실제 Physical Memory와 1:1로 맵핑되기 때문에 이 Page Table에서 찾은 i (Index)가 Physical Memory공간에서 Index가 된다.

Shared Pages

Shared code

공유되는 코드들. Ex. Text Editor, Compilers, Window Systems

공유되는 코드들은 같은 메모리 어딘가에 위치하고, Page에서 표시를 해주어야 한다.

Private code and data

Private한 code와 data Ex. 한글에서 읽고 있는 문서들

Shared Pages Example

ed1, ed2, ed3 이라는 공유되는 코드들은 프로세스 각각의 Page Table에서 같은 메모리 공간을 가리키고 있는것을 알 수 있다.

 

Segmentation

Segmentation = 조각

메모리를 볼 때 사용자의 View를 반영해주는 메모리 관리 방식.

프로그램의 구성요소는 main program, procedure, function....등등으로 구성되어 있는데,

프로그램의 요소마다 크기가 상이하다.

이 프로그램 요소들을 Segment단위로 설정하고

각각의 Segement는 연속적인 메모리 공간을 할당해주고

Segment끼리는 연속하지 않을수도 있는 메모리 공간을 할당해주는 방식.

Segmentation Architecture

여러개의 Segment를 관리하는 방법.

Logical Address는 <Segment-number, offset> 두 파트로 나누어진다.

<base,limit>을 갖는 Segment Table을 만든다.

base : 특정 Segement의 시작주소.

limit : 특정 Segment의 크기.

Segment Table을 참조하기 위해서는 Segment Table의 시작 주소와 크기도 갖고 있어야 한다.

Segment-Table Base Register(STBR) : Segment Table의 시작주소

Segment-Table Length Register(STLR) : Segment Table의 크기.

Segment number(base)가 STLR보다 크다면 Trap이 발생한다.

 

Address Translation Architecture

CPU에서 발생된 Logical Memory가 Physical Memory로 바뀌는 과정

CPU에서 <segment, displacement> 발생

Segment Table Base Register을 보고 Segment Table을 참조, segment를 찾음.

displacement가 특정 segment의 limit보다 크다 ⇒ Trap 발생.

작다 ⇒ 특정 segment의 base + d ⇒ Physical Memory 주소.

Segmentation Architecture (Cont.)

• Relocationbase값을 변경함으로써 특정 segment의 Physical Memory는 재할당될 수 있다.
• Segment의 위치를 동적으로 재할당할 수 있다.
• Sharing같은 segment number를 사용한다.
• 공유되는 Code는 Segment 단위로 공유가 된다.
• AllocationRelocation이 가능하기 때문에 Compact를 통해 External Fragmentation Exist가 해결가능하다.
• 빈공간 관리는 First Fit or Best Fit을 사용한다.
• Protectionsegment단위로 보호가 되고, segment 단위로 공유가 된다.Continous Memory Allocation에서 사용하는 방법과 비슷한 방법을 사용.
• segment의 크기가 서로 상이해서 Dynamic Storage-Allocation Problem이 발생한다.
• segment table에 유효성을 표시하는 추가 bit를 만들어 유효한 segment인지 또는 어떤 역할의 segment인지(Read/Write/Execute)를 확인할 수 있다.

Segementation With Paging - MULTICS

한 프로그램 안에 여러개의 segment가 있을 수 있고 각각 segment마다 크기가 상이하다.

segment는 Page보다 단위가 크다.

MULTICS System : segment를 page로 분할하여 관리하는 방식.

segment를 구성하는 page들은 서로 연속적이지 않은 메모리공간에 위치할 수 있다.

 

(segment,displacement)에 해당하는 Logical Address를 MULTICS 방식으로 Physical Address로 바꾸는 방식

segment값을 보고 Segment Table에서 segment length와 page-table base를 찾는다.

segment length가 displacement보다 작다면 적절하지 않은 접근으로 보고 Trap이 발생한다.

segment length가 displacement보다 크다면 적절한 접근으로 보고, displacement값을 page와 displacement2로 바꾼다.

page = displacement(word) / frame(page)크기 → 몫

displacement2 = displacement(word) % frame(page)크기 → 나머지

page-table base + p를 통해 특정 segment의 page table에서 frame주소를 찾고 frame에 displacement2만큼을 접근함으로써 Logical Address를 Physical Address로 바꿀 수 있다.

 

MULTICS의 장점

사용자 입장에서는 segment들이 연속적인 공간을 할당받았다고 볼 수 있다.

하지만 실제로는 segment의 page끼리 불연속적인 메모리할당이 가능하기 때문에 효율적인 메모리 공간 관리가 가능하다.