7.1. 가상 메모리 관리

김민우·2022년 6월 4일

목록 보기

13/14

운영체제는 어떻게 크고 느린 장치를 사용하면서 마치 커다란 가상 주소 공간이 있는 것처럼 할 수 있을까?
멀티프로그래밍 시스템이 발명되면서 많은 프로세스들의 페이지를 물리 메모리에 전부 저장하는 것이 불가능하게 되었다.
그래서 일부 페이지들을 스왑 아웃하는 기능이 필요하게 되었다.
멀티프로그래밍과 사용 편의성 등의 이유로 실제 물리 메모리보다 더 많은 용량의 메모리가 필요하게 되었다.
이것이 현대 가상 메모리의 역할이다.

📌 가상 메모리 (기억장치)

Non-continuous allocation
- 사용자 프로그램을 block으로 분할하여 적재/실행
- Paging/Segmentation system

가상 메모리 관리의 목적
- 가상 메모리 시스템 성능을 최적화
- Cost model, 다양한 최적화 기법이 존재

Cost Model for Virtual Memory. Sys.

Page Fault Frequency, Page Fault Rate
Page Fault Rate를 최소화 할 수 있도록 전략들을 설계해야 함
- Context switch 및 Kernel 개입을 최소화
- 시스템 성능 향상

📖 Terminologies

Page reference string(d)
- 프로세스의 수행 중 참조한 페이지 순서

Page fault rate = F(ω)

HW Components

가상 메모리를 사용하기 위한 여러가지 장치들에 대해 알아보자

Address translation device (주소 사상 장치)
- 주소 사상을 효율적으로 수행하기 위해 사용
- E.g., TLB, Dedicated page-table register, Cache memories

Bit Vectors
- Page 사용 상황에 대한 정보를 기록하는 비트들
- Reference bits (used bit) : 참조 비트
- Update bits (modified bits, write bits, dirty bits) : 갱신 비트

❓ Bit vectors

Reference bit vector

메모리에 적재된 각각의 page가 최근에 참조 되었는지를 표시
운영
1. 프로세스에 의해 참조되면 해당 page의 Ref. bit를 1로 설정
2. 주기적으로 모든 reference bit를 0으로 초기화
Reference bit를 확인함으로서 최근에 참조된 page들을 확인 가능

Update bit vector

Page가 메모리에 적재된 후, 프로세스에 의해 수정 되었는지를 표시
주기적으로 초기화하지 않음 (Memory에서 나올 때 초기화 함)
Update bit = 1
- 해당 page의 (Main memory 상 내용) ≠ Swap device의 내용
- 해당 page에 대한 Write-back (to swap device) 필요

💡 SW Components

가상 메모리 성능 향상을 위한 관리 기법들로는 다음과 같다.

Allocation strategies (할당 기법)
Fetch strategies
Placement strategies (배치 기법)
Replacement strategies (교체 기법)
Cleaning strategies (정리 기법)
Load control strategies (부하 조절 기법)

1. Allocation Strategies

: 각 프로세스에게 메모리를 얼마 만큼 줄 것인가?

Fixed allocation (고정 할당)
- 프로세스 실행 동안 고정된 크기의 메모리 할당
Variable allocation (가변 할당)
- 프로세스 실행 동안 할당하는 유동적인 메모리 할당
고려 사항
- 프로세스 실행에 필요한 메모리 양을 예측해야 함
- 너무 큰 메모리 할당 -> 메모리 낭비
- 너무 적은 메모리 할당 -> Page fault rate 상승, 시스템 성능 저하

2. Fetch Strategies

: 특정 page를 메모리에 언제 적재할 것인가?

Demand fetch (demand paging)
- 프로세스가 참조하는 페이지들만 적재
- Page fault overhead 존재
Anticipatory fetch (pre-paging)
- 참조될 가능이 높은 page 예측
- 가까운 미래에 참조될 가능성이 높은 page를 미리 적재
- 예측 성공 시, page fault overhead가 없음
- Prediction overhead (Kernel의 개입), Hit ratio에 민감함
실제 대부분의 시스템은 Demand fetch 기법 사용
- 일반적으로 준수한 성능을 보여 줌
- Anticipatory fetch -> Prediction overhead, 잘못된 예측 시 자원 낭비가 큼

3. Placement Strategies

: Page/Segment를 어디에 적재할 것인가?

paging system에는 불필요
Segmentation system에서의 배치 기법
-> First-fit, Best-fit, Worst-fit, Next-fit

4. Replacement Strategies ✨

: 빈 page frame이 없는 경우 새로운 page를 어떤 page와 교체 할 것인가?

Replacement Strategies의 내용은 양이 방대하기에
여기서 확인해보자!

5. Cleaning Strategies

: 변경된 page를 언제 write-back 할 것인가?

변경된 내용을 swap device에 반영
Demand cleaning : 해당 page에 메모리에서 내려올 때 write-back
Anticipatory cleaning (pre-cleaning)
- 더 이상 변경될 가능성이 없다고 판단할 때, 미리 write-back
- Page 교체 시 발생하는 write-back 시간 절약
- Write-back 이후, page 내용이 수정되면 Overhead가 발생!
실제 대부분의 시스템은 Demand cleaning 기법 사용
- 일반적으로 준수한 성능을 보여 줌
- Anticipatory cleaning -> Prediction overhead, 잘못된 예측 시 자원 낭비가 큼

6. Load control strategies

: 시스템의 Multi-Programming degree 조절
- Allocation strategies와 연계 됨

적정 수준의 multi-programming degree를 유지해야 함
- Plateau(고원) 영역으로 유지
- 저부하 상태 (Under-loaded) : 시스템 자원 낭비, 성능 저하
- 고부하 상태 (Over-loaded) : 자원에 대한 경쟁 심화, 성능 저하
- Thrashing(스레싱) 현상 발생
  
  ❓스레싱 현상
  과도한 Page Fault가 발생하는 현상!

Other Considerations

가상 메모리를 관리할 때 신경써야 할 것들 몇 개 더 말해보자면 다음과 같다.

Page Size
Program restructuring
TLB reach

1. Page Size

시스템 특성에 따라 다름
- No best answer!
- Page Size가 점점 커지는 경향이 있음
- HW의 발전과도 연관이 깊다.
- CPU의 성능이 발전하고 Memory Size도 점점 커지면서 상대적인 Page fault의 처리 비용이 증가하고 있다.

일반적인 page size : 2^7(128) bytes ~ 2^22(4M) bytes
Small page size일 경우
- Large page table / # of PF -> High overhead (kernel)
- 내부 단편화 감소
- I/O 시간 증가
- Locality 향상
- Page fault 증가
Large page size
- Small page table / # of PF -> Low overhead (kernel)
- 내부 단편화 증가
- I/O 시간 감소
- Locality 저하
- Page fault 감소

2. Program Restructuring

가상 메모리 시스템의 특성에 맞도록 프로그램을 재구성
사용자가 가상 메모리 관리 기법에 대해 이해하고 있다면, 프로그램의 구조를 변경하여 성능을 높일 수 있음

Example
- Paging System, Page size= 1KB
- sizeof(int) = 4 bytes

// program-1
int main()
{
	int zar[256][256]; // 행, 열
    int i, j;

    for(j=0; j < 256; j++)
    	for (i=0; i < 256; i++)
        	zar[i][j] = 0;

    return 0;
}

Row-major order for array

// program-2
int main()
{
	int zar[256][256];
    int i, j;

    for(i = 0; i < 256; j++)
    	for(j = 0; j < 256; j++)
        	zar[i][j] = 0;

    return 0;
}

3. TLB Reach

TLB를 통해 접근 할 수 있는 메모리의 양
- number of entries * page size
TLB의 hit ratio를 높이려면?
1. TLB의 크기를 증가 -> Expensive
2. Page 크기를 증가 or 다양한 page size 지원
- 현대 OS의 발전으로 인해 OS의 지원이 가능함