사실 많은 경우에 프로그램 전체가 한꺼번에 메모리에 늘 올라와있어야 하는 건 아니다.
- 프로그램의 크기를 물리 메모리의 크기로 제한하니까..
왜?
- 오류 상황을 처리하는 코드는 거의 발생하지 않음.
- 배열이 실제로는 거의 10x10 정도만 사용되는데도 100x100 으로 선언 됨.
- 프로그램 내의 어떤 옵션이나 기능들은 거의 사용되지 않음.
- 전체 프로그램이 필요하더라도 그 프로그램의 모든 부분이 모두 동시에 요구되지 않을 수 있음.
프로그램을 일부분만 메모리에 올려놓고 실행하는 것의 장점
- 프로그램이 물리 메모리 크기에 제약받지 않아도 됨.
- 각 프로그램이 더 작은 메모리를 차지하니 더 많은 프로그램을 동시에 수행할 수 있음.
- 프로그램을 메모리에 올리고 스왑하는 데 필요한 I/O 횟수가 줄어듬 → 프로그램이 보다 빨리 실행 됨.
- 가상 메모리를 사용하는 스왑인-아웃이 아니라, 메모리 부족으로 인해 발생하는 스왑인-아웃을 줄인다는 의미
가상 메모리
실제 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한 것.
- 장점 : 작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공.
가상 주소 공간
그 프로세스가 메모리에 저장되는 논리적인(가상적인) 모습(view)
- 물리 메모리는 페이지 프레임(Page Frame)으로 구성, 프로세스에 할당된 페이지 프레임들은 실제적으로는 연속적으로 구성되지 않을 수 있음.
- 물리적인 메모리 프레임을 논리적인 페이지로 매핑하는 것은 메모리 관리 장치(MMU)에 달린 것이다.
- 실제로 작업과 데이터가 늘어났을 때 물리 메모리에 메모리(페이지)를 올린다.
- 힙 또는 스택이 확장되어야만 ← 이라고 할 수도.
- 가상 주소 공간을 희소(saprse) 주소 공간이라고 한다.
페이지 공유
가상 메모리는 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 구성되는 것을 가능하게 한다.
- 각 프로세스는 라이브러리가 자신의 가상 주소의 일부라고 생각하지만, 사실 라이브러리가 존재하는 물리 메모리의 페이지들은 모든 프로세스에 공유되고 있다.
- 왜냐하면 CPU 를 점유할 땐 한 프로세스만 점유하니까, 프로세스는 컴퓨터에 자신만 동작한다고 생각한다. ㅎㅎ 귀엽네ㅋ
- 라이브러리는 읽기만 허용되는 상태로 프로세스 주소 공간에 매핑된다.
- 프로세스들의 메모리 공유를 가능하게 하며 공유 메모리를 통해 통신할 수 있다. (공유 메모리 영역을 통해)
- 페이지는 fork() 시스템 콜을 통해 프로세스 생성 과정 중에 공유될 수 있으니 프로세스 생성 속도를 높일 수 있다.
- 예를 들어 크롬 탭 프로세스가 fork() 된다면 크롬이 가진 공통 기능은 공유될 수 있을 것. → 새로 만드는 비용을 아낌.
요구 페이징
필요한 페이지만 메모리에 적재하는 것.
기본 개념
필요할 때만 페이지를 메모리에 적재하는 것이며 프로세스가 실행되는 동안 일부 페이지는 메모리에 있고 일부 페이지는 보조저장장치에 있음.
- 유효, 무효(valid-invalid)비트 기법이 사용될 수 있다.
- 비트가 유효 : 해당 페이지가 메모리에 있다는 뜻.
- 비트가 무효 : 해당 페이지가 유효하지 않거나(가상 주소 공간 상에 정의되지 않았거나), 유효하지만 보조저장장치에 존재함.
페이지 폴트
프로세스가 메모리에 올라와있지 않은 페이지에 접근하려고 하면 페이지 폴트 트랩(page-fault trap)이 발생한다.
→ 운영체제가 필요한 페이지를 적재하는데에 실패했기 때문에 발생.
페이지 폴트를 처리하는 과정
- (PCB 에 존재하는) 내부 테이블을 검사하여 메모리 참조가 유효, 무효인지 확인.
- 무효한 페이지를 참조 → 그 프로세스는 중단.
- 유효한 참조이지만 아직 메모리에 올라오지 않은 페이지 참조 → 보조 저장장치로부터 가져옴
- 빈 공간, 즉 가용 프레임(free frame)을 찾음.
- 예를 들어, 페이지 프레임 리스트에서 하나를 가져옴.
- 보조 저장 장치에 새로 할당된 프레임으로 해당 페이지를 읽어오도록 요청.
- 보조(페이지) → 메모리(프레임) → 페이지를 프레임으로 읽는다.
- 보조 저장장치 읽기가 끝나고 페이지 테이블을 갱신하며, 프로세스의 내부 테이블도 수정한다.
- 중단되었던 명령어를 다시 수행한다.
- 프로세스는 마치 그 페이지가 항상 메모리에 있었던 것처럼 해당 페이지에 접근 가능!
순수 요구 페이징
어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재하지 않음. → 극단적인 경우 : 메모리에 페이지가 하나도 안 올라와 있어도 프로세스를 실행시킬 수 있음.
- 사용할 모든 페이지에 페이지 폴트가 일어난다.
- 필요한 모든 페이지가 적재되고 나면 더 폴트가 발생하진 않는다.
참조 지역성(locality of reference)
프로그램의 어느 한 특정 작은 부분만 집중적으로 참조하는 성질.
- 이 때문에 프로세스는 만족할만한 성능을 보임.
요구 페이징을 지원하는 HW
페이징과 스와핑을 위한 하드웨어와 동일하다.
- 페이지 테이블 : 보호 비트들을 특별한 값 또는 유효/무효 비트를 통해 특정 항목을 무효로 설정 가능해야 함.
- 보조저장장치(secondary memory) : 고성능의 디스크 또는 NVM 장치(스왑 장치) → 이 목적을 위해 사용하는 저장장치 영역을 스왑 공간(swap space)라고 함.
요구 페이징의 필수 요구 사항
페이지 폴트 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 함.
- 페이지 폴트가 발생했을 때 중단된 프로세스 상태(레지스터들, code, counter..)들을 보관해둔다.
- 페이지 폴트가 되어 해당 페이지가 메모리에 올라오면, 프로세스가 중단되었던 바로 그 상태로 돌아간다.
- 차이는 페이지의 유무 차이일 뿐…다른 값들은 다 그대로.
요구 페이징 최악의 경우
ADD 와 같은 3-주소 명령어를 실행.
→ 3-주소 명령어 : 3개의 주소를 사용하는 명령어(두 개의 입력 피연산자와 결과를 저장할 목적지)
- 명령어(ADD) 를 인출(fetch)하여 해독
- A 인출
- B 인출
- A 와 B 를 더한다.
- 합을 C 에 저장한다.
- 페이지 폴트 시, 1~5를 다시 수행..
한 명령어가 많은 메모리 주소를 다룰 때는 상당히 어려운 문제 발생..
만약 한 번에 256 바이트에 데이터를 복사한다고 가정해보자.
- 이 데이터가 페이지 경계를 넘는다면 중간에 페이지 폴트 발생 가능성
- 페이지 경계를 넘다? → 일부는 한 페이지, 일부는 다른 페이지에 있는 것.
- 만약 A의 끝 128 바이트와 B의 시작 128 바이트로 겹친다면
- 일부만 복사
- 명령어 재실행
- 이 과정에서 데이터가 꼬일 수 있다.
주로 사용하는 해결책
마이크로 코드(microcode)로 양 블록의 두 끝을 계산하여 겹치지 않는 것을 확인 후에 접근을 시도하기.
- 만약 페이지 폴트가 발생할 가능성이 있다면
- 수정하기 전에 일단 페이지 폴트를 발생시킴.
가용 프레임 리스트
물리 메모리에서 비어있는 프레임 리스트를 추가하는 것 → 가용 프레임의 풀
- 시스템이 시작되면 모든 메모리가 가용 프레임 리스트에 넣어짐.
- 가용 프레임이 요청될 경우(예:요구 페이징) 가용 프레임 리스트의 크기가 줄어듬(가용 프레임을 사용하게 함)
- 리스트의 크기가 0이 되거나 특정 임계값 밑으로 떨어지면
- 다시 채우기 위해 기존 페이지를 스왑-아웃 하여 빈 가용 공간 확보.
요구 페이징의 성능
페이지 폴트가 발생하는 데에 실질 접근 시간을 알아보기 위해서는 페이지 폴트를 처리하는 데에 얼마나 많은 시간이 걸리는지 알아야 함.
페이지 폴트 처리 작업의 3요소
- 인터럽트 처리
- 페이지 읽기
- 프로세스 재시작
페이지 폴트 처리 순서
- 운영체제에 트랩 요청
- 레지스터들과 프로세스 상태를 저장(PCB) → 컨텍스트 스위칭
- 인터럽트 원인이 페이지 폴트임을 알아냄.
- 페이지 참조가 유효한지 확인 → 보조저장장치에 있는 페이지 위치 알아냄.
- 저장장치에서 가용 프레임으로 읽기 요구.
- 읽기 차례가 돌아올 때까지 대기 큐에 기다림
- 디스크에서 찾는(seek) 시간과 회전 지연 시간(읽는) 동안 기다림.
- 가용 프레임으로 페이지 전송 시작.
- 기다리는 동안 CPU 코어는 다른 프로세스에 할당.
- 저장장치가 다 읽었다고 인터럽트 발생(I/O 완료!)
- 다른 프로세스의 레지스터들과 프로세스 상태를 저장 → 컨텍스트 스위칭
- 인터럽트가 보조저장장치로부터 왔다는 걸 알아냄.
- 새 페이지가 메모리에 올라왔다는 걸 페이지 테이블과 다른 테이블들에 기록.
- CPU 코어가 자기 차례로 오기까지 다시 기다림.
- CPU 차례가 오면 PCB 에서 데이터들을 복원시키고 인터럽트 되었던 명령어부터 다시 실행!
→ 실제 접근 시간은 페이지 폴트율(page fault rate)에 비례한다. → 그러니 페이지 폴트율을 낮게 유지하는 것이 상당히 중요하다.
스왑 공간 관리
요구 페이징의 또 다른 특성은 스왑 공간(디스크 특정 영역)관리임.
스왑 공간에서의 디스크 I/O는 일반적으로 파일시스템의 입출력보다 빠르다.
- 스왑 공간은 파일 시스템보다 더 큰 블록을 사용.
- 스왑 공간과 입출력 할 때는 파일 찾기나 간접 할당 방법 등은 사용하지 않기 때문
- 이건 파일 시스템 공부하고 나서 추가 ㅠㅠ 잘 모르겠음.
첫 번째 : 전체 파일 이미지를 스왑 → 스왑 공간에서 요구 페이징
전체 파일 이미지를 스왑 공간에 복사한 다음 스왑 공간에서 요구 페이징을 수행하면 더 빠른 페이지 처리량 얻을 수 있음.
- 단점 : 프로그램 시작 시 파일 이미지를 복사하는 게 큼…
두 번째 : 처음엔 파일시스템, 교체할 땐 스왑 공간.
Linux 와 Windows 에서 실제로 사용하는 방법.
- 파일 시스템으로부터는 꼭 필요한 페이지만 읽어오고, 교체될 땐 스왑 공간에 페이지 기록.
- 가져온 페이지를 다시 읽어올 땐 스왑 공간에서 읽어오는 것을 보장.
세 번째: 파일 시스템에서 직접 가져옴.
모바일에서 스와핑을 지원하지 않으니 사용.
- 실행 파일을 스왑 공간에 넣지 않고 스왑 공간 크기 줄인다.
- 파일 시스템에서 직접 이미지를 가져온다.
- 페이지 교체가 필요하면 페이지를 메모리에 덮어 씌운다.
iOS 에서는 실행 중에 생겨난 페이지들은 앱이 종료되거나 명시적으로 방출되지 않으면 결코 앱으로부터 방출되지 않는다.
쓰기 시 복사
fork() 시스템 콜을 통해 프로세스를 생성하면 페이지 공유와 비슷한 기법으로 첫 요구 페이징조차 생략이 가능하다.
장점
- 프로세스 생성 시간을 더 줄일 수 있다.
- 새로 생성된 프로세스에 새롭게 할당되어야 하는 페이지 수도 최소화할 수 있다.
쓰기 시 복사 페이지
fork() 후 exec() 를 하는 것이 대부분이고, 그렇게 되면 부모 페이지가 쓸모가 없는데도 복사하고 초기화해야 한다.
- 그래서 대신 쓰기 시 복사 방식을 사용할 수 있다!
- 복사하는 게 아닌, 공유 시키고 쓰기 시 복사하는 것!
- 자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 사용하도록 한다.
- 이 때 공유되는 페이지가 쓰기 시 복사 페이지
사용 예시
- 자식 프로세스는 부모 프로세스의 주소 공간에 매핑한다.
- 수정되지 않는 페이지들은 계속 공유될 수 있다.
- 프로세스가 수정하는 페이지에 대해서만 복사본이 생긴다.
- 수정될 수 있는 페이지만 쓰기 시 복사를 할 수 있다.
vfork() (virtual memory fork)
부모 프로세스는 보류되고 자식이 부모의 페이지 사용.
- 자식이 만들어지자마자 exec() 를 하는 경우를 위해 만들어짐.
- 페이지가 전혀 복사되지 않으므로 효율적 → shell 구현 시에도 사용.
: 자식이 부모 공간의 페이지를 수정하면 그 페이지에가 부모에게도 그대로 보이니 주의
페이지 교체
요구 페이징의 기본.
- 아주 작은 물리 메모리로도 프로그래머에게 방대한 가상 메모리를 제공할 수 있음.
- 어떤 프로세스가 20개의 페이지로 이루어져있어도, 10 프레임만 가지고 요구 페이징과 교체 정책을 이용해 프로세스 실행 가능.
페이지 교체가 필요한 이유
- 전체 10 페이지 중 실제 5페이지만 사용하는 프로세스가 있다면, 요구 페이징을 통해 전혀 사용되지 않을 5페이지를 적재하는 데 필요한 I/O 를 줄일 수 있다.
- 이 때문에 프로세스 수를 2배 늘리면 메모리 과할당이 생길 수 있다.
- 특정 데이터 조합에 프로세스들이 10페이지를 모두 사용해야하는 상황이면…아주 곤란.
- I/O 를 위한 버퍼도 상당한 양의 메모리를 사용함. → 메모리 할당 알고리즘의 부담 증가.
얼마만큼의 메모리를 I/O 로 할당하고 얼마만큼의 메모리는 프로그램에 할당하는가 하는 건 매우 중요한 문제이다.
실제로 사용되는 방법
표준 스와핑 + 페이지 교체 결합
- 표준 스와핑 : 프로세스를 스왑 아웃하여 모든 프레임을 비우고 멀티프로그래밍 정도를 줄인다.
기본적인 페이지 교체
- 빈 프레임이 없다면 현재 사용되지 않는 프레임을 찾아 그걸 비워버린다.
- 그 프레임 내용을 스왑 공간에 쓰고 그 페이지가 이제는 메모리에 없으므로 페이지 테이블을 업데이트 한다.
페이지 폴트 서비스 루틴
- 보조저장장치에서 필요한 페이지 위치를 알아냄.
- 빈 페이지 프레임을 찾음.
- 비어있는 프레임이 있으면 → 사용.
- 비어있는 프레임이 없으면 → 희생될(victim) 프레임을 선정하기 위해 페이지 교체 알고리즘 가동.
- 희생될 페이지를 보조저장장치에 기록하고(필요하다면), 관련 테이블 수정.
- 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정
- 페이지 폴트가 발생한 지점에서부터 프로세스 실행.
빈 프레임이 없는 경우
디스크를 두 번 접근해야 한다. 그럼 페이지 폴트 처리 시간이 2배 → 실질 접근 시간도 증가.
- 프레임을 비울 때
- 읽어들일 때
변경 비트
페이지가 변경되었음을 나타내기 위한 설정.
- 변경 비트가 설정되어 있음 : 페이지 내용이 원래 보조장치에 있던 페이지 내용과 달라졌다는 걸 암.
- 이런 경우엔 현재 내용을 보조저장장치에 기록.
- 변경 비트가 설정되어 있지 않음 : 메모리를 보조저장장치에 기록할 필요 없음.(변경된 내용이 없으니)
페이지가 변경되지 않으면 I/O 시간을 반으로 줄일 수 있으니 페이지 폴트 처리 시간을 많이 줄일 수 있다.!
요구 페이징 알고리즘
여러 프로세스가 존재하면 각 프로세스에 얼마나 많은 프레임을 할당해야 할지, 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야할지 결정
- 요구 페이징 방법을 조금만 개선해도 시스템의 전체 성능이 크게 향상 됨.
- 보조저장장치 I/O 가 매우 비용이 많이 드는 작업이니까..
- 운영체제는 페이지 폴트율이 가장 낮은 알고리즘을 선택한다.
요구 페이징이 해결해야 할 두 가지 문제
- 프레임 할당 알고리즘
- 페이지 교체 알고리즘
페이지 교체 알고리즘
참조열(특정 메모리 참조 나열)에 대해 알고리즘을 적용하여 페이지 폴트 발생 횟수를 계산하여 평가.
- 참조열
- 인공적으로 생성하거나
- 주어진 시스템을 추적해 매 메모리 참조 시의 주소 기록
데이터 수를 줄이기 위한 방법
- 주소 전체를 고려하기 보다 페이지 번호만을 고려
- 페이지 p에 대한 참조가 발생하면, 직후에 p에 접근하는 모든 참조는 페이지 폴트를 발생시키지 않음.
- 참조했으니 메모리에 존재할 테니까.
3. 페이지 프레임 수가 많으면 페이지 폴트 횟수가 감소
- 물론, 물리 메모리를 추가해야 프레임 수가 증가..ㅎㅎ
안 쓰이는 FIFO 알고리즘이나 최적 페이지 교체 등등은 적지 않겠다.. 그냥 책에서 한 번 읽어보기만 했음 하하
- 최적 알고리즘 : 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하라
근데 프로세스가 앞으로 메모리를 어떻게 참조할지 어케 알음?;;
LRU 페이지 교체 (least-recently-used)
최적 알고리즘을 기반으로 “가장 오랜 기간 동안 사용되지 않은 페이지를 교체”
구현 방법
- 계수기(counters)
- 가장 간단한 방법 → 그러나 잘 안씀
- 각 페이지 항목마다 사용 시간 필드를 넣어, 마지막 **참조 시간**을 유지하고 시간 값이 가장 작은 페이지가 교체된다.
- LRU 페이지를 찾기 위해 페이지 테이블을 탐색하고 사용 시간 필드 갱신을 위해 메모리 쓰기를 하고, 시간 값을 관리하고, 시간 값의 overflow 도 고려해야 함..
- 스택(stack)
- 페이지 번호의 스택을 유지하는 법 → 잘 씀
- 페이지 참조가 될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 꼭대기에 놓임
- 스택 top : 가장 최근에 사용된 페이지
- 스택 bottom : 가장 오랫동안 사용되지 않은 페이지.
- 스택 맨 아랫부분을 제거해야하니, doubly linked list 로 구현된다.
스택 알고리즘
n 개의 프레임에 수록되는 페이지의 집합이 항상 n+1 개의 프레임에 수록되는 페이지 집합의 부분집합이 되는(n 과 관계없이) 알고리즘이다.
- 한 마디로 스택이 늘어나도 페이지는 기존 페이지 집합을 유지한다.
단, 두 방법 모두 표준적인 TLB 레지스터 이상의 하드웨어 지원이 필요함.
LRU 근사 페이지 교체
하드웨어적인 지원 없이 알고리즘을 쓸 때 참조 비트를 이용하자!
기본 설정
- 모든 참조 비트는 처음에 0으로 채워진다.
- 참조되는 페이지의 비트는 하드웨어가 1로 세팅한다.
- 페이지 사용의 순서는 몰라도, 어떤 페이지가 한 번도 사용되지 않았는지는 알 수 있다.
2차 기회 알고리즘
기본은 FIFO 교체지만, 페이지가 선택될 때마다 참조 비트를 확인하여 걸러낸다.
- 참조 비트가 0이면 페이지 교체
- 참조 비트가 1이면 다시 한 번 기회를 주고 다음 FIFO 페이지로 넘어감.
- 한 번 기회를 받으면 참조 비트는 해제(0)되고 도착 시간이 현재 시각으로 재설정.
- 그 페이지는 모든 페이지가 교체될때까지 교체 X
- 참조 비트가 계속 설정되어 있을 정도로 자주 사용되는 페이지는 전혀 교체되지 않는다!
개선된 2차 기회 알고리즘
(사용, 변경) 두 개의 비트를 사용해 네 가지 등급을 사용한다.
- (0, 0) 최근에 사용되지도 변경되지도 않음 → 교체하기 가장 좋다.
- (0, 1) 최근에 사용되진 않았지만 변경은 됨 → 뺏어오려면 디스크에 내용을 기록해야 하므로 교체에 적당 X
- (1, 0) 최근에 사용은 되었으나 변경은 되지 않음 → 곧 다시 사용될 가능성이 높음
- (1, 1) 최근에 사용도 되었고 변경도 됨 → 아마 곧 다시 사용될 것이고, 뺏으려면 디스크에 내용 기록 필요.
→ 이 중 가장 낮은 등급을 가지며 처음 만난 페이지를 교체한다.
페이지 버퍼링 알고리즘(Page-Buffering)
교체될 페이지의 내용을 디스크에 기록하기 전에 가용 프레임에 새로운 페이지를 먼저 읽어들이는 방법.
- 기존 페이지가 더 이상 필요 없으면 그 프레임을 가용 프레임에 넣는다.
- 즉, 교체될 페이지를 즉시 내보내지 않고 일단 가용 프레임에 두고 새로운 페이지를 읽는 것.
- 디스크 I/O 최적화 목적.
- 페이지 폴트가 일어날 때 찾는 페이지가 아직도 풀에 훼손되지 않은 채로 남아있는지 검사하고 → 만약 없으면 그 때 페이지를 읽어들임.
애플리케이션과 페이지 교체
운영체제가 페이지를 잘못 교체하거나 가상메모리가 비효율적으로 작동하면, 어떤 때에는 앱이 직접 관리하는 게 나을 수도 있다. → 대표적인 예가 데이터베이스
- DB는 자신이 사용하는 메모리들을 더 잘 이해하고 있을 수 있다.
- 몇몇 운영체제는 파일 시스템을 거치지 않고 디스크 블록을 직접 사용할 수 있는 기능이 있다.
- raw disk 라고 불리며, 입출력은 raw I/O 라고 함.
- 그치만 대부분의 앱은 정상적인 파일 시스템을 사용해 동작하는 것이 더 나음 ^^
프레임 할당
운영체제와 사용자 프로그램 모두 프레임을 사용한다.
- 예비로 가용 프레임 리스트에 3개는 남겨둔다. (페이지 폴트 대비)
- 사용자 프로세스는 어떤 가용프레임이든 할당받아야 한다.
최소로 할당해야 할 프레임 수
최소한 몇 페이지는 할당해야 한다. → 이유는 성능..
- 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 폴트율 증가 → 프로세스 실행은 늦어짐.
- 명령어 수행이 완료되기 전에 페이지 폴트 발생 → 그 명령어를 재실행해야 함.
→ 하나의 명령어가 참조하는 모든 페이지는 동시에 메모리에 올라와 있어야 명령어의 수행이 끝날 수가 있다.
최소 프레임 수 → 아키텍처에 의해 결정.
명령어 길이가 길어져 1개의 페이지가 아니라 그 이상의 페이지를 포함한다면
- 예를 들어 인텔 아키텍처는 CPU 가 메모리 → 메모리끼리 직접 데이터를 이동할 수 없고 레지스터에 갔다가 이동해야 함.
- 그래서 프로세스에 필요한 최소 프레임 수를 제한 함.
→ 최대 수는 사용 가능한 물리 메모리의 양에 의해 정의된다.
할당 알고리즘
현재 운영체제(커널)이 사용하는 프레임은 제외하고 생각한다.
- n : 프로세스
- m : 프레임
- 균등 할당
- 모두에게 같은 몫 m/n 프레임씩 준다.
- 93개의 프레임과 5개의 프로세스가 있으면 각 프로세스가 18개씩 균등하게 프레임을 받는다.
- 나머지 3개는 가용 프레임 버퍼 저장소로 사용.
- 비례 할당
- 가용 메모리를 각 프로세스 크기 비율에 맞춰 할당하는 방법.
- 균등성보다는 각자의 요구량에 기반을 두는 것.
- 멀티 프로그래밍 정도가 높아지면 각 프로세스는 덜 받고, 낮아지면 더 넉넉히 받는다.
→ 하지만 우선 순위가 낮은 프로세스에 손실을 주더라도 우선순위가 높은 프로세스에 더 많은 메모리를 할당하여 빨리 수행하고 싶을 수도 있다.
→ 비례 할당 방법을 사용하며 프레임 비율을 우선순위 또는 크기와 우선순위에 조합을 사용하여 결정하면 된다.
전역 대 지역 할당
- 전역 교체
- 프로세스가 교체할 프레임을 모든 프레임을 대상으로 찾는다.
- 지역 교체
- 프로세스가 자기에게 할당된 프레임 중에서만 교체한다.
전역 교체 예시
- 우선 순위가 높은 프로세스가 우선순위가 낮은 프로세스 프레임 중에서 할당이 가능하다.
- 그래서 한 프로세스에 할당된 프레임 수는 바뀔 수 있다.
지역 교체 예시
- 프로세스에 할당된 프레임 수는 변하지 않는다.
전역 교체 문제점
프로세스의 메모리에 있는 페이지 집합이 다른 프로세스의 페이징 동작에도 영향을 받는다는 것.
- 동일한 프로세스도 그때그때 외부적 환경에 따라 전혀 다르게 실행될 수 있다.
- 어떨 때는 0.5초 걸리는데 다음엔 10.3 초…
지역 교체 문제점
지역 교체에서는 다른 프로세스의 페이지 동작에 영향받는 현상이 발생하지 않는다.
- 하지만 잘 안 쓰는 페이지 프레임이 있어도 그걸 그대로 낭비
일반적으로 전역 교체가 지역 교체 알고리즘보다 더 좋은 시스템 성능에 도움이 되고 따라서 보다 많이 사용되는 방법이다.
전역 페이지 교체 방법 : 커널 리퍼 루틴
리스트 항목의 개수가 0일 때가 아니라 특정 임계값 아래로 떨어지면 페이지 교체를 시작함.
- 새로운 요청을 충족시키기 위한 충분한 여유 메모리가 항상 있도록 보장하려고 노력한다.
- 일반적으로 LRU 근사 형태의 알고리즘 사용.
- 리퍼 루틴이 가용 프레임 리스트를 최소 임계값 이상으로 유지할 수 없는 경우 ?
- OS 는 아마 2차 기회 알고리즘을 중단하고 순수 FIFO 사용할 것.
- Linux 는 OOM 킬러 루틴이 종료할 프로세스를 선택해 메모리 회수
비균등 메모리 접근 NUMA
사실 여러 개의 CPU 를 가진 NUMA 시스템에서는 특정 CPU 는 메인 메모리의 일정 영역을 다른 영역보다 빠르게 접근할 수 있다.
- 다른 CPU 의 로컬 메모리보다 자신의 로컬 메모리에 빠르게 액세스 할 수 있다.
- 메인 메모리를 하나만 가진 시스템보다는 느리다.
- 하지만 더 많은 CPU(메모리를 가진)를 수용할 수 있으므로 더 높은 수준의 처리량과 병렬 처리를 달성할 수 있다.
NUMA 의 목표
프로세스가 실행 중인 CPU에 가능한 가장 가까운(최소 지연 시간을 가진) 메모리 프레임을 할당하도록 함.
- 스케쥴러가 각 프로세스 직전에 실행된 CPU에 스케쥴하고, 가상 메모리는 스케쥴 된 CPU 와 가장 가까운 프레임을 할당한다면?
- 캐시 적중률이 높아져 메모리 접근 시간이 감소
- 스레드도 마찬가지로 자신이 실행중인 노드(로컬 메모리)에서 메모리를 할당받는 것을 보장 받는다.
스래싱
프로세스에 충분한 프레임이 없다면 바로바로 반복해서 페이지 폴트가 발생하며 교체된 페이지를 또 읽어올 필요가 생기는 과도한 페이징 작업
- 어떤 프로세스가 실제 실행보다 더 많은 시간을 페이징에 사용하고 있으면 스래싱이 발생했다고 한다.
- 심각한 성능 문제를 야기한다.!
스레싱의 원인
프로세스들이 페이징 장치를 기다리는 동안 CPU 이용률이 떨어진다는 것에 주목하자.
- 페이지 폴트 하느라 CPU 이용률 Down → 그래서 멀티프로그래밍 Up → 또 페이지 폴트 … 악순환
- 멀티프로그래밍 정도가 최댓값 이상으로 커지면 스래싱이 일어나고, CPU 이용률은 급격히 떨어진다.
- 이 지점에서는 CPU 이용률을 높이고 스레싱을 중지하기 위해 멀티프로그래밍 정도를 낮춰야 함.
→ 이 때, 지역 교체 알고리즘(또는 우선순위 교체 알고리즘)을 사용하여 스래싱 영향 제한 가능.
스래싱 방지
각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 함. → 이걸 어떻게 아냐고?
- 프로세스가 실제로 사용하고 있는 프레임 수가 몇 개인가 알아본다 → 지역성 모델 기반
- 지역성 모델 기반 : 프로세스가 실행될 땐 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조하는 것.
- 지역 : 집중적으로 함께 참조되는 페이지들의 집합
- 물론 지역성의 크기와 프레임 크기가 충분하면 페이지 폴트 없이 지역 참조가 가능하겠지…
예시
- 새 서브루틴(새롭게 호출되는 명령어 함수)이 호출될 때는 서브루틴의 명령어, 지역변수, 일부 전역 변수를 참조한다.
- 이 서브루틴의 실행이 끝나면 프로세스 메모리 참조는 이 지역을 벗어난다.
- 한동안 더이상 참조하지 않겠지만, 언젠가 다시 돌아올 수도 있다.
- 즉, 호출되는 함수가 가진 비슷한 구역의 명령어들을 사용할 것이다.
지역성 모델은 캐싱 기법의 기본 원리이기도 하다.
작업 집합 모델
한 프로세스가 최근 x 만큼의 페이지를 참조를 관찰하겠다는 기본 아이디어.
- 한 프로세스가 최근 x 번 페이지를 참고했다면 그 안에 들어있는 서로 다른 페이지들의 집합 → 작업 집합
- x : 특정 수치
- 페이지가 더 사용되지 않게 되면 마지막 참조로부터 x 만큼의 페이지 참조 후에는 작업 집합에서 제외된다.
- x가 7 이라면 처음 참조할 땐 0 이었는데 점점 1, 2, 3 늘어나며 7을 넘게 참조당하지 않으면 그 작업 집합에서 페이지가 제외된다.
- 작업 집합의 정확도는 x 의 선택에 따라 좌우된다.
- x 가 너무 작다 → 전체 지역을 포함하지 못함.
- x 가 너무 크다 → 여러 지역을 과도하게 수용할 것.
- 극단적으로 x 가 무한히 크다 → 프로세스가 실행 중에 만난 모든 페이지의 집합.
→ 그러므로 집합의 크기가 중요하다.
예시
- 각 프로세스의 작업 집합 크기에 맞는 충분한 프레임을 할당한다.
- 이렇게 할당했는데 여분의 놀고 있는 프레임이 있다 → 새 프로세스 시작 가능.
- 실행 중인 프로세스의 수가 너무 많아져 D(프로세스들의 최소 메모리 요구량의 합)이 m(시스템이 보유한 총 메모리 크기)보다 커지면 → 운영체제는 프로세스를 선택해 페이지를 빼앗고, 연기시키고, 빼앗은 프레임을 다른 프로세스에 준다.
페이지 폴트 빈도(PFF)
직접적으로 스래싱(페이지 폴트율이 너무 높은 것)을 조절하는 법
- 페이지 폴트율이 너무 높다 → 그 프로세스가 더 많은 프레임이 필요하다.
- 근데 남은 가용 프레임이 없으면, 한 프로세스를 선택해서 예비 저장장치로 스왑 아웃 시킴 → 높은 페이지 폴트율을 가진 다른 프로세스들에게 분배.
- 페이지 폴트율이 너무 낮다 → 프로세스가 너무 많은 프레임을 갖고 있다.
→ 따라서, 페이지 폴트율이 상한을 넘으면 그 프로세스에 프레임을 더 할당해주고, 하한보다 낮아지면 그 프로세스의 프레임 수를 줄여 스레싱을 방지한다.
그런데 그거 아세요? 가장 최선책은 가능한 충분한 물리 메모리를 장착하는 것이래요.. 돈 마니 벌고 용량 큰 램 사세요 ^^
메모리 압축
스왑 아웃 대신 여러 프레임을 하나의 프레임으로 압축한다.
- 가용 프레임 리스트에서 제거 된 페이지 n개를 한 프레임에 압축하는 식
- 압축된 프레임 중 하나가 참조되면 압축 해제하여 메모리를 복원한다.
- 모바일 시스템은 페이지 스와핑을 지원하지 않아, 메모리 압축이 메모리 관리 전략의 핵심이다.
- CPU 성능이 좋으면 메모링 압축을 병렬로 수행하여 메모리 압축이 더욱 효과적임!
커널 메모리 할당
커널 메모리는 보통 사용자 모드 프로세스에 할당하는 페이지 리스트와는 별도의 메모리 풀에서 할당받는다.
- 커널은 다양한 크기의 자료 구조를 위해 메모리를 할당 받는데, 페이지 크기보다 작은 크기도 있다.
- 단편화에 의한 낭비를 최소화해야 한다.
- 많은 운영체제들이 커널 코드나 데이터를 페이징하지 않기 때문에 특히 중요하다.
- 물리 메모리에 직접 접근하는 특정 HW 장치는 물리적으로 연속적인 메모리가 있어야하는 경우가 있다.
- 커널은 HW 장치를 관리하기 때문에 연속적인 메모리가 필요하다.
커널 프로세스에 할당되는 메모리를 관리하는 기법
버디 시스템
물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트(메모리를 논리적으로 나눈 단위)로부터 메모리를 할당.
- 2의 거듭 제곱 할당기로 할당한다. (4KB, 8KB, 16KB …)
- 2의 거듭 제곱 크기가 아닌 메모리 요청은 가장 가까운 2의 거듭제곱 크기로 올림된다.
- 예) 5KB 필요 → 8KB 할당
장점
- 합병(coalescing) 으로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다.
단점
- 가장 가까운 2의 거듭제곱으로 올림이 할당되면, 세그먼트 내부 단편화가 일어난다.
- 예) 33KB 요청 → 64KB 세그먼트에 기록
→ 메모리 낭비가 심해서 사용하지 않는 방법
슬랩 할당
- 슬랩(slab) : 하나 또는 그 이상의 연속된 페이지들로 구성
- 캐시(cache) : 하나 혹은 그 이상의 슬랩들로 구성
- 각 커널 자료구조마다 하나의 캐시가 존재.
- 커널 객체를 저장하기 위해 캐시 사용
- 초기에는 캐시 내의 모든 객체가 free
- 객체 할당(할당 된 객체) 되면 used
Linux 에서 슬랩 상태
- Full : 슬랩 내의 모든 객체가 used
- Empty : 슬랩 내의 모든 객체가 free
- Patial : Used, free 객체가 섞여 있음.
슬랩 할당기 동작
- 먼저 patial 슬랩의 free 객체를 이용해 요청을 처리하려고 시도함.
- Patial 슬랩이 없다면 empty 슬랩으로부터 free 객체를 할당
- Empty 슬랩도 없으면 새로운 슬랩을 연속된 물리 메모리에서 할당하여 캐시에 줌.
- 쉽게 말해, 커널이 새로운 슬랩을 할당하기 위해 연속된 물리 메모리 공간을 확보해옴.
슬랩 할당 장점
- 단편화에 의해 낭비되는 메모리가 없다.
- 커널이 메모리 할당을 요구할 때마다 슬랩 할당기는 정확히 필요한 만큼의 메모리만을 할당한다.
- 메모리 요청이 빠르게 처리된다.
- 메모리 할당과 해제는 상당히 시간이 많이 소요 됨.
- 할당 가능한 메모리 주소 찾고, 다 차있으면 비우고~ 채워넣고 등등
- 슬랩 할당에서는 객체들이 미리 생성되어 있고 캐시에서 쉽게 할당 가능
- 커널이 특정 객체를 다 사용하고 해제하면 free 상태로 캐시에 반환 → 다음 요구 시 즉시 할당 가능.
- 메모리 할당과 해제는 상당히 시간이 많이 소요 됨.
SLUB
슬랩은 특정 메타 데이터를 슬랩마다 저장하지만, SLUB 은 페이지 자료구조에 저장한다.
- 한 마디로 캐시를 단순하게 저장.
- CPU당 큐를 포함하지 않고, 하나의 전역 캐시로 취급함.
- 시스템 처리기 개수(CPU) 가 증가할 수록 더 나은 성능을 보인다.
페이징 시스템이 효과적으로 실행되기 위한 기타 고려 사항
페이징 시스템이 효과적으로 실행되기 위한, 페이지 교체 알고리즘과 할당 정책 외의 고려 사항.
페이지 크기
Huge Pages 같은 기술을 이용해 개발자가 페이지 크기를 일부를 조정할 수 있다.
- 페이지 크기를 결정할 수 있는 방법은 여러 가지가 있다.
- 페이지 테이블의 크기
페이지 테이블의 크기
큰 페이지
주어진 가상 메모리 공간에서 페이지 크기를 감소 시키면 → 페이지의 수가 늘어나고 → 결국 페이지 테이블의 크기가 증가한다.
- 예) 4BM(2^22) 가상 메모리에서
- 페이지 크기 : 1,024바이트 → 4,096 페이지
- 페이지 크기 : 8,192바이트 → 512 페이지
- 모든 활성 프로세스는 각자 페이지 테이블을 유지해야하니, 큰 페이지가 좋다.
작은 페이지
내부 단편화를 최소화하기 위해서는 작은 페이지 크기가 좋다.
페이지를 읽거나 쓰는 데 필요한 시간(I/O)
큰 페이지
I/O 시간을 최소화하려고 한다면 큰 페이지가 좋다.
- 작은 페이지 2개를 읽는 것보다 큰 페이지 하나를 읽는 것이 지연 시간과 탐색 시간이 없으니 빠름.
- 페이지 폴트 횟수가 줄어듬
작은 페이지
지역성이 향상되어 전체 I/O 는 줄어들 것이다.
- 1바이트 단위의 페이지를 사용한다면, 실제로 사용될 100KB 만을 정확히 읽어들일 수 있다.
- 정밀도가 좋아진다.
- 하지만 페이지 크기가 1바이트면 → 바이트 접근마다 모두 페이지 폴트가 생김…;;
시대적으로는 페이지 크기가 커지는 추세다. ^_^
TLB Reach (페이지 테이블 캐시 적중률)
TLB 로부터 액세스 할 수 있는 메모리 공간의 크기.
- TLB 항목 수(엔트리 수, 페이지가 들어갈 수 있는 수) x 페이지 크기 = TLB reach
- 이상적으로는 한 프로세스의 작업 집합이 TLB 에 다 들어갈 수 있으면 좋지만, 다 들어가지 못하면 페이지 테이블까지 들러야하고 그러면 수행 시간이 매우 느려짐.
TLB reach 늘리는 법
TLB 크기를 두 배로 늘리면
- TLB reach 크기도 두 배 늘어나지만, 메모리를 많이 필요로하는 프로세스에서는 결국 부족할 수 있다.
페이지 크기를 늘리거나 여러 페이지 크기를 제공
페이지 크기를 4KB 에서 16KB 로 늘리면 TLB reach 가 4배가 됨.
- 큰 페이지 크기가 필요하지 않으면 단편화가 증가할 수 있으나..
- 현대 운영체제는 여러 페이지 크기를 지원한다.
- Linux : 기본 페이지 크기는 4KB 지만, 더 큰 페이지(예: 2MB)가 사용될 수 있는 거대 페이지(Huge Page) 기능도 제공
- ARMv8 : 원래 여러 페이지와 region 제공. 게다가 TLB 항목에 연속 비트가 있어 인접한 메모리 블록 매핑 가능.
- 예) 16x4KB 인접 블록으로 구성된 64KB TLB
- 예) 32x32MB 인접 블록으로 구성된 1GB TLB
- 여러 페이지 크기를 지원하는 TLB 는 운영체제가 페이지 정보를 나타내야 한다.
프로그램 구조
사용자가(또는 컴파일러가) 요구 페이징의 특성을 이해하면 성능을 크게 개선할 수도 있다.
- 배열이 행 중심으로 저장되어있다고 가정하자.
- data[0][0], data[0][1], data[0][2] …
안 좋은 코드의 예
int i, j;
int[128][128] data;
for (j = 0; j < 128; j++) {
for (i = 0; i < 128; i++) {
data[i][j] = 0;
}
}
- 페이지가 128 워드 크기이므로 각 행은 한 페이지를 점유하는데, 각 페이지에서 한 워드씩 0으로 하고 다음 페이지에서 또 다른 워드를 0으로 하면…
- 128 x 128 = 16,384 의 페이지 폴트 초래
좋은 코드의 예
int i, j;
int[128][128] data;
for (i = 0; i < 128; i++) {
for (j = 0; j < 128; j++) {
data[i][j] = 0;
}
}
- 한 페이지에 있는 모든 워드를 0으로 한 다음 → 새 페이지로 옮김
- 페이지 폴트가 128로 감소!!
결론
자료구조와 프로그래밍 구조를 잘 선택하면 지역성을 향상할 수 있고, 페이지 폴트율과 작업 집합의 페이지 수를 줄일 수 있다.
- 스택은 항상 한쪽 끝만 참조하니 지역성이 높다.
- 반대로 해시 테이블은 참조를 분산시키니 지역성이 나쁘다.
- 탐색 속도, 메모리 참조 횟수, 총 페이지 접근 횟수도 중요하다.
컴파일러와 로더
재진입 가능 코드를 생성하면, 변경되지 않은 페이지는 교체 시 페이지 아웃 하지 않아도 된다.
- 재진입 가능 코드 : 중단 되었다가 다시 실행해도 이상 X (전역변수 안 건드림) → 멀티 스레딩 가능.
- 특히 큰 페이지 크기를 갖는 경우에 유용
I/O 상호 잠금과 페이지 잠금
요구 페이징(필요할 때만 페이지를 로드)할 때 페이지의 일부는 메모리에 붙박이로 고정하는 것이 필요할 때가 있다.
- I/O 하려는 메모리 공간이 CPU 사용 중, 다른 프로세스에 할당 되어 버렸다면? → ^^;;;; 다시 불러와야되..
해결책
페이지를 메모리에서 잠금한다.
- 잠금 비트(lock-bit)를 프레임마다 두고 만약 프레임이 잠시면 교체 고려 대상에서 제외한다.
- I/O가 완료되면 그 페이지의 잠금은 해제된다.
사용자 프로세스도 메모리를 잠글 필요가 있다?
- DB 같은 경우, 데이터 사용 방식에 관해 자신이 제일 잘 알고 있음 → 메모리 영역을 직접 관리하기를 원함.
- 그래서 앱이 자신의 영역을 메모리에 고정할 수 있도록 요청하는 시스템 콜도 존재한다!
- 하지만 악용될 수 있고 메모리 관리 알고리즘에 부담을 주니 → 메모리 고정 요청을 하기 위해 앱도 특권이 필요함.
잠금 비트 사용
최소한 한 번이라도 사용될 때 까지는 새롭게 읽힌 페이지를 교체하지 못하도록 하기 위해 잠금 비트를 사용할 수 있다.
- 그러나 위험한 상황이 있을 수도..
- 일단 잠금 비트를 1로 세팅되고 나서 언젠가 해제되어야 하는데 그렇지 않을 수 있음.
- 버그로 잠금된 프레임이 영원히 사용할 수 없게 된다면?ㄷㄷㄷㄷ
- 그래서 운영체제는
- 빈 페이지 풀이 너무 적거나
- 프로세스들이 페이지 잠금을 너무 많이 요구하면 이를 적절히 무시한다.
운영체제별 가상 메모리 구현
Linux
요구 페이징을 사용하여 가용 프레임 리스트에서 페이지를 할당한다.
- 전역 페이지 교체 정책 사용.
- 시스템 전체가 페이지 프레임을 공유하며, 다른 프로세스에서 페이지를 가져옴.
- 자주 사용되는 것이 더 많은 메모리가 다른 프로세스의 메모리를 빼앗아옴.
- 시간이 지남에 따라 최근에 가장 참조되지 않은 (교체될 페이지)가 active_list 맨 앞에 있고 inactive_list 맨 뒤로 이동한다.
- 참조되면 다시 active_list 맨 뒤로..
kswapd
사용 가능한 메모리가 특정 임계값 아래로 떨어지면 kswapd 가 inactive_list 에서 페이지를 검사하여 가용 프레임 리스트로 회수한다.
Windows
windows 10 은 클러스터링이 가미된 요구 페이징을 사용해 가상 메모리를 구현한다.
- 클러스터링 : 메모리 참조의 지역성을 인지하는 전략으로, 페이지 폴트가 발생한 페이지뿐만 아니라 그 페이지 앞뒤 페이지들을 함께 메모리로 읽어들임.
- 지역 및 전역 페이지 교체 정책을 조합해 LRU 근사 클록 알고리즘 을 사용한다.
- 최근에 사용되지 않은 페이지를 교체
- 사용 가능한 메모리 양이 충분하지 않으면 커널은 프로세스의 작업-집합에서 **지역 LRU 페이지 교체 정책**을 사용해 교체할 페이지를 선택하고, 임계값보다 높아지도록 값을 복원한다.
- 다른 프로세스가 아니라 내 프레임 안에서 페이지를 교체하는 것.
- 메모리가 충분하거나 프로세스(유휴 상태인 더 큰 프로세스)가 작업-집합 최솟값에 도달할 때까지 작업-집합에서 페이지를 제거한다.