[OS]Memory Management(Paging, Segmentation)

이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.

지난 챕터에 이어 Memory Management에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다

---

Paging

• Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
• Virtual memory의 내용이 page 단위로 noncontiguous(여러 영역에 분산 되어)하게 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장

| Basic Method

• physical memory를 동일한 크기의 frame으로 나눔
• logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
• 모든 가용 frame들을 관리
• page table을 사용해서 logical address를 physical address로 변환
• External fragmentation 발생 안함, Internal fragmentation 발생 가능

| Address Translation Architecture

• 페이지 번호를 프레임 번호로 바꿔주면 되는 것
• 내부에서의 상대적인 위치는 같기 때문에 offset은(상대 주소) 변화가 없고, 앞의 page번호만 변하게 된다

| Page table

• 주소 변환을 위해서는 page table이 사용된다
• 논리적 메모리가 물리적 메모리 어디에 올라가 있는가를 나타낸다
• 물리 메모리에서 올라갈 수 있는 부분을 page frame이라고 한다
• 그래서 논리 메모리 크기 만큼의 페이지 테미블 엔트리가 존재하게 된다
• 각 엔트리에는 몇번에 올라가 있는지 알려주게 된다

| Implementation of Page Table

• Page Table은 main memory에 상주
• Page-table base register(PTBR) : page table을 가리킴
• Page-table length register(PTLR) : 테이블 크기를 보관
  -> 모든 메모리 접근 연산에는 2번의 memory access 필요(page table 접근 1번, data/instruction 접근 1번)
  -> 두번의 메모리 접근은 비용이 아주 많이 들기 때문에 별도의 하드웨어를 사용하게 된다(일종의 캐쉬)
  -> 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속 lookup hardware cache 사용

| Paging Hardware with TLB

• 메인 메모리에는 캐시 메모리가 존재해 빈번히 사용되는 메모리를 캐쉬 메모리에 올려놓고 빠르게 사용되게 한다
• 그런 것처럼 주소 변환을 위한 캐쉬 메모리인 TLB를 놓고 일부 메모리를 캐싱하게 된다
• TLB는 테이블 정보의 일부를 가지게 되고, page number/frame number(몇번째 entry에 해당하는가)을 동시에 가지게 된다
• TLB는 전체를 서칭해야 하는데 그것이 오래 걸리기 때문에 병렬 탐색이 가능한 associative register을 가지고 있다
• TLB안에 해당 정보가 없으면 TLB miss 가 되며 page table을 이용한 주소 변환을 하게 된다
• page table은 각각의 프로세스마다 존재하게 되며, 페이지 테이블의 TLB도 프로세스마다 다른 정보이다(context switch가 일어날 때 flush가 일어난다)

| Effective Access time (EAT)

• Associative register lookup time = ε
• memory cycle time(메인 메모리 접근 시간)= 1
• Hit ratio(associative register에서 찾아지는 비율) = α
• EAT = (1 + ε) α + (2 + ε)(1 - α) = <Hit> + <Miss>
  = 2 + ε - α

Two-Level Page Table

• 현대의 컴퓨터는 address space 가 매우 큰 프로그램 지원( 32 bit address 사용 시 2^32(4G) 주소 공간)
• page size 4K 시 1M 개의 page table entry 사용, 각 page entry 4B 시 프로세스당 4M의 page table 필요
• 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
  -> page table 자체를 page로 구성(공간 줄이기를 위해서 사용)
  -> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)

• logical address(32-bit , 4K page)의 구성 : page number(20 bit), page offset(12 bit)
• page table 자체가 page로 구성되기 때문에 page number은 다음과 같이 나뉜다 : page number(10 bit), page offset(10 bit)
  
• P1 은 outer page table의 index , P2는 outer page table의 page에서의 변위(displacement)
• 안쪽 페이지 테이블의 경우는 사용되는 부분에 대해서만 만들어지기 때문에 효율적이다

| Multilevel Paging and Performance

• Address space 가 더 커지면 다단계 페이지 테이블이 필요하다
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• TLB를 통해 메모리 접근 시간을 줄일 수 있다(대부분의 주소 변환은 TLB에서 해준다)

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

logical memory -> page table -> physical memory

• 페이지 테이블에는 주소 변환 정보 뿐만 아니라 valid-invalid bit과 같은 것이 들어가게 된다
• 32 bit address 체계를 사용하면 페이지 최대 1M개 존재(상위 : 코드 데이터 구성 페이지, 중간 : 사용되지 않는 메모리, 맨 아래: 스택을 구성하는 페이지)
• 사용되지 않더라도 모든 엔트리는 다 만들어지고, 사용 유무를 valid, invalid bit으로 표시하게 된다
• 페이지 중 당장 필요한 것은 물리적인 메모리에 올라가 있고, 아닌 것은 backing store에 있을 것이다
• 물리적인 메모리에는 아무것도 올라가있지 않을 경우 invalid라고 해놓을 것이다

| Memory Protection

Page table의 각 entry 마다 아래의 bit을 둔다

Protection bit

• page 에 대한 접근 권한(read/write/read-only 중 어떤 연산에 대해 접근이 가능한가)
• 페이지 테이블에 접근했으면 본인의 페이지에 대해서만 주소 변환을 할 수 있게 한다
• 다른 프로세스가 페이지를 못 보게 하려는 용도는 아니다

Valid-invalid bit

• valid : 해당 주소의 frame 의 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
• invalid : 해당 주소의 frame에 유효한 내용이 없을을 뜻함(접근 불허)
• 유효한 내용이 없음 1) 프로세스가 그 주소 부분을 사용하지 않는 경우
• 유효한 내용이 없음 2) 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

Inverted Page Table

• 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
• 대응하는 page가 메모리에 있든 아니든간에 page table에는 entry로 존재
• 그에 따라 page table이 매우 크다는 문제가 생김(page table entry 자체가 100만개 이상이 되면 공간 오버헤드가 많이 나온다)
• 그러한 것을 막기 위한 inverted page table 존재

• inverted page table은 시스템 안에 페이지 테이블이 딱 하나 존재한다
• page table의 entry가 프로세스의 페이지 갯수만큼 존재하는 것이 아니라 물리적인 페이지 프레임 갯수만큼 존재하게 하는 것이다
• 첫번째 entry에는 첫번째 페이지에 들어가는 논리적인 페이지 번호가 들어가 있다
• 두번째 entry에는 두번째 페이지 엔트리에 들어가는 논리적 페이지 번호가 들어가있다
  -> 즉 역방향으로 이루어진다(원래 주소 변환은 logical address -> physical address 순으로 이루어지나, inverted page table에서는 physical -> logical 순으로 이루어진다)
• 공간은 줄일 수 있지만 논리주소에 해당하는 p가 물리주소 어디에 올라가는 지를 알기 위해서는 해당하는 페이지를 전부 찾아야한다(시간 적 오버헤드 발생)
• 논리적인 페이지 번호만 저장할 것이 아니라 어떤 프로세스의 페이지인지 알려주는 process id(Pid)가 같이 들어가야 한다
• 오버헤드가 크기 때문에 병렬적으로 동시에 검색할 수 있는 association register에 넣어 시간을 줄일 수 있다

Shared Page

다른 프로세스와 공유할 수 있는 페이지가 있다

| Shared code

• share 할 수 있는 코드에 대해서 각각을 물리적 메모리에 별도로 올리는 것이 아니라 share이 가능한 한 카피만 올리도록 한다
• Re-entrant Code ( = pure code)
• read-only로 하여 프로세스간에 하나의 code만 메모리에 올림 ( ex text editors, compilers, winsow systems
• shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함 (code 안에는 logical address가 적혀있기 때문)

| Private code and data

• 각 프로세스들은 독자적으로 메모리에 올림
• prviate data 는 logical address space의 아무 곳에 와도 무방

---

Segmentation

• 프로그램은 의미 단위인 여러 개의 segment로 구성 (작게는 함수, 크게는 프로그램 크기로)
• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의 됨

Segmentation Archtecture

• Logical Address는 segment-number, offset으로 구성이 된다

| Segment table

table entry는 각각 base, limit을 가지고 있다

• base : segment중 시작하는 물리적 주소 (segment의 시작 위치)
• limit : segment의 길이
• limit을 저장하는 이유는 segment가 논리적 단위이기 때문에 길이가 일정하지 않아서, 길이를 함께 저장하게 된다

| STBR(Segment-table-base register)

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

| STLR(Segment-table length register)

• 프로그램이 사용하는 segment의 수
• segment number(s)는 STLR 보다 작아야한다
• 논리 주소의 segment 번호가 segment length보다 작은지 확인해서 작지 않을 경우 trap이 걸리게 된다

| Protection

• 각 segment별로 protection bit이 있다
• valid bit = 0 -> 허용되지 않은 bit이다
• read, write, execution bit이 있다

| Sharing

• shared segment
• 같은 segment 번호일 경우 sharing 가능
• segment는 의미 단위이기 때문에 공유(sharing)과 보안(protection)에 있어 paging보다 효과적이다

| Allocation

• first fit/best fit
• external fragmentation 발생
• segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생
• segment도 길이가 균일하지 않기 때문에에 hole과 같은 외부 조각이 생기게 된다
• 실제적으로 페이지는 갯수가 굉장히 많지만, segmentation은 갯수가 적다
• 의미 단위로 일을 할 경우 segmentation이 효과적이다

Segmentation With Paging

• segment 당 페이지 테이블이 존재하는 것
• segment-table-entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음
• segment offset(d), p(페이지번호)/d`(페이지당 오프셋) 별로 메모리의 다른 위치에 올라가게 된다
• 사실상 메모리 관리에서는 운영체제가 하는 일이 없다 -> 주소 변환은 하드웨어적으로만 이루어진다