Virtual Memory
Background
코드를 실행하려면 메모리 위에 올라와 있어야 하는데 전체 프로그램은 거의 사용이 안됨
그래서, 전체 프로그램이 메모리에 로드될 필요는 없음
Virtual Memory
user logical memory를 physical memory로 부터 분리함
logical memory space의 일부만 physical address space로 들어감
Benefits
address space가 프로세스끼리 공유가능함
더 많은 프로그램을 병렬실행 가능
프로세스 로드 및 스왑에 필요한 I/O가 감소함
Virtual Address Space
가상 메모리의 주소 공간으로 연속적인 주소를 사용함
프로세스가 메모리에 어떻게 저장되어있는지에 대한 logical view임
Demand paging과 Demand segmentation으로 구현됨
Demand Paging
필요할때 storage에서 memory로 페이지를 가져오는거
잘못된 참조면 중단, 메모리에 없으면 메모리에 가져오기
swapping을 하는 page system이랑 비슷한 구조임
page table entry마다 valid-invalid bit을 달 수 있음
v->memory에 있음
i->memory에 없음
주소 변환 중 valid-invalid bit가 i면 page fault임을 의미함
Handling Page Fault
- 페이지에 대한 참조를 할 때 페이지에 대한 첫 참조면 운영 체제에 trap이 생김 -> page fault
- 운영 체제는 다른 테이블을 확인하여 결정함
잘못된 참조면 중단 or 그냥 메모리에 없음 - free frame 찾기
- 예약된 디스크 작업을 통해 page를 frame으로 전환
- page를 표시하도록 table을 재설정합니다
valid-invalid bit = v - page fault를 일으킨 명령어 재시작
Performance of Demand Paging
Page Falut Rate=p라고 하면 0<=p<=1임
p==0이면 page fault가 없는거, p==1이면 모든 참조가 fault인거
Effective Access Time(EAT)
(1–p) x memory access(address translation+page access time)
+p(page fault overhead+swap page out+swap page in)
swap page out은 free frame이 없는 경우에만 계산함
Copy-on-Write (COW)
부모 및 자식 프로세스가 메모리에서 처음부터 동일한 페이지를 공유하도록 허용함
두 프로세스 중 하나가 공유 페이지를 수정하면 페이지 복사
Free-Frame List
page fault시 원하는 페이지를 storage에서 memory로 가져오기 위한 free frame들의 리스트
OS는 보통 zero-fill-on-demand를 통해 free frame을 할당함
할당되기전에 frame의 내용을 0으로 채우는거
시스템이 시작하면 모든 메모리들을 free frame list에다가 놓음
Page Replacement
free frame이 없으면 안쓰는 페이지를 찾아서 정리하는 page replacement가 일어남
오버헤드를 줄이기 위해 dirty bit을 사용하기도함
dirty->수정 여부
기본적으로 아래의 단계를 따름
1. 디스크에서 원하는 page 찾기
2. free frame 찾기
있으면 씀
없으면 victime frame을 택하기 위한 page replacement 알고리즘을 돌림
dirty면 victime frame을 디스크에 작성
3. 원하는 page를 free frame에 가져오고 frame table 업데이트
4. trap을 유발한 명령어 재시작
총 2개의 page transfer이 가능함
Page Replacement Algorithms
Frame-allocation algorithm은 프로세스마다의 프레임 개수를 정함
Page-replacement algorithm은 낮은 page fault rate을 지향하며 어떤 프레임이 교체될지를 정함
알고리즘은 특정 메모리 참조 문자열(reference string)에서 실행하고 해당 문자열의 page fault 수를 계산해 평가함
FIFO Page Replacement
가장 오래된거를 교체
밑에 처럼 frame 개수를 추가하다보면 더 많은 page fault를 야기할 수 있음 -> Belady’s Anomaly
Optimal Page Replacement
가장 오랫동안 안 쓰일 거를 교체
실제로는 적용이 안 되고 다른 알고리즘들의 성능 평가를 위해 쓰임
LRU Page Replacement
가장 오랫동안 안 쓰인 거를 교체
FIFO보다 낫고 OPT보다 안 좋음
무난히 좋아서 많이 씀
Counter 구현
모든 page entry마다 clock을 기반으로한 counter를 둬서 counter가 젤 적은 page를 교체하는 방식
테이블 검색이 필요함
Stack 구현
page number의 스택을 이중 링크 형식으로 구현
페이지가 참조되면 top으로 이동해야하며 6개의 포인터를 바꿔줘야함
업데이트 비용이 비싸긴 한데 버릴 거를 bottom에서만 꺼내면 되니 간단한 구조
LRU Approximation Algorithms
Reference bit
참조 여부를 나타내는 bit
초기값은 0이고 읽쓰를 당하면 1이 됨
Second-chance algorithm
FIFO 기반인데 하드웨어 기반의 reference bit을 추가한 구조
0이면 그냥 교체하고 1이면 비트를 0으로 바꾸고 한 번 더 기회를 줌
clock replacement임(한 바퀴씩 순회)
Global vs. Local Replacement
Global Replacement
프로세스는 모든 프레임 세트에서 교체 프레임을 선택함
다른 프로세스에서 프레임을 가져올 수 있음
프로세스 실행 시간이 달라지고 처리량이 많아지지만 일반적임
Local Replacement
얘는 다른 프로세스가 아니라 본인의 할당된 프레임 세트에서 선택함
프로세스 성능과 page fault가 일정한데 memory util이 낮아짐
Thrashing
프로세스가 높은 page fault rate로 인해 바쁜 상태를 말함
프로세스에 충분한 페이지가 없으면 발생
낮은 CPU 사용률로 인해 OS는 멀티프로그래밍의 정도를 늘려야한다고 생각해서 다른 프로세스들을 들여옴
demang paging이 잘 작동하는 이유? -> Locality model
thrashing이 일어나는이유? -> process가 필요한 메모리 크기가 총 메모리 사이즈보다 커서 그럼
그래서 우선순위 page replacement를 쓰고 process마다 frame할당을 제한해야함
Working-Set Model
Locality를 표현하기 위한 model임
Δ = working-set window = 고정된 페이지 참조 수
WSSi(Working Set Size of Process Pi) : 최근 Δ에서 참조된 page 개수
Δ가 너무 작으면 충분한 local 참조X
Δ가 너무 크면 너무 많은 local 참조
Δ가 무한이면 전체 프로그램 참조
D : 모든 WSSi의 합으로 총 demand frames를 말함
D>m이면 Thrasing이 발생하고 하나의 프로세스를 중단하거나 swap out함
Page-Fault Frequency (PFF)
허용가능한 page-fault frequency를 정하고 local replacement policy를 쓸 수 있음
actual rate가 낮으면 프로그램이 frame 손실난거임
actual rate가 높으면 프로그램이 frame 이득본거임
WSS보다 직관적인 접근!
Allocating Kernel Memory
user process뿐만 아니라 kernel도 메모리를 할당 받아야함
보통 free-memory pool에서 할당을 받고 다양한 사이즈의 구조를 메모리에 요청함
몇몇 kernel memory는 연속적이어야 함
Buddy System Allocator
physical contiguous page로 구성된 fixed-size segment로부터 메모리를 할당함
power-of-2 allocator를 이용함
청크가 요청과 알맞은 2의 거듭제곱 단위를 가짐
사용하지 않는 청크를 큰 청크로 빠르게 통합할 수 있어 좋지만 fragmentation이 생김
예를 들어, 21KB짜리 요청이 들어오면 저렇게 32KB까지 나눠서 할당함
Slab Allocator
Slab은 하나 이상의 물리적으로 연속된 page임
Cache는 하나 이상의 slab으로 이루어짐
kernel 데이터 구조마다 하나의 캐시를 가지고 각 캐시는 object로 채워짐
캐시가 생성되면 object들을 free로 채우고 데이터 구조가 저장되면 used로 표시함
fragmentation이 없고 빠른 메모리 요청을 만족해서 좋음
