🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟

🗳️ Memory Management 2

1. Noncontiguous allocation(불연속할당)

불연속할당(noncontiguous allocation) 기법이란 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말한다. 불연속할당 방식에는 하나의 프로그램을 분할하는 기준에 따라 동일한 크기로 나누어 메모리에 올리는 페이징 기법과, 크기는 일정하지 않지만 의미 단위(코드, 데이터, 스택 영역)로 나누어 메모리에 올리는 세그멘테이션 기법, 그리고 세그먼테이션을 기본으로 하되 이를 다시 동일 크기의 페이지로 나누어 메모리에 올리는 페이지드 세그먼테이션 기법 등이 있다.

1.1 Paging

페이징 기법은 프로세스의 가상 메모리를 동일한 크기의 Page로 잘라서 각 Page 별로 비어있는 물리적 메모리에 저장하는 방식을 말한다. 페이징 기법에서는 각 프로세스의 주소 공간 전체를 물리적 메모리에 한번에 올릴 필요없이 일부는 백킹스토어, 일부는 물리적 메모리에 혼재 시키는 것이 가능하다.
페이징 기법에서는 물리적 메모리를 페이지 크기와 동일한 프레임으로 나누어두기 때문에 앞서 설명한 동적 메모리 할당 문제가 발생하지 않는다. 비어있는 공간이 모두 동일한 크기여서 어떠한 위치에도 저장할 수 있기 때문이다. 하지만 이러한 특징은 복잡한 주소변환 절차를 필요로 한다.

✔️ 하나의 Page의 크기는 4KB

✔️ Paging 기법을 사용할 경우 해당 page의 **page table 주소와 논리적 주소를 물리적 메모리의 주소로 변환한다.

1️⃣ Paging 기법의 주소변환 절차는 어떻게 이뤄지나?

페이징 기법은 주소 변환이 페이지 단위로 이뤄져야 하기 때문에 조금 더 복잡한 주소변환 절차가 필요하다. 따라서 페이징 기법에서는 각각의 주소 변환을 위한 페이지 테이블을 가진다. 페이지 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가지고 있으며, 엔트리는 페이지 번호와 페이지 오프셋으로 이루어져 있다. 추가로 페이지 테이블은 프로세스의 페이지 수 만큼 엔트리가 생성되기 때문에 큰 용량이 필요하여 메인 메모리에 저장된다.

1.2 Page Table

페이지 테이블이란 Page의 물리적 메모리 주소 변환을 하기 위한 자료구조이다. 페이지 갯수만큼 엔트리가 생성되기 때문에 많은 용량을 필요로 하여 메인 메모리에 저장된다. CPU가 물리적 주소에 접근하려면 Page table을 거쳐서 Page Frame 까지 도달해야 하는데, 둘 다 메인 메모리에 저장되어 있기 때문에 메모리에 두 번 접근하게 되는 오버헤드가 발생한다. Page table의 문제점을 해결하기 위한 방법을 알아보자

✔️ Page Table의 구성

Page-table base register (PTBR)

✔️ 페이지 테이블만 있었을 때, 물리적 메모리 주소에 닿기까지 2번의 메모리 접근이 필요하다. 첫번째 접근은 CPU → Page Table 접근 두번째 접근은 Page Table → Page frame 접근이다.

Page-table base register (PTBR)가 page table을 가리킴
- 메모리에 상주하고있는 page table의 시작위치
Page-table length register (PTLR)가 테이블 크기를 보관
모든 메모리 접근 연산에는 2번의 memory acess 필요
- page table 접근 1번, 실제 data/instruction 접근 1번
translation look-aside buffer (associative register or TLB)
- 속도 향상을 위해 사용되는 고속 lookup hardwore cache
- 메모리 접근 연산이 2번 이뤄지는 비효율적인 접근방식을 보완함
- page table에서 접근이 자주 이뤄지는 엔트리를 캐싱하고 있음
- CPU가 캐싱되어있는 페이지 주소를 찾을 경우 CPU → TLB → Physical Memory
- TLB에 존재하지 않을 경우 CPU → Page table(Physical Memory) → Physical Memory
- 물리적 페이지와 논리적 페이지 주소의 쌍으로 이뤄져있음

Associative registers(TLB) : 병렬 검색이 가능

TLB에는 page table 중 일부만 존재

Address translaction

page table 중 일부가 associative register에 보관되어 있음
만약 해당 page가 associative register에 있는 경우 곧바로 frame #을 얻음
그렇지 않은 경우 main memory에 있는 page table로 부터 frame #을 얻음
TLB는 context switch 때 flush (remove old entries)

1.3 Two-Level Page Table

속도는 느려지더라도 페이지 테이블의 크기를 줄이기 위한 방법이다.
이단계 테이블에서는 page table 자체를 page로 구성한다.
page table 자체를 page로 구성
사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 null (대응하는 inner page table이 없음)
- 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원 (최근에는 64bit 구성도 많음)
  - 32 bit address 사용 시: 2의 32승의 주소 공간이 필요하다 (4GB)
    - page size가 4K 시 1M개의 page table entry 필요
    - 각 page entry가 4B시 프로세스당 4M의 page table 필요
    - 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다

🌟 이단계 페이지 테이블 예시

✔️ Logical Address (on 32-bit machine with $K page size)의 구성

20 bit의 page number
12 bit의 page offset

✔️ Page table 자체가 page로 구성되기 때문에 page Number는 다음과 같이 나뉜다

(각 page table entry가 4B)

10 - bit의 page number

10 - bit의 page offset

따라서, logical address는 다음과 같다

스크린샷 2022-04-07 오후 9 55 33

P1은 outer page table의 index이고

P2는 outer page table의 page에서의 변의(displacement)

✔️ 2단계 페이징에서의 Address-translation scheme

논리적 주소에서 outer table 의 index 번호를 찾는다.
outer table에서 P1값에 위치로 이동한 후 inner page table 엔트리의 위치 값을 가져온다.
outertable에서 inner page table로 이동한다.
inner table에서 P2값에 해당하는 엔트리로 이동한 후 저장된 물리적 페이지 프레임 주소를 얻게된다.

inner table의 크기는 4KB로 페이지의 크기와 동일하다.

이단계 테이블은 속도는 느리더라도 페이지 테이블의 공간을 줄이는 것이 목적인 반면에

여전히 inner table의 엔트리는 100만개 이상이 필요하다. 추가적으로 outer table 과 inner table로 구성되어 있어서 공간과 시간이 기존 page table에 비해서 더 손해이다.

하지만 그럼에도 이단계 테이블을 사용하는 이유는 ?!

프로그램을 구성하는 공간에서 사용되는 페이지의 수는 얼마 안되지만 페이지 테이블은 실제 사용하는 페이지의 수가 적더라도 논리적 메모리의 최대 크기만큼 엔트리를 생성한다. 그런데 이단계 페이지 테이블은 outer page table은 논리적 메모리 크기만큼 생성하지만 실제 사용이 되지않는 엔트리는 Null로 할당하고 inner table의 엔트리를 생성하지 않는다.

실제 프로그램은 프로그램이 사용되지 않더라도 4KB의 메모리 공간을 전부 채운다.

1.4 Multilevel Paging and Performance

주소공간이 더 커지면 다단계 페이지 테이블이 필요하다 다단계 테이블은 단계별로 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다 하지만 이러한 문제점은 TLB를 통하여 접근시간을 줄일 수 있다.

✔️ 4단계 페이지 테이블을 사용하는 경우

메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
TLB hit ratio가 98%인 경우
- effective memory access time = 0.98 x 120 + 0.02 x 520 = 128 nanoseconds
  - 결과적으로 주소변환을 위해 28ns만 소요한다.

1️⃣ Memory Protection

Page table의 각 entry 마다 아래의 bit를 둔다.

✔️ Protection bit

Page에 대한 접근 권한 (read/write/read-only)
1. 페이지 테이블은 프로세스 마다 각각 생성되므로 다른 프로세스가 Page에 접근하는 것을 막기위한 것이 아니라 연산에 대한 접근 권한을 의미한다
2. 예를 들면 코드영역은 실행도중 변경되면 안되므로 read-only 권한을 부여하고 데이터나 스택영역에는 read, write 권한을 부여한다.

✔️ Valid (v) / Invalid (i) Bit in a Page Table

valid-invalid bit
- Valid (v)
  - Page 0을 예로 들면 Page 0이 실제로 2의 주소를 가진 Page frame에 할당된 것을 의미함 (실제로 페이지가 물리적 메모리에 존재한다)
- Invalid (i)
  - 해당 주소의 frame에 유효한 내용이 없을을 의미한다 (접근 불허)
    1. 프로세스가 그 주소 부분을 사용하지 않는 경우
    2. 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

257F2E3C5757C75D31 (1)

1.4 Inverted Page Table (역방향 페이지 테이블)

Page table은 실행되는 프로세스마다 독립적으로 생성되기 때문에 메모리를 많이 차지한다. 하지만 Inverted Page Table은 기존 Page table과 다르게 모든 프로세스가 Inverted Page Table을 참조하게 하는 방식이다. Inverted Page Table은 Page Frame 기준으로 엔트리를 생성한다.

💡 Page table이 매우 큰 이유

모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재

✔️ Inverted page table (역방향 페이지 테이블)

Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
메모리 공간을 확보하기 위해 사용 됨
역방향 페이지 테이블의 엔트리는 논리적인 페이지 번호와 Pid를 저장하고 있음
단점
- 테이블 전체를 탐색해야 함
조치
- associative register 사용 (expensive)

✔️ 주소변환과정

Page Table에서 pid와 page number로 해당 정보가 저장된 엔트리의 위치를 찾는다
찾아진 엔트리가 몇번째 위치에 존재하는지 확인하고 해당 주소의 페이지 프레임을 찾는다.
각 page tavle entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)

1.5 Shard Page

✔️ Shared code

Re-entrant Code (=Pure code)
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (eg, text, editors, compliers, winodw, systems)
Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함 (동일한 page number를 가져야함)
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무 위치에 할당되어도 무방

✔️ 예를 들면?

서로 다른 프로세스 P1, P2, P3가 동일한 코드를 사용하다면 코드를 프로세스마다 각각 올리는 것은 비효율 적이다. 즉 공유할 수 있는 코드는 별도로 올리는 것이 아니라 같은 Frame으로 매핑하여 한칸의 Page Frame 만을 할당하는 것이 효율적이라고 할 수 있다. 하지만 모든 프로세스가 같은 코드영역을 참조하고 있기 때문에 공유하는 코드영역은 read-only로 설정해야한다. 그리고 공유코드는 프로세스가 다르더라도 동일한 logical address를 가져야한다.

2. Segmentation

프로그램은 의미 단위인 여러 개의 segment로 구성
작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
일반적으로는 code,data,stack 부분이 하나씩의 세그먼트로 정의됨
Paging 방식처럼 동일한 크기로 분할하는 것이 아니라 동적 메모리 할당 문제가 발생할 수 있다.

✔️ Segment는 다음과 같은 logical unit 들

main()
function
global variables
stack
symbol table, arrays

2.1 Segmentation Architecture

✔️ Logical address 구성

segment-number, offset

✔️ Segment table

each table entry has:
- base - starting physical address of the segment
- limit - length of ther segment

✔️ Segment-table base register (STBR)

물리적 메모리에서의 segment table의 위치

✔️ Segment-table length register (STLR)

프로그램이 사용하는 segment의 수
- segment number의 크기는 STLR의 범위를 넘어서면 안됨

✔️ Segmentation의 주소변환

논리주소의 SegmentNumber가 STLR보다 작은 값인지 확인하고 만약 더 큰 값을 요청했다면 trap을 발생시킨다.
값이 STLR 범위에 포함될 경우 offset의 값이 segment의 메모리 범위안에 포함되는 지 확인한다
포함되는 값이면 Segment 시작위치와 Offset을 더해, 물리적 메모리 주소의 위치를 찾는다.

✔️ Sharing of Segments

첨부된 이미지를 보면 segment0은 프로세스 P1, P2가 서로 공유하여 사용하고 있다. 하나의 세그먼트를 여러개의 프로세스가 사용할 경우 각 프로세스들은 segment0에 대해 동일한 논리적메모리 주소를 가져야한다. 반면 각 프로세스마다 따로 사용하는 private segment의 경우 각자 다른 물리적 메모리 주소에 위치해있기 때문에 프로세스마다 논리적 메모리 주소도 동일하지 않아도 된다.

2.3 Paged Segmentation

Paged Segmentation은 Segmentation과 Paging 기법의 장점만을 가져와서 각 기법의 단점들을 보완한 방식이다.
무슨 말이냐 하면, Segmentation의 의미있는 단위로 프로그램을 나누는 방식과 Paging 기법의 동일한 크기로 프로그램을 나눈다는 장점이 합쳐진 것이다.
Paged Segmentation기법에서는 segment가 임의의 길이를 가진 것이 아닌 동일한 크기의 page들의 집합으로 구성되어 있다. 물리적 메모리에 적재하는 단위도 page 단위이기 때문에 외부조각 문제가 발생하지 않는다. 기존 Segmentation 방식과의 차이점은 segment table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있다는 것이다.

✔️ Paged Segmentation

Paged Segmentation 기법에선 주소 변환을 위해 외부의 세그먼트 테이블과 내부의 세그먼트 테이블을 이용한다.
하나의 세그먼트가 여러개의 페이지 테이블로 구성되기 때문에 각 세그먼트마다 페이지 테이블을 가진다.

✔️ Paged Segmentation의 주소변환 과정

논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목으로 접근한다. (논리적 주소에서는 세그먼트 번호와 offset이 존재)
1. 접근한 세그먼트 항목에는 세그먼트 길이와 그 세그먼트의 페이지 테이블 시작 주소가 들어 있다.
세그먼트 길이값과 논리적 주소 하위 비트인 offset 값을 비교하고 offset값이 더 크다면 유효하지 않은 접근이므로 트랩을 발생시킨다.
그렇지 않은 경우 offset 값을 다시 상위 비트와 하위비트로 나눈다. (상위 비트는 세그먼트 내의 페이지 번호로 사용하고 하위 비트는 페이지 내의 변위로 사용한다)
세그먼트 테이블에 저장된 해당 세그먼트를 위한 페이지 테이블의 시작 위치를 확인했으므로 그 위치에서 페이지 번호만큼 떨어진 페이지 테이블 항목으로부터 물리적 메모리의 페이지 프레임 위치를 얻게 된다.
해당 페이지 프레임 위치에서 offset의 하위 비트값인 페이지 내 변위만큼 떨어진 곳이 물리적 메모리 주소이다.

💡 Memory Management에서 운영체제의 역할은?

없다. 앞서 설명한 내용들은 운영체제가 아닌 하드웨어들의 역할이다. 왜냐하면 프로세스가 CPU를 할방받으면서 메모리에 접근하는 것은 운영체제가 도움을 주는 것이 아니기 때문이다. 만약 메모리에 접근할 때 사용자 프로그램이 운영체제를 필요로하게 된다면, 사용자 프로그램이 메모리에 접근을 시도할 때마다 사용자 모드에서 커널모드로 변경되는 매우 비효율적인 작업이 진행될 것이다. 사용자 프로그램이 운영체제의 도움이 필요할 때는 메모리 접근이 아닌 I/O device 접근이다.

Reference

이화여자대학교 반효경 교수님 운영체제 강의

[운영체제 스터디] 불연속할당