가상기억장치
보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것
용량이 작은 주기억장치를 마치 큰 용량을 가진 것 처럼 사용하는 것
프로그램을 여러개의 작은 블록 단위로 나눠서 가상기억장치에 보관,
프로그램을 실행 할 때마다 요구되는 블록만 주기억장치에서 불연속적으로 할당해서 처리한다.
주기억장치의 용량보다 큰 프로그램을 실행하기 위해서 사용
주기억장치 이용률과 다중 프로그래밍의 효율 높일 수 있다
가상기억장치에 저장된 프로그램을 실행하려면
가상기억장치 주소를 주기억장치 주소로 바꾸는 변환이 필요하다
일반적인 구현방법으로는 블록의 종류에 따라 페이징 기법과 세그먼테이션 기법
블록 단위로 사용하므로 연속 할당 방식에서 발생될 수 있는 단편화 해결
운영체제 설계 복잡해짐
오버레이 문제는 자동 해결
Paging
가상기억장치에 보관되어있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후
나눈 프로그램 페이지를 동일하게 나눠진 주기억장치의 영역 페이지프레임에 적재시켜 실행하는 기법
프로그램을 일정한 크기로 나눈 단위 : 페이지(Page)
페이지 크기로 일정하게 나누어진 주기억장치의 단위 : 페이지 프레임(Page Frame)
외부 단편화는 없으나 내부 단편화는 발생할 수 있다
(내부 단편화 : 페이지 블록만큼 데이터가 딱 맞게 채워져 있지 않을 때 공간이 낭비되는 것)
주소 변환을 위해서 페이지의 위치 정보를 갖고 있는 페이지 맵 테이블이 필요함
페이지 맵 테이블 사용으로 비용이 증가되고, 처리 속도가 감소
Segmentation
가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후
주기억장치에 적재시켜 실행하는 기법
세그멘테이션에서는 프로세스 = 세그먼트의 집합
프로세스를 논리적 내용을 기반으로 나눠 메모리에 배치 -> 각 세그먼트는 연관된 기능을 수행하는 하나의 모듈 프로그램
한 프로세스는 기본적으로 세가지 segment로 나눌 수 있음 (그 안에서 각각 더 작은 세그먼트로 나눌 수도 있음)
- Text(=code) segment(Read) - 프로그램의 기계어 명령이 들어있음
- Data segment(Read & write) - 초기화 된 전역변수, 정적변수 저장
- Stack segment & Heap segment - 크기가 가변적
프로그램을 배열, 함수 등과 같은 논리적인 크기로 나눈 단위 : 세그먼트(Segment)
각 세그먼트는 고유한 이름과 크기 가짐
기억 장치의 사용자 관점을 보존하는 기억장치 관리 기법
세그멘테이션 기법을 이용하는 궁극적인 이유는 기억공간을 절약하기 위해서
주소 변환을 위해서 세그먼트가 존재하는 위치 정보를 갖고 있는 세그먼트 맵 테이블이 필요함
세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역 침범 불가
이를 위해 기억장치 보호키(Storage Protection Key) 필요
내부 단편화는 없으나 외부 단편화는 발생할 수 있다
(외부 단편화 : 실제 물리메모리가 세그먼트가 요구하는 원하는 크기를 제공하지 못 하는 경우가 발생한다.
실제 물리메모리의 빈 공간이 군데군데 나뉘어져서 한 세그먼트 전체 용량은 만족하나, 중간중간의 빈 공간들이므로 세그먼트 정보를 연속된 공간에 저장하지 못하는 현상을 외부 단편화라 한다.)
(내부 단편화와 외부 단편화의 해결 방법은 각각 세그먼트/페이징이나, 각각의 두 기법이 또한 각각 외부 단편화/내부 단편화 문제를 발생시키는 아이러니가 있다.
참고로, 리눅스는 페이징 기법을 기반으로 구현되어 있다.)
Segmentation 기법의 일반적인 주소 변환
주소 형식에 따른 주소와 세그먼트 맵 테이블의 구성
가상주소는 세그먼트 번호를 나타내는 s와 세그먼트 내에 실제 내용이 위치하고 있는 곳 까지의 거리를 나타내는 변위값 d로 구성
가상주소 형식 : | 세그먼트 번호(s) | 변위값(d) |
실기억주소는 완전주소 형태를 사용하며 이는 세그먼트의 기준번지와 변위값을 더함으로써 얻을 수 있다.
실기억주소 형식 : 실기억주소(세그먼트 기준번지 + 변위값)
세그먼트 맵 테이블은 세그먼트 번호 s와 세그먼트의 크기L(한계번지), 주기억장치상의 기준번지(시작주소)b로 구성된다.
주소변환 순서
세그먼트 맵 테이블 | 세그먼트 번호(s) | 세그먼트 크기(L) | 기준번지(b) |
-
가상 주소의 세그먼트 번호로 세그먼트 맵 테이블에서 해당 세그먼트 기준번지와 세그먼트 크기를 구한다. 세그먼트 번호는 세그먼트 맵 테이블에 대한 색인으로 사용된다.
-
가상주소의 변위값과 세그먼트의 크기를 비교한다
-
변위값이 작거나 같을때 : 기준번지 + 변위값 후 실기억주소를 만들어 주기억장치를 액세스
-
변위값이 크면 : 다른 영역을 침범하게 되므로 실행 권한을 운영체제에 넘기고 트랩을 발생시킴. (변위값이 크다는건 현재 찾는 세그먼트의 위치가 해당 세그먼트의 크기를 초과했다는 뜻)
페이지 교체 알고리즘
페이지 부재(Page Fault)가 발생하였을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이 때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것 인지를 결정하는 기법
OPT(Optimal replacement, 최적 교체)
앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
= 가장 오래 사용 안 할 페이지 교체
Belady(벨라디) 제안 페이지 부재 횟수 가장 적게 발생하는 가장 효율적인 알고리즘
(Belady의 역설 : http://melonicedlatte.com/2020/10/13/003700.html)
(각 페이지 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 불가 ?)
ex) 3개 페이지 프레임 가진 기억장치에서 페이지 부재 수는 4회
FIFO(First In First Out)
각 페이지가 주기억장치에 적재될 때 마다 그 때의 시간을 기억시켜 가장 먼저 들어와 가장 오래 있었던 페이지를 교체하는 기법
= 주기억장치 가장 먼저 들어와 가장 오래된 페이지 교체
이해 쉽고 프로그래밍 설계 간단
프로세스 할당 페이지 프레임 수 증가 시
페이지 부재 수 감소해야 하지만
실제는 페이지 프레임 수 증가 시 페이지 부재 증가하는 모순 anomaly 발생
ex) 3개 페이지 프레임 가진 기억장치에서 페이지 부재 수는 6회
LRU Least Recently Used
최근들어 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
= 최근 가장 오래 미사용 페이지 교체
페이지마다 계수기(Counter)나 스택(Stack)을 두어
현 시점에서 가장 오랫동안 사용하지 않은(=가장 오래 전에 사용된) 페이지를 교체한다
ex) 3개 페이지 프레임 가진 기억장치에서 페이지 부재 수는 5회
LFU(Least Frequently Used)
사용 빈도가 가장 적은 페이지를 교체
활발하게 사용되는 페이지는 사용 횟수가 많아 교체 x
ex) 3개 페이지 프레임 가진 기억장치에서 페이지 부재 수는 5회
NUR, NRU(Not Used Recently, Not Recently Used, 클럭 알고리즘)
NUR은 LRU와 비슷한 알고리즘으로 최근에 사용하지 않은 페이지를 교체
최근에 사용 안 했으니 향후에도 사용되지 않을 가능성이 높다는 것을 전제로 LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
최근 사용여부 확인 위해 각 페이지마다 2개의 비트, 참조비트(Reference Bit)와 변형비트(Modified Bit, Dirty Bit)가 사용된다.
참조비트 변형비트 값 따라 순서 결정되고 페이지 교체
NUR 교체순서 0 미참조 1 참조
참조비트 변형비트 교체순서
0 0 1
0 1 2
1 0 3
1 1 4
SCR(Second Chance Replacement, 2차 기회 교체)
가장 오랫동안 주기억장치에 있던 페이지 중 가장 자주 사용되는 페이지의 교체를 방지하기 위한 것으로 FIFO의 단점 보완
교체대상 되기 전 참조비트 검사하여
1일 경우 한번 더 기회
각 페이지에 프레임을 FIFO순 유지하며
LRU 근사 알고리즘처럼 참조비트 가짐
원문 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=xpiart&logNo=220233276021
https://velog.io/@mainxcharacter/paging
https://sol-cito.github.io/technology-os/2021/02/28/Tech-Blogging-OS_note13
