[운영체제] 9. Virtual-Memory Management 가상 메모리 관리

Computer Science/OS 2022. 12. 3. 04:56

728x90

목적 ) 1. 가상 메모리 정의, 장점 2. 요구 페이징 기법에 의한 메모리 적재 3. FIFO, 최적, Least Recently Used 교체 기법, 4. 워킹 셋, 프로그램 지역성에 대한 설명

가상 메모리 기본 개념

지금까지의 메모리 관리 기법

실행하는 코드와 데이터는 반드시 물리적 메모리에 적재되어야 한다.
- 프로세스 크기가 물리적 메모리의 크기로 제한됨

메모리에 모든 내용이 있어야 하는가?

-> 프로그램의 모든 부분이 동시에 요구되지는 않다. (순차적 실행)

-> 오류 상황을 위한 코드, 잘 사용되지 않는 기능에 대한 코드, 필요 이상으로 할당된 큰 용량의 배열

Background

프로그램 일부만 적재 후 실행하면?

다양한 크기의 프로그램을 자유롭게 실행 가능

프로그램 일부만 적재하여 실행 (필요에 따라 추가 적재)

프로그램 실행에 적은 메모리 필요 -> 더 많은 프로그램 적재하여 실행
CPU 이용도, 처리량(Throughput) 향상
프로그램 적재에 적은 IO -> 프로그램 적재 속도 향상
프로그램 실행을 위한 준비시간 감소
swap을 위한 입출력 감소 -> swap 시간 감소

단점

실행 중, 프로그램 추가 적재할 필요 -> 프로그램 실행 시간 증가
프로그램 실행 중 추가 적재를 위한 운영체제 기능 필요 -> 운영체제 복잡도 증가

Virtal memory (가상 메모리)

virtual memory (가상 메모리) : 물리적 메모리로부터 논리적 메모리를 분리.

실행하기 위해 프로그램의 일부만 적재
논리적 주소공간이 실제 메모리 공간보다 커진다.
주소 공간을 공유
프로세스 생성에 효율적이다. (프로그램 적재가 빠름)

실행이 요구된 Page, segmentation만 적재하여 프로세스 실행한다.

Virtual Memory That is Larger Than Physical Memory

가상 메모리 - 물리적 메모리 크기에 제한을 받지 않는다.
사전에 모든 페이지를 적재하지 않고, 실행에 필요한 페이지만을 적재하여 실행
-> 메인메모리보다 훨씬 큰 프로그램 실행 가능하다.

Process Execution

실행 시작 Page를 포함 일부 Page를 적재
적재된 페이지에 대해 페이지 테이블 설정
참조할 페이지가 적재되어 있지 않으면, page fault 발생 (인터럽트)
실행 프로세스를 중단생태로 변경
OS는 참조할 페이지를 메인 메모리로 요청하는 IO request.
시스템 프로세스가 디스크 IO 실행
디스크 IO 완료시, 중단된 프로세스의 상태를 준비상태로 변경

Demand Paging (요구 페이징)

실행에 필요한 페이지만 적재

Less I/O needed
Less MM needed
Faster response
More users (or program)

페이지 필요할때, 이미 메모리에 적재되어 있는 경우엔 메모리를 참조한다.

invalid reference -> abort (잘못된 참조는 오류 발생, 실행 중단)

not-in-memory -> bring to memory (아직 불러오지 않았으면, page fault)

Valid-Invalid Bit

페이지들이 메모리에 있는지 보조기억장치에 있는지 표시하기 위해서 valid-invalid bit가 사용된다.

v : valid, 해당 페이지가 메모리에 존재한다.

i : Invalid, 해당 페이지가 disk에 존재한다., page table의 초기 상태

Page Table When Some Pages Are Not in Main Memory

예를 들어 6번 페이지인 G가 페이지 테이블에서 valid-invalid bit가 i이면 페이지 G는 보조기억장치에 있다는 것을 의미합니다. 이렇게 페이지가 보조기억장치에 있는 상황을 Page Fault라고 한다.

Page Fault 처리 절차

첫 번째 참조 시에는 적재

해당 페이지가 유효한지 유효하지 않은 메모리 접근인지 판단하기 위해서, 내부 테이블를 확인
만약 페이지가 유효한 경우에는 그대로 처리, 유효하지 않은 페이지라면 페이지 폴트(Page Fault)이므로 해당 페이지를 보조기억장치에서 메모리에 적재
사용 가능한 메인 메모리 페이지를 확보 (Get empty frame)
디스크에서 페이지를 적재 (Swap page into frame)
페이지 테이블 수정 (Reset tables), 유효 비트 v로 설정 (Set validation bit)
다시 프로세스를 재개

Steps in Handling a Page Fault

특정 메모리를 접근하기 위해서 페이지 테이블을 참조
invalid이므로, 운영체제에 의해서 트랩(trap). 운영 제제 입장에서는 페이지 폴트가 일어났다고 판다 합니다.
운영체제는 Backing Store(보조기억장치)로 이동합니다.
보조기억장치에 있는 페이지를 물리적인 메모리의 비어있는 프레임에 적재합니다.
페이지 테이블에서 해당 페이지 번호의 valid-invalid bit를 i에서 v로 변경합니다.
프로세스 실행을 재개합니다.

Performance of Demand Paging

디스크로부터 Page 가져오는 것은 시간 오래 걸린다.

Page Fault Rate(페이지 폴트 비율) :

0≤p≤1.0

p=0, 페이지 폴트 없음 (전부다 적재되어있다. - 가상 메모리가 아님.)
p=1, 모든 페이지가 적재되지 않았다.

Effective Access Time (EAT)

EAT = (1-p) * 메모리 접근 시간 + p * 페이지 폴트 처리시간

Demand Paging EAT 구하기

메모리 접근 시간 = 200 nano sec

평균 page-fault 처리 시간 = 8 ms = 8,000,000 ns

EAT = (1-p) * 200 + p * 8,000,000 = 200 + 7,999,800 p

만약, 페이지 폴트 1000번 발생 시, EAT=8200ns. 메모리 접근 속도보다 41배 늦음.

page fault 처리는 많은 시간 소요가 필요하다. 따라서, page fault ratio를 낮추어야 한다.

ex) EAT를 220ns 이하로 하려고 할 때 p는?

200 + p*8,000,000 < 220

p < 20/8,000,000 = 1/400,000

즉, p <0.0000025이어야 한다.

What happens if there is no free frame?

메인 메모리보다 큰 프로세스를 다수 실행하면, 메모리 프레임이 부족하게 된다.

-> 페이지 교체 필요

page fault 수가 적게 발생하는 페이지 교체 알고리즘이 최고의 알고리즘

Page Replacement 페이지 교체

과도한 페이지 프레임 할당 방지

modify (dirty) bit 사용 (변경됐음을 표시하는 bit)

-> 변경되지 않은 페이지는 disk에 다시 저장할 필요 없다.

Need For Page Replacement

Basic Page Replacement

OS가 하는 일

원하는 Page의 위치 확인
free frame이 없으면 페이지 교체 알고리즘 수행. (victim(희생되는) frame 선택)
새로 생긴 공간에 Page 할당. Page Table, Frame Table 업데이트
프로세스 재시작.

Page Replacement Algorithms 페이지 교체 알고리즘

페이지 폴트 가작 적은 방법이 가장 이상적이다.

예시 ) Program이 5개의 page, 메인 메모리가 4개의 frame일 때

메모리 프레임이 많이 할당될수록, 페이지 폴트 수가 감소한다.

할당된 프레임과 페이지 폴트는 반비례한다. (메인 메모리 클수록 페이지 폴트 감소)

First-In-First-Out (FIFO) Algorithm

메모리 프레임이 늘었음에도, 페이지 폴트가 더 늘어나는 이상현상 발생 가능성이 있다.

FIFO ilustrating Belay's Anomaly

FIFO Page Replacement

Optimal Algorithm (가장 오랫동안 사용하지 않을 프레임을 교체)

실제 구현 불가, 성능 비교 목적으로만 사용

Optimal Page Replacement

LRU Algorithm - 가장 많이 쓰임

가장 오랫동안 참조되지 않은 것을 교체한다.

LRU Page Replacement

20 access, 8 hits, 12 faults

LRU Approximation Algorithms

LRU 구현 어려움 -> 근사 알고리즘 사용

Reference bits

처음 4bit 초기화 0000
참조될 때마다 맨 왼쪽 bit setup ex) 1000
주기적으로 shift right ex) 0100
가장 작은 reference bits를 가진 page 교체 (참조가 가장 오래된 페이지 교체)

Second chance

Clock replacement

Second-Chance (clock) Page-Replacement Algorithm

Counting Algorithms (참조된 횟수를 기록) - 잘 안 쓰임

LFU Algorithm : 참조 횟수가 가장 적은 페이지 교체
MFU Algorithm : 참조 횟수가 가장 많은 페이지 교체

초반 여러 번 참조 후 나중에 안 쓰는 페이지가 변경되지 않아서 잘 안 쓰인다.

Allocation of Frames (물리적 프레임 할당)

각 프로세스는 최소한의 메모리 페이지 프레임을 할당받아야 실행 가능하다.

fixed allocation : 고정 할당
priority allocation : 우선순위 할당

Fixed Allocation (고정 할당 - 한번 할당하면, 변하지 않음)

Equal allocation : 모두 동일한 프레임 할당 ex) 100 frames, 5 processes에서 각 프로세스 20 frame씩 할당.

Proportional allocation : 프로그램 크기에 비례해서 할당. (비율대로 할당)

ex)

Priority Allocation - 우선순위 고려한 할당

우선순위가 높은 프로세스에게 더 많은 frame을 할당하여 페이지 폴드가 적도록 배려한다.

자신에게 할당된 페이지에서 선택해서 교체
자신보다 낮은 우선순위의 프로세스의 프레임을 선택해서 교체

Global vs Local Allocation

Global replacement : 메인 메모리 전체에서 교체할 페이지를 선택 (다른 프로세스에 할당된 프레임을 뺏어와서 할당)
Local replacement : 프로세스에게 할당된 페이지 프레임 중에서 교체할 페이지를 선택

Thrashing

프로세스가 충분한 메인 메모리를 할당받지 못함

페이지 폴트 발생
프레임 교체
너무 잦은 프레임 교체 발생

=> CPU이용도 감소, OS는 CPU가 놀고 있다고 생각하여, 시스템에 프로세스 추가 실행.

메인 메모리 부족 현상 심화 -> 많은 페이지 폴트 발생한다.

Thrashing : CPU가 작업 처리 못하고, 충분한 메모리 공간 확보 못하여 필요한 코드와 데이터를 하드디스크로부터 다시 불러오는데 시간을 허비하는 상황

Demand Paging and Thrashing

locality (지역성) : 프로세스가 현재 실행 중인 메모리 주변을 자주 참조하는 특성이나 메모리 영역을 말함

현시점의 locality 영역을 커버하는 페이지들이 주기억 장치에 적재되어야 원활히 실행될 수 있음.

Locality model

시간 구역성 (Temporal locality) : 프로세스의 locality는 시간에 흐름에 따라 전이
공간 구역성 (Spatial locality) : locality는 서로 중복될 수 있다. 100번지를 참조 중이라면 99번, 101번지도 사용할 가능성 있다.

thrashing 발생 이유

실행 중인 프로세스의 locality 영역 합이 총 메모리 용량보다 큰 경우, 각 프로세스는 충분한 메모리 공간 확보 불가.

-> thrashing 발생

해결책

프로세스 몇 개를 중단시켜 메인 메모리 공간을 확보해야 한다.

Working-set Model

Working set : 특정 시점의 프로세스 locality를 포함하는 페이지의 집합

working set 주기억 장치에 유지되어야 모든 프로세스들이 원활히 실행된다는 이론

모든 프로세스의 working set의 합 = 요구되는 frame
필요한 프레임이 실제 메모리보다 큰 경우 => thrashing 발생
thrashing 발생 시, 프로세스 일부 중단시키거나 swap out 시킨다.
working set을 적재하기 위한 충분한 메모리 공간 확보.
working set은 실행 시간에 따라 크기가 변화한다.

Page-Fault Frequency Scheme (적절한 수의 frame 할당 기법)

Working Set model 보다는 더 직접적인 해결책.

받아들일 수 있는 페이지 폴트 비율을 사전에 정한다.

실제 페이지 폴트 비율이 너무 낮으면, 프로세스 프레임을 더 적게 할당
실제 페이지 폴트 비율이 너무 높으면, 프로세스 프레임을 더 많이 할당

Other Considerations (다른 고려사항)

Prepaging : 사전에 페이지를 가져옴.
Page size
TLB reach : TLB에 의해 번역되는 주소의 범위 (넓으면 좋다.)
Program structure
IO interlock and page locking
Inverted page table

기존의 페이지 테이블에 각 프로세스의 가상 주소 공간을 물리적 공간에 매핑. 각 프로세스는 별도의 페이지 테이블을 가진다.

Inverted page table에서는 컴퓨터 시스템에 1개의 페이지 테이블. 주 기억 장치의 frame을 기준으로 프로세스와 가상 페이지를 매핑 정보로 저장하는 페이지 테이블

프로세스 증가와 관계없이 페이지 테이블 크기가 고정된다. (메인 메모리 사이즈에 따라)

Inverted page table

일반적인 페이지 테이블

각 프로세스의 가상 페이지 -> 물리적 페이지로 매핑
각 프로세스마다 페이지 테이블 존재

inverted page table

메모리에 적재된 page -> 프로세스 id와 가상 페이지로 번역
프로세스 id와 페이지 번호로 검색 -> 검색되면 frame 번호 반환 -> 검색 안되면, page fault (페이지 테이블이 시스템에 1개만 존재)

Other Issues - Prepaging

프로세스 시작할 때 많은 페이지 폴트 발생 (처음 참조 시)

페이지 참조 전에 일부 페이지를 사전에 적재해 둔다. (prepaging)

fragmentation : 맨 마지막 페이지의 내부 단편화를 줄이려면 작은 페이지

table size : 페이지 테이블 크기를 줄이려면 큰 페이지

IO overhead : 대용량 디스크 IO 하는 것이 유리하므로 큰 페이지

locality : 지역성에 맞추어 메모리에 적재하려면 작은 페이지

number of page faults : 큰 페이지는 페이지 폴트 수를 줄인다.

TLB size : 큰 페이지는 페이지 수를 줄인다.

Ohter Issues - TLB Reach

TLB Reach : TLB에 의해 접근 가능한 메모리 영역. 넓은 것이 좋다. 빠른 주소 번역이 가능하기 때문

TLB Reach = (TLB Size) * (Page Size)

페이지가 커지면 TLB reach도 증가.

IO interlock

IO interlock : 어떤 페이지는 반드시 메인 메모리에 lock 되는 경우가 있다. 이러한 페이지는 디스크로 쫓겨나지 않는다.

Pining : 페이지를 고정하여 locking 할 수 있다.