운영체제 (Operating Systems) 가상 메모리 (Virtual Memory) 문양세 강원대학교 IT대학 컴퓨터과학전공

강의 목표 가상 메모리 가상 메모리 도입 배경 지금까지는 “프로세스 전체가 실행 전에 메모리에 올라와야 한다”는 전제로 논의하였다. 가상 메모리는 프로세스 전체가 메모리에 있지 않아도 실행 가능하다. 물리 메모리로부터 논리 메모리를 분리시켜 엄청나게 큰 배열로 추상화시켜 준다. 강의 목표 가상 메모리 시스템의 장점을 이해한다. 요구 페이징(demand paging), 페이지 교체 정책, 메모리 사상 파일 등의 가상 메모리 기술에 대해 학습한다.

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

배경(Background) 가상 메모리 가상 메모리(virtual memory)는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한다. 프로그램의 일부만을 메모리에 올려놓고 실행한다.  현재 실행되고 있는 프로세스가 반드시 물리 메모리에 있어야 한다는 조건을 완화 주어진 물리 메모리 보다 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다. 가상 메모리가 필요한 사례 프로그램의 상당 부분은 거의 실행이 되지 않는 부분이 있다. (예: 오류 처리) 배열, 리스트, 테이블 등은 필요 이상으로 크게 할당하는 경우가 많다. 프로그램 내의 어떤 옵션이나 기능은 거의 사용되지 않는다. (예: 예산 관련 루틴) 가상 메모리 구현 요구 페이징(demand paging) 요구 세그먼트(demand segmentation)

물리 메모리보다 큰 가상 메모리 가상 메모리

프로세스의 가상 주소 공간 스택은 위에서 아래로, 힙은 아래에서 위로 할당된다. 중간의 공백도 가상 주소 공간의 일부이다. 가상 메모리 스택은 위에서 아래로, 힙은 아래에서 위로 할당된다. 중간의 공백도 가상 주소 공간의 일부이다. 이들 공백은 스택이나 힙이 확장되어야만 실제 물 리 페이지를 요구하게 된다. 가상 메모리에서 공백은 실제 메모리가 할당되지 않는다.

가상 메모리를 사용할 때의 공유 라이브러리 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있다. 가상 메모리는 프로세스들이 메모리를 공유하는 것을 가능하게 한다. (예제: Linux의 shared memory) 가상 메모리는 fork()를 통한 프로세스 생성에서 페이지 공유를 가능하게 하고, 이에 따라 프로세스 생성 속도를 빠르게 할 수 있다.

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

요구 페이징(Demand Paging) 필요한 페이지만을 물리 메모리에 적재한다. 게으른 스와퍼(lazy swapper) 가상 메모리 필요한 페이지만을 물리 메모리에 적재한다. 사용되지 않는 페이지를 메모리에 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비 를 줄임 장점: 입출력 과정 감소, 적은 메모리 사용, 빠른 응답, 더 많은 사용자 허용 게으른 스와퍼(lazy swapper) 프로세스를 실행하고 싶으면 메모리로 읽어 들이되, 필요한 페이지만 적재한다. 페이지를 관리하는 스와퍼를 페이저(pager)라 한다. 스와핑 vs 페이징 (스와퍼 vs 페이저) 스와핑: 프로세스 전체를 디스크에 내리거나(swap out), 메모리에 올린다(swap in). 페이징: 필요한 페이지만을 메모리에 올리거나, 필요치 않은 페이지는 디스크에 내린다.

디스크 내 인접한 공간과 페이지화 된 메모리 간 이동 가상 메모리

유효-무효 비트(Valid-Invalid Bits) 가상 메모리 페이지가 메모리에 올라와 있는지를 구별하기 위해 페이지 테이블에 유 효-무효 비트를 관리한다. 유효비트(v, valid)로 세트되면 페이지가 메모리에 있음을 표시한다. 무효비트(i, invalid)로 세트되면 페이지가 메모리에 없음을 표시한다. 프로세스가 접근하는 페이지가 무효비트 i로 세트 되어 있다면 페이지 부재(page fault)가 발생한다. v i …. frame # valid-invalid bit page table

유효-무효 비트 예제 가상 메모리

페이지 부재(Page Fault) 가상 메모리 프로세스가 메모리에 올라와 있지 않는 페이지를 접근하는 경우 페이지 부재 트랩(page fault trap)이 발생한다. 좀 더 기술적으로 이야기 하면, 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에서 무효 비트를 발견하고 운영체제에게 트랩을 건다. 페이지 부재 처리 과정 1. 운영체제는 내부 테이블(PCB와 함께 유지)을 검사하여 메모리 참조가 유효한지 그렇지 않은지를 조사한다. 유효하지 않은 참조  프로세스 중단 유효한 참조  해당 페이지를 읽어오는 작업을 진행 2. 빈 공간, 즉 자유 프레임(free frame)을 검색한다. 3. 새로 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다. 4. 페이지 테이블을 갱신한다. 5. 트랩에 의해 중단된 명령어(즉, 프로세스)를 다시 수행한다.

페이지 부재 처리 과정 가상 메모리

요구 페이징의 성능 (Performance of Demand Paging) 가상 메모리 유효 접근 시간(effective access time) = (1 – p) x ma + p x 페이지_부재_처리시간 p: 페이지의 부재 확률(0  p  1), (기대하기로) 0에 무척 가까울 것임 ma: 메모리 접근 시간(memory access time) 페이지_부재_처리시간: 인터럽트 처리 + 페이지 읽기 + 프로세스 재시작 페이지_부재_처리시간 인터럽트 처리: 페이지 부재가 발생하면 운영체제에 트랩으로 페이지 부재를 알린다. 페이지 읽기: 디스크로부터 자유 프레임에 페이지를 읽는다. (이때 CPU는 다른 프로세스에게 할당된다.) 프로세스 재시작: CPU가 다시 할당될 때까지 기다리고, 문맥 전환에 의해 다시 실행을 재개한다.

요구 페이징의 성능 예제 가정 유효 접근 시간 메모리 접근 시간: 200ns (최근 하드웨어는 대개 10ns~200ns) 가상 메모리 가정 메모리 접근 시간: 200ns (최근 하드웨어는 대개 10ns~200ns) 페이지 부재 처리시간: 8ms (디스크 관련 시간은 기본적으로 무척 길다.) 유효 접근 시간 (1 – p) x 200ns + p x 8,000,000ns = 200 + 7,999,800 x p 1000번에 한 번 접근 시 페이지 부재가 발생한다면, 유효 접근 시간은 8.2s  요구 페이징으로 인해 40배 느려짐 (= 8,200 / 200 = 약 40)

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

쓰기-시-복사(Copy-on-Write) 가상 메모리 가상 메모리는 프로세스 생성(fork()) 시 페이지를 공유하여 프로세스 생성 시간을 크게 줄일 수 있다. 원칙적으로, 자식 프로세스가 생성되면 부모 프로세스를 그대로 복사하게 된다. 생성된 자식 프로세스는 대개 후속의 exec() 호출을 통해 다른 프로세스가 되는데, 굳이 부모 프로세스를 그대로 복사하는 것 보다는 공유하는 것이 유리하다. 쓰기-시-복사 자식 프로세스가 시작할 때, 부모 프로세스의 페이지들을 당분간 함께 공유한다. 둘 중 한 프로세스가 공유 중인 페이지에 쓸 때, 페이지의 복사본을 생성한다. 수정되는 페이지만 복사본을 만들어 효율적으로 프로세스를 관리한다.

쓰기-시-복사 예제 가상 메모리 process1이 page C를 수정하기 전 process1이 page C를 수정한 후

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

페이지 교체(Page Replacement) 가상 메모리 모든 메모리가 사용 중이어서 빈 프레임이 없는 경우는? 다중 프로그래밍 정도를 높이면 과할당(over-allocating)이 발생한다. 할당 가능한 메모리 프레임이 없다면 페이지 교체를 수행해야 한다. 페이지 교체 알고리즘(page replacement algorithm) 사용 중인 페이지 중 하나를 선택하여 교환한다. 새로운 페이지를 메모리로 가져온다. 대신에 교체되는 페이지(victim)는 디스크에 저장한다. 수정된 페이지만을 디스크에 저장하여 페이지 전송 오버헤드를 줄임 변경 비트(modify bit, dirty bit) 사용

페이지 교체의 필요성 가상 메모리 사용자 1의 페이지 M이 로드된 후, 사용자 2의 페이지 B가 요청되었다 하자.  페이지 B를 로드 할 메모리 프레임이 부족하므로, 페이지 교체가 필요하다.

기본적인 페이지 교체 페이지 부재 서비스 루틴의 수정 (아래 2번이 확장되었다) 가상 메모리 페이지 부재 서비스 루틴의 수정 (아래 2번이 확장되었다) 1. 디스크에서 필요한 페이지의 위치를 알아낸다. 2. 빈 페이지 프레임을 찾는다. 빈 페이지 프레임이 있다면 그것을 사용한다. 없다면 희생 프레임(victim frame)을 선정하기 위해 페이지 교체 알고리즘을 가동한다. 희생 페이지를 디스크에 기록하고 관련 테이블을 수정한다. 3. 비워진 프레임에 새 페이지를 읽어오고 프레임 테이블을 수정한다. 4. 사용자 프로세스를 재시작한다.

페이지 교체 과정 가상 메모리

요구 페이징과 페이지 교체 페이지 교체는 요구 페이징의 기본이다. 가상 메모리 페이지 교체는 요구 페이징의 기본이다. 이를 통해 논리 메모리와 물리 메모리 간의 분리가 완성된다. 매우 작은 물리 메모리로도 프로그래머에게 광대한 가상 메모리를 제공한다. 페이지 부재의 오버헤드: 통상 2번의 디스크 입출력이 일어난다. 변경 비트(dirty bit or modify bit)를 사용하여 감소시킬 수 있다. 특히, 읽기 전용 페이지(이진 코드 페이지)의 경우 변경 없이 사용할 수 있다. 요구 페이징의 두 가지 중요한 문제 프레임 할당: 여러 프로세스가 존재할 경우, 각 프로세스에게 얼마나 많은 프레임을 할 당해야 하는가? (제9.5절에서 다루나, 본 강의에서는 다루지 않음) 페이지 교체 알고리즘: 어떤 페이지를 교체해야 하는가?

페이지 교체 알고리즘(Page Replacement Algorithm) 가상 메모리 페이지 부재율(page-fault rate)이 가장 낮은 것을 선정한다. 페이지 교체 알고리즘의 성능 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 부재 발생 횟수를 계산하여 평가한다. 메모리 주소의 참조 나열을 참조열(reference string)이라고 한다. 참조열의 예제 페이지 크기가 100바이트라 가정하자. 주소열: 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 참조열: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

페이지 부재 횟수 vs 프레임 개수 그래프 앞서와 같이 6개 페이지에 대해 아래 참조열로 실험하였을 경우임 가상 메모리 앞서와 같이 6개 페이지에 대해 아래 참조열로 실험하였을 경우임 참조열: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 페이지 프레임이 한 개 이면, 매번 부재 발생  총 11번 페이지 프레임이 6개 이면 부재가 발생하지 않음  총 0번

FIFO 페이지 교체(FIFO Page Replacement) (1/2) 가상 메모리 메모리에 올라온 기간이 가장 오래된 페이지를 희생자로 선택한다. 각 페이지들에 대해 메모리에 올라온 시간을 기록한다. 혹은 페이지에 올라온 순서로 FIFO 큐를 유지한다. FIFO 페이지 교체 알고리즘의 예제 3개의 페이지 프레임 15개의 페이지 부재 발생

FIFO 페이지 교체(FIFO Page Replacement) (2/2) 가상 메모리 논의사항 FIFO 알고리즘은 매우 간단하고, 오래된 놈을 내쫓으니 일견 일리가 있다. 문제점1: 자주 쓰이던 거의 쓰이지 않던 동일하게 취급되는 문제가 있다. 문제점2: Belady의 모순의 발생한다. (다음 페이지)

Belady의 모순(Belady’s Anomaly) 가상 메모리 Belady의 모순 프레임을 더 늘였는데 오히려 페이지 부재율이 더 증가하는 현상을 일컫는다. FIFO 알고리즘은 Belady의 모순이 발생한다. 예제: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3개 프레임  9개 부재 발생 4개 프레임  10개 부재 발생 1 2 3 4 5 9 page faults 10 page faults

Belady의 모순을 보여주는 FIFO 가상 메모리

최적 페이지 교체(Optimal Page Replacement) (1/2) 가상 메모리 앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체한다. 모든 알고리즘 보다 낮은 페이지 부재율을 보이는 최적 알고리즘이다. Belady의 모순이 발생하지 않는다. 최적 페이지 교체의 예제(9번 발생, FIFO는 15번 발생)

최적 페이지 교체(Optimal Page Replacement) (2/2) 가상 메모리 문제점: 앞으로 가장 오랜 동안 사용되지 않을 페이지를 어떻게 알 수 있는가? 특수한 경우를 제외하고는 프로세스가 페이지를 어떻게 참조할 것인지 알 수 없다. 최적 페이지 교체 알고리즘은 주로 비교 연구 목적을 위해 사용한다.

LRU 페이지 교체(LRU Page Replacement) 가상 메모리 LRU: Least Recently Used 가장 오랜 기간 동안 참조되지 않은 페이지를 희생자로 선택한다. 최근의 과거를 가까운 미래의 근사치로 추정하는 접근법이다. LRU 페이지 교체 알고리즘 적용 예제 페이지 부재 횟수: LRU = 12, FIFO = 15, OPT = 9

LRU 알고리즘 구현 계수기(counter) 스택(stack) 각 페이지 항목마다 계수기(시간 필드) 추가한다. 가상 메모리 계수기(counter) 각 페이지 항목마다 계수기(시간 필드) 추가한다. 페이지 참조마다 계수기를 증가시킨다. 페이지 교체 시, 계수기가 가장 작은 페이지를 희생자로 선택한다. LRU 페이지를 찾기 위해 페이지 테이블을 검색해야 함 메모리 참조마다 계수기 갱신을 위해 메모리 쓰기가 발생함  계수기 등 유지를 위해 하드웨어 지원이 필요하다. 스택(stack) 페이지 번호의 스택을 유지한다. (참고: 스택은 대개 이중 연결 리스트로 구현) 페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 꼭대기(top)에 놓 인다. 페이지 테이블 검색 필요 없음 포인터 값 변경 오버헤드  (하드웨어 지원 없이) 소프트웨어나 마이크로 코드 구현에 적합하다.

LRU 스택의 사용 예 가상 메모리

계수-기반 페이지 교체의 다른 기법 LFU(Least Frequently Used) 알고리즘 가상 메모리 LFU(Least Frequently Used) 알고리즘 참조 횟수가 가장 작은 페이지를 교체한다. “활발하게 사용되는 페이지가 앞으로도 더 많이 참조될 것”이라는 직관에 기반 초기에 한 페이지를 집중 사용하다가 나중에 사용하지 않을 경우 판단이 틀린다. MFU(Most Frequently Used) 알고리즘 참조 횟수가 가장 큰(많은) 페이지를 교체한다. “가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조되었고 앞으로도 많이 사용될 것” 이라는 직관에 기반한다.

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

메모리 사상 파일(Memory-Mapped File) 가상 메모리 파일을 다룰 때 빈번한 read()/write() 시스템 호출 대신에 파일을 메모리 처럼 사용할 수 있는 방법은 없을까? 디스크의 파일을 메모리에 사상시키고, 메모리 접근하듯이 파일을 사용한다. 메모리를 통한 파일 입출력을 통해 파일 접근과 사용을 단순화한다. Solaris 등에서 mmap() 시스템 호출로 기능을 제공한다. 메모리 사상 파일 입출력은 디스크 블록을 메모리 참조로 변환한다. 메모리 내 페이지와 관련시켜 사상(mapping)한다. 디스크의 페이지들이 메모리의 물리 페이지로 적재된 후, 이후 파일 읽기/쓰기는 일반 메모리 접근으로 처리한다. 메모리 내의 페이지들이 공유되어 여러 프로세스들이 같은 파일에 사상 될 수도 있다. (공유 메모리와 같이, 갱신 시 동기화 기법이 필요함)

메모리 사상 파일 예제 디스크 파일의 6개 페이지는 물리 메모리 6개 페이지에 매핑되어 있다. 가상 메모리 디스크 파일의 6개 페이지는 물리 메모리 6개 페이지에 매핑되어 있다. 프로세스 A와 B는 가상 메모리를 통해 파일을 메모리로 인식하고 사용한다.

쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 강의 목차 가상 메모리 배경 요구 페이징(Demand Paging) 쓰기-시-복사(Copy-on-Write) 페이지 교체(Page Replacement) 메모리 사상 파일(Memory-Mapped Files) 요약

요약 (1/2) 가상 메모리(virtual memory) 요구 페이징(demand paging) 쓰기-시-복사 물리 메모리와 논리 메모리 개념을 분리, 물리 메모리보다 훨씬 큰 가상 주소 공간을 제공 요구 페이징(demand paging) 필요한 페이지만을 물리 메모리에 적재 스와핑(프로세스 단위) vs 페이징(페이지 단위) 페이지 부재: 메모리에 없는 페이지 참조 시 발생 쓰기-시-복사 부모-자식 프로세스에서, 초기에 복사하지 않고, 쓰기 시에 페이지 복사

요약 (2/2) 페이지 교체 메모리 사상 파일 할당 가능한 페이지가 없으면 페이지 교체 수행 가상 메모리 페이지 교체 할당 가능한 페이지가 없으면 페이지 교체 수행 페이지 교체 알고리즘: FIFO, OPT, LRU, LFU, MFU LRU 알고리즘 구현: 계수기 vs 스택 메모리 사상 파일 디스크 파일을 가상 메모리 매핑시켜 사용