[OS] 가상메모리(Virtual Memory)

2023. 5. 1. 14:36·운영체제
목차
  1. 가상 메모리 개념
  2. 요구 페이징(Demand Paging)
  3. 페이지 교체(Page Replacement)
  4. FIFO 페이지 교체
  5. 최적의(Optimal) 페이지 바꾸기
  6. LRU(Least Recently Used, 가장 최근 사용)
  7. LRU 근사 알고리즘
  8. 카운팅 알고리즘
  9. 할당
  10. 고정 할당(Fixed Allocation)
  11. 우선 순위 할당(Priority Allocation)
  12. 글로벌 vs. 로컬 할당
  13. 스레싱(Thrashing)
  14. 작업 세트(Working-set) 모델
  15. 페이지-오류 빈도 체계
  16. 요약

가상 메모리 개념

제한된 물리적 메모리 크기

  • 실제 메모리의 사용 가능한 공간보다 큰 프로그램은 실행할 수 없다.

일반 프로그램 실행 패턴

  • 프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않는다.
    • 오류 코드,예외 코드
    • 배열 100x100 요소이지만 10x10 요소만 사용
    • 프로그램의 특정 옵션 및 기능은 거의 사용되지 않는다.
  • 전체 프로그램이 필요한 경우에도 모든 프로그램이 동시에 필요하지 않을 수 있다.

가상 메모리

  • 메모리에 완전히 저장되지 않은 프로세스를 실행할 수 있다.
  • 프로그램의 일부는 실행을 위해 메모리에 있어야 한다.
  • 논리 메모리 주소 공간과 실제 메모리 주소 공간의 분리
  • 논리 메모리 주소 공간은 물리적 메모리 주소 공간보다 클 수 있다.

가상 주소 공간

 


요구 페이징(Demand Paging)

가상 메모리는 요구 페이징을 통해 구현할 수 있다.

필요한 경우에만 페이지를 메모리로 가져온다.

  • 적은 I/O가 필요
  • 적은 메모리가 필요

페이지를 주고받을 수 있어야 한다.

페이지를 참조할 때,

  • 유효한(valid) 참조 → 참조
  • 잘못된(invalid) 참조 → not-in-memory → 메모리로 가져온다.

valid–invalid 비트는 각 페이지 테이블 항목과 연결된다.

  • v → in-memory
  • i → 메모리에 없거나 올바르지 않습니다(잘못된 주소, 보호 위반)
  • 주소 변환 중 valid–invalid 비트가 i인 경우 페이지 오류(page fault)

일부 페이지가 메인 메모리에 없는 경우 페이지 테이블

잘못된 페이지에 액세스하면 페이지 오류(page fault) 발생

→ OS 내의 페이지 오류 처리기(Page fault handler)가 호출

페이지 오류 처리기(Page fault handler)

  1. 잘못된(invalid) 참조
    • 잘못된 주소 또는 보호 위반 → 프로세스 중단
    • 메모리에 없는 경우 → 2
  2. 빈 페이지 프레임을 가져온다.
    • 빈 페이지 프레임이 없는 경우 일부 페이지 프레임을 바꾼다.
  3. 페이지 프레임에 페이지를 읽는다.
    • 이 프로세스는 디스크 I/O가 수행될 때까지 차단된다.
    • 디스크 I/O가 완료되면 페이지 테이블 항목을 유효(valid)로 설정
    • 프로세스를 준비 대기열(ready queue)에 다시 삽입하고 나중에 발송(dispatch)
  4. 페이지 오류를 발생시킨 명령을 재시작

페이지 오류 처리(Page fault handling)

페이지 오류율(Page Fault Rate) 0 ≤ p ≤ 1.0

  • p = 0 : 페이지 오류 없음
  • p = 1 : 모든 참조가 오류

유효 액세스 시간(EAT, Effective Access Time)

  • EAT = (1 – p) x 메모리 액세스 시간 + p x 페이지 오류 서비스 시간
  • 예)
    • 메모리 액세스 시간 = 200ns
    • 평균 페이지 오류 서비스 시간 = 8ms(=8,000,000ns)
    • EAT = (1 – p) x 200 + p x 8,000,000 = 200 + p x 7,999,800
    • 1,000개의 액세스 중 하나가 페이지 오류를 유발하는 경우
      • EAT = 8,200 ns
      • 이는 40배로 둔화된 것

페이지 오류율을 낮게 유지하는 것이 중요

  • 좋은 페이지 교체(page replacement) 정책이 필요

 


페이지 교체(Page Replacement)

페이지 교체

  • 실제로 사용하지 않는 페이지를 찾기 → 페이지 교체
  • 좋은 페이지 교체 알고리즘
    • 페이지 오류의 최소화

참조 위치(Locality of reference)

  • 같은 페이지를 여러 번 메모리에 저장할 수 있다.
  • 실제 대부분의 프로그램에서 관찰되는 현상
  • 일정 시간에 극히 일부 페이지만 집중적으로 참조하는 프로그램 동작
    • Loop
  • 페이징 시스템이 성능이 좋게 되는 근거

페이지 교체를 포함한 페이지 오류 처리기(Page fault handler)

  1. 디스크에서 원하는 페이지의 위치를 찾는다.
  2. 빈 프레임을 찾는다.
    • 빈 프레임이 있는 경우 : 사용
    • 빈 프레임이 없는 경우 : 페이지 교체 알고리즘 사용, 대상 선택
  3. 원하는 페이지를 (새로) 빈 프레임으로 가져와서 페이지 테이블을 업데이트
  4. 프로세스 재시작

이상적인 알고리즘

  • 페이지 오류율이 가장 낮다.

알고리즘 평가

  • 특정 메모리 참조 문자열에서 실행
    • 참조 문자열
  • 해당 문자열의 페이지 오류 수를 계산

일부 예에서 참조 문자열

  • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

페이지 오류 수 vs 프레임 수

 


FIFO 페이지 교체

FIFO(First In First Out) 순서로 대체하는 페이지 교체

15 page faults

참조 문자열

  • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3프레임

4프레임

벨라디의 변칙(Belady’s Anomaly)

  • 더 많은 프레임 → 더 많은 페이지 오류

벨라디의 변칙을 보여주는 FIFO

 


최적의(Optimal) 페이지 바꾸기

장기간 사용되지 않는 페이지 교체

다른 프레임 예제

  • 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  •  

이것을 어떻게 아는가?

알고리즘의 성능을 측정하는 데 사용

  • 최적 알고리즘은 페이지 오류율의 하한을 나타낸다.

 


LRU(Least Recently Used, 가장 최근 사용)

가장 최근에 사용하지 않은 페이지를 바꾼다.

참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

구현 방법

  • 각 페이지마다 참조 시간을 기록
  • 참조 시간이 가장 오래된 페이지를 찾는다.
  • 공간 및 시간 오버헤드가 너무 큼
    • → 많은 근사 알고리즘이 제안

카운터 구현

  • 모든 페이지 항목에는 카운터 존재
  • 페이지가 참조될 때마다 클럭이 증가
  • A페이지가 참조되면 A의 카운터에 클럭를 복사
  • 가장 작은 카운터 값으로 페이지를 바꾼다.

스택 구현

  • 페이지의 스택을 유지
  • 페이지가 참조되면 맨 위로 이동
  • 교체 검색이 없다.

스택 구현

 


LRU 근사 알고리즘

LRU 페이지 교체의 경우,

  • 많은 시스템이 하드웨어 지원을 제공

참조 비트

  • 각 페이지에 대한 비트로, 처음에는 0으로 설정
  • 페이지 참조 시 1로 설정
  • 0인 것을 교체 (있는 경우)
    • 하지만, 우리는 참조 순서를 모른다.

두 번째 기회 페이지 교체 알고리즘(클럭 알고리즘)

  • 교체할 페이지에 기준 비트 1이 있을 경우,
    • 페이지를 메모리에 남긴다.
    • 참조 비트 0을 설정
    • 참조 비트가 0인 페이지를 찾을 때까지 다음 대상에 대한 사전 포인터

 


카운팅 알고리즘

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

  • 작성된 참조 번호를 유지
  • 가장 작은 카운트로 페이지를 교체

할당

이전 교체 알고리즘

  • 페이지 오류가 발생하면 대상을 선택
    • 그들은 변수 할당이 아닌 고정 할당을 가정
  • 페이지 오류 시 페이지 프레임을 하나 더 할당하는 것을 고려?

할당 문제

  • 페이지 오류에서 할당 크기를 결정
    • 고정 할당(fixed allocation)
    • 우선 할당(prioity allocation)

 


고정 할당(Fixed Allocation)

균등 할당(Equal allocation)

  • 프레임이 100개이고 프로세스가 5개인 경우,
    • 각 공정에 20프레임을 제공

우선순위 배분(prioity allocation)

  • 프로세스 규모에 따른 배분

 


우선 순위 할당(Priority Allocation)

  • 비례 할당 체계 사용
    • 크기보다는 우선순위 사용
    • 상위 프로세스에 더 많은 메모리 제공

 


글로벌 vs. 로컬 할당

글로벌 교체

  • 프로세스는 모든 프레임 집합에서 교체 프레임을 선택
  • 한 프로세스가 다른 프로세스의 프레임을 가져올 수 있다.

로컬 교체

  • 각 프로세스는 고유한 할당된 프레임 집합에서만 선택

 


스레싱(Thrashing)

프로세스에 "충분한" 페이지가 없으면 페이지 오류율이 매우 높다.

  • 낮은 CPU 활용률
  • 운영 체제 : 멀티프로그래밍의 정도를 높여야 힌다.
  • 다른 프로세스가 시스템에 추가

스레싱

  • 페이지를 주고받을 때 프로세스가 사용 중

스레싱 발생 이유

  • 로컬 사이즈 크기의 합 > 총 메모리 크기

 


작업 세트(Working-set) 모델

메모리 참조 패턴의 지역성(Locality)

  • 시간적 지역성 : 상대적 짧은 시간 내에 특정 데이터 및/또는 리소스를 재사용
  • 공간적 지역성 : 비교적 가까운 저장 위치 내에서 데이터 요소를 사용

작업 세트 모델

  • 지역성을 전제
  • ∆ ≡ working-set window ≡ 고정된 수의 페이지 참조

WSSi(프로세스 Pi의 작업 세트)

  • 가장 최근에 참조된 총 페이지 수 ∆
    • ∆이 너무 작으면 : 전체 지역을 포함 X
    • ∆이 너무 크면 : 여러 지역을 포함
      • ∆ = ∞ : 전체 프로그램을 포함

D = Σ WSSi ≡ 총 수요 프레임

  • D > m 인 경우 스래싱
  • → 프로세스 중 하나를 일시 중단


페이지-오류 빈도 체계

"허용 가능한" 페이지 오류율을 설정

  • 실제 비율이 너무 낮으면 : 공정에서 프레임이 손실
  • 실제 비율이 너무 높으면 : 공정이 프레임을 획득

 


요약

  • 가상 메모리
    • 메모리에 완전히 있지 않은 프로세스를 실행할 수 있는 메커니즘
  • 요구 페이징
    • 필요할 때만 페이지를 메모리로 가져온다.
  • 페이지 오류율을 낮게 유지하는 것이 중요 → 좋은 페이지 교체 정책 필요
  • LRU(가장 최근에 사용) : 가장 최근에 사용되지 않은 페이지를 대체
  • 프로세스에 페이지 프레임이 충분하지 않으면 스레싱이 발생
저작자표시 변경금지 (새창열림)

'운영체제' 카테고리의 다른 글

[OS] I/O Systems  (0) 2023.05.15
[OS] 대량 저장 구조(Mass-Storage Structure)  (0) 2023.05.08
[OS] 메인메모리(Main Memory)  (0) 2023.04.24
[OS] 교착상태(Deadlocks)  (0) 2023.04.17
[OS] 동기화 도구  (0) 2023.04.03
  1. 가상 메모리 개념
  2. 요구 페이징(Demand Paging)
  3. 페이지 교체(Page Replacement)
  4. FIFO 페이지 교체
  5. 최적의(Optimal) 페이지 바꾸기
  6. LRU(Least Recently Used, 가장 최근 사용)
  7. LRU 근사 알고리즘
  8. 카운팅 알고리즘
  9. 할당
  10. 고정 할당(Fixed Allocation)
  11. 우선 순위 할당(Priority Allocation)
  12. 글로벌 vs. 로컬 할당
  13. 스레싱(Thrashing)
  14. 작업 세트(Working-set) 모델
  15. 페이지-오류 빈도 체계
  16. 요약
'운영체제' 카테고리의 다른 글
  • [OS] I/O Systems
  • [OS] 대량 저장 구조(Mass-Storage Structure)
  • [OS] 메인메모리(Main Memory)
  • [OS] 교착상태(Deadlocks)
파스텔코랄
파스텔코랄
Developer Blog 📜 Lots of rules and no mercy ✨
파스텔코랄
슬기로운 개발일지
파스텔코랄
전체
오늘
어제
  • 스터디
    • 컴퓨터시스템구조
    • 모바일프로그래밍
    • 프로그래밍언어론
    • 운영체제
    • 컴퓨터네트워크
    • 데이터분석
    • 소프트웨어공학
    • 시스템프로그래밍

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • About

링크

공지사항

인기 글

태그

어셈블리어
운영체제
네트워크
프로그래밍언어론

최근 댓글

최근 글

hELLO· Designed By정상우.v4.6.1
파스텔코랄
[OS] 가상메모리(Virtual Memory)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.