Paging

이 글은 KOCW 강좌 중 경성대학교 양희재 교수님의 '운영체제' 강의를 정리한 글입니다.

 

Paging

Contiguous Memory Allocation

External fragmentation

외부 단편화

컴퓨터가 부팅되면서 운영체제가 Memory에 할당된다.

이때, Memory에는 운영체제만 할당되고 나머지는 비어있는 상태이며 비어있는 공간을 hole이라고 한다.

부팅 직후 Memory에 운영체제 외 나머지 비어 있는 hole을 Big single hole이라고 한다.

이후 Process가 생성, 종료되면서 Memory 곳곳에 hole이 생기는데 이러한 상태를 scattered holes라 한다.

scattered holes 상태에서 hole들이 불연속 하게 흩여져 있다.

큰 Process가 생성되려고 해도 hole보다 작으면 Memory에 할당이 될 수 없다.

이렇게 불연속하게 생긴 hole들로 Process가 Memory에 할당 못 되는 것을 External fragmentation이라 한다.

Contiguous Memory Allocation

연속 메모리 할당

External fragmentation을 해결하기 위한 방법으로 먼저 연속 메모리 할당 방법이 있다.

연속 메모리 할당 방법에는 3가지 방법이 있다.

• First-fit(최초 적합) -> Memory를 순차적으로 탐색하여 할당 가능한 최초의 hole에 Process 할당
• Best-fit(최적 적합) -> Memory의 hole 중 Process 크기와 가장 비슷한 hole에 Process 할당
• Worst-fit(최악 적합) -> Memory의 hole중 Process 크기와 가장 차이가 큰 hole에 Process 할당

3가지 방법을 비교하면 First-fit이 가장 속도가 빠르다.

Memory 이용률에서는 First-fit, Best-fit이 좋다고 알려져 있다.

하지만 Best-fit으로 할당해도 External fragmentation로 전체 Memory에 1/3를 낭비한다고 한다.

또 다른 방법으로 흩어져 있는 hole를 한 곳으로 합치는 Compaction이 있다.

하지만 hole이나 Process를 이동하면서 자원이 들 수 있고 이동에 대한 최적의 알고리즘이 없다.

Paging

External fragmentation을 해결할 방법에 Paging이 있다.

Process를 일정한 크기로 나누어서 Memory에 할당하는 방식이다.

Proess뿐만 아니라 Memory 역시 일정한 크기로 나누어진다.

일정한 크기로 나누어진 Process를 Page, Memory를 Frame이라 한다.

Process가 연속적으로 Memory에 할당되는 것이 아니라 Page로 흩어져서 할당될 수 있다.

CPU에서는 흩어져 있는 Process를 실행할 수 없다.

이 문제를 해결하기 위해 MMU(Memory Management Unit)에서 처리한다.

Address Translation

MMU에서 Logical Address, Physical Address를 이용한다.

실질적으로 Physical Address는 흩여져 있지만 Logical Address로 한 곳으로 모아준다.

MMU의 Page Table에서 Logical Address와 Physical Address를 매핑해 준다.

• Logical Address
  • CPU가 내는 주소는 2진수로 표현
  • 하위 n bit(d)는 offset 또는 displacement
  • 상위 m-n bit(p)는 Page 번호
• Physical Address
  • Logical Address에서  Page 번호(p)는 Page Table에서 Index -> 해당 Index에 있는 값이 Frame 번호
  • Page 번호가 Frame번호로 바꿔서 Physical Address에서 사용
  • offset(d)는 Physial Address에서 그대로 사용

Internal Fragmentation

내부 단편화

Process의 크기가 Page크기의 배수가 아니라면 빈 공간이 발생한다.

예를 들어, Process의 크기가 17인데 Page의 크기가 5라고 하자.

그러면 해당 Process는 4의 Page에 나눠지며 1개의 Page는 Frame에 빈 공간 3이 생긴다.

이러한 상황을 Internal Fragmentation이라고 한다.

하지만 Internal Fragmentation은 무시해도 될 정도로 미미한 문제이다.

Page Table

Page Table을 CPU Register나 Memory에 두지 않는다.

CPU Register에 두면 속도는 빠르지만 자원이 너무 한정적이라 Table 크기가 작을 수밖에 없다.

Memory에 두면 Table을 크게 둘 수 있지만 속도는 느리다.

그래서 Page Table을 별도의 칩(SRAM)으로 만들어 CPU와 Memory 사이에 위치해 있다.

Page Table이 있는 이 칩을 TLB(Translation Look-aside Buffer)라 한다.

Protection

Page Table을 통해 보호 기능을 수행할 수 있다.

모든 주소는 Page Table을 경우하고 있다.

Table 엔트리마다 r(read), w(write), x(execute) bit를 두어 해당 bit가 켜져 있을 때만 수행하게 한다.

이러한 제어 bit를 통해 Page마다 접근 제어가 가능하다.

Sharing

Page Table을 통해 Memory 낭비를 막을 수 있다.

같은 Program으로 여러 개의 Process가 실행될 수 있다.(예, 한글 파일 동시에 여러 개 실행)

Process는 code, data, stack으로 구성되어 있다.

data, stack은 같은 Program이지만 Process마다 다를 수 있다.

하지만 code는 같은 Program의 Process라면 동일하다.

(대신 non-self-modifying, reentrant, pure code일 경우)

이럴 경우 Process 마다 code영역을 Memory에 Load 하는 것은 비효율적이다.

code 영역은 하나만 Load 하고 Page Table에서 여러 개의 Process가 공유하게 한다.