[운영체제] 9장 Virtual Memory Management

개념 – swapping(물리 메모리에 있는 정보와 하드디스크 영역에 있는 정보를 올렸다 내렸다 하는 방식) -> 그래서 마치 메모리가 무한대인 것처럼 동작함

 

Background

Virtual Memory의 가장 기본적인 개념은 logical한 메모리와 물리주소를 분리를 해서 생기게 됨(변환 방법은 8장에서 배움)

이러한 메모리를 변환하는 과정에서 이점이 있음 -> Virtual Memory는 무한하다.

>Demand paging

>Demand segmentation

이러한 Virtual Memory는 위와 같은 기법들을 구현을 해서 만들 수 있음

그러나 결국 앞에서 배운 것과 같이 segmentation한 이후 paging을 함

-> 따라서 Virtual Memory의 핵심은 swapping을 하는 것임

-> 그러나 swapping을 하는 대상이 page이기 때문에 paging에 대해서만 이야기해도 충분함

 

Virtual Memory 과정 예시

무한한 메모리 사용

 

프로그램을 실행시키면 모든 정보가 물리 메모리에 올라와야 실행되는 구조인데 실제로 프로그램을 실행 시켜보니까 현재 프로그램이 실행되고 있는 부분은 메모리에 올라가 있는 정보 중 일부였음 -> 따라서 메모리에 사용하지 않는 부분은 secondary storage에 저장을 했다가 사용을 하게 되면 그때 다시 불러오는 방법으로 사용을 하게 됨.

 

Virtual Memory의 작동 방식 -> 처음에는 어떠한 데이터도 올려놓지 않고 논리주소만 할당이 되어 있는 상태임 -> 프로그램에서 어떠한 프로세스를 수행시키려면 그 프로세스의 페이지는 현재 하드디스크에 저장이 되어있기 때문에 그 페이지를 읽어서 메인 메모리에 올림

-> 이렇게 필요한 페이지만을 올려서 사용하는 방식을 demand paging이라고 함

 

 

demand paging

이런 demand paging을 사용하는 이유 – 페이징들은 locality속성을 가지고 있기 때문이다.

>Temporal locality – 시간단위로 locality(지역성)을 확보하는 것, 가장 최근에 사용한 것을 메모리에 보존하는 것

>Spatial locality – 해당 페이지 근처에 있는 것이 사용될 확률이 높다고 판단을 하고 그러한 것들을 보존시켜두는 것

 

 

Valid-Invalid Bit

Demand Paging – 프로세스가 요구를 하였을 때 메모리에 올려두는 기법

-> 구현 – Valid-Invalid(8장에서 memory protection 때문에 사용된다고 배웠음) Bit를 사용을 해서 구현을 함

그림은 앞부분은 전부 valid하고 뒷부분은 모두 invalid하다는 것을 나타냄

-> 그런데 왜 굳이 이렇게 하나? VM를 위함 -> 페이지테이블에 프레임번호와 Valid-Invalid 정보를 가지고 있는데(1 -> in-memory, 0 -> not-in-memory)

-> 처음 페이지 요청이 들어오게 되면 Valid-Invalid Bit가 모두 0임

-> 이러한 요청이 들어오게 되면 우선 TLB라고 하는 곳에서 먼저 들어가서 캐시메모리에 있는지 없는지를 확인을 하고 없다면 페이지테이블로 넘어가 확인을 함. 그러나 현재 메모리에 올라와 있지 않기 때문에 전부다 0으로 표시되어 있음 그렇다면 CPU가 데이터를 불러올 수 있는 방법이 없기 때문에 운영체제에 요청을 함(실제로 메모리에 없어도 valid하다는 정보는 운영체제에서 알 수 있음) -> 따라서 valid하다는 정보는 알고 있지만 physical memory에 존재하지 않음 -> 그래서 하드디스크에서 읽어서 올리는 작업을 해줌

invalid의 2가지 케이스

-정말로 invalid한 메모리를 access를 한 것인지(자기가 사용하는 logical memory를 넘어서 사용한 케이스)

-실제로는 valid한데 하드디스크에 있는 경우(page fault)

 

Page Table When Some Pages Are Not in Main Memory

-> 프로세스는 8개의 페이지로 구성되어 있음

원래는 8개의 페이지가 모두 valid한 상태여야 함 page table을 넘어가는 페이지는 invalid한 상태여야 함 -> 그러나 그림을 보면 어떤 것은 valid하고 어떤 것은 invalid함 -> 0,2,5번 페이지는 physical memory에 올라가 있다는 것을 의미함, 나머지는 하드디스크에 저장되어 있음(하드디스크 입장에서는 모든 페이지 데이터를 가지고 있는 것임)

 

Page Fault

CPU가 명령을 수행을 할 때 logical address, physical address를 변환(translate)하려고 봤는데 TLB에 없는 상황이라며 페이지테이블로 가야함 -> 그곳에서 모두 invalid한 상황이라고 가정을 하면 -> 이것을 OS가 처리를 해줘야함 -> 2가지 케이스존재(memory process fault, 실제로는 valid한 페이지-> 이것이 하드디스크에 있는 것(page fault – 요청한 페이지가 메모리에는 없고 하드디스크에 있는 상황))

 

Page Fault – 메모리에 올라와 있지 않은 데이터를 참조하려고 할 때 발생함, 페이지 테이블에서 invalid 비트를 확인하고 CPU가 처리할 수 없으니 자기 자신에게 trap을 거는 과정

 

Page Fault시 동작 예시

M -> page number

M과 page table 중간에 TLB가 존재해야함 -> TLB의 캐시 메모리를 가장 먼저 확인을 하고 없으면 page table로 넘어가서 찾는 작업을 진행함

page table 내에 상태가 invalid임 -> 이렇게 되면 CPU 내에서만 처리가 가능하지 않음 CPU에 trap을 걸어서 OS로 들어감(이러한 과정 자체를 page fault라고 함) -> 운영체제에 page fault 상태를 알려서 하드디스크에 있는 페이지 데이터를 메모리에 올려놓음 -> 올려놓은 메모리를 page table에서 다시 valid로 바꿔줌 -> 페이지를 돌려주면서(translation) 데이터를 불러옴

>>물리 메모리에 free frame이라는 곳이 존재하는데 이는 메모리 안에서 빈 프레임 공간을 이야기함

>>만약 free frame이 physical memory 안에 하나도 존재하지 않는다면 free frame이 생길 때까지 대기하는 것이 아님 -> 메모리에 올라와 있는 것들 중 하나를 내려서 그곳에 요청이 들어온 하드디스크 데이터를 올리게 됨.

-> 메모리에 올라가 있는 것들 중 어떤 것을 내릴지를 오늘 시간에 배움

(프로그램이 처음 시작이 되었을 때는 상태가 모두 invalid상태를 갖는다. -> 최초에는 physical memory에 올라가져 있는 메모리가 없을 것이기 때문임) -> 따라서 어떠한 데이터를 불러오더라도 초기에는 page fault가 발생하게 된다.

-> 이렇게 요구하는 페이지를 올려놓는 방식을 demand paging 기법이라고 함.

 

Memory Reference(메모리 참조)

프로그램을 사용을 한다면 VM을 사용하게 됨(page table에 대해서만 이야기를 함) -> 프로그램이 실행이 되면 VA(가상주소)를 가지고 TLB(캐시메모리, 빠르게 불러올 수 있음)에 가게 됨. -> TLB에 page number와 frame number가 있다면 TLB hit가 일어나면서 바로 메모리에서 데이터를 불러옴(보통 99%가 TLB에서 해결이 됨) but TLB에 page number와 frame number가 없다면 TLB miss가 일어나서 page table로 이동을 해서 참조를 하고 translation해서 주소 값을 알려줌 / 이 과정에 추가로 valid, invalid과정을 거침(valid이면 메모리에서 가져와서 사용하면 됨 but invalid이면 운영체제가 개입을 해서 메모리에 올려놓음(invalid에도 2가지 경우가 존재함 -> 1번째 메모리가 참조해서는 안 되는 영역이라서 memory protection기능이 작동하는 경우, 2번째는 page fault – 앞서 이야기한 page fault과정이 이루어짐)

 

common case(전체 경우의 99%) -> TLB hit가 일어나는 경우를 말하는 것

TLB miss(나머지 1%) -> page table에서 invalid한 정보일 때 발생함

2가지 경우

>1번째 메모리가 참조해서는 안 되는 영역이라서 memory protection기능이 작동하는 경우, >2번째는 page fault – 앞서 이야기한 page fault과정이 이루어짐)

 

 

What happens if there is no free frame?(physical memory에 빈공간이 하나도 없다면 어떻게 할 것인가?) -> 어떤 프레임을 내릴 것인가?

-> 앞으로 가장 사용되지 않을 프레임을 내리는 것이 효율적이다.

-> 그럼 앞으로 사용되지 않을 프레임을 어떻게 알 수 있지? 알 수 없다...

-> 그렇다면 과거의 데이터를 보고 앞으로 사용되지 않은 프레임을 앞으로도 사용되지 않을 것이라고 예측할 수 있음(locality)

 

Demand Paging의 성능에 대해서 측정을 함

-> TLB miss는 실제로 자주 발생하는 것이 아님

page fault가 많이 일어나게 되면 좋지 않음 -> 성능이 저하됨

 

 

Page Replacement

page fault발생 빈도가 아주 작다면 하드디스크에서 페이지정보를 가져오는 것이 전체적이 성능에 미치는 영향은 크지 않다. -> 그렇지만 page fault가 일어나는 것을 최대한으로 방지해야 성능이 좋아짐. -> page fault가 일어났을 때 페이지를 swap(replacement) - 사용하지 않을 것 같은 것을 내리고 앞으로 사용될 것 같은 것을 메모리에 올리는 것 -> 이러한 과정에서 SSD나 하드디스크에서 정보를 올리는데 이것들이 I/O작업임 -> 이런 것들이 많아지게 되면 컴퓨터가 계속 I/O작업만 하게 되어 느려지게 됨 -> 따라서 page replace를 잘해주어야 함

Page Replacement 그림 예시

 

physical memory에 더 이상 빈공간이 없을 때 두 개의 페이지(physical memory에 있는 정보와 secondary storage에 있는 정보)를 swap을 함

 

Page Replacement 그림 예시

victim - physical memory에서 내려가게 되는 페이지

 

Page Replacement Algorithms (스케줄링 알고리즘에서 배웠던 것과 유사함)

어떤 페이지를 내리는지에 대해서는 각각의 알고리즘이 존재함

이러한 알고리즘은 page fault rate을 가장 작게 만드는 것이 좋은 것임

밑에 reference string은 page number를 의미함

 

page replacement알고리즘의 핵심은 page fault 횟수를 줄여서 하드디스크에서 불러오는 페이지 I/O작업을 최소화하는 것

 

number of frame이 많아질수록 page fault가 발생할 확률이 낮아짐

 

FIFO(먼저 들어온 것이 먼저 나감)

>이렇게 되면 성능이 좋지 못함 -> 가장 늦게 들어왔다고 가장 사용이 안 될 것이라는 생각은 옳지 않음

 

FIFO 예시

 

Optimal Algorithm(SJF와 유사 -> 뒤에서 참조하는 페이지를 보고 가장 사용이 안 되는 페이지를 빼주는 것) - 이후에 참조될 것을 보고 가장 나중에 참조되는 것 중에 현재 메모리에 올라와 있는 것을 빼줌

-> 가장 최적이기는 하지만 구현하기 어렵다(이후의 참조 순서를 예측하기가 어려움)

 

Optimal 예시

그림과 같이 막대기 형식으로 풀이를 해야함

 

 

Least Recently Used (LRU) Algorithm(과거 데이터를 보고 가장 최근에 사용된 것을 보존함) -> 가장 많이 사용됨

 

LRU 예시

 

 

>Second Chance – 한 번의 기회를 더 줌(FIFO알고리즘 기반임, 효율이 좋지 못함)

>LRU Clock

있다고만 알 

 

 

Not Recently Used (NRU) - 과거의 참조유무를 조회를 해서 교체페이지를 선정함(LRU와 유사) -> 하나의 ref bit를 주어서 페이지가 참조될 때 1로 설정, 초기에는 0

있다고만 알고 있기

 

 

Counting Algorithms(이전 페이지 참조 횟수를 기반으로 보존여부를 결정함)

종류

>LFU(Least Frequently Used) Algorithm – 가장 참조가 적게 된 것을 내려 보냄

-> 한쪽에 쏠리게 되면 비효율적 -> aging을 통해 해결

>MFU Algorithm

 

-> 위에서 배운 대표적인 3가지 알고리즘에 대해 자세히 파악해두기

 

 

Allocation of Frames – 프로세스에 프레임을 얼마나 어떻게 할당할 것인가?

프로세스가 10개가 있다고 하고 페이지가 10개가 있다고 하면 총 100개의 physical memory frame이 필요함 -> 그러나 physical memory frame은 50개만 있다고 하면 이것을 어떻게 나누어줄 것인지?

이것을 어떻게 나누어 줄 것인지 (2가지 방식)

>fixed allocation – 각 프로세스 당 똑같은 수의 프레임을 나누어 주는 것(RR과 비슷)

>priority allocation – 우선순위가 더 높은 프로세스에 더 많은 physical memory frame을 할당해주는 것(우선순위 스케줄링과 비슷)

 

Global vs. Local Allocation - 기본은 가장 오래된 프레임을 찾아서 교체하는 것임

Local Allocation - 메모리에서 page replacement를 할 때 프로세스에서 할당받은 프레임 내에서 교체할 페이지를 정하는 방법(특정 프로세스, 기본적으로 사용하고 있음 – 현재 운영체제)

Global Allocation – 모든 프레임(physical memory) 내에서 교체할 프레임을 정하는 방법

Evicted page – 교체될 페이지

 

 

Thrashing – 하나의 프로세스가 local replacement 방식으로 page fault를 처리를 하려고 교체할 페이지를 정해서 replacement를 수행하려고 했는데 또 page fault가 발생하는 것

-> 하나의 page fault를 처리하고 있어 swap을 계속하다가 시간을 다 보내는 것(deadlock과 비슷) ->운영체제이서 page replacement를 잘못해주는 것

발생 상황

>이 프로세스에 프레임이 적게 할당된 경우 – 프레임을 적게 할당해주면 page fault횟수가 늘어남

>page fault가 많이 일어나면 하드디스크에서 메모리에 올려놓는 작업시간이 생각보다 오래 걸림 이 작업을 수행하는데 시간이 오래 걸리니 디스크에서 데이터를 읽어서 처리하는 시간이 지연됨.(CPU utilization이 떨어짐, 보통 요즘 컴퓨터에는 SSD(데이터를 읽어올 때 정기적인 신호를 주고받음)에 os가 깔리고 데이터 저장소로 하드디스크(기계적으로 데이터를 읽는 방식)를 많이 사용함, 사실 SSD를 사용하게 되면 Thrashing구간이 발생하기 어려움)

 

그래프의 가로축 프로세스의 수를 의미함

프로세스의 개수가 계속 늘어나면 가 프로그램에 할당되는 프레임의 수도 줄어들게 됨.

그럼 page fault가 발생할 확률이 기하급수적으로 늘어남 그러면 page fault가 많아지고 실제로 page fault를 처리하느라 CPU에서 프로세스가 아예 수행되지 않는 현상이 발생할 수도 있음 -> 이러한 문제를 해결하기 위해서는 프로세스에 프레임을 많이 할당해주면 될 수도 있지만 현 상황에서는 그럴 수가 없음(ex. 게임이 튕기는 현상) -> 이미 프로세스가 많아져서 프레임이 부족한 상황이 되어버렸기 때문에 -> 그렇다면 해결 방안은 프로세스를 죽이면 된다.(프로세스를 계속 죽여 나가는 것)

 

프로세스의 Locality를 나타냄 -> 시간이 지남에 따라 어떤 페이지가 참조가 얼마나 일어났는지를 보여줌(하얀 부분은 참조가 전혀 안되는 부분임)

시간이 지남에 따라 페이지들이 참조되는 상황 -> Temporal locality

참조된 페이지 주변으로 참조되는 것 -> Spatial locality

-> 그림을 통해 소프트웨어가 locality 특성이 있음을 알 수 있음

 

 

Working-Set(자주 참조되는 페이지) Model

자주 참조되는 페이지 수만큼 페이지를 할당해줌

필요한 프레임이 전체 메모리보다 크다면 Thrashing이 또 발생을 함 -> 프로세스 수를 줄이는 방안이 있음, 또 다른 방법은 메모리를 더 사서 메모리를 늘리는 방법이 있음

 

 

운영체제가 취하고 있는 방법은 프로세스에 프레임을 할당해주는 방식임 -> 이것을 미분하게 나눠주는 방식 – fixed allocation

우선순위에 따라 더 많은 수를 나눠주는 것 - priority allocation

Page-Fault Frequency – page fault rate에 따라 프레임 할당 수를 결정 짓는 것

-> 현재 운영체제에서 사용됨

 

 

 

기타 메모리 관리 방법

>Prepaging - Spatial locality방법 기반, 우리가 읽어오는 페이지 주변이 다시 참조될 확률이 높다고 생각하여 같이 가져오는 방식(사전에 미리 올리는 것) - > 디스크헤더가 많이 움직이지 않아야 시간이 단축됨(불러오는 김에 같이 불러옴)

>Page size selection – 내부단편화 문제

Fragmentation – 페이지 사이즈가 작아야 내부단편화 문제가 줄어듦

Table size – 페이지 사이즈가 커지면 테이블 사이즈는 작아짐(페이지 사이지가 크면 좋은 것임)

I/O overhead – 페이지크기가 커야 접근이 줄어듦

Locality – 페이지크기가 커야 관리가 용이함

>>여러 개의 측면에서 봤을 무조건 페이지크기가 작기만 하거나 크기만 해서 좋은 것이 아님

>>trade off가 존재 -> 현재는 페이지 사이즈 단위를 4KB단위로 관리를 하고 있음

 

TLB(페이지 테이블에서 참조하였던 것을 캐시메모리 형태로 가지고 있는 것) Reach – TLB가 커버하는 영역

TLB Reach = (TLB Size) X (Page Size)

-> 페이지사이즈가 커져야 좋음

>>결국 적당한 크기로 페이지 사이즈를 관리하는 것이 필요함

 

Increasing the Size of the TLB

>Increase the Page Size – 페이지 크기를 무한정 크게 해도 문제가 발생하기 때문에 4KB수준으로 관리를 하고 있음

>Provide Multiple Page Sizes – 때에 따라서는 페이지 사이즈를 한단위로만 하는 것이 아니라 여러 가지 크기로 쪼게어 사용하는 것

 

-> 참조하는 영역이 행이냐 열이냐에 따라서도 page fault문제가 다르게 나타남

-> 메모리 구조는 2차원 구조가 아님

-> 일정크기의 단위를 가지고 각 데이터가 할당이 됨

-> Spatial locality에 의해 차이가 발생함 – 밑에 것만 적용이 가능 (메모리에 더 효과적임)

 

 

I/O장치에서 데이터를 불러올 때 virtual address에서는 연속이지만 physical address에서는 연속이 아닐 수 있음 -> 따라서 I/O장치에서 사용할 buffer는 physical address에서 연속적이어야 함

 

윈도우와 솔라리스에서는 우리가 배웠던 virtual memory관리기법을 둘 다 사용함