[정처기 실기 - 계산식] 주기억 장치 계산식 / 페이지 교체 알고리즘

주기억 장치 계산식

Q. 주기억장치 배치 전략 기법으로 First Fit 방법을 사용할 경우, 다음과 같은 기억 장소 리스트에서 10K 크기의 작업은 어느 영역에 할당되는가?(단, 탐색은 위에서 아래로 한다.)

영역 번호	영역 크기	상태
A	11K	사용 중
B	5K	공백
C	15K	공백
D	30K	공백
E	12K	사용 중
F	25K	공백

• 풀이
  
  • First Fit(최초 적합)은 비어있는 공간 중 가장 처음 들어갈 수 있는 영역에 배치되게 됨
  • A의 경우 이미 사용 중이고, B의 경우 5K로 부족하고, C의 경우 15K는 10K가 들어갈 수 있음
  • 단, 5K의 내부 단편화가 발생

 

Q. 메모리 관리 기법 중 Worst Fit 방법을 사용할 경우 10K 크기의 프로그램 실행을 위해서는 어느 부분에 할당되는가?

영역 번호	영역 크기	상태
NO.1	8K	FREE
NO.2	12K	FREE
NO.3	10K	IN USE
NO.4	20K	IN USE
NO.5	16K	FREE

• 풀이
  
  • Worst Fit(최악 적합)은 배치할 수 있는 메모리 중 크기가 가장 큰 메모리에 배치를 하게 됨
  • NO.3과 NO.4는 사용 중이기 때문에 제외되고
  • FREE인 8K, 12K, 16K 중에 배치가 되는데 10K가 들어가기 위해서는 12K와 16K가 됨
  • 각각에 배치되게 되면 2K, 6K의 내부 단편화가 발생하는데 Worst(최악)은 6K
  • 따라서, NO.5에 배치

Q. 다음 표는 고정 분할에서의 기억 장치 Fragmentation 현상을 보이고 있다.
총 External Fragmentation은 얼마인가?

작업	분할 크기	작업 크기
A	20K	10K
B	50K	60K
C	120K	160K
D	200K	100K
E	300K	150K

A. 170K

• 풀이
  
  • External Fragmentation은 외부 단편화이며, 외부 단편화는 메모리 크기 < 작업크기일 때 메모리 크기만큼을 외부 단편화라고 함
  • 표에서 작업 크기가 더 큰 것은 B, C
  • 따라서, B와 C의 분할 크기인 50K + 120K = 170K가 외부 단편화

Q. 페이지 기억 장치 할당 기법에서 한 페이지의 크기가 512바이트이고 페이지 번호는 0부터 시작한다면 논리적인 주소 1224번지는 어디로 변환되는가?
A. 페이지 2, 변위 200

• 풀이

크기	페이지 번호	주소
512	0	512  → 1224 - 512
512	1	512  → 712 - 512
512	2	200

 

Q. 다음 조건을 만족하는 가상기억장치에서 가상 페이지 번호(Virtual Page Number)와 페이지 오프셋의 비트 수를 쓰시오.

페이징 기법을 사용하며 페이지 크기는 2048 바이트이다.

가상 주소는 길이가 32비트이고 가상 페이지 번호와 페이지 오프셋으로 구분된다.

페이지 오프셋 : 페이지를 나타날 때 페이지에 있는 비트 수(주소값)을 의미

A. 가상 페이지 번호 : 21 / 페이지 오프셋 : 11

• 풀이
  • 2048 = 2^11
  • 11개비트가 페이지 오프셋이 되며, 가상 페이지 번호는 가상 주소 길이 32비트 - 11비트 = 21비트가 됨

Q. 다음과 같은 세그먼트 테이블을 가지는 시스템에서 논리 주소(2, 176)에 대한 물리 주소는?

세그먼트 번호	시작 주소	길이(바이트)
0	670	248
1	1752	422
2	222	198
3	996	604

A. 398

• 풀이
  • 논리주소 2는 세그먼트 번호 / 176은 변위값
  • 따라서, 세그먼트 번호 2의 시작 주소인 222 + 176가 물리 주소가 됨

페이지 교체 알고리즘 - FIFO (First In First Out)

Q. 3개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3일 경우 FIFO 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태를 쓰시오

A. 4, 1, 3

	1	2	1	0	4	1	3
	1	1	1	1	4	4	4
		2	2	2	2	1	1
				0	0	0	3
페이지 부재	O	O		O	O	O	O

• 풀이
  • FIFO는 가장 처음에 들어온 것이 가장 먼저 나감
  • 따라서, 3개의 페이지 프레임이 가득 찼을 때 가장 먼저온 1이 4로 교체되고, 그 다음 들어온 2가 1로 교체되고, 그 다음 들어온 0이 3으로 교체 됨
  • 페이지 부재(교체 횟수)는 총 6회

Q. 3개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 FIFO 방법을 사용한다면 몇 번의 페이지 부재가 발생하는 지 쓰시오.
(단, 현재 기억 장치는 모두 비어있다고 가정한다.)
요청된 페이지 번호의 순서 : 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2

A. 9번

	2	3	2	1	5	2	4	5	3	2	5	2
	2	2	2	2	5	5	5	5	3	3	3	3
		3	3	3	3	2	2	2	2	2	5	5
				1	1	1	4	4	4	4	4	2
페이지 부재	O	O		O	O	O	O		O		O	O

 

Q. 3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어있다고 가정한다.
다음의 순서로 페이지 참조가 발생할 때 FIFO 페이지 교체 알고리즘을 사용할 경우, 몇 번의 페이지 결함이 발생하는가?

페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5

A. 7번

	1	2	3	1	2	4	1	2	5
	1	1	1	1	1	4	4	4	5
		2	2	2	2	2	1	1	1
			3	3	3	3	3	2	2
페이지 부재	O	O	O			O	O	O	O

 

Q. 페이지 프레임의 수가 4이고, 가상 페이지의 수가 8인 가상 메모리에서 선입선출 페이지 교체 정책이 사용된다.
처음에 4개의 페이지 프레임들이 비어있다고 가정했을 때 페이지 참조열이 0, 1, 7, 2, 3, 2, 7, 1, 0, 3이라면 페이지 부재횟수와 페이지 교체 횟수를 쓰시오.

A. 페이지 부재 : 6회 / 페이지 교체 : 2회

	0	1	7	2	3	2	7	1	0	3
	0	0	0	0	3	3	3	3	3	3
		1	1	1	1	1	1	1	0	0
			7	7	7	7	7	7	7	7
				2	2	2	2	2	2	2
페이지 부재	O	O	O	O	O				O
페이지 교체					O				O

• 풀이
  • 페이지 부재 : 페이지 부재는 주기억장치에 해당 페이지가 없을 때 페이지 부재라고 함
  • 페이지 교체 : 주기억장치의 페이지 프레임이 가득 차 있을 때 페이지 부재가 발생하면, 해당 페이지를 가상기억장치에서 가지고 와서 교체를 하게 됨

페이지 교체 알고리즘 - LRU (Least Recently Used)

Q. 3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어있다고 가정한다.
다음의 순서로 페이지 참조가 발생할 때, LRU 페이지 교체 알고리즘을 사용할 경우, 몇 번의 페이지 결함이 발생하는지 쓰시오.
페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5, 4

A. 6회

	1	2	3	1	2	4	1	2	5	4
	1	1	1	1	1	1	1	1	1	4
		2	2	2	2	2	2	2	2	2
			3	3	3	4	4	4	5	5
페이지 부재	O	O	O			O			O	O

• 풀이
  • LRU는 페이지 부재가 발생하여 교체를 해야할 경우, 가장 최근에 사용된 페이지를 제외하고 교체하게 됨
  • 즉, 가장 오래 사용되지 않은 것을 교체한다는 의미
  • 페이지 4가 최초 등장 했을 때, 바로 전에 사용된 페이지는 2이고, 전전은 1이기 때문에 페이지 3이 4로 교체가 되었음
  • 페이지 프레임이 4라면, 전 / 전전 / 전전전 까지는 유지를 함

Q. 3개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3일 경우 LRU 알고리즘에 의한 페이지 대치 최종 결과는?

A. 1, 4, 3

	1	2	1	0	4	1	3
	1	1	1	1	1	1	1
		2	2	2	4	4	4
				0	0	0	3
페이지 부재	O	O		O	O		O

 

Q. 4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어있다고 가정한다.
다음의 순서로 페이지 참조가 발생할 때 LRU 페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생하는가?
페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5

A. 5번

	1	2	3	1	2	4	1	2	5
	1	1	1	1	1	1	1	1	1
		2	2	2	2	2	2	2	2
			3	3	3	3	3	3	5
						4	4	4	3
페이지 부재	O	O	O			O			O

 

Q. 가상 메모리 교체 정책 중 LRU 알고리즘으로 구현할 때 최종 대치 상태를 쓰시오.
(단, 고정 프레임이 적용되어 프로세스에 3개의 프레임이 배정되어 있다.)
페이지 참조 순서 : B, C, B, A, D

A. B, D, A

	B	C	B	A	D
	B	B	B	B	B
		C	C	C	D
				A	A
페이지 부재	O	O		O	O

 

Q. LRU 교체 기법에서 페이지 프레임이 3일 경우 페이지 호출 순서가 3인 곳의 최종 대치 상태를 쓰시오.

4	2	0	5	2	1	7	3
4	4	4	5	5	5	7
	2	2	2	2	2	2
		0	0	0	1	1

A. 7, 3, 1

 

페이지 교체 알고리즘 - LFU (Least Frequency Used)

Q. 3개의 페이지 프레임으로 구성된 기억장치에서 다음과 같은 순서대로 페이지 요청이 일어날 때, 페이지 교체 알고리즘으로 LFU를 사용한다면 몇 번의 페이지 부재가 발생하는가?
(단, 초기 페이지 프레임은 비어있다고 가정한다.)
요청된 페이지 번호의 순서 : 2, 3, 1, 2, 1, 2, 4, 2, 1, 3, 2

A. 5번

	2	3	1	2	1	2	4	2	1	3	2
	2	2	2	2	2	2	2	2	2	2	2
		3	3	3	3	3	3	3	3	3	3
			1	1	1	1	4	4	1	1	1
페이지 부재	O	O	O				O		O

• 풀이
  • LFU는 사용 빈도수가 제일 적은 페이지가 교체되는 알고리즘
  • 풀다보면 페이지 프레임 N - 1까지는 고정이고 N 번째 페이지만 계속 교체가 됨
  • Ex) 페이지 프레임이 4개라면, 최초 처음 들어온 페이지 3개를 제외하고 제일 마지막 페이지만 교체가 일어남

Q. 4개의 페이지 프레임으로 구성된 기억장치에서 다음과 같은 순서대로 페이지 요청이 일어날 때, 페이지 교체 알고리즘으로 LFU를 사용한다면 페이지 대치의 최종 결과를 쓰시오.
(단, 초기 페이지 프레임은 비어있다고 가정한다.)
요청된 페이지 번호의 순서 : 2, 3, 1, 3, 1, 2, 4, 5

A. 2, 3, 1, 5

	2	3	1	3	1	2	4	5
	2	2	2	2	2	2	2	2
		3	3	3	3	3	3	3
			1	1	1	1	1	1
							4	5
페이지 부재	O	O	O				O	O