OS : 가상 메모리(virtual memory)

프로세스 일부만 메모리에 적재하여 실행하는 장점

프로그램 크기가 실제 메모리 크기에 제한받지 않는다.

멀티 프로그래밍 정도를 높여 cpu이용율, 처리율을 높인다.

swap I/O양이 적어 각 프로그램이 빠르게 실행된다.

가상 메모리

작은 물리 메모리로 큰 가상 기억 장치를 제공

overlay^[각주:1]를 사라지게 함

주로 요구 페이징(demand paging)으로 구현

요구 페이징(demand paging)

필요한 페이지만 주 기억장치에 적재

페이지가 메모리에 있는지 디스크에 있는지 valid/invalid bit로 표시(1=valid 0=invalid)

메모리에 없는(invalid) 페이지를 참조하려 하면 페이지 부재 트랩(page-fault trap)^[각주:2] to OS

순수 요구 페이징(pure demand paging)

아무 페이지도 가져오지 않은 상태에서 프로세스 실행한다.

항상 페이지 부재 트랩 발생

HW지원

페이지 테이블 : valid/invalid bit 포함

보조 기억 장치

SW지원

명령어 패치시 페이지 부재가 발생하면 페이지를 적재한 후 다시 그 명령어를 패치하도록 한다.

요구 페이징의 성능(performance of demand paging)

p = 페이지 부재 확률

ma = 메모리 접근 시간

유효 접근 시간 = (1-p)*ma + p*페이지 부재 시간^[각주:3]

페이지 교체(page replacement)

페이지 부재가 일어났지만 메인 메모리에 빈 프레임이 없을 경우 가능한 조치

과정

디스크에서 페이지 위치 확인

가용 프레임 찾기

가용 프레임이 있으면 사용

없으면 희생 프레임 선정(페이지 교체 알고리즘)

희생 프레임을 디스크에 기록

부재 페이지를 메모리에 적재

프로세스 재시작

페이지 교체 알고리즘(page replacement algorithm)

페이지 부재율이 가장 낮도록 하는 것이 목표

일반적으로 프레임 수가 증가하면 페이지 부재가 줄어든다.

선입선출 알고리즘(FIFO page replacement)

가장 오래된 프레임을 희생시키는 알고리즘

FIFO 큐를 사용하여 구현

구현은 쉬우나 성능이 좋지 않다.

belady의 변이(belady's anomaly)가 발생(프레임 수가 증가해도 페이지 부재가 줄어들지 않는다.)

최적 알고리즘(optimal page replacement)

가장 오랫동안 사용되지 않을 프레임을 희생시키는 알고리즘

belady의 변이가 발생하지 않는다.

미래를 예측해야하기 때문에 구현이 어렵지만 성능이 좋다.

최근 최소 사용 알고리즘(LRU page replacement)

가장 오랫동안 사용되지 않은 프레임을 희생시키는 알고리즘

최근 과거를 미래의 근사치로 사용

성능이 좋아 자주 사용되며 리눅스에서 사용한다.

HW자원이 필요

계수기(counter) : 논리 클럭 또는 계수기를 이용하여 페이지 테이블에 추가한 time-of-use field값이 최소인 것을 대치

스택(stack) : 페이지 번호들의 스택 유지(double linked list) top에는 가장 최근에 사용한 페이지 bottom에는 가장 오래전에 사용한 페이지

LRU 근접 알고리즘(LRU approximation page replacement)

참조 비트 추가 알고리즘 : 8bit shift register를 이용해 참조되면 최상위 비트에 1을 추가하고 타이머 인터럽트마다 오른쪽으로 shift

2차 기회 알고리즘 : 참조 비트를 추가하여 시작할 때 전부 0으로 reset하고 참조될 때 마다 1로 set한다. 후보 큐에서 하나씩 꺼내면서 참조 비트가 0이면 교체하고 1이면 참조 비트를 0으로 reset하면서 다시 큐에 삽입한다.

개선된 2차 기회 알고리즘

계수 알고리즘(counting page replacement)

LFU : 계수값이 최소인 프레임 교체

MFU : 계소값이 최대인 프레임 교체

페이지 버퍼링 알고리즘

희생될 프레임을 디스크에 기록하기 전에 새로운 페이지를 읽고 희생될 프레임은 빈 프레임의 pool에 더한다.

변경된 프레임 정보를 기억하고 있다가 필요하면 디스크까지 가지 않고 pool에서 바로 사용한다.

프레임의 할당(allocation of frame)

single-user : 페이지 부재가 일어나면 그냥 교체

multi-user(multiprogramming) : 여러 프로세스가 메모리에 있기 때문에 그냥 교체할 수 없다.

최소 프레임 수

직접 1주소 형식 : 2프레임

간접 1주소 형식 : 3프레임

전역 대 지역 할당

전역대치 : 대치할 프레임을 메모리 전체에서 선택->프레임 수 가변

지역대치 : 대치할 프레임을 자신의 영역에서 선택->프레임 수 고정

프레임 할당 알고리즘(frame allocation algorithm)

균등할당

m = 프레임 수

n = 프로세스 수

m/n개 할당

비례할당

프로세스 크기에 비례

우선순위에 비례

우선순위 + 크기에 비례

1. 저장장소가 중첩되는 경우 [본문으로]
2. 필요한 페이지를 디스크에서 메모리로 적재시키고 실행하려 했던 명령을 실행한다. 과정 [참조 - 트랩 - 페이지가 보조 기억 장치에 있음 - 부재 페이지를 가져옴 - 페이지 테이블을 재설정 - 명령어를 재시작] [본문으로]
3. 구성 요소 [페이지 부재 인터럽트 처리, 페이지를 디스크로 부터 판독, 프로세스 재시작] [본문으로]