목차
- 가상메모리(가상주소공간, Demand Paging, Free frame list)
- 페이지 교체(FIFO, OPT, LRU, LFU, second chance)
- Thrashing Prevention(Thrashing, working-set 모델)
배경
코드가 실행되기 위해서는 메모리에 있어야 하지만 전체 프로그램은 거의 사용되지 않고 보통 프로그램의 일부만이 반복적으로 사용됩니다. 그래서 우리는 굳이 프로그램 전체를 메모리에 올리는게 아니라 부분적으로 필요한 부분만 올리는 방법을 사용하고 그 덕분에 효율적인 메모리 사용으로 더 많은 프로그램을 동시에 돌릴 수 있고, 메모리에 프로그램 일부만 로드/스왑하기 때문에 더 적은 I/O 만으로도 가능하니 각 사용자 프로그램은 더 빠르게 돌릴 수 있습니다.
가상 메모리(Virtual Memory)
가상 메모리는 메모리가 실제 물리 메모리보다 많아 보이게 하여 물리 메모리 크기의 한계를 해결하는 메모리 관리 기법입니다. 프로그램이 실행될 때, 프로그램의 모든 코드가 메모리에 있을 필요가 없으니, 일부만 메모리에 올라오고 나머지는 계속 디스크에 남아 있습니다. 가상메모리 구현을 위해서는 컴퓨터가 특수 메모리 관리를 위한 하드웨어를 가지고 있어야하고 MMU(Memory Management Unit)라고 합니다. MMU는 논리 주소를 물리 주소로 변환해주고 메모리 보호 기능을 가지고 있습니다.
논리 주소 공간 : 프로세스가 메모리에 적재되어있는 걸 보는 논리적 뷰입니다. 사용자가 보는 모든 주소는 이 가상 주소입니다.(어셈블리 16진수 주소도 논리 주소. 실제 물리 주소를 볼려면 커널 디버거, OS 제공하는 특정 API 등 사용) 가상 메모리는 Demand paging이나 Demand segmentation을 통해 구현할 수 있습니다.
가상 주소 공간(Virtual address space )
가상주소공간은 가상 메모리 기법으로 제공되는 주소 공간으로, 프로세스의 관점에서 사용하는 주소입니다.
각 프로세스마다 주어지는 논리 공간으로 레지스터 크기에 종속적입니다.
일반적으로 가상 주소 공간은 max 논리 주소에서 스택이 아래로 힙이 위로 확장됩니다.
Stack : 지역변수, 함수의 매개변수, 시스템 스택으로 컴파일 타임에 그 최대 크기가 확정됩니다.
Heap : 사용자의 동적 할당 영역으로 크기는 런타임에 결정됩니다. 공간이 레지스터 크기에 종속적입니다.
BSS : 초기화 안된 전역변수, 배열 등으로 컴파일 타임에 그 크기가 확정됩니다.
Data : 초기화 된 전역변수, 배열 등으로 컴파일 타임에 그 크기가 확정됩니다.
Code or Text : 실행할 기계어 상태에 코드로 컴파일 타임에 확정되고 ReadOnlyMemory입니다.
가상주소공간에서 스택과 힙은 어마어마하게 멀리 있기 때문에 절대 만날일이 없어 스택과 힙 그 사이 어딘가에 공유라이브러리를 둡니다. 64비트 아키텍처라면 48개의 비트만 써도 테라단위에 가상 주소 공간을 갖습니다.
Demand Paging
Demand paging은 메모리에 페이지를 필요할 때만 가져오는 방식입니다.
valid-invalid bit를 이용해 페이지 테이블에 해당 페이지가 메모리에 있다면 v, 없다면 i 체크를 하며 비트가 물리 메모리에 있는지 체크하여 있다면 쓰고 없다면 page fault라는 오류를 발생시킵니다.
주소 변환 과정은 다음과 같습니다.
1. TLB를 확인합니다.
2. TLB hit인 경우 바로 주소로 변환해주고, miss인 경우 페이지 테이블을 확인합니다.
3. 페이지 테이블의 valid-invalid bit가 valid라면 주소를 변환하고 TLB에 페이지를 올립니다. invalid라면 페이지 폴트가 발생합니다.
*invalid는 1.주소 범위 밖에 없거나(오류로 data영역을 code영역에 써진경우) 2.메모리에 없는 2가지 경우를 뜻합니다.
4. 페이지 폴트가 발생하면 MMU가 OS에 trap을 걸고 사용자 레지스터와 프로세스 state를 저장합니다.
*trap(sw interrupt) 인터럽트(하드웨어 인터럽트)와 달리 내부에서 생긴 사건 때문에 발생하는 것입니다.
5. 불법적인 접근이라면 프로세스를 종료시키고, 그렇지 않다면 빈 페이지 프레임을 얻습니다. 만약 빈 프레임이 없다면 메모리에서 희생할 페이지를 선택해 바꿉니다.
6. OS는 참조된 페이지를 디스크에서 메모리로 로드하고 디스크 로드(I/O)가 끝날 때 까지 이 프로세스는 waiting합니다.
7.디스크 로드가 끝나면 페이지 테이블을 업데이트해주고 valid 비트로 바꿔준 후 프로세스가 ready 큐에서 다시 CPU가 잡게 되면 이전 작업을 이어서 합니다.
시작할 때 메모리에 어떤 페이지도 없는 방식을 Pure Demand paging이라 합니다. 이 경우 초기 페이지 폴트가 너무 많기 때문에 메모리에 일부를 미리 로딩하여 해결할 수 있는데 이 방식을 prepaging이라 합니다.
페이지 폴트 TMI
Major 페이지 폴트 : 페이지가 메모리에 없는 경우를 말합니다.
Minor 페이지 폴트 : 메모리에 있지만 매핑이 안되어 있는 경우(공유 라이브러리), 또는 원하는 페이지가 free-frame list에 아직 남아있는 경우를 말합니다.
리눅스는 마이너 페이지 폴트가 메이저 페이지 폴트보다 월등히 많습니다. 이는 리눅스가 공유 라이브러리를 많이 활용하고 있다는 증거입니다.
명령어가 다중 페이지에 접근할 수도 있기 때문에 다중 페이지 폴트가 발생할 수 있습니다. 드물지만 한 명령어에 최대 4번의 페이지 폴트도 가능하다고 합니다.
Hardware support to demand paging
● 페이지 테이블 : valid-invalid 비트를 통해 설정
● 보조저장장치 : 메인 메모리에 없는 모든 페이지 가지고 있고 스왑장치 with 스왑공간이라 합니다.
● 페이지폴트 트랩 처리 후 명령어 재시작을 해야합니다. 이 때 중단된 프로세스 상태를 모두 보관하고 있어야 합니다.
Free Frame List
페이지폴트가 발생하면 OS는 해당 페이지를 메인 메모리로 불러야하는데, 대부분의 OS는 free-frame list를 유지/관리하여 사용합니다.
초기 안드로이드, ios에서는 스와핑이나 페이징을 지원하지 않는 경우가 있습니다. 대신 이 경우 메모리 압축(Memory Compression)을 사용합니다.
Demand Paging Optimizations
같은 디바이스여도 스왑 공간 I/O는 파일 시스템 I/O보다 빠릅니다.
프로세스 전체를 시작 전에 스왑공간에 복사해둘 수 있고 과거 BSD Unix에서 이 방법을 사용했습니다.
변하지 않는 바이너리 이미지는 파일시스템에서 읽어오고 anonymous memory는 스왑공간을 이용할 수 있습니다.
모바일 시스템에서 스와핑을 지원하지 않고 파일시스템을 사용하거나 메모리 압축 기법을 사용합니다.
페이지 교체(Page Replacement)
페이지폴트가 발생해서 가져와야하는데, 빈 프레임이 없어서 누군가를 교체해야하는 경우 페이지를 교체해줘야 합니다.
이 때 프로세스 당 몇개의 프레임을 할당할지, 어떤 프레임을 교체할지 등에 대한 기준이 필요하고 프레임 할당 알고리즘을 작성합니다.
페이지 교체 알고리즘은 페이지 폴트 비율이 적은 것을 목표로 작성합니다. 일반적으로 프레임을 늘리면 페이지 폴트가 감소합니다.
페이지 교체 알고리즘에 대한 page reference string을 가정하고 알고리즘에 따라 프레임에 어떤 페이지가 매칭되는지 확인합니다.
page reference string : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
프레임은 3개로 가정합니다.
FIFO(First-In-First-Out) 알고리즘
FIFO 알고리즘은 프레임을 추가 했음에도 더 많은 페이지 폴트가 생기는 현상을 보입니다. 이를 Belady's Anomaly라고 합니다. 현재 가정에서는 프레임을 3에서 4로 늘리면 페이지 폴트가 오히려 증가하는 현상을 볼 수 있습니다.
Optimal 알고리즘
최적 알고리즘은 페이지 교체 시점에서 앞으로 가장 오랫동안 쓰이지 않는 페이지를 교체합니다. 이 방법은 항상 최적의 결과를 갖습니다. 하지만 미래의 페이지 참조를 모두 알고 있어야 하므로 실사용은 어렵고 다른 알고리즘 성능에 대한 기준점(상한선) 역할을 합니다.
OPT알고리즘은 참조 문자열이 역참조 문자열이어도 동일한 페이지 폴트 수를 가집니다. OPT(S) == OPT(S_reverse)
LRU(Least Recently Used)알고리즘
LRU알고리즘은 과거 정보를 써서 가장 오래전에 참조된 것을 교체하는 방법입니다. LRU를 Counter 방식으로 구현할 수 있고, 스택으로 구현하는 방법은 하드웨어 도움 없이 소프트웨어로만 한다면 10배 이상 느려진다고 합니다.
스택방식의 경우 최근 사용과 과거 사용을 정리를 해주는 방식으로 합니다.
*스택알고리즘(LRU, OPT)
LRU알고리즘과 OPT 알고리즘은 N개의 프레임을 사용했을 때 참조 문자열이 끝나고 남아있는 페이지의 집합이 N+1개의 프레임을 사용했을 때 남아있는 페이지의 집합의 부분집합이며, 이런 형태를 띄는 알고리즘을 스택 알고리즘이라고 부릅니다. 스택 알고리즘은 Belady's Anomaly가 발생하지 않습니다.
예를들어 LRU, OPT 모두 마지막에 프레임에 0,1,7 이 남아있는데 만약 프레임이 4개라면 그 4개 중 3개는 반드시 0, 1, 7입니다.
Countung Algorithm
카운팅 알고리즘은 구현이 비싸고, OPT 알고리즘에 근접하지 못해 그리 일반적이지는 않습니다.
LFU 알고리즘(Leaset Frequently Used) : 가장 참조횟수가 적은 페이지를 교체합니다.
MFU 알고리즘(Most Frequently Used) : 가장 참조횟수가 큰 페이지를 교체합니다.
LRU 근사 알고리즘(LRU Approximation)
LRU는 특별한 하드웨어가 필요하고 있더라도 느리다고 합니다.
참조 비트(Reference Bit)는 초기화시 0으로 초기화되고 참조되었다면 1로 변경됩니다. 이 비트를 통해 0인 페이지가 먼저 희생하여 교체됩니다.
Second Chance Algorithm(FIFO + 참조 비트)
FIFO 방식과 하드웨어가 제공한 참조 비트를 합쳐서 만든 알고리즘입니다. 시계처럼 돈다고해서 Clock 알고리즘이라고도 합니다. LRU의 근사 알고리즘입니다.
페이지 교체가 필요하면 돌면서 참조 비트가 0이라면 제거하고 1이라면 비트를 0으로 바꾸고 1번 더 기회를 줍니다.
Enhanced Second Chance Alogrithm
이 방법은 참조 비트에 추가로 modify bit(dirty bit)를 추가합니다.modify 비트는 해당 페이지의 내용이 변경되었는지 여부를 표시합니다. 우선순위는 (ref, mod)비트일 때 0,0 > 0, 1 > 1, 0 > 1, 1순으로 희생합니다.
TMI
LRU 근사 알고리즘
Additional 참조 비트 알고리즘으로 Timer 인터럽트를 통해 주기적으로 OS가 참조 비트를 밀면서 이전 history register를 가중치처럼 남겨 history register가 클수촉 최근 것으로 판정하는 방법이 있다고 합니다.
Demand Paging의 경우 페이지가 불려오면 조회가 되므로 참조 비트는 1로 세팅되는데, pure demand paging에서 1만 존재할 수 있기에 Second-Chance 알고리즘을 수행하기 위해 주기적으로 모든 참조 비트를 0으로 리셋하는 방법을 고려할 수 있다고 합니다. (참조하자마자 0으로 바뀌는건 감안하는 방법)
Page-Buffering 알고리즘
프리 프레임을 미리 만들어 놓은 Pool을 사용해 페이지 폴트 시간에 찾지 않고 바로 할당하는 방법을 쓸 수 있습니다. 풀을 사용하면 Victiom 페이지를 스왑공간에 쓰는 것과 병행으로 실행이 가능하며, 프로세스를 빨리 restart 할 수 있다 합니다.
변경된 페이지를 페이징 디바이스가 놀 때, backing store에 써 놓으면 나중에 시간을 절약할 수 있고, 프리 프레임의 내용이 backing store와 같으면 재사용 할 수도 있습니다.
Application and 페이지 교체
DBMS와 같이 응용프로그램이 스스로 메모리와 I/O 버퍼를 관리하면 double buffering 현상이 발생할 수 있다고 합니다.
OS는 파일시스템을 우회하는 raw disk모드를 제공함으로써 DBMS처럼 응용프로그램 자신에 최적화된 솔루션을 개발할 수 있다고 합니다. 하지만 대부분의 응용프로그램은 그냥 파일 시스템을 사용하는 것이 유리하다고 검증됐다 합니다.
Allocation of Frames
각 프로세스 프레임 할당에는 min과 max가 있습니다. min은 최소한 1개의 instruction이 가능한 data 공간이 필요하고 max도 적절한 제어가 필요한데 이는 CPU(instruction set, addresing mode, etc)에 따라 달라질 수 있습니다.
일반적으로 2가지 기초적인 할당 아이디어가 있습니다.
1. Fixed Allocation : 각 프로세스마다 균일하게 할당합니다. 총 프레임 수 / 프로세스 수
2. Proportional Allocation : 트로세스 사이즈 등 기준을 토대로 비례하여 할당합니다.
프로세스가 페이지 폴트가 발생하면 대체될 프레임 그룹에 따라 Global, Local 교체로 나뉩니다.
Global Replacement : 모든 프레임 중 교체할 프레임을 정하기에 한 프로세스가 다른 다른 프로세스에 할당된 프레임을 가져올 수 있습니다. 할당된 프레임의 수가 자신은 물론 다른 프로세스에 의해 영향을 받기 때문에 변수가 많습니다.
Local Replacement : 모든 프로세스는 자신에게 할당된 프레임 내에서 교체합니다. 일관된 프로세스 성능을 제공할 수 있으나 쉬고 있는 프레임을 쓸 수 없기에 메모리가 비효율적입니다.
Thrashing Prevention
프로세스가 프로그램 실행보다 페이징에 더 많은 시간을 보낼 때 이것을 thrashing이라고 부릅니다. 과정은 다음과 같습니다.
페이지 폴트 발생 → 스와핑 발생 → I/O 작업 증가 → 일을 못하는 상태 → OS는 CPU 사용을 안하니 일을 안한다 생각해서 프로세스를 시스템에 추가 → 더 많은 페이지 폴트 → ...
Demand Paging and Thrashing
Locality Model : 같이 활발하게 사용되는 페이지의 집합으로 지역성, 반복적으로 쓰이는 페이지 집합입니다.
스레싱이 발생하는 이유는 locality의 사이즈가 전체 메모리 사이즈보다 커져서 스와핑이 필요해서인데 로컬 혹은 우선순위 페이지 교체 알고리즘으로 스레싱을 억제할 수 있습니다.
하지만 Local Page replacement 알고리즘도 스레싱 문제를 완전히 해결하지 못하는데, 왜냐하면 어떤 프로세스가 스레싱이 일어나면 페이징 디바이스가 바빠지므로 다른 프로세스는 스레싱이 아니더라도 EAT가 나빠진다고 합니다.
Working - Set 모델
Working-set이란 Δ시간동안 조회된 페이지의 집합이라고 합니다. 워킹셋 모델도 스레싱을 간접적으로 방지하는 방법의 일종인데 필요한 페이지의 수 D(모든 Working-set의 합)가 메모리 프레임의 수 m보다 크다면 스레싱이 발생합니다.
정확한 델타 크기도 중요한데 너무 작다면 충분한 페이지 접근 리스트를 얻지 못해 지역성을 도출하지 못하고, 너무 크다면 너무 많은 프레임을 할당받아 여러 지역성이 도출되고, 델타가 무한대라면 모든 프로그램이 도출됩니다.
그렇기 때문에 D > m이라면 프로세스 중 하나를 중단합니다. 문제점은 working set을 어떻게 추적하느냐에 있어 Timer와 refernce bit를 사용하여 근사치를 계산하는 방법도 있다고 합니다. (D = total demand frames)
TMI내용들 마구마구
버디 메모리 할당(Buddy System)란 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘입니다. 보통 물리적으로 연속적인 페이지에 메모리의 크기를 절반씩 분할하면서 가장 잘 맞는 크기의 메모리를 찾습니다. 버디 메모리 시스템은 약간의 외부 단편화와 메모리 간결화를 하는 오버헤드를 가지고 있습니다. 또 작동방식 때문에 적당한 양의 내부 단편화가 있을 수 있습니다. 70K 메모리 요청시 64는 안되니 128이 할당될텐데 이 경우 58K가 낭비됩니다.
Slab Allocator(슬랩 할당자)
Slab은 하나 이상의 물리적으로 연속적인 프레임입니다. 커널에서 kmalloc을 통해 동적 할당을 받을 때 슬랩 할당자는 미리 할당해 놓은 작은 메모리 조각을 요청에 따라 요청양에 가장 근접한 메모리 조각을 반환해 줍니다.
즉 커널에서 사용하는 동적 메모리 할당자입니다. 메모리 풀 구조를 가지고 있어 미리 고정된 크기의 메모리 블록을 준비해 놓습니다. 단편화가 매우 적고 빠른 메모리 할당이 가능합니다.
I/O interlock
I/O 버퍼로 사용될 페이지가 교체되면 문제가 발생합니다. 이를 해결하기 위한 2가지 해결법이 있는데
1. I/O 를 사용자 메모리에서 수행하지 않고 커널 영역에서 수행합니다(Double Buffering)
2. 페이지 교체가 안되도록 잠가둡니다.(pinning)
방학이 되고 시험기간에 정리한 파일도 있으니 되게 빨리 블로그에 적을거라 생각했는데 엄청 오래걸렸다...
심지어 보면 볼수록 내가 아는게 맞나? 이번 학기에 수강한게 아니었나? 싶었던... 뭔가 좀 더 정리가 필요하지만 나중에 다시 보면서 그때 깨끗한 머리속으로 다시 정리해야겠다.
또 학기 중에는 챕터 10까지 나갔는데 공룡책 원서를 찾아보니 스토리지 관리, 파일 시스템, 보안, 등등 챕터가 21까지있고 추가로 OS별 얘기가 있는 A~D까지 있다니...
'강의 > OS' 카테고리의 다른 글
OS - 메인메모리(Main Memory) (0) | 2023.07.22 |
---|---|
OS - Deadlock (0) | 2023.07.18 |
OS - 동기화 예시 (0) | 2023.07.17 |
OS - 동기화 툴 (0) | 2023.07.16 |
OS - CPU Scheduling (0) | 2023.07.13 |