가상 메모리

주소사상

• 사용자 프로그램을 여러 개의 block으로 분할
• 필요한 block들만 실행시키고자 할 때 메모리에 적재
• 나머지 block들은 swap device에 존재

연속할당

• Continuous Allocation
• 상대 주소: 프로그램의 시작 주소를 0으로 가정한 주소
• 재배치(Relocation): 메모리 할당 후, 할당된 주소에 따라 상대 주소들을 조정하는 작업

비연속할당

• Non-continuous Allocation
• 가상 주소: 논리 주소, 연속된 메모리 할당을 가정한 주소
• 실제 주소: 실제 메모리에 적재된 주소
• 주소 매핑: 가상 주소 → 실제 주소
• 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행할 수 있음

블록 매핑

• 사용자 프로그램을 block 단위로 분할/관리
• 가상주소: v = (b, d)
  • b = 블록 수
  • d = offset in a block

Block Map Table(BMT)

• Address Mapping: 정보 관리
• 커널 공간에 프로세스마다 하나의 BMT를 가짐
• 프로세스는 swap device에 나눠진 블록으로 존재

Block Number	Residence Bit	...	Real Address
0 1 2 ...		. . .
B	1	......	a
... m-1		. .

• ① 프로세스의 BMT에 접근
• ② BMT에서 block B에 대한 항목을 찾음
• ③ Residence Bit 검사
  • Residence Bit = 1 인 경우, BMT에서 b에 대한 real address 값 a 확인
  • 0인 경우, swap device에서 해당 블록을 메모리로 가져옴, M 업데이트
• ④ 실제 주소 r 계산(r = a + d)
• ⑤ r을 이용하여 메모리에 접근

---

가상메모리 적용 방법

페이징 시스템

• 프로그램을 같은 크기의 블록으로 분할(Pages)
• Page: 프로그램의 분할된 block
• Page Frame: 메모리의 분할 영역, Page와 같은 크기로 분할
• 논리적 분할이 아닌 크기에 따른 분할, Page 공유 및 보호 과정이 복잡
• 간단하고 관리가 효율적
• 외부단편화 없음, 내부단편화는 발생 가능
• (윈도우) 시작 > 제어판 > 시스템 > 고급시스템 설정 > 고급 탭 > 가상메모리

주소 매핑

• 가상주소: v = (b, d)
• Page Map Table(PMT) 사용
• Address Mapping Mechanism
  • 직접 사상(Direct Mapping)
  • 연관 사상(Associative Mapping) - TLB(Translation Look-aside Buffer)
  • 혼합 사상(Hybrid Direct/Associative Mapping)

Direct Mapping

• Block Mapping 방법과 유사
• 문제점
  • 메모리 접근 횟수가 2배 → 성능 저하
  • PMT를 위한 메모리 공간 필요
  • 해결방안: 연관 사상

Associative Mapping

• TLB(Translation Look-aside Buffer)에 PMT 적재
  • Associative High-speed Memory
• PMT를 병렬 탐색
• 낮은 오버헤드 및 빠른 속도
• 비싼 하드웨어로 구현

Hybrid Direct/Associative Mapping

• 두 기법을 혼합하여 사용
  • HW 비용은 줄이고, 연관사상의 장점 활용
• 작은 크기의 TLB 사용
  • PMT: 메모리(커널 공간)에 저장
  • TLB: PMT 중 일부 entry를 적재(최근에 사용된 page에 대한 entry 저장)
• Locality(지역성) 활용
  • 프로그램의 수행과정에서 한번 접근한 영역을 다시 접근(temporal locality) 또는 인접 영역을 다시 접근할(spatial locality) 가능성이 높음
• 프로세스의 PMT가 TLB에 적재되어 있는지 확인
  • TLB에 적재된 경우: Residence Bit를 검사하고 page frame 번호 확인
  • 적재되지 않은 경우: Direct Mapping으로 page frame 번호 확인, 해당 PMT entry를 TLB에 적재

---

요구 페이징

• 가상 메모리에서 많이 사용하는 메모리 관리 방법
• 스와핑을 사용하는 페이징 시스템과 유사
• 프로그램을 실행하려고 프로그램의 일부만 메인 메모리에 적재하되 순차적으로 작성되어 있는 프로그램의 모듈을 처리할 부분만 올리고, 다른 부분은 실행하지 않음을 이용
• 동적 주소 변환에서는 가상 메모리와 메인 메모리의 매핑을 매핑 테이블로 표시
  • 페이지 방법에서는 페이지 테이블로 표시

페이지 부재

• Page Fault
• 프로세스가 접근하려는 페이지가 물리적 메모리에 존재하지 않는 상태에서 발생하는 인터럽트
• 프로세스가 비타당 비트(0)로 표시된 페이지에 액세스하려고 한다면 '페이지 부재'라고 함

장점

• 액세스하지 않는 페이지를 적재하지 않으므로 메모리를 절약
• 프로그램을 시작할 때 적재 지연이 적음
• 적은 수의 페이지를 읽기 때문에 초기 디스크 오버헤드가 적음
• 프로그램을 실행할 충분한 메모리가 없는 시스템에서도 대용량 프로그램을 실행할 수 있음

단점

• 페이지 교체 알고리즘을 포함하는 메모리 관리가 복잡함
• 페이지 액세스 시간은 디스크에서 페이지를 적재할 수도 있어 페이지 액세스 시간 예측 어려움

---

페이지 대치

• 페이지 부재 발생 시 메인 메모리에 있으면서 사용하지 않는 페이지를 없애 새로운 페이지로 바꾸는 것
• 보통 프레임 수가 증가하면, 페이지 부재 감소

선입선출 대치 알고리즘(FIFO)

• 가장 간단한 알고리즘
• 메모리에 있는 페이지는 모두 선입선출 큐가 관리
• 큐의 헤드 부분에 있는 페이지를 먼저 대치
• 큐에 있는 페이지가 메모리로 들어갈 때 큐의 끝에 페이지 삽입
• 큐의 크기는 사용 가능한 메모리 프레임의 수
• 프레임을 늘렸는데 폴트가 늘어나는 경우가 있음 → 벨래디의 변이

최적 페이지 대치 알고리즘

• OPT(OPTimal replacement algorithm)
• 벨래디의 알고리즘
• 모든 알고리즘 중 페이지 부재 비율이 가장 낮음
• 기본 아이디어: 앞으로 가장 오랫동안 사용하지 않을 페이지를 대치한다

최근 최소 사용 대치 알고리즘

• LRU(Least Recently Used)
• 프로세스가 가장 최근의 페이지에 액세스했다는 것은 멀지 않아 다시 액세스할 가능성이 있다는 의미
• 과거 오랫동안 사용하지 않은 페이지로 대치하는 효과로 생각
• 메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용한 시간을 연관
• 페이지를 대치할 때 오랫동안 사용하지 않은 페이지를 선택하므로 시간적으로 거꾸로 찾는 최적 페이지 대치 알고리즘이라고 할 수 있음

카운터(계수기)를 이용한 순서 결정 방법

• 각 페이지 테이블 항목에 사용 시간 레지스터를 연관시키고 프로세서에 논리 클록을 추가한 후 카운터 필드를 덧붙여 프레임 순서 결정
• 메모리관리장치(MMU)는 페이지 참조가 있을 때마다 모든 참조의 프로세서 클록을 각 페이지 테이블 항목에 업데이트
• 페이지를 참조할 때마다 클록은 증가하고, 클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용 시간 레지스터에 복사하여 각 페이지의 최후 참조 시간을 가짐

스택을 이용한 순서 결정 방법

• 페이지 번호를 스택에 넣어 관리하고 페이지를 참조할 때마다 페이지 번호를 스택의 톱(top)에 두어 순서 결정
• 톱에 있는 페이지 번호는 가장 최근에 사용한 페이지가 됨
• 바텀에 있는 페이지 번호는 가장 늦게 사용한 페이지가 되어, 페이지 부재를 일으킬 때 교체

최근 최소 사용 근접 알고리즘

• 대부분 최근 최소 사용 알고리즘을 이용한 페이지 대치에서 하드웨어를 지원하지 않기 때문에 다른 알고리즘을 사용
• 처음에 모든 비트는 0으로 초기화 한 후 사용자 프로세스를 수행할 때 참조된 각 페이지와 관련된 비트를 1로 변환
• 저렴한 가격으로 최근 최소 사용 알고리즘을 구현하려고 상당수 시스템이 참조 비트 형태 지원

시계(2차적 기회 대치) 알고리즘

• 가장 오랫동안 메인 메모리에 있던 페이지 중 자주 사용하는 페이지의 대치 방지
• 선입선출 대치 알고리즘을 기반으로 구현하기에 2차적 기회 대치 알고리즘이라고도 함
• 최근 최소 사용 알고리즘과 성능은 비슷하지만 오버헤드가 적음
• 각 프레임의 사용 여부를 나타내는 참조 비트를 추가하여 페이지를 메모리 안의 프레임에 처음으로 적재했을 때를 1로 설정한 후 참조할 때마다 다시 1로 설정
• 프레임들은 원형 버퍼(큐)로 구성되고 각각 포인터를 가짐
• 페이지를 교체하면 포인터는 교체된 버퍼의 다음 프레임을 가리키도록 설정

NUR 알고리즘

• Not Used Recently
• 최근 사용하지 않는 페이지를 교체하는 방법
• 낮은 오버헤드로 최근 최소 사용 페이지 교체 전략에 거의 동일
• 최근에 사용하지 않는 페이지들은 가까운 미래에도 사용하지 않을 가능성 높다는 아이디어 바탕
• 최근 최소 사용 알고리즘과 같이 비트를 2개 추가하고 참조 비트(R)는 해당 페이지의 액세스 여부를 확인해서 최근에 사용한 페이지들을 메모리에 유지

구분	특징
0 (0, 0)	최근에 사용(참조)하지 않으면서 수정하지도 않은 페이지
1 (0, 1)	최근에 사용하지는 않았으나, 수정한 페이지
2 (1, 0)	최근에 사용했으나, 수정하지 않은 페이지
3 (1, 1)	최근에 사용하고 수정한 페이지

• 희생할 페이지를 디스크에서 읽은 후 내용 수정을 했다면, 해당 페이지를 먼저 디스크에 복사하여 제거해야 함
• 수정한 페이지는 페이지 부재가 발생하면 디스크에 두 번 액세스하므로 오버헤드 큼
• 부담이 적은, 참조나 수정이 없는 페이지 선택하여 제거해야 함

최소 사용 빈도수(LFU) 알고리즘

• Least Frequantly Used
• 각 페이지마다 참조 횟수 카운터가 있으며, 카운터수가 가장 작은 페이지 대치
• 프로세스의 초기 단계에서 한 페이지를 많이 사용한 후 다시는 사용하지 않을 때 곤란
• 해결책: 카운터를 일정한 시간 간격으로 하나씩 오른쪽으로 이동하여 지수적으로 감소하는 평균 사용 수 형성하는 것

최대 사용 빈도수(MFU) 알고리즘

• Most Frequantly Used
• 계수가 가장 작은 페이지는 방금 들어와서 아직 사용하지 않았기 때문에 앞으로 사용할 확률이 높다고 가정하여 대치 페이지 후보에서 제외
• 가장 많이 사용한 페이지, 즉 계수가 높은 페이지 대치
• 일반적이지 않음(알고리즘을 구현하는 데 비용 많고, 최적 페이지 대치에 비해 성능 낮음)

페이지 버퍼링

• 최근 최소 사용 알고리즘과 시계 알고리즘은 선입선출 대치 알고리즘보다 성능은 좋지만, 복잡성과 페이지 교체로 오버헤드는 더 큼
• 선입선출처럼 성능이 떨어지는 것을 막으려고 교체 대상으로 선택한 페이지를 즉시 교체하지 않은 채 잠시 동안 메인 메모리에 유지
• 포인터 리스트 2개를 사용하여 페이지 관리

---

프레임 할당 알고리즘

• 프레임을 적절히 할당하여 페이지 부재의 횟수 줄임
• 메모리 할당은 제한적이라 총 유효 프레임 수보다 많이 할당할 수 없지만, 할당 가능한 최소 프레임 수를 찾음
• 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 부재 비율은 올라가고 프로세스 수행 속도는 떨어짐
• 프레임을 몇 개만 할당하면 당연히 성능이 떨어지므로 할당해야 하는 최소 프레임 수가 정해져 있음
• 최소 프레임 수는 명령어 구조로 정의
• 수행 중인 명령어를 완료하기 전에 페이지 부재 현상이 일어나면 해당 명령어를 다시 시작해야 함
• 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임이 있어야 명령어 하나를 실행 가능
• 주소가 간접 참조이면 페이징 방법에서는 프레임 3개를 요구함
• 한 프로세스당 최소 프레임 수는 컴퓨터 구조로 정의함
• 최대 수는 실제유효 기억장소의 양으로 정의함
• 이 두 가지 사이에서 적당한 프레임을 할당해야 함

---

스레싱

• Thrashing
• 페이지 교환이 계속 일어나는 현상
• 어떤 프로세스에 프레임이 충분하지 않다면 할당된 프레임을 최소 프레임 수까지 줄일 수 있다 하더라도 실제 사용하는 프레임 수만큼 갖지 못하면 빈번하게 페이지 부재가 발생 가능
• 기타 자원 부족으로 필요한 연산을 수행할 수 없는 상태가 되면 운영체제는 다른 프로세스에서 자원을 회수하는 등 방법을 이용하여 자원 확보
• 페이징 동작(스왑 인/스왑 아웃), 즉 디스크와 메모리 간에 빈번한 페이지 교환 발생
• 모든 페이지를 실제로 사용하고 있어도 페이지를 교환해야 한다면 페이지 부재 연속 발생
• 프로세스는 계속 페이지를 교환하려고 많은 시간을 낭비하면서 유용한 작업을 느리게 하므로 시스템 성능 낮아짐
• 어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 길면 '스래싱을 하고 있다'라고 표현

스래싱의 발생 원인

• 너무 많은 다중 프로그래밍
  • 새로운 프로세스가 늘어나면 프로세스에 고정된 프레임 수가 현재 활동에 충분하지 않으므로 서로 프레임을 빼앗기고 뺏는 과정(지속적인 페이지 부재)이 유지됨
  • 일부 시스템에서 프로세서 사용률이 낮으면 다중 프로그래밍을 증가해야한다고 해석하여 더욱 악화를 야기시킴
  • 그러나 전역 페이지 대치에서는 새로운 프로세스가 수행 중인 프로세스의 페이지를 빼앗아서 수행을 시작하면 더 많은 페이지 부재 발생 → 각 프로세스는 자신에게 필요한 만큼 프레임을 배당 받지 못하게 됨
• 프로세서가 요구하는 최소한의 수보다 페이지 프레임 수가 적으면 적을수록 페이지 부재 비율 증가
  • 페이지 부재가 발생하면 페이징 처리장치를 사용하려고 프로세스가 대기하기 때문에 준비 큐는 비어있게 됨
  • 페이지 부재가 많이 발생할수록 프로세스가 페이징 처리장치를 기다리는 시간은 길어지므로 프로세스의 효율성 낮아짐
  • 결국 프로세서의 이용률은 더 낮아지고 프로세서 스케줄러는 이용률을 올리려고 다중 프로그래밍의 정도를 점점 더 높이지만 프로세스의 실행은 점점 느려짐
  • 이러한 페이지 부재로 프로세서의 이용률이 감소하면 결국 스래싱 발생

 

스래싱 방지 방법

• 작업 집합(워킹 셋) 모델: 프로세스가 실제로 얼마만큼 프레임을 많이 사용하는지 검사하여 지역 모델(작업 집합 모델)을 정의함
• 지역 모델: 프로세스를 실행할 때 프로그램은 보통 지역 몇 개로 중첩해서 구성하므로 한 지역에서 다른 지역으로 이동하는 과정을 의미함

지역성(locality)

• 실행 중인 프로세스에서 나타나는 특성
• 동일한 값이나 관련 저장 위치를 자주 액세스하는 현상
• 프로세스는 어느 실행 단계 동안 메모리의 정보를 균일하게 액세스하는 것이 아니라 선호하는 특정 페이지만 집중적으로 참조하는 현상(국부성)