가상 메모리
물리 메모리의 크기와 프로세스가 올라갈 메모리 위치를 신경 쓰지 않고 프로그래밍하도록 지원
가상 메모리는 물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술
프로세스는 운영체제가 어디에 있는지 물리 메모리의 크기가 어느 정도인지 신경 쓰지 않고 메모리를 마음대로 사용 가능
가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 자신이 메모리의 어느 위치에 있는지 상관없이 0번지부터 시작하는 연속된 메모리 공간이다
논리 주소는 물리 메모리의 주소 공간에 비례하고 가상 주소는 물리 메모리 공간이 아닌 가상의 주소 공간을 갖는다
When a process asks for dynamic memory, it doesn’t get additional frames; instead, it gets the right to use a new range of virtual address space (e.g., memory region in Linux).
가상 메모리는 크게 프로세스가 바라보는 메모리 영역과 메모리 관리자가 바라보는 메모리 영역으로 나뉜다
가상 메모리의 최대 크기는 CPU 비트에 따라 결정된다
예를 들어 32 비트 CPU의 경우 2의 32승 - 1 즉, 4GB가 메모리 최대 크기고 가상 메모리 최대 크기도 4GB이다
가상 메모리 시스템에서는 물리 메모리의 내용 중 일부를 하드디스크의 일부 공간, 즉 스왑 영역으로 옮긴다
스왑 영역은 하드디스크에 존재하지만 메모리 관리자가 관리하는 영역으로서 메모리의 일부이며 가상 메모리의 구성 요소 중 하나이다
메모리 관리자는 물리 메모리의 부족한 부분을 스왑 영역으로 보충한다
즉, 물리 메모리가 꽉 차면 일부 프로세스를 스왑 영역으로 보내고 swap out
몇 개의 프로세스가 작업을 마치면 스왑 영역에 있는 프로세스를 메모리로 가져온다 swap in
가상 메모리 크기
가상 메모리에서 메모리 관리자가. 사용할 수 있는 메모리의 전체 크기는 물리 메모리(실제 메모리)와 스왑 영역을 합친 크기이다.
Dynamic Address Traslation, DAT 동적 주소 변환
가상 메모리 시스템에서 메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주로를 실제 메모리의 물리 주소로 변환한다
DAT를 거치면 프로세스가 아무 제약 없이 사용자의 데이터를 물리 메모리에 배치 가능하다
이 과정에서 메모리 관리자는 물리 메모리를 어떤 방법으로 나눌지, 사용자 프로세스를 어디에 배치할지, 부족한 물리 메모리를 어떻게 처리할지 등의 복잡한 문제를 처리한다
가상 메모리의 메모리 분할 방식
실제 메모리에 있는 물리 주소 0번지는 os 영역이기 때문에 일반 프로세스가 사용 불가하다
따라서 가상 메모리 시스템에서는 os를 제외한 나머지 메모리 영역을 일정한 크기로 나누어 일반 프로세스에 할당한다
페이징, 세그멘테이션 기법이 있는데 세그멘테이션은 외부 단편화 등의 문제로 잘 사용되지 않는다
또한 페이징 기법은 페이지 관리에 어려움이 있어 두가지를 혼용하여 주로 사용한다
매핑 테이블의 필요성과 역할
가상 메모리 시스템에서 가상 주소는 실제로 물리 주소나 스왑 영역 중 한 곳에 위치하며 메모리 관리자는 가상 주소와 물리 주소를 일대일 매칭 테이블로 관리한다
페이징 기법
물리 주소 공간을 같은 크기로 나누어 사용한다
가상 주소의 page와 물리 메모리의 frame 크기는 같다
페이지와 프레임은 크기가 같기 때문에 페이지는 어떤 프레임에도 배치 가능하다
페이지 테이블에는 페이지의 위치 정보, 즉 어떤 페이지가 어떤 프레임에 있는지에 대한 연결(매핑) 정보가 담겨있다
페이지 테이블은 하나의 열 column으로 구성된다
페이지가 물리 메모리에 없으면 페이지 테이블에 invalid라고 표시되며 이는 해당 페이지가 스왑 영역에 있다는 뜻이다
Page table is per-process data structure and is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PRLR) indicates size of the page table
주소 변환 과정
VA = <P, D>
가상 주소 = <페이지, 페이지의 처음 위치~해당 주소까지의 거리>
PA = <F, D>
물리 메모리 주소 = <프레임, 프레임의 처음 위치~해당 주소까지의 거리>
페이지 테이블은 페이지 번호, 프레임 번호로 구성된 페이지 테이블 엔트리의 집합
(페이지 번호가 순서대로 저장되지 않은 경우, 일반적으로는 프레임 번호만 갖는다)
테이블 관리 문제점
전체 페이지 테이블의 크기는 프로세스의 수에 비례해서 커짐
물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨지는 것이 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨짐
+) 페이지 테이블에 빠르게 접근하기 위해 레지스터가 존재
각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 재빨리 파악할 필요가 있다
각 페이지 테이블의 시작 주소를 Page Table Base Register PTBR 페이지 테이블 기준 레지스터에 보관한다
PTBR은 각 프로세스의 프로세스 제어 블록에 저장되는 데이터로 물리 메모리 내에 페이지 테이블의 시작 주소를 갖는다
페이지 테이블 매핑 방식
- 직접 매핑 direct mapping
- 연관 매핑 associative mapping
- 집합-연관 매핑 set-associative mapping
- 역매핑 invert mapping
Example: Two-Level Page-Table
직접 매핑
직접 매핑은 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식
별다른 부가 작업 없이 바로 주소 변환이 가능하기 때문에 직접 매핑이라고 부름 -> 속도 빠름
연관 매핑
페이지 테이블 전체를 스왑 영역에서 관리하는 방식
물리 메모리의 여유 공간이 작을 때 사용하는 방식으로 모든 페이지 테이블을 저장장치의 스왑 영역에 저장하고 그중 일부만 물리 메모리에 가지고 있는다
무작위로 저장된 일부분의 테이블을 변환 색인 퍼버 Translation Look-aside Buffer TLB / associate register 연관 레지스터라고 부름
TLB는 페이지 번호와 프레임 번호로 구성된 작은 크기의 테이블
- 메모리에 접근하기 위해 먼저 TLB를 찾는다
- 원하는 페이지 번호가 TLB에 있으면 hit, 곧바로 물리 주소로 변환
- 없는 경우 miss, 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환
페이지 테이블의 일부만 무작위로 가져오기 때문에 페이지 번호와 프레임 번호 둘 다 표시한다
전체 페이지 테이블을 물리 메모리에 보관하지 않아도 되어 메모리 절약 가능
그러나 TLB miss가 빈번히 발생하면 시스템 성능 저하 우려!
주소 변환 시 직접 매핑은 원하는 프레임 번호를 한 번에 바로 얻지만 연관 매핑은 물리 메모리 내의 페이지 테이블을 다 검색해야 하는 번거로움이! 시간 낭비!
집합-연관 매핑
연관 매핑의 문제를 개선한 방식으로 모든 페이지 테이블을 스왑 영역에서 관리하고 일부한 물리 메모리로 가져오는 원리는 같다
하지만 연관 매핑에서는 물리 메모리에 있는 데이터가 무작위로 올라오기 때문에 원하는 프레임 번호를 얻기 위해 모든 테이블을 검색해야 하는 문제가 발생
-> 집합-연관 매핑은 페이지 테이블을 일정한 집합으로 자르고 자른 덩어리 단위로 물리 메모리에 가져옴
새로 set table을 생성해서 일정하게 자른 페이지 테이블이 물리 메모리에 있는지, 스왑 영역에 있는지 위치 정보 표시
-> 전체 테이블을 찾아보지 않아도 TLB miss 알 수 있음
directory mapping, multi page mapping이라고도 부름
역매핑
Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs
페이지 번호 기준이 아닌물리 메모리의 프레임 번호를 기준으로 테이블 구성
물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는지 표시
프로세스의 수와 상관없이 테이블이 하나만 존재
테이블의 크기가 작지만 프로세스가 가상 메모리에 접근할 때 프로세스 아이디와 페이지 번호를 모두 찾아야 한다는 번거로움이! 속도 느림!
요구 페이징
프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것은 가져오기 정책이다
가져오기 정책은 프로세스가 요청할 때 메모리로 가져오는 방법이 일반적이며 이를 요구 페이징이라고 한다
요구 페이징의 개요
메모리를 절약 및 효율적으로 관리하고 응답 속도를 향상시키기 위해 프로세스의 일부만 메모리로 가져온다
반대로 미리 가져오기는 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식이며 대표적인 예시로 캐시가 있다
캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다놓음으로써 시스템의 성능을 향상시킨다
그러나 미리 가져온 데이터가 쓸모 없는 경우 피해가 크기 때문에 주로 요구 페이징을 사용한다
페이지 테이블 엔트리의 구조
가상 메모리 크기는 물리 메모리와 스왑 영역을 합친 것으로
스왑 영역은 하드디스크에 존재하나 메모리 관리자가 관리하는 영역으로 가상 메모리의 구성 요소 중 하나이다
스왑인 : 스왑 영역에서 물리 메모리로 데이터를 가져오기
스왑아웃 : 물리 메모리에서 스왑 영역으로 데이터 내보내기
가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 위치
이때 페이지가 스왑 영역에 있는 경우
- 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우
- 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우
어떤 경우든 페이지 테이블에는 페이지가 메모리에 있는지
아니면 스왑 영역에 있는지 표시해야 한다 -> valid bit 사용
Page Table Entry
페이지 테이블의 한 행
페이지 번호, 플래그 비트, 프레임 번호로 구성
마지막에 있는 프레임 번호는 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려주는 자료 구조로 페이지 테이블의 핵심
메모리 관리자는 찾은 프레임 번호를 이용하여 가상 주소를 물리 주소로 변환
access bit
페이지가 메모리에 올아온 후 사용한 적이 있는지 알려준다
즉 해당 메모리에 읽기나 실행 작업을 했다면 1이 되고 reference bit라고도 부름
modified bit
페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려준다
즉 해당 메모리에 쓰기나 추가 작업이 있었다면 1이 되도 dirty bit이라고도 부름
valid bit
페이지가 실제 메모리에 있는지 나타낸다
가상 메모리 시스템에서는 물리 메모리가 부족하면 일부 페이지가 스왑 영역으로 옮겨진다
이는 프로세스가 물리 메모리에 접근했을 때 해당 데이터가 메모리에 있지 않고 저장장치에 있을 수 있다는 의미다 present bit이라고도 부름
read bit, write bit, execute bit
혼용 기법에서 테이블의 크기를 줄이기 위해 right bit을 세그멘테이션 테이블로 옮긴다
페이지 부재 page fault
가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지 스왑 영역에 있는지 표시하기 위해 valid bit을 사용한다
- valid bit이 0일 때 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장됨
- valid bit이 1일 때 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지 주소가 저장됨
페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야함
어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘을 page replacement algorithm이라고 victim page를 찾아낸다
세그멘테이션 오류와 페이지 부재 차이
세그멘테이션 오류는 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생
즉 사용자 프로세스에 의해 발생하며 해당 프로세스를 강제 종료하여 해결
페이지 부재는 해당 페이지가 물리 메모리에 없을 때 발생하는 오류로 사용자 프로세스와 무관!
페이지 부재가 발생하면 메모리 관리자는 스왑 영역에서 해당 페이지를 물리 메모리로 옮긴 후 작업을 진행한다
victim page를 찾을 때는 Locality 지역성을 바탕으로 한다
앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템 성능을 향상시키다
세그멘테이션
Memory-management scheme that supports user view of memory
Logical address space is divided into segments with variable size.
Address translation is done through segment table that contains the base address and its length.
물리 메모리를 프로세스 크기에 따라 가변적으로 나누어 사용하는 방법
세그멘테이션 테이블에서는 세크먼트의 크기를 나타내는 limit와
물리 메모리상의 시작 주소를 나타내는 address가 있다
페이징 기법에서는 메모리를 같은 크기의 페이지 단위로 분할하기 때문에 매핑 테이블에 크기 정보를 유지할 필요 ㄴㄴ
하지만 세그멘테이션 기법에서는 프로세스의 크기에 따라 메모리를 분할하기 때문에 매핑 테이블에 크기 정보를 포함해야 한다!
각 세그먼트가 자신에게 주어진 메모리 영역을 넘어가면 안 되기 때문에 세그먼트의 크기 정보에는 크기를 뜻하는 size 대신 limit을 사용한다
장점은 메모리를 프로세스 단위로 관리하기 때문에 페이지 테이블이 작고 단순하다는 것이고
단점은 물리 메모리의 외부 단편화로 인해 물리 메모리 관리가 복잡하다
세그멘테이션 기법의 주소 변환
VA = <S, D>
가상 주소 = <세그먼트 번호, 세그먼트 시작 지점~해당 주소까지의 거리>
가상 메모리 시스템에서 사용자에게 보이는 메모리는 항상 0부터 시작하기 때문에 페이징이든 세그멘테이션이든 D는 사용자가 지정한 주소 그자체이다
세그멘테이션 테이블의 limit은 메모리를 보호하는 역할
프로세스 크기보다 더 큰 주소에 접근하려고 하면 메모리 관리자는 해당 프로세스를 강제종료하는데 이 때 발생하는 오류를 트랩이라고 한다 -> segmentation fault
세그멘테이션-페이징 혼용 기법
메모리 접근 권한
메모리 접근 권한은 메모리의 특정 번지에 저장된 데이터를 사용할 수 있는 권한으로 read, write, execute, append 권한이 있다
프로세스는 코드 영역, 데이터 영역, 실행을 위한 스택 영역과 프로세스 제어 블록 PCB로 구성됨
세그멘테이션-페이징 혼용 기법의 도입
페이지마다 접근 권한이 다르기 때문에 페이지 테이블의 모든 행에는 메모리 접근 권한과 관련된 right bit 권한 비트가 추가됨
메모리 관리자는 주소 변환이 이루어질 때마다 페이지 테이블의 권한 비트를 이용하여 유용한 접근인지 아닌지 확인한다
페이지 테이블에 권한 비트가 추가되면 페이지 테이블 크기가 커진다
-> 인접한 페이지의 메모리 접근 권한이 같은 경우가 많은데도 불구하고 페이지마다 권한 비트를 설정하여 메모리를 낭비하는 요소가 된다
-> 권한 비트를 줄이는 방법이 필요
권한 비트 추가에 따라 페이지 테이블 크기가 커지는 문제는 세그멘테이션 테이블을 이용하면 된다
페이지로 분할된 가상 주소 공간에서 서로 관련 있는 영역을 하나의 세그멘트로 묶어 세그멘티이션 테이블로 관리하고 각 세그먼트를 구성하는 페이지를 해당 페이지 테이블로 관리한다
-> 각 세그멘테이션 테이블은 자신과 연결된 페이지 테이블의 시작 주소를 갖는다
세그멘테이션-페이징 혼용 기법의 주소 변환
VA = <S, P, D>
가상 주소 = <세그먼트 번호, 페이지 번호, 페이지의 처음 위치~해당 주소까지의 거리>
요구 페이징
프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것은 가져오기 정책이다
가져오기 정책은 프로세스가 요청할 때 메모리로 가져오는 방법이 일반적이며 이를 요구 페이징이라고 한다
요구 페이징의 개요
메모리를 절약 및 효율적으로 관리하고 응답 속도를 향상시키기 위해 프로세스의 일부만 메모리로 가져온다
반대로 미리 가져오기는 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식이며 대표적인 예시로 캐시가 있다
캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다놓음으로써 시스템의 성능을 향상시킨다
그러나 미리 가져온 데이터가 쓸모 없는 경우 피해가 크기 때문에 주로 요구 페이징을 사용한다
Use modify (dirty) bit to reduce overhead of page transfers – only
modified pages are written to disk.
Need an algorithm which will result in minimum number of page faults.
Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string.
페이지 테이블 엔트리의 구조
가상 메모리 크기는 물리 메모리와 스왑 영역을 합친 것으로
스왑 영역은 하드디스크에 존재하나 메모리 관리자가 관리하는 영역으로 가상 메모리의 구성 요소 중 하나이다
스왑인 : 스왑 영역에서 물리 메모리로 데이터를 가져오기
스왑아웃 : 물리 메모리에서 스왑 영역으로 데이터 내보내기
가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 위치
이때 페이지가 스왑 영역에 있는 경우
- 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우
- 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우
어떤 경우든 페이지 테이블에는 페이지가 메모리에 있는지
아니면 스왑 영역에 있는지 표시해야 한다 -> valid bit 사용
FIFO 선입선출
시간상으로 메모리에 먼저 들어온 페이지를 victim page로 선정한다
Optimal (OPT or MIN) 최적
메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 victim page로 선정한다
Least Recently Used (LRU)
페이지에 접근한 시간 기준으로 victim page 선정한다
Second Chance (Clock) Algorithm
Memory-Mapped Files
Reference Bit Algorithm
각 페이지에 일정 크기의 참조 비트를 만들어 사용한다
참조 비트의 초기값은 0이고 페이지에 접근할 때마다 1로 바뀐다
주기적으로 오른쪽으로 한 칸씩 이동한다
스레싱
If a process does not have enough pages, the page-fault rate is very high (assume global replacement)
Thrashing is a process is spending more time swapping pages in and out than executing
하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태
degree of multiprogramming
How to Monitor Working Set
Example = 10,000 references (continued)
If a page fault occurs, we can examine the current reference bit and two in-memory bits to determine whether a page was used within the last 10,000 to 15,000 references
frame allocation
Need enough frames to hold all the different pages that any single instruction can reference.
static : equal, proportional
dynamic : working set model, page fault frequency
정적 할당 방식은 프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정하는 것으로 균등, 비례 할당 방식이 있다
먼저 균등 할당은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다
크기가 큰 프로세스의 경우 필요한만큼 프레임을 할당받지 못하여 페이지 부재가 빈번히 발생한다
비례 할당은 프로세스 크기에 비례하여 프레임을 할당한다
이러한 정적 할당 방식은 프로세스를 실행하는 초기에 프레임을 할당하기 때문에 프로세스 실행 중에 메모리 요구를 반영하지 못한다 이러한 점을 극복한 방법이 바로 동적 할당이다
working set model은 locality를 바탕으로 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다는 가정에서 출발한다
working set windows 크기에 따라 프로세스 실행 성능이 달라진다
페이지 부재 빈도는 횟수를 기록하여 비율을 계산하는 방식이다
상한선, 하한선을 설정하여 상한선을 초과하면 프레임이 적다는 것을 의미하므로 프레임을 추가한다
하한선으로 내려가면 메모리가 낭비된다는 의미로 할당한 프레임을 회수한다
프로세스가 처음 시작될 때는 페이지 할당량을 예측하기 어렵다
페이지 부재 빈도 방식은 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절한다
File System Framework
From a user’s perspective, a file is the smallest allotment of logical secondary storage; that is, data cannot be written to secondary storage unless they are within a file
Directory Structure
When we create a file, one corresponding FCB (File Control Block) (such as i-node in UNIX) is also created
Information about files are kept in the directory structure where it
includes either the information in FCB or a pointer to FCB
Example of On-Disk Structures
Boot Control Block – contains information needed by the system to boot from the partition; Typically the first block of a partition; Also called boot block (UFS) or partition boot sector (NTFS)
Volume Control Block – contains partition details, such as the # and size of blocks in partition, free block count and pointers, and free FCB (File Control Block) count, etc; Also called super-block (UFS) or master file table (NTFS)
Free Space Management in Linux FS
