7주차. 메모리 관리(3) _ 그 외 Paging 기법, Segmentation, Paged Segmentation

Multilevel Paging and Performance

Address Space가 더 커지면 다단계 페이지 테이블이 필요하다.

• 각 단계의 페이지 테이블은 물리 메모리에 page로서 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하게 된다.
• TLB를 사용함으로서 메모리 접근 시간을 줄일 수 있다.

4단계 페이지 테이블을 사용하는 경우 접근 시간 계산

(메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, TLB hit ratio가 98%인 경우로 가정한다.)

• 0.98 * (20 + 100)ns + 0.02 * (20 + 400 + 100)ns ⇒ ( 120 * 0.98 + 520 * 0.02 )ns
• 98%는 TLB 접근시간 20ns와 page주소의 메모리에 접근하는 100ns
  2%는 TLB 접근 시간 20ns + 4단계 테이블이므로 4번의 메모리 접근 + page 주소의 메모리 접근 100ns가 소요된다.
• 결과적으로 117.6 + 10.4 = 128ns가 소요된다.

Page Table이 갖는 추가적인 bit

Valid / Invalid Bit

 

multi page table구조에서 비어있는 page에 대해서는 page table이 page 주소(page table을 가지는)를 가지지 않고 널을 넣어놓는다고 했는데, page table에 접근했을 때, 널값이 0일 때, 0이 주소인지 널인지 구분할 수가 없다.
따라서 page table은 대응되는 page 주소와, 해당 값의 유효 여부를 나타내는 valid - invalid bit를 같이 갖게 된다

 

Protection Bit

• page에 대한 접근(연산) 권한을 나타낸다. ( read / write / read-only )
• page는 Code, Data, Stack, Heap 등 다양한 부분의 내용을 갖고있게 되는데 변경되도 되는 값이 있고 그렇지 않은 값들이 존재한다

Paging : Inverted Page table

page table의 문제는 각 프로세스 별로 address space가 허용하는 범위까지 page table entry가 만들어져야 한다는 점이다. 따라서 공간적 부담이 존재하게 된다.

 

이를 해결하고자 page table을 단 하나만 두게 하고, Page table을 physical memory관점에서 채우게 한다. page table의 entry들은 physical memory의 frame들이 어느 프로세스의 page에 해당하는지에 대한 정보를 갖게된다.

즉, 기존 Hierarchy 구조의 page table에서는 논리주소를 통해 물리주소로 접근하였지만, Inverted 구조에서는 물리 메모리에 접근하면 맞는 프로세스의 논리적 주소를 알려주게된다.

 

연산을 위해 논리주소를 줄 때 프로세스 id인 PID, Page 번호, page 내 offset을 전달한다. 이를 통해 page table에서 해당하는 pid - page number 쌍을 찾는다. 이때 완전탐색을 하여 찾게되므로 시간상 소모가 있다. (TLB 사용으로 커버가능)

찾은 page entry로 physical memory를 접근하면 해당하는 프로세스의 논리적 page 주소를 구할 수 있게된다.

• 논리적 주소를 찾기위해 page table 전체를 탐색해야하는 단점이 존재하며, 이를 위해 associative register를 사용해야한다.
  (병렬처리를 위해, 단점은 가격이 비싸다)

Paging : Shared Page

동일한 프로그램에 대해서 여러개의 프로세스가 돌아갈 때, code 부분은 동일할 것이므로 동일한 부분은 따로 메모리에 적재하지 않고 공유하게 하는 것.

• Re-entrant Code (pure code, 재진입 가능 코드)
• read - only로 해서 프로세스간에 하나의 Code만 메모리에 올리게 한다. 공유부분으로 수정이 일어나면 안되므로
• Shared code는 모든 프로세스의 Logical Address Space에서 동일한 위치에 있어야한다.
• 즉, Code를 공유하는 프로세스 끼리는 논리적 주소 값이 동일해야한다. 그래야 Compile시 갖고있는 Logical Address가 유효하게 사용될수 있다.

---

Segmentation

프로그램은 의미 단위인 여러개의 segment로 구성되어 있다.

• 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의.
• 크게는 프로그램 전체를 하나의 세그먼트로 정의.
• 일반적으로 Code / Data / Heap / Stack 부분이 하나씩 세그먼트로 정의된다.
• Segment는 다음과 같은 Local Unit들이다.
  -> main(), function, global variables, stack, symbol table, arrays

Segmentation Architecture

Logical Address는 다음 두가지로 구성된다.

• < Segment-Number , Offset >

Segment Table

• 각 세그먼트 별로 물리적인 메모리에 올라갈 수 있으므로 세그먼트 table을 통해 주소변환을 한다.
• table-entry는 Base & Limit을 가진다.
  • Base : Starting physical address of the segment (물리적 메모리에서 세그먼트의 시작 주소)
  • Limit: Length of the Segment (의미 단위이므로 세그먼트 크기가 제각각이다.)

 

Segment Table이 사용하는 두가지 Register

Segment-Table Base Register (STBR)

• 물리적 메모리에서의 Segment table의 위치

Segment-Table Length Register (STLR)

• 한 프로그램이 사용하는 Segment의 수를 나타낸다.
• Segment-Number는 STLR보다 항상 작아야한다.

 

구조

Logical Address → S와 D로 이뤄져있다 (segment number, offset)

• Segment Table에서 (STBR에서) S번째 segment에 접근, segment의 Limit, Base를 구한다.
• S의 번호가 STLR의 크기보다 작다면 Segment Table의 S위치에 접근한다. (벗어나면 trap) 잘 접근했다면 Base를 가지고 세그먼트의 시작 주소로 간다.
• D의 크기가 세그먼트의 길이인 Limit보다 작다면 Base에서 D위치를 접근한다 (벗어나면 trap)

즉, Segment의 번호가 세그먼트 테이블 길이보다 작아야되고, Segment의 Offset은 세그먼트의 길이보다 작아야한다.

 

장점 / 단점

Protection

• 각 세그먼트 별로 protection bit가 있다.
• 각 Entry → Valid bit & Read , Write, Execution 권한 bit
• page단위로 일률적으로 자른 것보다 의미단위로 잘랐으므로 protection bit를 주는것이 더 자연스럽다.
• page단위의 경우 code의 bit와 stack의 bit가 한 page에 존재할 수 있으므로 권한 설정을 위해 따로 찢어야된다.

Sharing

• segment 방식이 공유부분을 공유하기에 더 유리하다.
• 같은 의미 (Code) 등을 공유할 때 더 편하게 할 수 있다.
• 하나의 프로그램에 대해 여러 프로세스가 돌아갈 때, 같은 의미를 같는 세그먼트를 공유하는 것이 paging보다 효과적이다.

Allocation

first fit, best fit을 이용해서 메모리 공간에 적재하는데, segment 크기는 제각각이므로 외부 단편화(External fragmentation)문제가 발생할 수 밖에 없다.

• 가변 분할 방식과 동일한 문제점이 발생하게된다.

Paging vs. Segement

paging기법은 page가 백만개씩 생기게 되지만, segment기법은 의미단위로 나누므로 5개정도 밖에 생기지 않아서 결국 테이블을 만들기 위한 메모리 낭비는 paging이 더 심하다.

단편화 문제는 Segment가 더 심하다.

Protection을 줄때는 의미단위로 나뉘어져 있는 세그멘테이션이 유리하다.

---

Paged Segmentation

각 segment를 page 단위로 구성하는 기법 → Hole문제를 해결할 수 있다.

Segmentation기법과의 차이점

segment table entry가 갖는 Base는 Segment에 대한 것이 아니라, 해당 Segment를 구성하는 Page Table의 시작 주소 S가 되어 Base Address를 갖는다. Limit은 그대로 Segment Length로 접근할 수 있는 최대 주소로 사용된다.

즉, 기존에는 segment의 시작주소를 Segment Table에서 바로 구해서 메모리에 접근했는데 그러지 않고, 해당 세그먼트에 해당하는 Page Table의 시작주소를 알려주게 된다.

그러면 Page table을 통해 page 주소를 구해서 메모리에 접근하게 되므로 메모리에서 External Fragmentation 문제가 발생하지 않게 된다. (메모리도 frame 단위로 되어있으므로)

 

정리

논리주소에서 S 값으로 세그먼트 테이블에 접근한다. 테이블에서 세그먼트의 길이 & 세그먼트 페이지 테이블의 시작 주소 Base를 얻는다.

Base는 해당 세그먼트의 페이지 테이블 시작주소로 사용된다. 페이지 테이블에 접근해서 논리주소 D의 앞 부분을 이용해서 Page에 접근한다. 해당 Page에서 물리 메모리 상 Page 시작주소를 얻는다. 물리 메모리에 위치하는 Page 시작주소에 D의 뒷 부분을 위용해서 원하는 위치에 접근한다.

 

Trap발생

S, D에 대해서 S를 통해 세그먼트 테이블에서 Base와 segment length를 구하고, 세그먼트 길이보다 D(segment내 offset)이 더 크면 trap을 발생시킨다.

그렇지 않다면

1. D를 ( Page번호 )와 ( Page 내 Offset ) 으로 나누고
2. Segment Table에서 구한 Page Table Base Address에 Page 번호로 접근한다. 거기서 원하는 물리 메모리 Page 주소를 얻는다.
3. 구한 Page 시작주소 + Page 내 Offset을 이용해서 물리 메모리에 접근한다.

참고
Logical Address를 통해 Physical Address를 구해서 메모리에 접근하는 주소변환 과정에서 OS의 역활은 없고 순전히 하드웨어 (MMU)의 역활만 있었다. OS는 메모리접근이 아니라, I/O에 접근할 때만 역활을 하게된다.

---

문제풀기

2^10 : 1Kb / 2^20 : 1Mb / 2^30 : 1Gb

Q. Page Size가 4Kb이고 메모리 크기가 256Kb인 메모리 Paging System일 때

Page Frame의 개수는?

→ page의 크기가 4Kb이고 Frame 또한 동일한 크기인 4Kbyte를 가지므로, 총 frame의 수는 2^18 / 2^12 = 2^6 인 64개이다.

 

이 메모리 주소를 해결하는데 필요한 비트 수는?

→ page를 총 64개 가질 수 있으므로 page 구별을 위해 6개의 비트가 필요하고, page내에서 byte를 구분하기 위해 12개의 bit가 필요하므로 총 18bit가 필요하다.

즉, 메모리 크기가 2^18 byte이므로 18bit가 필요한 것과 동일하다.

 

페이지 번호에 사용되는 비트와 page offset에 사용하는 비트는?

→ page를 가질 수 있는 개수가 2^6개이므로 6bit, page의 크기가 2^12byte이므로 12bit가 필요하다.

Q. 16bit 논리 주소를 이용하여 4Kb 크기의 페이지를 갖는 시스템 메모리가 있다고 가정해보자 (이때, 논리주소가 8196이라면 어떻게 될지도 생각해보자)

→ 2^12byte 크기의 페이지를 가지므로 12bit는 페이지 내 offset으로 사용된다. 그러므로 나머지 4bit로 page를 구별하는데 사용할 수 있으므로 2^4개의 page를 가질 수 있다.

이때, 논리주소가 8196이라면 bit로 0010 0000 0000 0100이므로, 0010은 page Number, 0000 0000 0100은 Page 내 Offset으로 사용된다.

그림과 같은 페이지 테이블을 사용하고 있다면 page Number Bit 0010은 페이지 테이블 2번에 접근하고, 110의 page 주소를 구하게 된다.
page 내 offset "0000 0000 0100"은 그대로 사용되어서 110 + 0000 0000 0100 의 물리적 메모리 내 page의 offset으로 변환되고, 총 15bit로 물리적 메모리의 크기가 2^15byte, 32Kb임을 알 수 있게된다.

Q. 32bit 시스템에서 page size가 4Kb일 때, 4Gb 메모리에 접근하기 위해 필요한 page table의 크기는? (page entry크기는 4byte)

→ page offset으로 2^12개가 필요하므로 나머지 2^20bit를 통해 page를 구별할 수 있다. 따라서 2^20개의 page entry가 필요하고, page entry 크기는 2^2byte이므로 2^20 * 2^2 Byte = 2^22, 4Mb를 갖게 된다.