1. Overview

가상메모리를 사용한다면 하나의 프로세스 전체가 주기억장치에 존재하지 않고 일부만 있더라도 해당 프로세스를 수행할 수 있다.

• virtual memory(가상메모리) : 가상 주소 공간, 논리적 주소
• real / main memory(주기억장치) : 실제 주소 공간, 물리적 주소
• 주기억장치보다 크기가 큰 프로세스를 수행시킬 수 있다.

Mapping (사상)

물리적 저장 공간과 가상 저장 공간 사이의 mapping(사상)은 운영체제에 의해서 수행된다.

• virtual address(가상 주소) : 수행중인 프로세스가 참조하는 주소
• real address(실제 주소) : 주기억장치 상에서 이용할 수 있는 주소

1.1 DAT(Dynamic Address Translation) (동적 주소 변환)

프로세스가 수행될 때 가상 주소를 실제 주소로 변환하는 대표적인 메커니즘

• artificial continuity(인위적 연속성)
  모든 프로세스가 가지는 가상 주소 공간 상의 연속된 주소들은 실기억 공간에서도 반드시 연속적일 필요가 없는 것을 의미
• DAT에서는 어떤 가상기억 주소에 대한 주기억장치 내의 존재 여부와 주기억장치의 어디에 위치하는가를 나타내기 위한 대응관계 테이블을 유지, 관리한다.

1.2 Block Mapping (블록 사상)

• DAT의 경우, mapping으로 인한 주기억장치가 많이 필요해질 수 있다.
• mapping 내용을 가상메모리의 block 단위로 저장하고, 시스템은 블록이 위치하는 장소를 추적한다.
• block(블록) : 가상메모리에 대한 분할 단위
• page(페이지) : block을 같은 단위로 구성
  • paging(페이징) : page를 활용한 가상메모리 구성
• segment(세그먼트) : block을 서로 다른 크기로 구성
  • segmentation(세그먼테이션) : segment를 활용한 가상메모리 구성

---

2. Paging (페이징)

• page : 일정한 크기의 block
• paging : 주소 공간을 페이지 단위로 나누고, 실제 주소 공간은 페이지 크기와 같은 page frame(페이지 프레임)으로 나눠서 사용

• 페이징 시스템에서 가상 주소는 $v=(p, d)$로 표현된다.
  • $p$ : 가상메모리 내에서 참조될 항목이 있는 페이지 번호
  • $d$ : 페이지 $p$ 내에서 참조될 항목이 위치하고 있는 곳의 변위
• 페이징 기법에서의 동적 주소 변환 과정
  1. page mapping table에서 페이지 $p$를 찾는다.
  2. 페이지 $p$가 페이지 프레임 $p'$에 있는지 확인한다.
  3. 이를 통해 주기억장치 상의 실제 주소 $r=p'+d$를 구한다.

• 위의 과정에서 페이지 $p$가 주기억장치 내에 존재하는지 확인해야 하는데,
  이는 page residence bit(페이지 존재 비트)를 활용한다.
  • 0 : 페이지가 주기억장치 상에 없기 때문에 하드 디스크에 잇는 내용을 메인 메모리에 적재
  • 1 : 주기억장치 내에 존재한다는 의미이므로 바로 사용

2.1 Direct Mapping (직접 사상)

mapping : 가상메모리의 주소를 주기억장치 내의 주소로 변환하는 방법

• direct mapping에서 크기가 큰 page mapping table은 보통 주기억장치에서 유지, 관리
• 빠른 주소 변환을 위해, 속도가 매우 빠른 highspeed cache memory(고속 캐시 메모리)를 이용해 direct mapping의 page mapping table을 구현

2.2 Associative Mapping (연관 사상)

동적 주소 변환을 신속하게 수행하기 위해 주기억장치보다 빠른 연관기억장치에 페이지 사상 테이블 전체를 넣는 방법

• 저장된 값을 이용해 데이터에 접근하는 CAM(Content Addressable Memory) (내용 주소화 메모리)와 내용의 일부를 기억하는 데이터 레지스터 운영
• 여러개 주소에 동시 접속 가능
• 주소만 참조하는 것이 아니라 내용도 참조
• 연관 기억 장치는 고가

2.3 Direct / Associative Mapping (연관 / 직접 사상)

가장 최근에 참조된 page는 다시 사용되기 쉽다는 사실을 이용해
연관기억장치에는 page mapping table의 전체 항목 중 가장 최근에 참조된 일부 page 항목들만을 수용하는 방식

• 캐시기억장치만을 사용하거나 (direct mapping), 연관기억장치만을 사용하는 (associative mapping) 구현 방식은 주기억장치보다 비용이 많이 들기 때문에 고안됨
• 동적 주소 변환 방식 (가상 주소 : $v=(p, d)$)
  1. 페이지 $p$를 연관 페이지 사상 테이블에서 찾는다.
     존재한다면 $p'$를 얻고 변위 $d$와 접속해 실제 주소 $r=p'+d$를 구한다.
  2. $p$와 일치하는 항목이 연관 페이지 사상 테이블에 없다면, 직접 페이지 사상 테이블의 주기억장치 주소를 페이지 사상 테이블 시작점 레지스터에 넣어 해당 페이지를 찾는다.

2.4 페이징 시스템의 공유

여러 사용자가 동일한 프로그램을 동시에 수행시킬 경우,
공유가 가능한 페이지를 가능한 공유하도록 한다.

• pure procedure(순수 프로시듀어) / reentrant procedure(재진입가능 프로시듀어)
  • 수정이 불가능한 프로시듀어
  • 이를 통해 자원을 공유한다.
    

2.5 페이지 크기

페이지 크기를 결정함에 있어서 고려할 사항

2.5.1 페이지 크기가 작을 경우

장점

1. 프로세스가 작업 세트(working set)을 확보하는데 도움이 된다.
   • 작업 세트(working set) : 프로세스가 자주 사용하는 페이지 집합
2. 동적 프로그래밍 정도 상승

단점

1. 테이블 단편화(table fragmentation) 발생
   • 페이지 크기가 작다면 페이지와 페이지 프레임이 증가하고, 이를 관리하기 위한 페이지 테이블의 크기가 증가하여 기억 공간이 낭비되는 현상

2.5.2 페이지 크기가 클 경우

장점

1. 페이지 크기가 크다면, 한번에 많은 양의 데이터를 전송할 수 있고, 이는 입출력 전송의 횟수(I/O interrupt)를 줄일 수 있다.
2. 메인메모리 적재횟수 감소 가능

단점

1. 참조되지 않을 정보들까지 주기억장치로 옮겨져 기억 공간이 낭비될 수 있다.

2.6 페이지 인출 기법

보조기억장치에서 주기억장치로 프로세스를 적재하는 방법

2.6.1 Demand Paging (요구 페이징)

실행 중인 프로세스에 의해 명백하게 참조되는 프로세스만이 보조기억장치에서 주기억장치로 옮겨진다.

장점

• 주기억장치에 적재된 프로세스는 모두 실제로 참조되는 프로세스라고 확신할 수 있다.
• 새로운 페이지를 임의로 주기억장치에 적재하지 않아도 된다.
• 어느 페이지를 얼만큼 주기억장치로 옮길지 결정하는 오버 헤드를 최소화 할 수 있다.

단점

• 현재 메인메모리에 데이터가 없다면 유휴시간이 발생한다.
  • 사용할 데이터만 기다리는 경우가 발생할 수 있다.

2.6.2 Anticipatory Paging (예상 페이징)

프로세스가 필요로 할 페이지들을 운영체제가 예측하여 주기적장치에 여유가 있을 때 해당 페이지를 미리 적재

• 예상이 맞다면 유휴시간 없이 해당 프로세스를 바로 사용할 수 있다.

2.7 Page Release (페이지 양도)

• 더 이상 필요로 하지 않는 특정한 페이지가 존재한다면, 작업세트에서 해당 프로세스를 제외해 페이지 프레임을 제대로 활용
• 효율적인 방법은 컴파일러나 운영체제가 자동으로 페이지 제거를 실행해 작업세트를 확보하도록 하는 것

---

3. Segmentation (세그먼테이션)

가변 분할 메모리 할당

3.1 Direct Mapping (직접 사상)

3.2 공유 및 보호

---

4. 세그먼트 / 페이징 혼용 기법

4.1 동적 주소 변환

4.2 시스템의 공유

---

5. 페이지 교체 알고리즘

주기억장치 공간을 확보하기 위해, 현재 주기억장치를 차지하고 있는 페이지들 중에서 어떤 페이지를 선택해 가상공간으로 보낼 것인가를 결정하는 기법

5.1 FIFO(First-In First_Out) 알고리즘

5.2 Optimal Replacement(최적 교체) 알고리즘

5.3 LRU(Least Recently Used) 알고리즘

5.4 Second Chance(2차 기회) 알고리즘

페이지를 바로 교체하지 않고 기회를 주는 알고리즘

5.5 LFU(Least Frequency Used) 알고리즘

가장 적게 사용되거나 집중적이 아닌 페이지가 대체

---

6. Thrashing (스래싱)

페이지 부재가 계속적으로 발생해 프로세스가 수행되는 시간보다 페이지 교체에 소비되는 시간이 더 많은 경우

6.1 Locality (구역성)

6.2 Working Set (작업세트)

---

References

• 생능출판사