5장 Report

운영체제

1. 기억 장치 관리 기법

1) 반입 정책(fetch strategic) - when

: CPU로 실행되거나 참조되려고 주기억 장치로 적재할 다음 프로그램이나 자료를 언제 가져 올 것인가를 결정하는 문제

가) 요구 반입 정책(demand fetch strategic)

- 어떤 프로그램이나 자료가 참조되는 시점에 그것을 주기억 장치로 옮기는 기법

* 메모리 공간 사용효율이 좋음

* 대기시간이 길다는 점

나) 예상 반입 정책(anticipatory fetch strategic)

- 현 프로그램 수행 중에 앞으로 요구될 가능성이 큰 자료 또는 프로그램을 예상하여 미리 주기억 장치로 옮기는 방법

* 대기시간이 짧음

* 반입 페이지 결정 관련 알고리즘이 필요

* 메모리 사용효율이 떨어짐

2) 배치 정책(placement strategic) - where

: CPU가 요구하는 페이지나 세그먼트를 주기억 장치의 어디에 위치시킬 것인가를 결정하는 정책

가) 최초 적합(first fit)

- 프로그램이이 적재될 수 있는 가용 공간 중, 첫 번째 블록에 할당

* 장점 : 배치시간이 신속

* 단점 : 사용되지 않은 작은 크기의 가용공간이 누적될 경우 할당 결정이 늦을 수 있음

나) 최적 적합(best fit)

- 적재 가능한 가용공간 중 가장 작은 공백이 남는 블록에 할당

* 기억장소를 크기순서로 배열해야 하므로 많은 시간소요

* 가용공간을 반만 탐색해도 필요한 공간을 찾을 수 있음

* 크기 순으로 되어있지 않으면, 가용공간 전체를 검색

다) 최악 적합(worst fit)

- 가용공간 중 가장 큰 공백이 남는 블록에 할당

* 할당 후 남은 공간이 크기 때문에 다른 프로그램 사용이 가능

* 큰 프로그램이 적재될 수 있는 가용공간이 없어짐

* 크기 순으로 배열되지 않으면 모든 공간 탐색이 필요

3) 재배치 정책(replacement strategy) 또는 교체 정책- who

: 새로 들어온 프로그램이나 들어갈 장소를 마련하려고 어떤 프로그램이나 자료를 주기억 장치로부터 제거할 것인가를 결정하는 정책

가) 최적 교체

- 최적의 성과를 얻으려고 현 페이제가 참조된 시점에서 그 이후로도 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법, Belady가 제안

* 장점 : FIFO의 모순을 피할 수 있는 알고리즘

최소의 페이지 부재율을 갖는 알고리즘

* 단점 : 미래를 예측하기 어렵기 때문에 실현 불가능

나) 무작위

- 특별한 사용자들에게 차이를 두지 않고 페이지를 교체하는 기법

* 장점 : 신속한 교체 결정이 가능

* 단점 : 조만간 참조될 페이지도 교체될 수 있음

다) FIFO

- 각 페이지가 주기억 장치로 들어올 때마다 타임-스탬프(time-stamp)를 찍어 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을 때 가장 먼저 주기억 장치에 들어와 이TSms 페이지와 교체 시키는 방법

* 장점 : 단순하며 이해하기 쉬움

* 단점 : 중요한 페이지가 오래 있었다는 이유로 교체되는 것은 불합리

라) LRU

- 한 프로세스에서 사용되는 각 페이지 마다 카운터를 두어 현 시점에서 가장 오랫동안 사용되지 않는 페이지를 제거하는 방법, 가장 널리 사용되고 있음

* 구현방식

□ 테이블 형태 : 페이지 참조 시간을 페이지 테이블에 기록

□ 리스트 형태 : 페이지들을 리스트 형태로 유지

가장 최근에 참조된 페이지는 앞부분에 배치

메모리 참조가 발생할 때마다 리스트를 갱신

* 단점 : 알고리즘은 단순하지만 구현이 어려움(메모리 참조마다 리스트를 갱신하려면 많은 시간이 소요됨)

마) LFU

- 컴퓨터 주기억 장치에 설치되어 있는 페이지가 각각 얼마나 집중적으로 사용되었는가에 관심을 갖고, 가장 적게 사용되거나 집중적으로 사용되지 않은 페이지로 대체하는 방법.

* 단점 : 과거의 사용기록을 보유하고 있기 때문에 가장 최근에 메모리에 적재된 페이지도 교체될수 도 있음

바) 2차기회

- FIFO 방식의 단점인 가장 오랫동안 주기억 장치에 있었던 가장 자주 쓰이던 페이지가 대체될 수도 있다는 것을 막으려는 방법으로, 모든 페이지들의 참조 비트를 두어 참조 비트가 1이면 피드백시켜 유지하고 0인 페이지만 교체하는 방법

* 단점 : 리스트의 페이지들이 계속해서 움직이므로 비효율적

사) 워킹세트(또는 작업 집합)

- 실행 중인 프로세스가 일정 시간 동안에 참조하는 페이지들의 집합

- 효율적인 수행을 위해서는 작업 집합을 메모리에 유지해야 함

* 그렇지 못한 경우 지속적으로 페이지를 요구하여 스레싱 현상 유발

* 프로세스가 수행되는 동안 페이지들이 추가되거나 삭제됨

- 프로세스가 다른 작업 집합으로 전이될 때 많은 변화 발생

- 메모리에 작업집합을 잘 유지하면 스레싱 현상 방지 가능(스레싱 현상을 최소화하기 위함)

아) 페이지부재율

- 페이지 부재가 일어나는 빈도수를 말한다.

- 페이지 부재 ↑ : 프로세스가 더 많은 프레임을 필요로 함.

페이지 부재 ↓ : 프로세스가 너무 많은 프레임을 갖고 있는 것.

* 가. 다. 라. 마는 페이지교체 알고리즘 구현(174페이지)

가) 최적화

참조열	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
페이지 프레임	7	7	7	2		2		2			2			2				7
		0	0	0		0		4			0			0				0
			1	1		3		3			3			1				1
	F	F	F	F		F		F			F			F				F

다) FIFO

참조열	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
페이지 프레임	7	7	7	2		2	2	4	4	4	0			0	0			7	7	7
		0	0	0		3	3	3	2	2	2			1	1			1	0	0
			1	1		1	0	0	0	3	3			3	2			2	2	1
	F	F	F	F		F	F	F	F	F	F			F	F			F	F	F

라) LRU

참조열	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
페이지 프레임	7	7	7	2		2		4	4	4	0			1		1		1
		0	0	0		0		0	0	3	3			3		0		0
			1	1		3		3	2	2	2			2		2		7
	F	F	F	F		F		F	F	F	F			F		F		F

마) LFU

참조열	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
페이지 프레임	7	7	7	2		2		4	4	3				3	3		3	3		3
		0	0	0		0		0	0	0				0	0		0	0		0
			1	1		3		3	2	2				1	2		1	7		1
	F	F	F	F		F			F					F	F		F	F		F

* 적게 참조된 페이진 똑같으나 최장 페이지 대치를 적용

2. 고정 분할과 가변 분할 기억 장치 할당에서 각각 단편화가 발생하는 종류와 그 원인을 비교하고, 단편화를 해결할 수 있는 방법에 대해 기술하시오.

고정 분할 기억 장치 할당에서의 단편화

■ 기억 장치 단편화

1) 내부 단편화(Internal Fragmentation)

- 기억 공간 할당 후에 남는 공간

2) 외부 단편화(External Fragmentation)

- 기억 공간의 크기가 작아서 프로그램이 사용하지 못하는 공간

■ 단편화 발생원인

● 고정 분할 기억 장치 할당에서의 단편화하는 사용자 작업의 크기가 정확하게 분할에 맞지 않거나, 작업보다 분할이 너무 작아서 이 분할에 대기 중인 어떤 작업도 적재될 수 없을 때에 발생함

■ 장점

● 다수의 프로그램을 기억장치 공간에 넣고 수행할 수 있어 다중 프로그래밍이 가능

● 수행 속도를 증가시킴으로써 CPU를 보다 효율적으로 사용

■ 단점

● 단편화 문제가 발생.

● 단편화에 의해 기억장치의 낭비

● 수행할 프로그램의 크기를 미리 알아야 함

가변 분할 기억 장치 할당에서의 단편화

■ 가장 합리적인 분할의 크기를 결정하여 각 작업에 메모리를 할당하는 기법으로 고정분할의 경계를 없애고 각 작업에 필요한 만큼의 메모리를 할당

■ 페이지 교환으로 발생하는 가용 공간은 병합 및 압축하여 재활용

■ 전략으로는 프로그램이 적재될 수 있는 공간중 첫번째 분할에 할당하는 최초적합(First fi)전략, 가장 작은 공백이 남는 분할에 할당하는 최적적합(Best fit) 전략, 가용공간 들 중에서 가장 큰공간에 배치하는 최악(Worst fit) 전략이 있음.(자세한 내용은 위에 내용과 중복되므로 생략)

■ 장점

● 기억장치의 불필요하게 낭비하는 단편화를 방지

● 다중 프로그래밍의 정도를 높여 자원을 효율적으로 사용

■ 단점

● 기억장치를 집약하는 시간 소비

단편화 해결방법

■ 통합(Coalescing)

● 쓰레기 수집(garbage collection) : 여러 개의 작은 단편화 공간, 즉 가용 공간을 모아서 하나의 큰 가용 공간을 만드는 것

● 기억장치 통합(memory coalescing) : 이웃되는 가용 공간을 하나의 커다란 가용 공간을 만드는 것

■ 집약 또는 압축(Compaction)

- 기억장치의 여러곳에 부난된 공백 영역을 합쳐 하나의 유용한 공간으로 만드는 작업