ch8 virtual memory(VM) #운영체제OS #가상메모리

Virtual Memory 🐇¸.•*¨*•¸.•*¨*•¸.•*¨*•¸.•*¨*•

해당 자료는 강의 학습자료입니다.'

https://www.youtube.com/watch?v=YCfP9I4K-8Y 를 참고하였습니다.

---

기본적으로 swap in, out으로 하드디스크를 실제 메모리처럼 사용하는 방식이다. overhead가 발생하여 효율적이지 않을 수 있는데 지역성(locality)를 이용하여 성능을 높일 수 있다.

 

 

Hardware and Control Structures

Paging & Segmentation

Memory management

1) All memory references within a process are logical addresses :

모든 메모리의 참조는 논리 주소를 사용한다. (변환)

- process may be swapped in and out of main memory. : 다른 위치에 로딩이 될 수도 있다.

2) A process may be broken up into a number of pieces : 한 프로세스를 여러 블록으로 나눈다.

- Process don't need to be contiguously located in main memory.

꼭 반드시 연속적으로 위치할 필요는 없다.

 

It is not necessary that all of the pages or segments of a process be in main memory during execution.

실행에 필요한 블럭만 메인 메모리에 가져오자.

 

If the piece that holds the next instruction to be fetches and the piece that holds the next data location to be accessed are in main memory,

- then at least for a time execution may proceed

 

OS begins by bringing only one or a few pieces : 시작할 때 몇개의 블록만 할당한다. 한동안은 실행 가능하다.

To include the initial program piece and the initial data piece

Resident set : Portion of process that is in main memory : 이미 시점에 메모리에 로딩되어 있는 부분

 

when address is needed that is not in main memory : 참조해야하는 주소가 resident set에 없다면?

-> interrupt 발생

 

OS puts the interrupted process in a blocking state : 일단 블록 (실행할 수가 없음)

OS issues a disk I/O Read request

 

which causes the OS to place the affected process in the ready state

- when it runs again, required data is in memory.

 

계속 interrupt가 발생하는데 효율적일까? 

-> 더 많은 프로세스를 메인 메모리에 올릴 수 있어 활용도를 높일 수 있다.

-> main memory 보다 큰 프로세스도 실행할 수 있다.

 

 

 

Partial Loading

main memory may be full : 메모리가 가득 찬 경우

when ths OS brings one piece in, it must swap one piece out

swap out을 진행해야 하지만, 방금 막 들어온 메모리를 out 시키는 경우?

thrashing : a state in which the processor spends most of its time swapping pieces rather than executing user instruction CPU 가 명령어 수행하지 못하고 swapping 하는데만 시간을 더 쓰는 경우

 

 

 

Principle of Locality

page 참조를 예측할 수 있어 VM 효율성을 높일 수 있다. swap out 을 어떤 것을 해야할지 예측하여 어떤 메모리를 부분적으로 로딩할지 선택할 수 있어서 interrupt 나 I/O 요구를 줄일 수 있기에 VM 효율성을 높일 수 있다.

 

 

 

Paging

Page :

 

 

page table을 만들어 정리한다.

page number + offset 외에도 들어오는 정보 중 4가지는

 

- Present Bit : 메인 메모리에 현재 있는지?

- Modify Bit : 내용이 수정되었는지?

- Other Control Bits : Shared? protect?

- Frame number

 

 

 

 

 

 

 

변환 과정

1. virutal address가 들어오면 페이지 넘버와 오프셋이 있다.

 

2. 페이지 넘버를 이용해 페이지 테이블의 index를 찾는다.

 

3. Frame number가 뒤에 있는 데 이를 + offset이랑 합쳐 계산하여 실제 메모리를 찾아낸다.

 

 

 

 

 

 

 

 

Page Table Size : 내가 몇 개나 계산할 수 있을까? 얼마나 크게 만들어야 하나?

Tha amount of memory devoted to page tables

- could be unacceptably high example :

 Each process can have up to 2^31bytes(2GB) of virtual memory // 최대 2기가 

Using 2^9bytes(=512B) page: // 페이지 크기

2^22 page table entries are required per process // 나눈 2의 22개의 page table이 이용 가능

 

To overcome this problem

- Most virtual memory schemes store page tables in virtual memory rather than real memory(n>m)

- when process is running, part of its page table is in main memory // 부족해서 가상 메모리에 이를 저장해야하나?

 

Page table sturcture (확장된 구조)

• Hierarchical page scheme : 2단 계층구조 : 일종의 directory만 가지고 있으면 되어 더 큰 메모리를 가지고 있을 수 있다.
  • 1st level root page table : main memory
  • 2nd level table : virtual memory
• 없으면 page fault(context switching)하고 가져와야한다. 

 

• - Hash / Inverted page tables : Hash 값을 사용한 구조

 

• Inverted Page Table
  • Page# of a virtual address ia mapped into a hash value
  • - Hash value points to inverted page table
  • Hash Function

 

 

 

 

 

 

 

 

 

Translation Lookaside Buffer (TLB)

Each virtual memory refenrnce -> two physical memory accesses

항상 물리 메모리에 두 번 접근하는데 

1) page table

2) real data

- doubling the memory access time

 

To overocme the memory access time

- uses special high-speed cache called a translation lookaside buffer (TLB); // 특별한 cache를 사용

- contains those page table entries that have been most recently used.

가장 최근에 참조된 table 항목을 가지고 있다.

 

TLB를 먼저 확인해서

있으면 -> 바로 사용

없으면 page table로 넘어감

 

page table에서

있으면 -> TLB 업데이트

없으면 -> page fault

context switching

 

 

 

 

 

 

TLB : Associative mapping

Processor is equipped with HW

That allows it to interrogate simultaneously a number of TLB entries to determine if there is a match on page number.

여러개의 TLB를 동시에 확인해야하는 경우?

 

TLB에 페이지 넘버와 함께 frame 번호까지 들고 있을 수 있어서 동시에 접근할 수 있다. TLB와 Cache가 같이 상호작용하는 예시가 윗 그림인데, TLB에 hit 하면 바로 아래로 내려와 Real address에 접근가능하다. TLB에 없는 경우 miss로 page table 에서 값을 찾아오게 된다. 그 이후 cache operation이 진행하게 되는데 cache에도 값이 있다면 값을 바로 사용하지만 없는 경우는 이를 update 하게 된다.

 

 

Page Size

smaller the page size

// page size가 작을 수록

 

- Lesser internal fragmentation // 내부 단편화가 줄어듭니다. (paging기법)

- but more pages are required per process // 페이지가 더 많이 필요로 한다.

- More pages are process means larger page tables // page tables의 개수가 늘어나 가상메모리를 이용해야 할지도 모른다.

page table , page에 없으면 두 번 falut가 발생할 수도 있다.

 

각 프로세스에 할당된 메모리양 -> 하드웨어를 설계할때 결정되는 page의 크기에 따라 달라질 수도 있다.

 

Large Program을 실행할때 :

참조 지역성이 떨어진다. -> (멀티스레드)여러 주소를 뛰어넘을 우려가 있다.

따라서 컴퓨터마다 page size가 다른데, 유연성을 가지게 설계하였다.

적은 수의 page에 mapping이 된다면, graph에 따라서 page size를 설정하면 된다.

thread stack과 같은 경우 page size를 작게하면서, 여러개의 page를 참조하는게 유리하다: 다양한 참조 부분 가져오기

운영체제는 하나만 지원하지만, 하드웨어는 여러 사이즈를 지원한다.

 

 

Thrashing Diagram

If a process does not have 'enough' pages, the page-fault rate is very high

// 프로세스를 실행하려면 page가 충분해야한다. 아니면 page-fault가 발생할 가능성이 높다.

-> Low CPU utilization

-> OS thinks that it needs to increase the degree of multiprogramming

-> another process added to the system.

CPU 사용률이 증가하다가 멀티프로그래밍이 한계에 도달하면?

memory 부족 더 많은 프로그램 -> page 개수가 줄어듬 -> 필요한 부분이 main memory 에 없음 ->page fault 발생 -> disk I/O를 요청

 

page fault 발생시 disk I/O를 요청

기다리고 있기 때문에 전체적으로 CPU 사용률이 뚝 떨어진다.

-> 다음 프로세스를 더 실행

-> I/O 요청, 더 떨어진다.

 

 

-> thrashing 발생

:memory가 부족하여 swap in out을 계속 반복하여 연산을 하지 않는 상태

 

지역성 모델을 기반으로 paging이 동작하는데, 프로세스는 다른 지역으로 이동할 수 있고 겹쳐질 수도 있다.

thrashing의 발생 원인 : 내가 참조할 필요한 size가 memory size보다 큰 경우

 

 

 

 

Segmentation

address space의 부분을 나눌 수 있다. 여러개의 segments로 나누는데 사이즈가 다양하다.

 

- simplifies handling of growing data structures

장점 : 덩어리채로 쓰는 것이 아닌 공간을 분할해서 사용한다. / / 큰 프로그램을 실행할 수 있다.

개발자가 자료구조를 설계하는데 특정 segment를 배정한다거나, 운영체제가 이 segment를 필요하면 더 늘리고, 더 줄이는 경우가 필요하기 때문에 사용한다.

 

전체 프로그램의 영향을 주지 않고 segment만 늘리면 된다.

인접 공간이 없다면, 더 큰 공간으로 이동하기도 한다. swap out

 

- allows programs to be altherd and recomplied independtly

부분만 컴파일을 다시할 수 있다.

- lends itself to sharing data among processes

프로세스 간에 segment를 공유할 수도 있다.

-lends itself to protection

보호 비트를 설정해서 보호할 수도 있다.

 

 

Segment Organization

paging과 다르게 length가 추가 되었다.

 

paging : external fragmentation 이 없음 (외부단편화), 내부 단편화가 있다. 메모리를 효율적으로 사용할 수 있다.

고정 크기로 사용하기 때문에, 프로그래머는 알 수 없지만 투명하게 paging 기법을 사용한다.

 

segment : internal fragmentation

프로그래머가 사용하기엔 직관적이다. 확장성도 좋으며 모듈화도 가능하다.

 

 

Combined Paging & Segments

 

address space

 

main memory (frame) 의 크기와 똑같은 page 크기로 나눈다. (segment) 크기는 page보다 커서 여러 page를 사용할 수도 있다. segment도 page를 할당 받아 쪼개진다.

 

개발자 입장에서 보는 주소와 system에서 보는 주소가 다르다.

프로그래머 입장에서 logical address가 어떻게 보이나면

system 관점에서 보는 segment 

segment 마다 page table 이 있다.

 

 

 

Protection and Sharing : Segment 의 이점

 

 

 

Operating System Software

Policies for Virtual Memory : minimize page faults.

단계별로 어떤 정책을 쓰는지

 

메모리 매니저

 

Policy for virtual memory (fetch, placement, replacement)

1. fetch Policy : 언제 main memory로 loading 할지 결정

- demand paging : 요청이 오면 fetching : page fault 가 일어나서 점점 더 많은 page들이 fetch되어 시간이 지나면 안정화가 된다.

- prepaging : 하드디스크의 물리적인 특징에 대해서 기구적으로 시간이 오래걸리는 하드디스크, 미리 가져다 놓고 처리하기,

ineffective if extra pages are not referenced

가져다 놓고 참조 안하면 무용지물. 지역성 기반 + 디스크의 특성

 

2. Placement Policy 어느 위치에 배치를 할 것인지 : segment 에선 중요하다. / 분산시스템, 멀티프로그래밍 / 참조할 때 거리가 달라지기 때문에

 

paging 기법에서는 그렇게 중요하지 않다. 메모리에 접근하는 하드웨어의 기능, 어디에 배치를 하던 상관이 없다.

 

3. replacement policy : 시간 차이가 많이 날 수 있다. / 가장 덜 쓸 거 같은 page를 제거한다.

 

 

static paging algorithms

- Random Replacement : random

- Optimal : 최적 / 구현 불가능

- Least Recently Used (LRU) : tag사용 오래된 것을 바꿈

- Least Frequently Used (LFU) : 가장 적게 사용하는 것을 바꿈

- First In First Out (FIFO) : 순환 해서 바꿈

 

Dynamic paging algorithm

- working Set model

 

 

- Random Replacement : random

 

 

stream 정보가 전혀 성능에 영향을 끼치지 않음.

결과가 매번 바뀔 수도 있다.

 

 

 

 

 

 

 

 

 

- Optimal (Belady's Optimal Algorithm)

 

가장 미래에 멀리 있는 page를 교체한다.

 

가장 page fault가 적지만

운영체제가 미래의 상황을 알지 못하므로 구현이 불가능하다. 따라서 평가 기준으로 사용한다. (최적의 상황)

FWD(forward distance): 앞 거리

 

 

 

 

 

 

  

 

 

 

 

 

 

 

 

- Least Recently Used (LRU) :

가장 오랫동안 사용하지 않았던 page를 교체한다.

가장 오래전에 참조했던 page를 기억 (시간)

 

지역성의 원리를 사용한다. -> tag(최종 참조시간)

BKWD(t) = 지난 거리

 

tag 를 매번 업데이트 하면 하드웨어에 overhead가 발생한다.

 

Frame을 하나만 늘려도 성능이 매우 좋아진다.

 

 

 

- Least Frequently Used (LFU)

적게 참조된 것을 선택

같으면 Random으로 선택

FREQ(x)

 

 

 

 

 

 

 

 

 

 

- First In First Out (FIFO) : 순환 버퍼처럼 다룬다. (제일 쉬운 방법 Round Robin)

- 연결한 포인터만 있으면 쉽게 가능하다.

- 구현이 쉽다.

- 가장 오래전에 선택된 페이지를 선택하기 때문에 순환 buffer을 사용한다.

- AGE(x)

 

 

 

 

 

 

 

 

 

 

 

벨라디의 역설 : Frame 개수를 늘렸는데 성능이 좋아지지 않는다.

 

stack alogorithms : frame을 늘렸을 때 포함관계가 성립한다. -> 벨라디의 역설이 발생하지 않고 frame을 늘리면 성능이 좋아진다.

 

LRU : stack

FIFO : 아님

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Clock Policy ( overhead 가 적은 LRU는없을까?)

Sets of frames is considered to be a circular buffer

each frame has use bit

The use bit is set to 1 -> page fault 가 발생

use bit이 0인 프레임을 체크한다.

-> (fetch됨)1을 0으로 변경

-> 0을 찾으면 그다음에 포인터 연결

 

한바퀴 도는 경우를 생각해야한다.

 

 

 

 

결국 frame 수를 많이 늘리면 성능은 좋아진다.

엄청난 비용이 소요된다.

 

 

 

 

 

 

 

 

 

Page buffering

 

page fault가 발생시 list를 검사를 한다.

-> 필요한 page가 메모리에 있다면 page table에서 p bit을 set을 한다.

-> 필요한 page가 메모리에 없다면, Free page list에 덮어쓴다. (buffer)

 

따라서 바로 사용하는 것이 아닌 리스트를 관리를 한다. 두 리스트가 있는데

Free page list : 페이지를 추가 (포인터만 가지고 있는 리스트)

Modified page list : 변경 사항을 추가

 

Note that the page is not physically moved about in main memory

논리적으로 움직이는 것이 아닌 포인터가 움직인다.

 

내가 가져온 page에 있는 내용이라면 사용한다.

page table에서만 포인터를 제거하고, bit=0, free list에 연결.

 

장점: 비용을 줄일 수 있다.

 

Dynamic Page Frames Allocation

단점: 메모리를 얼마나 할당 받았느냐에 따라 fault가 달라진다. -> 예상보단 fault이 줄지는 않는다. -> dynamic page frame적용

static paging -> number of required page is fixed, no adjusting the allocation.

Thrashing : 너무 많은 page fault로 인해 발생한다. (계속 교체)

 

필요한 만큼 frame을 할당한다.

 

working set algorithm (가장 현대적인 모델)

fault가 수용 가능한 정도를 감안한다.

window of time : 일정기간에 사용하는 page, 계속 바뀐다.

 

 

window 크기(최대 프레임 수)만 고려하면 되어 LRU 보다 overhead 가 적다.

 

 

 

 

 

 

 

 

그렇다면 언제 modified page의 수정사항을 disk에 적용할까?

Cleaning Policy

언제 swap out을 할까?

Demand cleaning : 요청이 오면, fetch가 먼저 일어나고, modified page를 적는다.

2번 처리해야하기 때문에 CPU 사용량이 좋지는 않다.

 

Precleaning : 요청되기 전에 batch에 한 번에 쓴다.

 

page buffering을 적용하면 더 효율적이다.

교체되는 페이지도 free와 modified(한번에 일괄처리) 로 나눈다.

free list를 계속 재활용 할 수 있기 때문에 효율적이다. disk 까지 갈 필요가 없다.

 

 

Load Control : determines the number of processes : 프로세스의 개수를 정한다.

너무 적은 프로세스 : swapping에 시간이 너무 많이 사용

너무 많은 프로세스 : thrashing이 발생

 

모니터링을 하고 있다가 use bit가 너무 많은 1이 나와 page fault 가 발생하면 : page를 늘린다.

use bit가 0인 사용하지 않는 page가 많이 발생하면 page를 줄인다.

 

 

L = S 값이 같도록 조절하여 프로세서의 사용을 최대화 한다.

L = page fault meat time

S = time to process a page fault

 

 

 

- 낮은 우선순위

- fault가 발생한 프로세스

- 가장 최근에 activated : working set이 작아 loading 한 정도가 적다.

- 가장 작은 resident set : 메모리에 로딩된 정도가 가장 적다. // 지역성 사용시 불리

- Largest Process : 과도한 메모리는 제거하면 효율적이다.

- Process with the largest remaining execution window : 남은 window가 많은 것