OS - [CH18_Paging]

Topic: How to virtualize memory with pages

공간 관리하는 문제 해결에는 두 가지 접근법이 있다.

- 변수 크기로 조각을 자르는 것

  ㄴ fragmented가 유발될 수 있다

- 고정된 크기로 조각을 자르는 것

  ㄴ> paging

 

* page: 고정된 크기의 유닛 각각을 page라고 한다.

* physical memory를 page frame이라고 부르는 고정된 크기의 슬롯 배열로 간주한다.

 

18.1 A simple example and overview

- 가상 주소 공간의 페이지는 physical memory에 각각 다른 위치에 놓여있다.

- Paging 장점

1. flexibility

   ㄴ heap, stack의 성장 등 사용할 공간을 생각할 필요가 없다

2. simplicity

   ㄴ free list에서 빈 공간을 쉽게 찾음

 

- page table

  ㄴ physical memory에서 각각의 virtual page가 어디에 있는지 저장함

  ㄴ 주역할: 주소 공간의 각 가상 페이지에 대한 address translation을 저장하여

                우리는 실제 메모리에서 각 페이지가 있는 위치를 알 수 있다.

  ㄴ per-process 구조이다 

      (대부분의 페이지 테이블 구조는 per-process 구조이지만, 'inverted page table'은 예외이다)

 

- 프로세스가 발생한 가장 주소를 변환하려면 우리는 이것을 두 가지 요소로 분리해야 한다

  ㄴ virtual page number(VPN)과 offset(페이지 내의)

 

상위 2bits는 virtual page number이고 나머지는 해당 page의 byte이다(= offset) 

 

physical frame number(PEN) (=physical page number (PPN))과 VPN을 같이 둬 virtual address를 변환시킬 수 있다.

- offset은 변환되지 않고 동일하게 유지된다.

  offset은 우리가 원하는 페이지 내의 byte를 알려줌

 

 

앞으로 알아볼 내용:

1. 어디에 page table들이 저장되는가?

2. page table에는 주로 어떤 내용이 담겨있는가?

3. 얼마나 큰가?

4. 페이징은 시스템을 느리게 하는가?

 

 

18.2 Where are page table stored?

- page table들은 매우 클 수 있다.

- 그래서 MMU에 page table을 저장하지 않고 각 프로세스의 페이지 테이블을 어딘가의 메모리에 저장한다.

 

 

18.3 What's acually in the page table?

- page table: virtual addresses와 physical addresses를 매핑하는 데 사용되는 데이터 구조

- 가장 간단한 형태는 linear page table이다 (배열임)

- OS는 배열을 virtual page number(VPN)로 인덱싱 하고,

  해당 인덱스에서 page-table entry(PTE)를 검색하여 원하는 physical frame number(PEN)를 찾습니다.

 

- PTE 구성

  1. valid bit: 특정 변환이 유용한 지 나타냄

     ㄴ 0: 현재 PTE가 가리키는 page frame이 존재하지 않음 / 1: 존재

     ㄴ 주소 공간이 유효하지 않는 곳에 사용하지 않는 페이지들을 모두 표시함

     ㄴ ex) 프로그램이 작동하면 코드와 힙이 주소 공간 끝에 위치한다. 나머지는 사용하지 않는 공간은 유효하지 않다. 

             만약 프로그램이 이 공간에 접근하려고 한다면 OS는 trap을 발생시켜 그 프로세스를 중단시킨다.

     ㄴ physical memory 총량을 증가시키는데 사용

  2. Proctection bits: 페이지가 읽고, 쓰고, 실행 가능한 상태인지 나타냄

  3. present bit: 이 페이지가 physical memory에 있는지 distk에 있는지 나타냄  (swap out)

    * swapping은 드물게 사용되는 페이지를 디스크로 옮김으로써 os가 physical memory를 비울 수 있게 함.

    * 실제 메모리보다 큰 주소 공간을 지원하기 위해 주소 공간의 일부를 디스크로 스왑

  4. dirty bit: 페이지가 메모리로 이동된 이후 수정되었는지 여부를 나타냄.

     ㄴ 변경 사항이 있으면 paging file에 해당 내용을 카피해야하고

         변경 사항이 없다면 카피하지 않아도 되므로 불필요한 카피를 억제

     ㄴ page out될 페이지 결정

  5. reference bit(accessed bit): 페이지에 접근이 있었는지 추척

     ㄴ 어떤 페이지를 많이 사용하는지 결정하기 유용해서 메모리에 남겨둬야 함.

                                                                                ㄴ page replacement 하는데 중요한 정보임

 

* page out: 기존에 사용중인 페이지 프레임의 내용을 swap space에 저장하고 그 페이지 프레임을 현재 필요로 하는 다른 프로그램에 주는 것

  -> free page가 모자랄 때 발생 (free space를 확보해야지만 빠르게 매핑 가능)

  page in: swap space에 머물러 있는 내용을 다시 불러들여 페이지 프레임을 제공하는 것을 말한다. 

 

* Swapping: 

  시스템 안에 메모리가 부족하게되면 사용빈도수가 적은 프로세스들을 내보내게 된다.

  메모리가 많이 부족할 경우 프로그램을 통째로 swap space로 내보낸다.  -> swap out

 

 

 

18.4 Paging: also too slow

예를 들어 mov1 21, % eax라는 명령이 있다고 하자

1. 먼저 원하는 데이터를 가져오기 위해 시스템은 가상 주소를 실제 주소로 변환해야 한다.

2. 주소 117에 데이터를 가져오기 전에 데이터는 프레세스의 페이지 테이블로부터 page table entry를 가져와야 한다.

3. 변환을 실행하고 실제 메모리로부터 데이터를 로드한다.

4. 이렇게 하면 하드웨어는 최근 작동 중인 프로세스의 페이지 테이블이 어디에 있는지 안다.

 

단일 page-table base register가 페이지 테이블의 시작 위치의 실제 주소를 포함한다고 가정하자.

원하는 PTE를 찾기 위해 하드웨어는 다음의 함수를 수행한다.

 

VPN_MASK는 전체 가상 주소에서 VPN 비트를 추출하는 0x30으로 설정된다.

SHIFT는 4로 설정된다(offset의 비트 개수)

ㄴ> 올바른 정수 virtual page number를 형성하기 위해 VPN 비트를 이동시킨다.

 

물리적 주소가 알려지면 하드웨어는 PTE를 메모리에서 가져와서 PEN을 추출하고

이를 가상 주소의 OFFSET과 연결하여 원하는 물리적 주소를 형성할 수 있다.

 

 

(↑ paging으로 메모리 접근)  <- 찾아보기

 

(↓메모리 참조할 때 일어나는 일에 대한 초기 프로토콜)

모든 메모리 참조를 위해서는, paging은 페이지 테이블로부터 변환을 가져오기 위해

하나의 추가적 메모리 참조를 요구한다.

-> cost ↑

 

 

 

18.5 SKIP   <- 읽기 시로 ㅠ

 

 

18.6 Summary

- paging 장점

  1. external fragmentation 유발하지 않는다 -> 메모리를 고정된 사이즈로 자르기 때문

  2. flexible하다. 가상 주소 공간을 드물게 사용할 수 있게 함

- paging 단점

  1. 기계를 느리게함 -> 페이지 테이블에 접근하기 위해 메모리 접근량이 많아져서

  2. 메모리 낭비 -> 메모리가 페이지 테이블로 차서