[6주차] Chapter 14. 스와핑, 페이징, 요구 페이징, 스래싱
Chapter 14 가상 메모리
14-1 연속 메모리 할당
1. 스와핑
① 스와핑(swapping)
-현재 실행되지 않는 프로세스를 메모리에서 보조기억장치 일부 영역으로 옮긴 후, 빈 메모리 공간에 다른 프로세스를 적재하여 실행하는 메모리 관리 기법
② 스왑 영역(swap space)
-프로세스들이 옮겨지는 보조기억장치의 일부 영역
③ 스왑 아웃(swap-out)
-현재 실행 중이 아닌 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
④ 스왑 인(swap-in)
-스왑 영역에 있던 프로세스가 다시 메모리로 옮겨지는 것
2. 메모리 할당
① 최초 적합(first fit)
-운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간이 있을 시 그 공간에 프로세스를 적재하는 방식
-발견 즉시 메모리를 할당하기 때문에 검색을 최소화할 수 있고 빠른 할당이 가능하다.
② 최적 적합(best fit)
-운영체제가 메모리 내의 빈 공간을 모두 검색해 본 후 프로세스가 적재될 수 있는 공간 중 가장 작은 곳에 프로세스를 적재하는 방식
③ 최악 적합(worst fit)
-운영체제가 메모리 내의 빈 공간을 모두 검색해본 후 프로세스가 적재될 수 있는 공간 중 가장 큰 곳에 프로세스를 적재하는 방식
3. 외부 단편화
① 외부 단편화(external fragmentation)
-메모리에 프로세스를 연속적으로 할당하며, 프로세스 간의 빈 공간이 너무 작아 프로세스를 할당하지 못하고 메모리가 낭비되는 현상
② 압축(compaction)
-메모리 내에 흩어진 프로세스를 재배치하여 작은 빈 공간들을 하나의 큰 빈 공간으로 만들어 외부 단편화를 해결하는 방법
-단점
: 작은 빈 공간을 모으는 동안 시스템은 하던 일을 중지해야 한다.
: 메모리에 있는 내용을 옮기는 작업은 오버헤드를 야기한다.
: 어떤 프로세스를 어떻게 옮기는 것이 최선인지 결정하기 어렵다.
확인문제
(기본 미션) 1. ① 최초 적합, ② 최적 적합, ③ 최악 적합
2. ④
3. ④
4. ①
14-2 페이징을 통한 가상 메모리 관리
가상 메모리(virtual memory)
-실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
-가상 메모리 관리 기법에 페이징과 세그멘테이션이 있다.
1. 페이징이란
① 페이징(paging)
-프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame)이라는 일정 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
-페이지와 프레임은 크기가 같다.
-프로세스 전체가 아닌 페이지 단위로 스와핑을 사용할 수 있다.
② 페이지 아웃(page out)
-페이징 시스템에서의 스왑 아웃
③ 페이지 인(page in)
-페이징 시스템에서의 스왑 인
2. 페이지 테이블
① 페이지 테이블(page table)
-물리 주소에서 불연속적으로 배치되어도 논리 주소가 연속적으로 배치되도록 하는 이정표
-어떤 페이지가 어떤 프레임에 할당되었는지를 알려준다.
-페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register) : 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
② 내부 단편화(internal fragmentation)
-프로세스의 논리 주소 공간이 페이지의 크기로 나누어 떨어지지 않아 생기는 메모리 공간 낭비
-하나의 페이지 크기보다 작은 크기로 발생한다.
③ TLB(Translation Lookaside Buffer)
-페이지 테이블의 캐시 메모리, 참조 지역성에 근거하여 주로 최근에 사용된 페이지의 페이지 테이블 일부 내용을 저장한다.
④ TLB 히트(TLB hit)
-CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
⑤ TLB 미스(TLB miss)
-페이지 번호가 TLB에 없어 메모리 내의 페이지 테이블에 접근해야 하는 경우
3. 페이징에서의 주소 변환
① 주소 변환
-논리 주소는 페이지 번호(page number, 접근하고자 하는 페이지 번호)와 변위(offset, 접근하려는 주소가 프레임의 시작 번지로부터 얼마나 떨어져 있는지의 정보)로 구성
-논리 주소<페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환된다.
4. 페이지 테이블 엔트리
① 페이지 테이블 엔트리(PTE; Page Table Entry)
-페이지 테이블의 각각의 행
② 유효 비트(valid bit)
-현재 해당 페이지에 접근 가능 여부를 알려준다.
-페이지가 메모리에 적재되어 있다면 1, 그렇지 않다면 0
-페이지 폴트(page fault) : CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 할 때 발생하는 예외
③ 보호 비트(protection bit)
-해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 읽기만 가능한 페이지인지 나타내는 페이지 보호 기능을 위해 존재하는 비트이다.
-읽고 쓰기가 모두 가능한 페이지일 경우 1, 읽기만 가능한 페이지이면 0
-읽기(Read), 쓰기(Write), 실행(eXecute)의 r, w, x의 조합의 세 개 비트로 복잡하게 표현도 가능
100 : 읽기만 가능, 쓰기와 실행 불가능
110 : 읽기, 쓰기만 가능, 실행 불가능
111 : 읽기, 쓰기, 실행 모두 가능
④ 참조 비트(reference bit)
-CPU가 페이지에 접근했는지의 여부를 나타낸다.
-적재 이후 CPU가 읽거나 쓴 페이지는 1, 적재 이후 CPU가 읽거나 쓴 적 없는 페이지는 0
⑤ 수정 비트(modified bit, 더티 비트(dirty bit))
-수정 여부를 나타낸다.
-변경된 적이 있는 페이지면 1, 변경된 적이 없는 페이지면 0
-스압 아웃 됐을 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 하므로, 그 여부를 판단하기 위해 필요하다.
확인문제
1. ④
2. ③
3. ②
4. ①
14-3 페이지 교체와 프레임 할당
1. 요구 페이징
① 요구 페이징(demand paging)
-실행에 요구되는 페이지만 적재하는 기법
-요구 페이징의 기본적인 양상은 아래와 같다.
① CPU가 특정 페이지에 접근하는 명령어를 실행한다.
② 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
③ 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
④ 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
⑤ 다시 ①번부터 반복한다.
-안정적 작동을 위해 페이지 교체와 프레임 할당을 해결해야 한다.
② 순수 요구 페이징(pure demand paging)
-아무런 페이지도 메모리에 적재하지 않고 무작정 실행부터 하는 방식
-실행에 필요한 페이지가 어느 정도 적재된 후 페이지 폴트 발생 빈도가 낮아진다.
③ 페이지 교체
-당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내는 것
-내보내야 하는 페이지 선정을 하는 데에 최선의 선택을 위해 페이지 교체 알고리즘을 사용한다.
2. 페이지 교체 알고리즘
① 페이지 교체 알고리즘
-페이지 폴트를 가장 적게 가져오는 알고리즘을 좋게 평가한다.
-페이지 참조열(page reference string) : 페이지 폴트 횟수를 알 수 있다.
② FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)
-메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
-먼저 들어왔지만 계속 실행되어야 하는 페이지가 있을 수 있다는 문제점이 있다.
+2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
-메모리에서 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별
-참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정한다.
③ 최적 페이지 교체 알고리즘(optimal page replacement algorithm)
-앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 방식
-가장 낮은 페이지 폴트율을 보장한다.
-앞으로 오랫동안 사용되지 않을 페이지를 예측하기가 어려워 실제 구현이 어렵다는 문제점이 있어 주로 이론상 성능을 평가하는 데에 사용된다.
④ LRU 페이지 교체 알고리즘(LRU; Least Recently Used Page Replacement Algorithm)
-가장 오랫동안 사용되지 않은 페이지를 교체하는 방식
3. 스래싱과 프레임 할당
① 스래싱(thrashing)
-지나치게 빈번한 페이지 교체로 인해 CPU의 성능이 저해되는 문제
② 멀티프로그래밍의 정도(degree of multiprogramming)
-메모리에서 동시에 실행되는 프로세스의 수
③ 프레임 할당 방식
~정적 할당 방식(프로세스의 크기와 물리 메모리의 크기만을 고려한 방식)~
-균등 할당(equal allocation) : 각 프로세스에게 균등한 수의 프레임을 할당하는 방식
-비례 할당(proportional allocation) : 각 프로세스의 크기에 비례하게 프레임을 할당하는 방식
~동적 할당 방식(프로세스의 실행을 보고 할당할 프레임 수를 결정하는 방식)~ -작업 집합 모델(working set model) : 작업 집합(working set, 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합)을 기억하여 잦은 페이지 교체를 방지한다. -페이지 폴트 빈도(PFF; Page-Fault Frequency) : 페이지 폴트율에 상한선과 하한선을 정하고 이 범위 안에서만 프레임을 할당하는 방식
확인문제
1. 3회
2. ④