OS - 9. Virtual Memory 연습문제

9.2 스레드의 상태를 준비 완료(ready),실행(running),봉쇄됨(blocked)으로 간단하게 정의 할 수 있다. 여기서 준비 완료는 실행할 준비가 되어 스케줄 되기를 기다리고 있는 상태이고, 실행은 처리기에서 실행 중인 상태 그리고 입출력 완료를 기다리는 것과 같은 대기 상태가 봉쇄됨이다. 이러한 상태를 도시한 그림이 9.30에 나와 있다. 스레드가 실행상태라고 가정하고 다음 질문에 답하시오

a.페이지 부재가 발생하면 스레드는 상태를 변화시키는가? 그렇다면 변화된 새로운 상태는 무엇인가?

answer) 페이지 부재가 발생하면 스레드는 blocked 상태가 된다. 그래서 페이지 부재가 해결되기를 대기한다.

b.페이지 테이블을 참조하여 해결할 수 있는 TLB 미스를 발생시킬 경우 스레드는 상태를 변화시키는가? 그렇다면 변화된 새로운 상태는 무엇인가?

answer)TLB miss가 발생했으면 페이지 테이블에서 다시 참조해 와야 하기 때문에 여전히 blocked상태에서 대기하게 된다.

c.페이지 테이블에 의해 주소 참조가 해결된다면 스레드는 상태를 변화시키는가?

그렇다면 새로운 상태는 무엇인가?

answer)주소 참조가 해결되면 스레드는 Ready상태가 된다. 그래서 스케줄 되기를 기다린다.

9.3 순수 요구 페이징을 사용하는 시스템이 있다고 하자.

a. 프로세스가 처음 실행을 시작할 때, 페이지 부재율은 어떻게 되는가?

- 순수 요구 페이징에서는 명령 포인터의 값을 프로세스의 첫 명령으로 설정하는 순간, 이 명령이 메모리에 존재하지 않은 페이지에 있으므로, 페이지 부재가 발생되고, 이후 연쇄적인 페이지 부재를 발생하여 프로세스에 필요한 모든 페이지를 적재 시킨다. 즉 메모리에 페이지가 모두 적재될 때까지 페이지 부재율은 높다.

b. 프로세서의 작업 집합이 메모리 적재된 후에는 페이지 부재율은 어떻게 되는가?

- 어떤 페이지가 필요할 때만 패이지 부재를 발생하여 해당 페이지를 가져온다. 따라서 처음 실행할 때보다 페이지 부재율이 낮다.

 

c. 프로세서의 지역성이 변하고 새로운 작업 집합의 크기가 너무 커서 자유 메모리에 적재될 수 없다고 가정하자. 이 상황을 해결하기 위하여 시스템 설계자가 선택 할 수 있는 결정들을 제시하시오.

- 페이지 교체를 통해 현재 진행에 필요 없는 페이지를 내리고, 반대로 필요한 페이지들을 메모리에 올린다.

 9.4  쓰기 시 복사가 어떤 기능인지 설명하고 이 기능을 어떤 상황에서 사용하는 것이 좋은지 설명하시오. 이 기능을 구현하기 위한 하드웨어 지원 사항은 무엇인가?

  두 개의 프로세스들이 같은 프로그램의 값에 접근 할 때 읽기용으로 물리적 페이지들을 두 개의 가상 메모리 공간으로 맵핑하여 준다. 실제적으로 쓰기가 일어나게 되면 쓰기 된 영역을 따로 할당하여 독립적으로 맵핑하여 준다. 이를 통해 라이브러리나 프로그램을 사용하는 프로세스들이 공통된 영역을 공유함으로서 메모리 공간을 작고 효율적으로 사용할 수 있다.

  읽기용으로 열린 페이지들을 하드웨어적으로 검사하여 페이지 테이블에 표시한다. 그런 읽기용 페이지에 쓰기를 할 경우 trap을 일으키고 그 trap은 운영체제가 잡아 새로운 Copy-on-Write되는 영역을 잡아줌으로써 처리한다.

9.5 어떤 컴퓨터는 사용자에게 바이트 크기의 가상 메모리 공간을 제공해준다. 컴퓨터는 바이트 크기의 실제 메모리 공간을 가진다. 가상메모리는 페이징에 의해 구현되고 페이지 크기는 4096바이트다. 사용자 프로세스는 가상 주소 11123456을 생성한다. 시스템이 이 가상 주소에 해당하는 실제 주소를 찾는 방법을 설명하시오. 소프트웨어와 하드웨어 연산을 구별하시오.

페이지의 크기가 바이트이므로, 페이지 테이블의 크기는 바이트이다. 또한, 논리 주소를 이진 표현으로 나타내면 0001 0001 0001 0010 0011 0100 0101 0110이다.

그러므로 상위 20비트인 ‘0001 0001 0001 0010 0011’은 페이지 테이블에서의 위치를 나타내고, 하위 12비트인 ‘0100 0101 0110’는 페이지 내의 변위를 나타낸다. 이러한 일련의 과정은 모두 하드웨어적으로 구현된다.

9.7 페이지 부재가 발생할 때, 페이지를 요청한 프로세스는 페이지가 디스크로부터 물리메모리로 적재될 때까지 기다리면서 봉쇄되어야 한다. 5개의 사용자 수준 스레드를 포함하고 사용자 수준 스레드와 커널 스레드의 사상이 다대일인 프로세스가 있다고 하자. 만약 한 사용자 스레드가 자신의 스택을 접근하려다 페이지 부재를 발생시키면 같은 프로세스에 속한 다른 사용자 스레드도 페이지 부재의 영향을 받아야 하는가? 즉 그 페이지가 메모리에 적재될 때까지 같이 기다려야 하는가? 여러분의 답을 정당화 하시오.

answer)하나의 프로세스가 페이지 부재에 의해서 봉쇄형이 되어버리면 다른 스레드도 봉쇄가 되어 그 페이지가 메모리에 적재될 때까지 기다려야 한다. 

9.8 다음과 같은 페이지 참조열을 생각해 보자.

7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1

프레임 3개를 가지고 요구 페이징을 할 때, 다음의 각 페이지 교체 알고리즘의 경우 몇 번의 페이지 부재가 발생하는가?

 1. LRU 교체 정책 : 가장 오랜 동안 사용되지 않은 페이지 교체

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
F1	7			1			3			7	7			5			2			1
F2		2			2			4				1			4			3
F3			3			5			6				0			6			0

        - 15번 교체

 2. FIFO 교체 정책 : 먼저 들어온 페이지 교체

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
F1	7			1					6				0			6			0
F2		2			2	5				7	7			5			2			1
F3			3				3	4				1			4			3

        - 14번 교체

 3. 최적 교체 정책 : 가장 오랜 동안 사용되지 않을 페이지 교체

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
F1	7	7	7	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
F2		2	2	2	2	5	5	5	5	5	5	5	5	5	4	6	2	3	3	3
F3			3	3	3	3	3	4	6	7	7	7	0	0	0	0	0	0	0	0

        - 10번 교체

9.9 그림에 보인 페이지 테이블은 16-비트 가상 주소와 물리 주소를 사용하고 한 페이지의 크기가 4096바이트인 시스템을 위한 것이다. 참조비트는 페이지가 참조될 때 1로 세트된다. 주기적으로 스레드가 모든 참조비트를 지운다. 페이지 프레임 열의 ‘-’는 페이지가 메모리에 없음을 나타낸다. 페이지 교체 알고리즘은 지역적 LRU가 사용되고 모든 숫자는 십진수로 표현되어 있다.

페이지	페이지 프레임	참조 비트
0	9	0
1	1	0
2	14	0
3	10	1
4	-	0
5	13	0
6	8	0
7	15	1
8	-	0
9	0	0
10	5	1
11	4	0
12	-	0
13	-	0
14	3	1
15	2	0

page number : 4자리, page offset : 12자리

  a. 다음의 가상 주소를(16진수) 대응하는 물리 주소로 변환하시오. 물리 주소는 십진수 또는 16진수로 표현 가능하다. 또한 페이지 테이블의 해당 항목을 찾아 참조비트를 세트하시오.

  > 0xE12C

   물리주소 = 0x312C

  > 0x3A9D

   물리주소 = 0xAA9D

  > 0xA9D9

   물리주소 = 0x59D9

  > 0x7001

   물리주소 = 0xF001

  > 0xACA1

   물리주소 = 0x5CA1

  b. 위의 주소를 지침으로 삼아 페이지 부재를 일으키는 논리 주소의 예를 들어 16진수로 보이시오.

  현재 메모리상에 페이지가 안 올라온 페이지 번호 -> 4, 8, 12, 13

  => 0x4051, 0x8A01, 0xC9AD, 0xD371 등

  c. 페이지 부재를 해결하기 위하여 LRU 페이지 교체 알고리즘은 어떤 집합에서 페이지를 선택하는가?

  페이지가 부재할시 지역적 LRU 교체알고리즘은 한 프로세스 내에서 가장 적게 사용된 페이지를 교체하게 된다. 위의 경우와 같이 참조비트를 가지는 경우 일정한 시간에 모든 참조비트를 0으로 초기화 하고 일정 시간 동안 사용한 페이지를 참조비트를 통해 1로 세트하여 표시한다. 페이지를 교체해야 하는 상황이 되면 FIFO순서로 검사하며 참조비트가 0인 페이지를 victim으로 하여 교체하게 된다.

9.10 클록 알고리즘에서 교체 후보 페이지를 나타내는 포인터가 이동하는 속도를 관찰하고 있다. 다음과 같은 관찰 결과를 얻는 경우 시스템에 대해 어떤 설명을 할 수 있는가?

a. 포인터가 빠르게 이동하고 있다: 가상 메모리 시스템이 교체 대상이 되는 페이지 후보를 찾지 못하였기 때문에 페이지 시스템 내의 페이지들을 탐색하면서 교체 대상을 선정하고 있는 것이다.

b. 포인터가 느리게 이동하고 있다: 가상 메모리 시스템이 교체 대상이 되는 페이지를 찾아낸 것이다.

9.12 MFU 교체 정책이 LRU 교체 정책보다 더 적은 수의 페이지 부재를 발생시키는 상황에 대해 설명하시오. 또한 반대의 경우는 어떤 경우인지 설명하시오.

answer)

페이지 참조열의 순서를 1 2 3 4 4 4 5 1 이라고 하자. 페이징 기법은 순수 페이징이라고 가정한다.

MFU의 경우, Page fault가 5회이다.(마지막에 1에서 Page fault가 없다.)

LRU의 경우, Page fault가 6회 이다.(마지막에 1에서 Page fault가 있다.)

대신 1 2 3 4 5 2일 경우에는 MFU의 Page fault가 더 많다.

9.13 > VAX/VMS 시스템은 최근에 사용되었던 가용 프레임 풀과 메모리 내의 페이지들(resident pages)에 대해 FIFO 교체 알고리즘을 사용한다. 가용 프레임은 LRU 정책에 의해 관리된다. 다음 질문들에 답하시오.

a. 페이지 부재 발생 시 가용 프레임 풀에 페이지가 존재하지 않으면, 새로 요청된 페이지를 위한 가용 공간을 어떻게 확보하는가?

 - 가용 프레임 풀에도 페이지가 존재하지 않으므로 FIFO 교체 알고리즘에 따라 가장 먼저 가용 프레임 풀에서 하나를 교체한다. 이후 새롭게 가용 프레임 풀에 올라온 페이지와 메모리 상에 있는 페이지와 교체한다. 이때 메모리 상 페이지도 FIFO교체 방식에 따라 교체 된다.

b. 페이지 부재 발생 시 페이지가 가용 프레임 풀에 존재하면, 요청된 페이지를 위한 공간을 만들기 위해 메모리 내의 페이지들과 가용 프레임 풀을 어떻게 관리하는가?

 - 메모리상에 공간이 있으면 해당 공간에 프레임을 넣고 없다면 메모리 상의 프레임 중 FIFO 교체 정책에 따라 하나의 희생 페이지를 선택하고 가용 프레임 풀에 있는 필요한 페이지와 교체한다.

c. 메모리 페이지 수가 1이면 시스템은 어떤 시스템으로 회귀한다고 할 수 있는가?

  - 메모리 페이지 수가 1이면 메모리 페이지와 가용 프레임 풀 합친 것과 디스크 사이에서는 FIFO 형태로 페이지를 교체하게 된다.

d. 가용 프레임 풀 내의 페이지 수가 0이면 시스템은 어떤 시스템으로 회귀한다고 할 수 있는가?

  - 가용 프레임 풀의 페이지 수가 0이면 페이지 부재 시 메모리와 디스크 사이에서 페이지를 FIFO형태로 교체하게 된다.

 9.14  다음과 같이 측정된 이용률을 가진 요구 페이징 시스템을 생각해 보시오.

CPU 이용률       20%

페이징 디스크       97.7%

기타 입출력 장치  5%

다음 항목 각각에 대해 CPU 이용률을 개선할 수 있는지(또는 개선 가능성이 있는지) 답하고 그 이유를 설명하시오.

  페이징 디스크만 바쁜 것으로 보아 위의 상황은 스레싱이 일어나는 상황이라 볼 수 있다.

 a. 더 빠른 CPU 설치

  없다 -> 스레싱으로 인해 현재의 CPU가 제 역할을 하지 못하고 노는 상황이다. 이에 더 빠
         른 CPU는 관계가 없다.

 b. 더 큰 페이징 디스크 설치

  없다 -> 페이징 디스크의 크기 보다는 물리적 메모리가 커져야 한다.

 c. 다중 프로그래밍의 정도 증가

  없다 -> 이미 다중프로그래밍의 정도가 지나쳐서 스레싱이 발생하게 되었다.

 d. 다중 프로그래밍의 정도 감소

  있다 -> 지나친 다중프로그래밍의 정도를 낮춰 페이지 fault를 적게 일어나게 만들어 CPU
         이용률을 높일 수 있다.

 e. 주 메모리 추가 장착

  있다 -> 교체 되지 않고 남아 있을 수 있는 페이지의 수를 더 늘려 페이지 fault를 막을 수
         있다.

 f. 더 빠른 하드디스크나 여러 개의 하드디스크를 가진 다중 제어기의 설치

  있다 -> 페이지 부재 시 교체를 할 때 속도의 개선이 될 수 있다.

 g. 페이지 인출 알고리즘에 프리페이징 추가

  있다 -> 다음에 사용할 페이지를 미리 가져옴으로써 속도를 개선시킬 수 있다.

 h. 페이지 크기 증가

  있다 -> 어느 정도의 페이지 크기 증가는 연속된 데이터를 하나의 페이지에 담음으로써 페
        이지 부재를 줄일 수 있다. 그러나 페이지 크기가 너무 커지게 되면 물리 메모리에
        남는 페이지의 수가 작아지고 더 많은 페이지 부재를 일으킬 수 있다.

9.15 어떤 시스템이 메모리를 1단계 간접 참조 방식을 통해 접근하는 명령어를 제공한다. 프로그램의 어떤 페이지도 메모리에 적재되어 있지 않은 상황에서 수행될 첫 명령어가 간접 참조 메모리 load 명령일 때 어떤 순서로 페이지 부재들이 발생하는가? 운영체제가 프로세스 단위의 프레임 할당 정책을 사용하고 이 프로세스에는 단지 2페이지만을 할당하였을 때는 어떤 상황이 발생하는가?

load 명령에 의해 참조되는 데이터가 메모리상에 적재되어 있지 않기 때문에 시스템에서는 페이지가 메모리에 존재하지 않는다는 page fault가 발생한다. 시스템에서 page fault가 발생하면, 가상 메모리 시스템은 HDD에서 페이지를 메모리에 적재한다.

만약, 프로세스에 2페이지를 가용할 수 있는 공간을 할당한다면, 프로세스에 의해 3개 이상의 페이지가 참조될 경우, 가상 메모리 시스템은 2개의 페이지 중에서 하나의 페이지를 선택하여 교체해야 한다. 교체 방식에는 FIFO, OPT, LRU 등이 있다.

9.17 페이지 교체 알고리즘은 페이지 부재의 수를 감소시켜야 한다. 이렇게 하려면 자주 사용되는 페이지들끼리 몇 개의 프레임을 가지고 경쟁하게 하기 보다는 이들을 균일하게 메모리 전체에 분산시켜야한다. 각 페이지 프레임에 그 프레임에 올라왔었던 페이지들의 수를 기억하여서 페이지를 교체 할 때는 그 수가 가장 작은 페이지 프레임을 찾는다.

a.이 기본적은 아이디어를 이용하여 페이지 교체 알고리즘을 정의하시오 특히 다음의 문제들을 해결하시오

1.프레임에 올라왔던 페이지들의 수의 초기 값은 무엇인가?

answer)초기 값 : 0

2.언제 프레임에 올라왔던 페이지들의 수가 증가하는가?

answer)카운터 값이 증가 하였을때

3.언제 프레임에 올라왔던 페이지들의 수가 감소하는가?

answer)카운터 값이 감소 하였을때

4.교체될 페이지를 어떻게 선정하는가?

answer)가장 작은 counter값을 가지는 frame을 찾는다.

b.다음의 참조 열에 대해 4개의 페이지 프레임에서 위에서 정의한 알고리즘이 발생시키는 페이지 부재 회수는 얼마인가?

1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2

answer) 14번의 페이지의 부재가 일어난다.

c.4개의 페이지 프레임을 가지고 b에 있는 참조 열에 대해 최적 페이지 교체 정책의 페이지 부재의 회수는 얼마인가?

answer)11번의 페이지의 부재가 일어난다.

9.18 > 액세스하고 전송하는데 평균 20밀리초가 소요되는 디스크를 가진 요구 페이징 시스템을 생각해 보자. 주소가 주 메모리 공간에 있는 페이지 테이블에 의해 번역되는데, 이 주 메모리 접근 시간은 1마이크로초이며, 이러한 페이지 테이블을 거쳐 실제 메모리에 있는 데이터를 접근하려면 결국 두 번의 메모리 접근을 필요로 한다. 이 시간을 개선하기 위하여 연관 메모리를 추가하는데, 이를 이용하면 만약 페이지 테이블 항목이 연관 메모리 내에 있다면 한 번의 메모리 접근만이 필요하게 된다. 접근의 80%가 연관 메모리 내에 있고, 나머지의 10%(또는 전체의 2%)가 페이지 부재를 일으킨다고 하면 실질 메모리 접근 시간은 얼마인가?

 - 18% (메모리), 80% (연관 메모리), 2% (디스크)

   1. 연관 메모리에 있을 시 : 1번 접근

   2. 메모리에 있을 시 : = 연관 메모리 못 찾고 메모리에서 찾고

   3. 페이지 부재 시 : = 연관 메모리, 메모리 못찾고 디스크

 즉 초가 걸린다.

9.19  스레싱의 원인은 무엇인가? 시스템이 스레싱을 발견하는 방법은 무엇이며, 일단 스레싱이 발견되면 이 문제를 해결하기 위해 시스템은 무엇을 할 수 있는가?

  스레싱은 프로세스가 필요로 하는 최저 페이지의 수를 만족시키지 못할 때 지속적인 페이지 부재를 일으키며 발생하게 된다. CPU의 이용률과 멀티프로그래밍의 정도를 보고 스레싱을 발견할 수 있다. 멀티프로그래밍의 정도는 높으나 CPU의 이용률이 감소하게 되면 스레싱이 발생한 것으로 볼 수 있다. 이러한 문제는 시스템에서 프로세스에 대한 최저 페이지 수를 만족하지 못하면 멀티프로그래밍의 정도를 줄임으로써 해결이 가능하다.

9.20 한 프로세스가 각각 데이터와 코드 영역을 나타내는 두 개의 작업 집합을 갖는 것이 가능한가? 이유에 대해 설명하시오.

많은 시스템에서는 프로세스가 각각 데이터와 코드 영역을 나타내는 두 개의 작업 집합을 갖도록 프로세스를 구현한다. 이러한 구현은 읽기만 하는 코드 영역과 읽기 및 쓰기 작업이 발생하는 데이터 영역을 분리하여 코드 영역은 HDD에 기록하지 않고, 내용의 수정이 발생하는 데이터 영역만 HDD에 기록하여 프로세스의 실행 효율을 향상시킬 수 있다.

9.23 > 사용자 수준 스레드와 커널 수준 스레드를 지원하는 시스템이 있다고 하자. 사용자 수준 스레드와 커널 수준 스레드의 사상은 일대일 사상을 사용한다. 즉 사용자 수준 스레드에 대응되는 하나의 커널 스레드가 존재한다. 다중프로세스는 (a) 전체 프로세스의 작업 집합 또는 (b) 각 스레드의 작업 집합으로 구성되는가? 이유를 설명하시오.

- 전체 프로세스 작업 집합 안에서 각 스레드의 작업집합으로 쪼개서 단편화를 시켜서 각 스레드의 작업 집합으로 구성되는 방법이 있고 단편화 방법을 막기 위해서 캐시를 할당해서 단편화에 의한 메모리 낭비를 막고 전체프로세스가 작업 집합을 공유할 수도 있습니다.

 9.24  슬랩 할당 알고리즘은 서로 다른 객체들에 대해 별도의 캐시를 사용한다. 객체별로 하나의 캐시가 존재하는 경우 CPU가 여러 개일 때 잘 확장되지 않는 이유를 설명하라. 이러한 문제를 해결하려면 어떻게 접근해야 하는가?

  global cache에 접근할 때 다른 프로세스의 접근을 막기 위해 lock을 사용한다. 이로 인해 cache의 접근이 serial하게 된다. 이러한 문제를 해결하기 위해 하나의 global cache를 사용하는 대신에 cpu당 캐시를 두는 것으로 해결하게 되었다.

9.25 프로세스에 서로 다른 크기의 페이지들을 할당하는 시스템을 생각하자. 이러한 페이징 시스템의 장점은 무엇인가? 가상 메모리 시스템을 어떻게 수정하면 이러한 기능을 제공할 수 있는가?

프로세스에 서로 다른 크기의 페이지들을 할당할 수 있도록 시스템을 구현한다면, 적은 양의 메모리를 이용하는 프로세스에는 작은 크기의 페이지를 할당하고, 많은 양의 메모리를 이용하는 프로세스에는 크기가 큰 페이지를 할당함으로써 메모리 사용량을 높일 수 있다. 또한, 메모리 사용량과 같은 크기의 페이지를 할당하기 때문에 페이지 내부의 공간이 낭비되는 내부 단편화가 발생하지 않는다.

이러한 기능을 제공하는 방법으로는 페이지 테이블에 페이지의 시작 주소만 기록하는 것이 아니라, 페이지의 시작 주소 및 마지막 주소까지 총 2개의 정보를 저장하여 한 페이지에 대한 시작 주소와 마지막 주소를 참조할 수 있도록 테이지 테이블을 구현하는 방법이 있다.