CS스터디

[CS스터디] Paging(2)

by VICENTE97P4

April 29, 2022, 11:52 a.m.

Hierarchy paging

32bit 환경에서 page의 크기가 4KB라고 하면 page는 총 2^32 / 2^12 = 2^20개의 page가 나옵니다.

그럼 page table entry는 1Mega(2^20)개 필요합니다.

page table의 크기를 구해봅시다.

page table에서 logical page 번호는 필요없습니다. 그만큼 내려오면 되니까요.

그럼 frame 번호만 필요합니다. valid-invalid bit는 일단 제외합시다.

frame 번호는 정수니까 4byte입니다. 그럼 2^20 * 4 = 4MB가 필요합니다.

즉, process 1개의 page table 크기는 4MB입니다. 그런데 4MB는 frame 1개에 안들어갑니다. frame 1개는 4KB니까요

4MB를 frame에 저장하려면 4MB / 4KB = 2^10 개의 frame이 필요합니다.

이 2^10개의 page table을 저장하기 위해 frame이 1개 더 필요합니다.

frame 1개의 크기는 4KB니까, 딱 2^10 만큼 저장할 수 있습니다.

이 기법을 Two-Level page-table scheme이라 합니다.

1. outer-page table을 look-up 해서 내가 원하는 정보를 담은 page table frame을 찾아갑니다.

2. 실제 physical frame을 알아내서 접근합니다.

logical address 1개로 outer-page table에서 원하는 page-table frame을 찾고 또 physical frame을 찾을 수가 있을까요?

page size가 2의 지수승이라 가능합니다.

원래는 32bit에서 20 + 12로 나누어서 원하는 data에 접근했습니다.

4KB는 12bit로 접근해서 offset 역할을 해줄 수 있었습니다.

시작하는 outer-page table를 봅시다. 여기에는 주소값이 적혀있기 때문에 entry가 2^10개 들어갑니다.

그럼 10bits 만 있으면 됩니다. 그리고 page table 역시 주소값만 있기 때문에 entry가 2^10개 들어가죠.

역시 10bits만 있으면 됩니다. 그리고 뒤 12bits는 원하는 page 안에서의 offset 역할을 합니다.

따라서 logical address 1개만으로 원하는 frame에 접근이 가능합니다.

(그런데 page table만 4MB면 너무 큽니다. process가 10개라고 하면 page table 크기만 40MB가 되는 기현상이 발생합니다.

그래서 page table 전체는 하드디스크에 저장되어있고 자주 접근하는 page table entry들은 memory에 올라옵니다.)

그런데 이 경우는 옛날 옛적에 쓰던 32bits 컴퓨터 이야기고, 요즘은 64bits를 쓰는데 그럼 도대체 몇 level이 필요할까요?

64bits를 다 쓰려면 6 level이 필요합니다만 logical address space가 2^64의 크기를 갖는 것은 불가능합니다.

그래서 48bits만 주소체계에 사용합니다. 그럼 4 level이 나옵니다.

2^48 / 2^12 = 2^36 개의 page가 생깁니다.

2^36 / 2^10 = 2^26개의 page table frame이 필요합니다.

그래서 2^6 -> 2^16 -> 2^26 -> 2^36 -> data, 따라서 4 levels가 생깁니다.

그런데 이러면 page table에서 4번, data에 1번 총 5번의 memory 접근이 발생합니다.

아니.. 2번 참조도 많다고 TLB 썼는데.. 5번의 참조면 감당이 될까요?

그래서 EAT를 다시 계산해봅시다.

EAT

hit ratio가 98%인 paging 기법을 쓴다고 해봅시다.

TLB look up time은 20ns, memory access time은 100ns라고 합시다.

EAT = 0.98 * (20 + 100) + 0.02 * (20 + 100 + 100 + 100 + 100 + 100) = 0.98 * 120 + 0.02 * 520 = 128ns

pagine 기법 적용 안했을 때는 그냥 memory에 접근하니까 100ns, paging 사용 시에는 128ns입니다.

28ns 차이는 괜찮습니다. 따라서 TLB hit ratio가 높으면 level이 높아져도 큰 문제가 없습니다.

* 추가로 32bits 컴에서는 4GB가 넘는 RAM은 못 쓸까요? 예를 들면 8GB RAM 말이죠.

네, 못 씁니다. 주소값 참조를 2^32 = 4GB밖에 못하니까요.

그런데 사실 4GB도 다 못 씁니다. 특수 목적으로 예약된 주소공간을 빼면 3.2GB 정도만 남기 때문입니다.

Hashed page table

주소변환은 결국 logical page 번호를 가지고 물리적 page 번호를 알아내기 위한 것입니다.

그래서 hash를 적용해서 O(1)만에 원하는 frame을 찾는 방법도 있습니다.

그럼 page table이 hash table이 됩니다.

그런데 이 hashing에는 문제점이 있습니다.

- collision이 발생할 수 있습니다. 이 경우 O(1)만에 찾지 못할 수 있습니다.

- chaining으로 해결한다면 worst case로 O(N)이 걸리기 때문에 tree만 못할 수 있습니다.

사실 32bits 체제일 경우에는 2단계밖에 없어서 굳이 Hash를 쓰지 않습니다. 그보다 큰 주소체제에서 씁니다.

logical page 번호가 hash key가 됩니다.

위 그림에서는 collision이 발생한 경우 chaining으로 해결한 모습입니다.

Inverted page table

아까 위에서 process는 자신만의 page table을 가진다고 했습니다.

그럼 process가 n개면 process table 용량만 4nMB가 됩니다.

그런데 모든 process들이 자신만의 page table을 가져야 할까요?

하나의 process가 전체 주소를 다 쓴다고 가정해야 2^32 만큼 필요합니다.

그런데 사실 process 1개가 2^32를 다 사용하는 경우는 극히 드뭅니다.

즉, 우리는 over visioning을 해서 logical address를 너무 크게 잡고 있습니다.

inverted page table은 logical page 번호를 physical page로 mapping하는게 아니라,

physical page를 logical page로 mapping하는 것입니다.

장점

- 실제 memory에 올라와서 사용되고 있는 page의 정보만 page table이 제공합니다.

- 이러면 process마다 page table이 존재하는 것이 아니라 DRAM에 대한 정보를 제공하는 page table 1개만 있으면 됩니다.(1개의 system-wide page table)

1. CPU가 logical address를 발생시킵니다.

2. pid와 p(page number)를 묶어서 해당하는 entry를 찾습니다. 몇 번 process의 몇 번째 page를 알고 있다는 뜻입니다.

그럼 전체 frame에서 찾았으니까 offset i, 즉, i가 frame number가 됩니다.

3. frame 번호 i에다가 offset 번호 d를 더하여 data를 찾습니다.

문제점

- 원하는 pid와 p를 찾으려면 제일 위부터 찾아야 합니다. 즉, direct access가 안됩니다. 그에 반해 paging은 direct access가 되었죠.

그래서 시간이 오래 걸립니다.

(이렇게 index로 search하는 것이 아닌 field 값을 비교해서 search하는 방법을 associative search라 합니다.)

- TLB의 도움을 받을 수 없습니다. 전체 frame을 TLB에 넣을 수는 없는 노릇이니까요..(그런데 잘 적용하면 어떻게든 TLB를 쓸 수는 있다고 합니다.)

이를 극복하기 위해 hash를 적용할 수 있습니다.

pid와 p를 hash 함수의 key값으로 하고 output을 inverted page table의 index로 만들면 바로 찾을 수 있죠.

하지만 위에서 말한 hashed page table과 별반 다를 바가 없어집니다.

* 제일 큰 단점은 page sharing이 불가능 하다는 것입니다.

page sharing은 paging 기법의 가장 큰 장점 중 하나입니다.

inverted page table은 pid가 있어서 sharing을 할 수 없습니다.

공유되는 page는 entry에 pid와 page 번호가 적힙니다.

그러면 pid는 공유되는 process의 개수만큼 적혀야 하는데 몇 개의 process가 공유할지 알 수 없습니다.

그래서 page table의 구조를 정할 수 없게 됩니다.

inverted page table은 search overhead가 커서 잘 쓰지 않습니다.

성능 상으로 hash와 TLB로 어떻게 맞춰본다고 해도 page sharing이 되지 않아서 잘 쓰지 않습니다.

Segmentation

그런데 paging 기법에서는 program code가 중간에 짤릴 수 있습니다.

예를 들어 array의 597번째 data까지는 5번째 page, 598번째부터는 6번째 page에 들어있게 될 수 있습니다.

- 이렇게 되면 의미적인 덩어리라는 개념을 잃게 됩니다.

- 의미론적인 관점 뿐만 아니라 공유할 때 안 좋을 수 있습니다.

어떤 page에 공유할 수 있는 data와 공유할 수 없는 data가 반씩 섞여있을 수도 있습니다.

이는 의미 단위가 아닌 크기 단위로 잘라서 생기는 문제점들입니다.

그래서 의미 단위를 유지해주는 방법이 segmentation 기법입니다. Address space를 의미 단위인 segment로 자릅니다.

위 그림에서는 의미단위인 5개의 segment로 잘랐습니다.

같은 segment는 연속적으로 올립니다. 물론 다른 segment까지도 연속할 필요는 없습니다. 다른 공간에 올릴 수 있죠.

segment의 시작주소와 원하는 data의 offset이 있으면 접근 가능합니다.

- logical address를 segment 번호와 offset으로 자르면 됩니다.

segment table

각 segment의 시작주소를 담고 있습니다. - base라는 field

해당 segment의 길이를 담고 있습니다. - limit이라는 field

그래서 base와 limit이 한 pair가 되어 segment table의 한 entry가 됩니다.

segment 번호를 보고 segment table에서 해당하는 segment의 base 주소를 읽고 limit 값을 읽습니다.

base 값 + offset 연산을 하면 원하는 data의 위치를 알 수 있습니다.

그러면 여기서 segment table 주소는 segment table base register에 있습니다. (STBR)

segment table의 길이는 segment의 개수입니다.(STLR에 있습니다.)

내가 접근하려는 segment의 번호가 segment table length register보다 크면 잘못된 접근입니다.

segmentation 주소 변환 과정입니다.

1. d(offset) 가 limit보다 큰지 protection 차원에서 먼저 검사합니다.

2. 정상적인 접근이면 base 값을 읽습니다.

Segmentation architecture 특징

- Protection

segment 역시 process에 몇 개의 segment가 있을지 미리 알기 힘듭니다. 그래서 미리 크기를 정해놓고 할당하게 됩니다.

그래서 paging 때와 동일하게 남는 공간이 생기는데 이 공간을 validation bit로 표시합니다.

R/ W/ X bits

read / write/ execution

해당 segment에 대한 접근 방법까지 명시할 수 있습니다. 의미 단위로 분할한 것이기 때문에 가능합니다.

(paging 기법에서는 R / W / X로 세분화해서 구분하지는 못했습니다.)

만일 read-only인 영역에 write하려 하면 막을 수 있습니다.

- Sharing

segment 단위의 sharing이 가능합니다.

paging 때처럼 한 page에 반은 공유가 가능하고, 반은 불가능한 문제가 해결되었습니다.

- External fragmentation

segment는 연속적이고 제각각 크기로 memory에 올라갑니다.

그럼 contiguous allocation 때와 같이 external fragmentation이라는 치명적인 문제가 생깁니다.

반면에 필요한 만큼 쓰니까 internal fragmentation 문제는 발생하지 않습니다.

paging과 반대 현상이 생깁니다.

위 그림은 segment sharing을 나타낸 것입니다.

process 1, 2가 모두 같은 editor를 쓰고 있습니다. 각 process의 0번 segment는 editor program code입니다.

그래서 0번 segment의 base를 보면 같은 값임을 알 수 있습니다.

그리고 segment table에서 base 옆에 column을 새로 만들어서 R / W / X를 표시할 수 있습니다.

Segment with paging

전통적으로 memory는 부족하다는 인식이 크기 때문에 external fragmentation 문제는 참을 수 없습니다.

그래서 segment에 paging 기법을 적용할겁니다.

Logical address space를 segment 단위로 자르고, DRAM은 frame size로 자를겁니다.

그리고는 각 segment를 page 단위로 자릅니다.

그러면 어떤 data는 몇 번 segment의 몇 번째 page의 몇 번째 offset이라는 개념이 생깁니다.

이 page를 frame에 끼워넣는겁니다.

말이 길어서 좀 어지러울 수 있는데 이때까지 해왔던 방식이랑 크게 다르지 않습니다.

paging 기법을 적용했으니 당연히 segment 시작 주소와 offset으로 접근이 불가능해졌습니다.

주소값을 위와 같이 나눌 수 있습니다.

위 그림은 주소변환법을 나타낸 것입니다.

1. segment 번호(s)로 segment table을 look up합니다.

이제는 segment마다 page table이 필요합니다. 그래서 segment의 page table의 위치가 나옵니다.

2. page table로 가서 page 번호(p)로 look up 하면 frame 번호가 나옵니다.

3. frame 시작 위치에서 d를 더해서 내가 찾고자 하는 위치에 접근합니다.

- 장점

page 단위로 memory가 관리되어서 external fragmentation 문제가 생기지 않습니다.

- 단점

internal fragmentation 문제가 생깁니다.

memory 사용의 효율성 측면은 paging 기법과 같아지지만 segment라는 의미 단위는 유지됩니다.

여기에다가 TLB까지 포함이 가능합니다.

위 그림은 TLB까지 포함한 주소 변환 과정입니다.

1. TLB에서 먼저 해당 segment와 page에 해당하는 physical address가 있는지 봅니다.

2-1. 있으면 그대로 변환해서 원하는 data에 접근합니다.(TLB hit)

2-2. 없을 경우 위에서 말한 방식대로 segment table에서 해당하는 segment의 page table 위치를 찾고,

page table에서 해당하는 page의 frame 번호를 찾아서 실주소 r에 매핑하여 d만큼 떨어진 곳으로 가서 원하는 data를 찾습니다.

최근 OS는 다 segmentation with paging 기법을 씁니다.

page 구현은 비슷한데 segment에 대한 부분이 OS마다 다르다고 합니다.

62 view 1304

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

WYr09FHL

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1 OR 2+357-357-1=0+0+0+1

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1 OR 3+357-357-1=0+0+0+1

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

*if(now()=sysdate(),sleep(15),0)

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1); waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1 waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

TXnXSxsZ'; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1 OR 683=(SELECT 683 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1) OR 481=(SELECT 481 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

-1)) OR 428=(SELECT 428 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

skubRjSo' OR 735=(SELECT 735 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

UKLOLOtc') OR 813=(SELECT 813 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

LKjDDVfp')) OR 643=(SELECT 643 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

��%2527%2522\'\"

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:27 p.m.

@@i8dwW

Updated: Feb. 22, 2025, 5:27 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

555

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:36 p.m.

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR Feb. 22, 2025, 5:37 p.m.