[OS] Virtual Memory 강의 정리 - 반효경 교수님 (v2017)

 

강의 출처

운영체제

 

---

Memory Management I

 

Logical Address

• 프로그램 실행 시, 독자적인 메모리 주소 공간 생성 = Logical Address
• 주소 바인딩
  • CPU가 바라보는 주소는 Logical Address, 그러므로 변환 필요
  • Symbolic Address < Logical Address < Physical Address
  • 종류 : Compile time, Load time , Run time(실행 후 메모리 상 위치 옮기기 가능; 하드웨어 지원 필요 base and limit register, MMU; 또한 주소 참조 시 mapping table을 통해 binding을 점검해야함)

 

MMU

• Memory Management Unit
• HW device to map logical address to physical

simple ex : Relocation Register (= Base Register), Limit Register 를 이용한 주소 바인딩 (가정; Contigous Allocation)

Logical Flow 로 보는 것도 재밌네

 

Dynamic Loading (Overlays와 유사)

• 프로세스 전체를 메모리에 미리 다 올리지 않고, 해당 라이브러리나 모듈이 불려질 때 메모리에 로드함
  • Q. 루틴이란? A. 특정 작업을 수행하는 코드의 집합 (함수, 메서드 등으로 불리며 입력을 받고 출력을 반환)
  • Q. Overlays와 유사하면, 어떻게 다름? A. 프로그램의 필요한 부분만 적재

 

Dynamic Linking (= Shared Library)

• linux: .so / window : .dll
• 소스코드 > 컴파일 > Linking (라이브러리를 실행 파일에 연결)
• 라이브러리 실행 시 Link; 라이브러리 루틴의 위치를 찾기위한 stub
• 프로그램 간에 공유가 가능해서 memory utilization 효율적

 

Swapping

• Backing Store (=Swap area) : Disk
• Swap out : Memory to Disk
• Swap In 시 빈 곳 어디에나 넣을 수 있는 Run tiem binding 지원이 필요함
• Original Swapping Time은 곧 I/O Transfer Time과 비례
  • 추후 부분적으로 Swapping 할 수 있는 Paging 기술

 

Allocation of Physical Memory

• Area : OS (low addr)  | 사용자 프로세스
• (현재에는 미사용) Contigous Allocation : Fixed, Variable partition
  
  • 트래킹 정보 : 할당 공간, 가용 공간 (Hole)
  • First-fit, Best-fit, Wort-fit (malloc-lab에서 배운 알고리즘이 여기서도 적용되네!)
  • compaction : 사용 중인 메모리 영역을 한군데로 몰고 hole을 큰 block으로 만듦 (마치 malloclab coalesce)

 

 

한줄평 : 우리가 변수에 대한 공간 확보를 위해 malloc을 쓴 것처럼, 프로그램을 올리기 위해 메모리 공간 확보를 어떻게 할까인거네. 그리고 paging 까지 기술 발전해온 과정

 

---

Memory Management II

 

Noncontigous allocation : Paging, Segmentation, Paged Segmentation

(Base, Limit) Register 2개로는 감당이 안됨

 

Paging

• Logical Memory (Page) ↔️ Physical Memory (Frame)
• (4KB) Page, Frame은 동일한 사이즈라 offset이 동일하게 적용 가능하구나
• Page Table을 사용한 주소 바인딩 (page idx, frame value 배열이라고 생각하면될 듯)

 

 

n-bit 의미는?

• n-bit 프로세스는 최대 (2^n) 개의 논리 주소 공간을 가질 수 있음 (예로, 32-bit, 4GB)
  • 주소 공간 : address space 
  • 1-bit : 0 / 1, 2개의 주소를 표현할 수 있음
  • 실제 물리 메모리는 이보다 작을 수 있음
• #page : 4GB / 4KB = 1M개 PTE (페이지 테이블 레코드)
• 위와 별개로 물리 메모리 공간은 각 바이트에 대해 고유한 물리 주소가 존재함
  • 물리 주소 0x1000 > (다음 바이트) > 0x1001

 

Page Table

• (physical) main memory 상주
• PTBR (Page-table base register) : page table
• PTLR (Page-table length register) : 테이블 크기
• 속도 향상을 위해 주소 전담 캐시, lookup hw cache TLB (Trranslation look-aside buffer) 사용
  • page table 일부만
  • page table idx 자체가 page 번호인점과 달리, entry = (p, f) 두 정보가 쌍으로 갖고 있어야함. 이를 탐색하는데 오래 걸려서 associative register를 가지고 병렬 탐색 진행
  • 일반 메모리 : 주소 기반 탐색 / associative register 데이터 내용 기반 탐색

 

 

예시: 32 bit process, 4M Page Table 필요

• 4GB address space
• 1M PTE (page_size =4K)
• 4M Page Table (PTE size = 4B)
  • PTE info :  page number / frame number / protection bit (R/W) / valid bit (사용 여부 및 memory 적재 여부)

Page Table 공간이 심하게 낭비됨

>> N-Level Page Table 등장

 

 

Two-Level Page Table

• 사용되지 않는 page의 경우 innter table 미생성
• Page Table이 곧 Page

[예시] 32bit Process (Page Size = 4KB)

• P1 : Outer Page Table index (그리고 나머지) 10bit
• P2 : Inner Page Table index (4K / 4Byte = 1K)개를 구분하기 위한 10bit
• d :offset (4K page size 표현을 위해, 12bit)

 

Q. 32bit Logical Address에서 10 / 10 / 12 할당하고 나면, 메타 정보은(권한, W/R 여부 등) 어디에 담기지?

A. 지금 헷갈리는게 Table Entry 와 Logical Address인데, Entry에 해당 정보가 있음

 

Q. 그리고 중간에 Entry가 Null 일 수 있나? 최종적으로 Physical Address가 없으면 초장에 Null 이어야 하는거 아님?

A. 각 Entry는 다수의 Child Entry를 갖고 있고 그 중 일부만 NULL 인거임

 

 

Multilevel Paging and Performance

• 최외각 Page Table만 만들고, 미사용 inner table은 미생성됨. memory utilization 이 좋아짐
• 주소 변환 시간이 많이 소요됨

 

한줄평 : 사용되지 않은 Page Table 이 생성되지 않아서(pte = null) 낭비되는 메모리를 줄인다고 했는데, 위 질문의 답까지 알아내야 좀 더 와닿을 것 같음

 

---

 

Memory Management III

 

Paging 기법 추가 설명

• Inverted Page Table ? 
• Shared Page for Shared Code (= Re-entrant Code, Pure Code)
  • Read Only
  • 모든 프로세스의 Logical Address Space에서 동일한 위치에

 

Segmentation

• 프로그램은 의미 단위인 여러개의 Segment로 구성
• 작게는 함수 단위 / 일반적으로는 code, data, stack
• Segment-table base Register (STBR) : segment table 시작 주소
• Segment-table length Register (STLR) : 프로그램이 사용하는 # Segment
• Q. trap: OS 자체에서 ?? 아니면 HW 지원? A. HW에서 trab을 발생시켜서 OS에서 처리

 

 

메모리 관리

	장점	단점
Paging	- 크기 단위 - 메모리 단편화 감소 및 단순환 메모리 관리	Entry 개수가 많음 (Multi-Level Paging 이 나온 이유)
Segmentation	- 의미 단위이기 때문에, Protection / Sharing에 있어 훨씬 효과적 - Entry 개수가 몇 안됨	- Segment 크기가 가변적이라 메모리 할당, 해제 과정이 복잡함  - 가변 Segment 예시 : heap, heap

 

 

Segmentation with Paging

• Segment Table Entry가 특정 Page Table의 Base Address를 갖고 있음

 

Q. 지금까지의 Memory Management 챕터는 HW의 역할이라고? 그럼 OS는 나중에 무슨일을 하는거지? fault 등 처리만 하나? 아까 트랩처럼?

A. 힌트 하나, Fault 떴을 경우 Disk 에서 로드하기 위해 I/O 즉 OS 개입이 필요함

 

 

한줄평 : 발전사가 신기하면서도, 이래서 최신 트렌드를 알아야겠다.

 

---

가상 메모리 I

(paging 기법 가정)

 

Demand Paging

• 실제로 필요할 때 Page를 메모리에 올림
• 주소 변환 시 Invalid Bit가 설정되면, "Page Fault"
  • 사용되지 않는 주소 영역
  • 페이지가 physical memory에 없는 경우
    • page trab : I/O 개입이 필요함, CPU는 사용자 프로그램에서 OS로 넘어감
    • Q. 어 그럼 physical memory는 RAM만 의미하는 듯?
    • A. YES (present bit = 1, RAM에 적재되었음을 의미함, 물리 메모리에 존재하지 않는 페이지를 접근하는 행위를 Page Fault라고 하니깐)

 

Page Fault Routine

 

 

Free Frame이 없는 경우

• 어떤 Frame을 뺏어올지 결정 필요
• Replacement Algorithm : page-fault rate를 최소화
  • OfflineOptimal Algorithm : 미래의 참조를 안다는 가정 하에 가장 먼 미래 참조 Frame=victim
  • FIFO, LRU (Least Recently Used), LFU (Least Frequently Used)
    • LRU: Linked List
    • LFU : Heap

 

Extra: 캐싱 기법

• 한정된 빠른 공간(=cache라 일컫음)에 요청된 데이터를 저장해두었다가 후속 요청 시 cache 로부터 서비스하는 방식
• paging system, cache memory, buffer caching, Web caching 등 다양한 분야에 적용

 

 

한줄평 : 캐시 victim 선정방식, FIFO, LRU-MRU 구현을 위한 Linked-List 구조체 등 익숙한 개념들이 자주 나온다. 하나만 잘 배워놓으면 다 똑같이 적용될 듯?

 

 

 

가상 메모리 II

Replacement Algoritm : 어떤 Page를 Swap Out 할까??

 

OS 개입 시점

• 기본적으로 주소 변환 시 OS 개입은 불필요
• 주소 참조 시
  • valid (memory에 이미 적재됨) : OS는 인지 못함
  • invalid : Page fault > OS는 I/O Interrupt를 위해 주소변환 인지

> OS는 모든 Page의 최근 사용 시점을 알 수 없음 (Page Fault가 발생하는 시점에만 알고 있음)

 

Clock Algorithm

• = LRU Approximation = Second Chance = Not Used Recently (Recently Used) Algorithm
• Reference Bit (= Access Bit) 을 이용한 Circular Linked List
  • 1은 최근에 사용했음을 인지하고 0으로 리셋 > 그래서 Second Chance라고 하는군
  • 0은 최근 미사용으로 Victim
• Modified Bit (Dirty Bit) : 적재된 Page에 대해 수정 사항이 발생했다면, Swap Out 시 변경사항 업데이트 필요
  • Read Only 였다면 단순히 Memory에서 지워버리면 끝!

요약 

	Reference Bit	Modified Bit
Read	1	-
Write	1	1

 

 

Allocaiton of Page Frame

• 지금까지는 Process에 대한 고려가 없었음.
• 예로, Loop 를 구성하는 page들은 한꺼번에 allocate되는 것이 유리함 (최소한의 allocation 미보장 시 매 loop마다 page fault 예상)
• 종류 : Equal, Proportional, Priority 

 

Replacemnet

• Global Replacemnt : FIFO, LIFO 등 알고리즘을 이용해 프로세스간 메모리 점유를 위한 무한 경쟁
• Local Replacement : 프로세스가 자신에게 할당된 Frame 내에서만 알고리즘을 적용 Replacement

 

Thrashing Diagram

• 특정 process 개수 이상부터는 프로세스가 원활히 돌아가야하는 최소 공간 확보도 되지 못한 상태
  • process scheduling이 되어도 잦은 page fault
  • OS 입장에서는 CPU Utilization이 낮다고 판단해서 계속 악순환

 

 

Working Set Model

• Trashing 방지
• Locality set : 집중적으로 참조되는 page들의 집합
• = (유사) Working set : 프로세스가 원활히 수행되기 위해 보장되어야하는 page들의 집합
• 구현 방법 
  • Working Set Window를 이동시키며, set에 존재하는 page면 유지 / 아니면 swap out
  • Window Size가 중요하겠네

 

PFF (Page Fault Frequency) Scheme 

• 프로세스마다 Page fault rate 상한/하한선을 둠

 

Page Size 결정

• Q. 32-bit Process가 4KB Page Size를 갖게된 배경이 있을까?
• Trend : Larger Page Size