# 메모리 불연속 할당 (Paging, Segmentation)

## 불연속 할당(Noncontiguous Allocation)

프로그램의 주소 공간을 작게 쪼개어 사용자 프로세스 영역의 여러 부분에 분산하여 할당하는 방식

* 하나의 프로세스가 메모리의 여러 영역에 분산되어 적재된다.
* `Paging`, `Segmentation`, `Paged Segmentation`이 있다.

\
\


## Paging 기법

프로그램의 가상 주소 공간을 `page`라는 단위로 쪼개는 기법

* page단위로 프로그램의 일부를 메모리에 적재하거나(swap in), backing store에 swap out한다.
* 프로그램에 할당된 물리 메모리를 page와 동일한 크기의 `page frame` 단위로 쪼갠다
* 운영체제는 메모리를 효율적으로 사용하기 위해 empty page frame을 관리한다
* `Page Table`을 통해 page 단위의 주소변환이 이뤄진다

> 장단점

* 장점 : 외부 조각이 발생하지 않기 때문에 `Dynamic Storage-Allocation Problem` 문제가 없다
* 단점 : page단위로 쪼개다보면 마지막 조각이 page 크기보다 작을 수 있기 때문에 `내부 조각이 발생`할 수 있다

### 📌 `Paging 기법의 주소 변환`

![](https://826718011-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxzBwrJtOrGh4cRsnXzQX%2Fuploads%2Fgit-blob-cdf766d1113cf1fdfc8ffa7898d9514d18e02f1a%2FUntitled.png?alt=media)

논리적 주소를 `페이지 번호(p)`, `페이지 오프셋(d)` 으로 구성한다

* `pageTable[페이지 번호(p)]` = 프로세스의 p번째 페이지가 존재하는 메모리의 시작 위치 `(f)`
* `f(시작점) + d(변위)` = CPU가 접근한 논리적 주소에 대응되는 물리적 주소

> Page Table

![](https://826718011-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxzBwrJtOrGh4cRsnXzQX%2Fuploads%2Fgit-blob-8ae53cf8c7e9116301019c4981ea28149d93756b%2FUntitled%201.png?alt=media)

그리고 page table을 통해 물리적 주소로 주소 변환이 이뤄진다.

* page table은 페이징 기법에서 주소 변환에 사용되는 자료구조이다
* page table는 프로세스의 page 개수만큼의 entry를 가진다
* 각 entry에는 `해당 page가 적재된 page frame 번호`가 들어있다
* page table은 메인 메모리에 저장된다.

> MMU → PTBR, PTLR

CPU는 특정 프로세스의 page table에 접근하기 위해서 `MMU`의 2개의 레지스터(PTBR, PTLR)에 접근한다.

* `PTBR(Page Table Base Register)` = 메모리에 존재하는 특정 프로세스의 page table 시작 주소 (base register)
* `PTLR(Page Table Limit Register)` = 특정 프로세스의 크기 (limit register)

> TLB(Translation Look-aside Buffer)

![](https://user-images.githubusercontent.com/44316546/163661390-c1ee0b73-fce3-4d90-9140-f3ce3b079330.png)

`MMU` 로 주소 변환을 하면 2번의 Memory Access가 필요하기 때문에 오버헤드가 크다. 따라서 속도 향상을 위해 `TLB`라는 고속 캐시를 사용한다.

* TLB에 빈번히 참조되는 페이지에 대한 주소 변환 정보(`page 번호`-`page frame 번호` 쌍의 데이터)가 저장된다.
* TLB에서 특정 페이지에 정보를 찾기 위해 full scan이 필요하다 → 병렬 탐색이 가능한 associative register를 사용한다.
* page table과 마찬가지로 프로세스마다 독립된 TLB 정보를 가진다. (context switch가 일어나면 TLB에 저장된 정보가 모두 지워진다)

> 페이징 기법에서 주소 변환 과정

1. CPU가 “`페이지 번호(p)`-`페이지 오프셋(d)`"으로 구성된 논리적 주소에 접근
2. MMU(PTBR, PTLR)를 통해 page table에 접근
3. pageTable\[page number(p)] = “`page frame number(f : 페이지 프레임의 시작 위치)`” 정보 참조
4. offset(d)과 f를 통해 실제 물리 메모리에 접근

### 📌 `계층적 페이징`

현대의 컴퓨터는 많은 주소 공간을 요구하는 프로그램을 지원한다. 그에 따라 page table의 entry수도 많아져 page table의 크기가 커지게 되었지만 대부분 프로그램은 일부만 사용되기 때문에 page table의 공간 낭비가 심하다.

→ `계층적 페이징` 기법을 사용하여 page table로 인한 공간 낭비를 줄일 수 있다.

> 2단계 페이징 기법

![](https://826718011-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxzBwrJtOrGh4cRsnXzQX%2Fuploads%2Fgit-blob-fe3b8c57dc0eba52776bc6f6d5bb3a4d26d02c60%2FUntitled%202.png?alt=media)

주소 변환을 위해 `외부 페이지 테이블`과 `내부 페이지 테이블`의 두 단계에 걸친 페이지 테이블을 사용한다.

* 사용하지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하며, 여기에 대응하는 내부 페이지 테이블을 생성하지 않는다.
* 페이지 테이블을 위해 사용되는 메모리 공간을 줄이지만, 페이지 테이블의 수가 증가하므로 시간적인 손해가 뒤따른다.

> 계층적 페이징 기법의 단점

page table을 위해 사용되는 메모리 공간 소모를 줄일 수 있지만 **메모리 접근 시간이 늘어난다**

### 📌 `역 페이징`

모든 프로세스의 모든 페이지에 대한 페이지 테이블 항목을 구성해야 하기 때문에 page table로 인한 공간 낭비가 심하다

→ `역페이지 기법`을 사용하여 page table로 인한 공간 낭비를 줄일 수 있다.

![](https://826718011-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxzBwrJtOrGh4cRsnXzQX%2Fuploads%2Fgit-blob-2152deed6c1ffbdd72a186de037353e38a09da7c%2FUntitled%203.png?alt=media)

프로세스마다 page table을 생성하는게 아니라, 물리적 메모리에 대한 page table을 생성한다.

* 시스템 전체에 하나의 page table만 생성한다.
* page table의 entry 개수는 page frame의 개수이다.
* entry에는 “`프로세스 번호(pid)` - `프로세스의 논리적 페이지 번호(p)`”가 담긴다.
* 논리적 주소를 `pid`, `page 번호`, `offset` 으로 구성한다

> 역 페이징 기법의 단점

주소 변환을 위해 page table 전체를 탐색해야 한다. (속도를 높이기 위해 associative register를 사용하여 병렬 탐색을 수행한다.)

\
\


## Segmentation 기법

프로그램의 가상 주소 공간을 `segment`라는 **의미 단위**로 쪼개는 기법

* 프로그램의 `code, data, stack`을 `code segment, data segment, stack segment`로 쪼개어 메모리에 적재한다.
* 작게는 프로그램을 구성하는 함수 하나씩 segment로 정의하고, 크게는 프로그램 전체를 하나의 segment로 정의한다.
* segment는 main 함수, function, global variables, stack, symbol table, arrays가 될 수 있다

> 장단점

* 장점 : 의미 단위로 주소 공간에 대한 접근을 제어하기 때문에 `공유, 보안 측면에서 페이징 기법보다 효과적이다`
  * 프로세스끼리 동일한 코드(text segment)를 공유하기 용이하다
  * memory section들 마다 서로 다른 read, write 권한을 설정할 수 있다
* 단점 : segment 길이가 각기 다르므로 `외부 조각 문제가 발생한다.`

### 📌 `Segmentation 기법의 주소 변환`

![](https://826718011-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxzBwrJtOrGh4cRsnXzQX%2Fuploads%2Fgit-blob-3cf27afc1c1056ff80aa71fb5f5e5dd12ec34e7c%2FUntitled%204.png?alt=media)

논리적 주소를 `segment number(s)`, `offset(d)`로 구성한다.

* `segment number(s)` = 프로세스 주소 공간 내에서 몇 번째 segment에 속하는지 나타낸다
* `offset(d)` = 해당 segment의 시작 주소에서 얼마만큼 떨어져 있는지 나타낸다

> Segment Table

주소 변환에 segment table을 활용한다. segment entry에 “`base`- `limit`”정보가 담긴다.

* `base` = 물리 메모리에서 해당 segment의 시작 주소
* `limit` = 해당 segment의 크기 (segment마다 크기가 다르기 때문에 필요하다)

> MMU → STBR, STLR

CPU는 특정 프로세스의 segment table에 접근하기 위해서 `MMU`의 2개의 레지스터(STBR, STLR)에 접근한다.

* `STBR(Segment Table Base Register)` = 메모리에 존재하는 특정 프로세스의 segment table 시작 주소 (base register)
* `STLR(Segment Table Length Register)` = 특정 프로세스를 구성하는 segment의 개수 (limit register)

> 주소 변환시 점검사항

1. CPU가 접근한 논리 주소의 segment number (s)가 STLR보다 작은 값인지 확인
2. 논리 주소의 offset(d)이 해당 segment의 limit보다 작은 값인지 확인

### 📌 `Segmentation 보호 기법`

* `각 segment 마다 protection bit를 둔다`
  * 이를 통해 해당 segment에 대한 읽기/쓰기/실행에 대한 제한을 설정할 수 있다.
* `각 segment 마다 valid bit를 둔다`
  * 해당 세그먼트가 현재 물리적 메모리에 적재되어 있는 지를 나타낸다. (paging도 마찬가지)

### 📌 `Segmentation 공유 기법`

여러 프로세스가 특정 segment를 공유하여 사용하는 개념이다.

* 공유되는 segment는 프로세스의 주소 공간에서 동일한 논리적 주소를 가져야 한다. (= 공유 segment는 각 프로세스에서 동일한 segment number를 가져야 한다)

### 📌 `Paging과 Segmentation 차이`

| Paging                                                                           | Segmentation                                                         |
| -------------------------------------------------------------------------------- | -------------------------------------------------------------------- |
| page table                                                                       | segment table                                                        |
| page의 크기가 균일하기 때문에 offset의 크기가 page 크기에 의해 결정된다.                                 | segment의 길이는 offset이 표현가능한 범위내에서 서로 다른 값을 가질 수 있다.                   |
| page table에서 page의 시작 주소 대신 page frame 번호로 주어진다. (page frame도 같은 크기로 나누어져 있기 때문) | segment table에서는 segment의 크기가 각기 다르기 때문에 segment의 시작 주소(base)가 주어진다. |

\
\


## Paged Segmentation

프로그램의 주소 공간을 segment로 나누되, 각 segment마다 page로 나누는 기법

* 세그먼트의 크기를 page 크기의 배수가 되도록 한다 →`segmentation의 외부 조각 문제를 해결`
* segment 단위로 접근 제어를 하여 보호한다 → `paging 기법의 보안 약점 해소`

### 📌 `Paged Segmentation 기법의 주소 변환`

![](https://user-images.githubusercontent.com/44316546/163666763-f6e8de0b-033b-437c-bdbe-6c8a34ec7388.png)

외부의 `segment table`, 내부의 `page table`을 통해 주소 변환이 이뤄진다

* segment table의 entry에는 “`segment length` -`page table base(내부 페이지 테이블 시작 주소)`" 정보가 들어있다.

1. CPU가 “`segment number(s)`-`offset(d)`"으로 구성된 논리적 주소에 접근
2. MMU(STBR, STLR)를 통해 segment table에 접근
3. segmentTable\[segment number] = “`segment length`- `page table base`” 정보 참조
4. page table base로 segment 내의 page table에 접근
5. offset(d) 는 segment 내의 page number(p)와 해당 page 에서의 변위(d’)로 이루어져있다. → p와 d’를 통해 실제 물리 메모리에 접근

> 장단점

* 장점 : segmentation의 장점(보호, 공유)과 paging의 장점(외부 조각 해결)을 가진다. → 운영체제에서 사용되고 있다.
* 단점 : 필요한 테이블(segment table, page table)이 많고, 실제 메모리 주소까지 접근 시간이 늘어난다
