[운영체제] Chapter 9. Virtual Memory (1)

[운영체제] Chapter 9. Virtual Memory (1)

2023. 1. 19. 16:36ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

Demanding Paging, Memory에 없는 Page의 Page Table, Page Fault, Steps in Handling a page Fault, Performance of Demand Paging, Free Frame이 없는 경우, Page Replacement, Optimal Algorithm, FIFO Algorithm, LRU(Least Recently Used) ALgorithm, LFU(Least Frequently Used) Algorithm, LRU와 LFU 알고리즘의 구현

1. 메모리

프로그램이 CPU에서 실행되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야 한다.
여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어 사용한다.
- 운영체제는 보통 모든 프로그램들에 공평하게 같은 크기의 메모리를 할당하기보다는
- 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후, 시간이 흐르면 이들로부터 메모리를 회수해서 다른 프로그램들에게 다시 집중적으로 메모리를 할당하는 방식을 채택한다.
운영체제는 CPU에서 당장 수행해야 할 부분만을 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다.
운영체제는 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다. 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상메모리(virtual memory)라고 부른다.
- 가상 메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크 스왑 영역에 존재하게 된다.
프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있다. 세부적인 구현에서는 요구 페이징 기법만이 사용된다고 할 수 있다.
물리적인 메모리의 주소 공간은 운영체제가 관여하지 않지만, 가상 메모리 기법은 전적으로 운영체제가 관여한다.

2. 요구 페이징(Demand Paging)

페이징 기법을 사용하고 있다는 전제하에
프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식을 말한다.
당장 실행에 필요한 페이지만을 메모리에 적재하기 때문에 효과적이다.
- 메모리 사용량 감소
- 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드 감소, 메모리에서 직접 서비스하는 비율의 증대로
- 응답 시간 단축
- 더 많은 사용자 수용
가상메모리 기법에서는 프로세스가 실행되는 동안 일부 페이지만 메모리에 올라와 있고 나머지 페이지는 디스크의 스왑 영역에 존재
→ 어떤 페이지가 메모리에 존재하고, 존재하지 않는지 구별 필요
- valid-invalid bit를 두어 각 페이지가 메모리에 존재하는지 표시, 페이지 테이블의 각 항목별로 저장
- 프로세스가 실행되기 전에는 모든 페이지의 항목이 invalid로 초기화
- invalid의 의미
  - 사용되지 않는 주소 영역인 경우(스왑 영역에도 없음, page table의 entry는 주소 공간의 크기만큼 만들어지기 때문에 사용되지 않는 주소 영역도 page table에 표시)
  - 페이지가 물리적 메모리에 없는 경우(= 스왑 영역에 내려가있는 경우)
- valid: 주소 변환을 통해서 물리적인 프레임 번호를 얻을 수 있는 경우(= 페이지가 참조되어 메모리에 적재되는 경우)
- 주소 변환 시에 invalid bit가 set 되어 있으면: page fault(페이지 부재) 발생
  - 요청한 페이지가 메모리에 없는 경우를 의미
  - page fault가 발생
    → 디스크에서 메모리로 올려야 하는 I/O 작업이 필요한데, 이 작업은 사용자 프로세스가 직접 못하는 작업으로
    → CPU는 자동적으로 운영체제에게 넘어가
    → page fault trap이 걸림(일종의 소프트웨어 인터럽트)
    → 운영체제가 fault난 페이지를 메모리에 올리는 작업 수행

2-1. page fault(요구 페이징의 페이지 부재 처리)

page fault에 대한 처리 루틴이 운영체제에 정의되어 있다.

CPU가 invalid page에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 page fault trap(페이지 부재 트랩)을 발생시킨다.
CPU가 운영체제로 넘어가 CPU의 제어권이 Kernel mode로 전환되고, page fault를 처리하는 코드인 page fault handler가 실행된다.

잘못된 요청(Invalid reference)이 아닌지 확인한다.
- 잘못된 주소(사용되지 않는 주소, bad address)이거나 접근 권한(protection violation)을 위반한 경우
→ 해당 프로세스 종료 abort
정상적인 접근일 경우 빈 페이지 프레임을 가져온다.
- 만약 physical memroy에 비어있는 페이지 프레임이 없고 메모리가 꽉 차있으면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아낸다.(swap out) - page replace
해당 페이지를 disk에서 memory로 읽어온다: 굉장히 느린 작업으로
- Disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당하고(= 뺏기고) 봉쇄 상태(block)가 된다.
  - 이때 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터 값을 PCB에 저장해 둠으로써 나중에 다시 수행될 때 정확히 같은 상태에서 다음 명령을 수행할 수 있도록 한다.
- Disk 입출력이 완료되어 인터럽트가 발생하면 page tables entry에 frame을 기록하고, valid/invalid bit를 valid로 변경한다.
- 봉쇄되었던 프로세스를 준비 큐로 이동시킨다.
이 프로세스가 다시 CPU를 할당받으면
PCB에 저장해 두었던 값을 복원시켜 이전에 중단되었던 명령 재개

2-2. 요구 페이징의 성능

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 page fault의 발생 빈도
- page fault가 발생하면 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생하기 때문
page fault rate 0 ≤ p ≤ 1.0
- p = 0: no page fault, 메모리에서 다 참조할 수 있다.
- p = 1: every reference is a fault
- 보통 page fault rate이 0.02 정도로, 대부분의 경우 page fault가 발생하지 않고 메모리로부터 직접 주소 변환을 할 수 있다.
유효 접근 시간 effective access time
- = (1 - p: page fault 발생하지 않음) X 메모리 접근 시간
  + p( OS로 CPU가 넘어가서 하드웨어적으로 page fault 처리 오버헤드
  + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드
  + 요청된 페이지의 스왑 인 오버헤드
  + 프로세스의 재시작 오버헤드 )

3. Page replacement(페이지 교체)

page fault가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수도 있다.
→ 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업이 필요하다 : page replacement
- 어떤 프레임을 메모리에서 쫓아내고 그 자리에 새로운 페이지를 올려놓을지를 결정해야 한다.
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋다.
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다.
  - 메모리에서 쫓겨날 떄 변경된 내용이 있다면 backing store에도 변경된 내용을 써줘야 한다.
  - 변경된 내용이 없다면 물리적 메모리에서 지워버리기만 하면 된다.
Replacement Algorithm
- page fault rate을 최소화하는 것이 목표
- 알고리즘의 평가: 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
  - reference string: 시간 순서에 따라서 페이지들에 서로 다른 번호를 붙여놓고 페이지들이 참조될 순서를 나열해 놓은 것
  - 예) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3-1. Optimal Algorithm, 최적 페이지 교체

page fault를 최소화하기 위해 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 방법
- 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하므로 실제 시스템에서 온라인으로 사용할 수 있는 알고리즘은 아니다: 오프라인 알고리즘
- 어떻나 알고리즘을 사용하는 경우보다도 가장 적은 page fault를 보장하므로 다른 알고리즘의 성능에 대한 상한선을 제공한다
  : 아무리 좋은 알고리즘을 만들어도 이보다 좋을 수 없다.
Belady’s optimal algorithm, MIN, OPT라고 부른다.

3-2. FIFO(First In First Out) Algorithm, 선입선출 알고리즘

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 방법
가장 먼저 물리적 메모리에 들어온 페이지가 계속해서 많은 참조가 이루어진다 하더라도 FIFO 알고리즘은 이 페이지를 내쫓게 되는
비효율적인 상황이 발생할 수 있다.
FIFO 이상 현상(FIFO Anomaly, Belady’s Anomaly): 메모리를 증가시켰음에도 불구하고 page fault가 오히려 늘어나는 상황

3-3. LRU(Least Recently Used) Algorithm

페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 쫓아내는 방법이다.
재사용된 페이지는 최근에 사용한 페이지로 간주하는 점이 FIFO와 다르다.

3-4. LFU(Least Frequently Used) Algorithm

물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재하는 방법이다.
최저 참조 횟수인 페이지가 여럿 있는 경우에는
- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정해도 상관이 없다.
- 하지만 성능 향상을 위해 가장 오래전에 참조된 page를 지우게 구현할 수도 있다.
Incache-LFU: 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식으로 페이지가 swap out 되었다가 swap in 되면 참조 횟수는 1부터 시작한다.
Perfect-LFU: 메모리에 올라와있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트한다. 정확성은 높지만 오버헤드가 상대적으로 더 크다.
장단점
- LRU처럼 직전 참조 시점만 보는 것이 아니라 LFU는 참조 횟수를 통해 장기적인 시간 규모에서의 참조 성향을 고려하기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
- 하지만 참조 시점의 최근성을 반영하지 못한다.
- LRU보다 구현이 복잡하다.

3-5. LRU와 LFU 알고리즘의 구현

LRU 알고리즘은 참조된 시간 순서에 따라 한 줄로 줄 세우며 linked list형태로 OS가 페이지들의 참조 시간 순서를 관리한다.
- 가장 오래전에 참조한 페이지가 linked list의 상단에 위치하고, 쫓아낼 때는 가장 상단에 있는 노드를 쫓아낸다.
- 참조한 적이 있는 페이지를 최근에 다시 참조하면 해당 페이지는 linked list의 하단으로 이동한다.
- 시간 정보로 모든 항목을 비교하면 O(n) 시간이 소요되기 때문에 비교하지 않고 linked list의 가장 상단에 있는 노드를 쫓아냄으로써 O(1) 시간이 소요된다.
LUF 알고리즘은 참조된 시간과 참조 횟수를 모두 고려하여 heap 형태로 관리한다.
- 가장 참조 횟수가 적은 노드는 힙의 상단의 루트 노드에 위치하고 참조 횟수가 많은 노드는 힙의 하단에 자식 노드에 위치한다.
- 참조한 적이 있는 페이지를 최근에 다시 참조하면 하단의 직계 자식 노드 2개와 비교하면서 자리를 바꿔 이동한다.
- 가장 상단에 있는 루트 노드를 쫓아내고 힙을 재구성하면 힙의 높이가 log2n이기 때문에 O(log n)의 시간이 소요된다.

[복습]

Virtural Memory 기법은 전적으로 운영체제가 관여하고 있다.
운영체제는 CPU에서 당장 수행해야 할 부분만을 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용
물리적인 메모리의 주소 공간은 운영체제가 관여하지 않지만, 가상 메모리 기법은 전적으로 운영체제가 관여한다.
요구 페이징: 당장 사용될 페이지만 메모리에 올리는 방식
- 어떤 페이지가 메모리에 존재하고, 존재하지 않는지 valid-invalid bit로 구별할 수 있다
- 주소 변환 시에 invalid bit라면 page fault(페이지 부재) 발생
page fault(요구 페이징의 페이지 부재 처리)
- CPU가 invalid page에 접근 → MMU가 page fault trap 발생 → CPU가 운영체제로 넘어가 page fault handler 실행
  → 잘못된 요청이 아닌지 확인 → 정상적인 접근일 경우 빈 페이지 프레임을 가져옴 → (빈 프레임이 없다면 swap out)
  → 디스크에서 메모리로 페이지를 읽어옴 → 이 프로세스는 선점당하고 block 상태 → PCB에 상태 저장
  → 입출력 완료 인터럽트 발생하면 페이지 테이블에 frame과 valid 기록 → block 프로세스를 준비 큐로 이동
  → 프로세스가 다시 CPU를 할당받음 → PCB값 복원시켜 명령 재개
요구 페이징 기법의 성능은 page fault 발생 빈도에 따라
페이지 교체: page fault 발생 시 빈 프레임이 존재하지 않으면 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업이 필요하다.
- optimal algorithm: 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 방법
- FIFO algorithm: 가장 먼저 올라온 페이지를 먼저 내쫓는 방법
- LRU algorithm: 가장 오래전에 참조가 이루어진 페이지를 쫓아내는 방법
  - linked list로 구현, 가장 상단의 노드가 가장 오래전에 참조한 페이지, 최근에 다시 참조하면 가장 하단으로 이동, O(1)
- LFU algorithm: 과거 참조 횟수가 가장 적은 페이지를 쫓아내는 방법
  - heap으로 구현, 루트 노드가 가장 참조 횟수가 적은 페이지, 최근에 다시 참조하면 하단의 직계 자식들과 비교하며 하단으로 이동, O(log n)

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

반효경 교수님의 [운영체제와 정보기술의 원리] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

반효경 [운영체제] 22. Virtual Memory 1

설명이 없습니다.

core.ewha.ac.kr