[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. ④