[2020 정보처리기사 필기 요약] 4과목 - 프로그래밍 언어 활용(응용 SW 기초 기술 활용_2)

3. 기억장치 관리의 개요

 

 

1) 기억장치 계층 구조의 특징

종류 : 레지스터(최상위) <- 캐시 기억장치 <- 주기억장치 <- 보조기억장치(최하위)

 

계층 구조에서 상위의 기억장치일수록 접근 속도와 접근 시간이 빠르지만, 기억 용량이 적고 고가이다.

주기억장치는 각기 자신의 주소를 갖는 워드 또는 바이트들로 구성되고 주소를 이용해 엑세스 가능함

레지스터, 캐시 기억장치, 주 기억장치의 데이터는 CPU가 직접 액세스 가능하지만,

보조기억장치에 있는 데이터는 직접 액세스 불가능

보조기억장치에 있는 데이터는 주기억장치에 적재된 후 CPU에 의해 액세스될 수 있다.

 

 

 

 

2) 기억장치의 관리 전략

보조기억장치의 프로그램이나 데이터를 주기억장치에 적재 시키는 시기, 적재 위치 등을 지정해 한정된 주기억장치의 공간을 효율적으로 관리하기 위한 전략

 

* Why? 보조기억장치의 데이터는 직접 액세스가 불가능하니, 주기억장치에 적재 시켜야만 액세스가 가능하기 때문!

 

 

 

 

3) 반입(Fetch) 전략

보조기억장치에 보관중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인지 결정

 

요구반입 : 실행중인 프로그램이 특정 프로그램이나 데이터 등의 참조를 요구할 때 적재

예상반입 : 실행중인 프로그램에 의해 참조될 프로그램이나 데이터를 미리 예상해 적재

 

 

 

 

 

4) 배치 전략(Placement)

새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에 위치시킬 것인가 결정

 

최초 적합(First Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 첫번째 분할 영역에 배치

최적 적합(Best Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화(Fragment)를 가장 작게 남기는 분할 영역에 배치

최악 적합(Worst Fit) : 데이터가 들어갈 수 있는 크기의 빈 영역 중에서 단편화를 가장 많이 남기는 영역에 배치

* 단편화 : 빈 영역에 데이터를 배치하고 남은 기억 공간.

ex) 빈 영역이 13, 데이터가 10일때 배치 후에 남는 영역을 말한다.

 

 

예제 : 기억장치 관리 전략을 사용해 최초, 최적, 최악 적합의 방법으로 10K프로그램이 할당되는 영역의 번호는?

영역번호	영역크기	상태
1	5K	공백
2	14K	공백
3	10K	사용중
4	12K	공백
5	16K	공백

최초 : 2번(14K<=10K)

최적 : 4번(12K<=10K)

최악 : 5번(16K<=10K)

 

*1회+2회 기출문제입니다.

 

 

 

 

5) 교체 전략(Replacement)

주 기억장치의 모든 영역이 이미 사용중인 상태에서 새로운 프로그램이나 데이터를 주기억장치에 배치하려고 할 떄, 이미 사용되고 있는 영역에서 어느 영역과 교체할지를 정하는 전략

종류 : FIFO, OPT, LRU, LFU, NUR, SCR

 

 

 

 

 

 

 

 

 

 

 

4. 가상기억장치 구현 기법 / 페이지 교체 알고리즘

 

* 개정 전에도 빠짐없이 기출되었고, 개정 후에도 기출되었던 아주 중요한 개념입니다!

 

 

1) 가상기억장치 개요

보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 기법

• 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상 기억장치에 보관 후, 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리한다.
• 주기억장치의 용량보다 큰 프로그램 실행을 위해 사용
• 주기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있음.
• 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업 필요함.
• 블록 단위로 나누어 사용하기 때문에 연속 할당 방식에서 발생할 수 있는 단편화 해결 가능
• 가상기억장치의 구현 방법 : 페이징 기법, 세그먼테이션 기법

* 장점과 특징을 기억하세요!

 

 

 

 

 

2) 페이징(Paging) 기법

가상 기억장치에 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후,

나눠진 프로그램(페이지)을 동일하게 나눠진 주기억장치의 영역(페이지 프레임)에 적재시켜 실행

페이지 : 프로그램을 일정한 크기로 나눈 것

페이지 프레임 : 페이지 크기로 일정하게 나눠진 주기억장치의 단위

외부 단편화 발생x, 내부 단편화 발생o

주소 변환을 위해 페이지 맵 테이블이 필요함

페이지 맵 테이블 사용으로 비용이 증가, 처리속도가 감소

 

 

 

 

 

3) 세그먼테이션(Segmentation) 기법

가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 기법

배열이나 함수 등과 같은 논리적 크기로 나눈 단위를 세그먼트라고 부르며, 각 세그먼트는 고유한 이름과 크기를 가짐.

기억장치의 사용 관점을 보존하는 기억장치 관리 기법이다.

사용하는 이유 -> 기억공간 절약

주소 변환을 위해 세그먼트 맵 테이블이 필요함

세그먼트가 주 기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없도록 기억장치 보호키가 필요함.

내부 단편화x, 외부 단편화o

 

 

 

 

 

4) 페이지 교체 알고리즘

페이지 부재(Page Fault)가 발생시 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 할때, 주기억장치의 모든 페이지 프레임이 사용중일 경우 어떤 프레임을 선택하여 교체할지를 선텍하는 알고리즘이다.

* 페이지 부재 : CPU가 액세스한 가상 페이지가 주기억장치에 없는 경우. 페이지 부재가 발생하면 해당 페이지를 보조기억장치(디스크)에서 주기억장치로 가져와야함.

 

 

OPT(OPTimal replacement), 최적 교체

가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

밸레이디(Belady) 개발

페이지 부재횟수가 가장 적게 발생하는 효율적인 알고리즘

 

 

FIFO(First In First Out)

그때의 시간을 기억시켜 가장 먼저들어와서 가장 오래 있었던 페이지를 교체하는 기법

ex) FIFO 알고리즘 사용시

참조페이지	2	3	2	1	5	2	3	5
페이지 프레임	2	2	2	2	2->5	5	5	5
		3	3	3	3	3->2	5	2
				1	1	1	1->3	3
부재발생	O	O		O	O	O	O
	(1)				(2)	(3)

총 부재수 = 6

 

(1) 참조 페이지를 각 페이지 프레임에 차례로 적재시키되, 이미 적재된 페이지는 해당 위치의 페이지 프레임을 사용한다.

(2) 사용할 페이지 프레임이 없을 경우 가장 먼저 들어와서 오랫 있었던 페이지 2을 제거하고 5를 적재한다.

(3) 같은 방법으로 나머지 참조 페이지를 수행

 

 

LRU(Least Recently Used)

최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

각 페이지마다 계수기(Counter)나, 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은,

즉 가장 오래전에 사용된 페이지를 교체한다.

 

ex) LRU 알고리즘 사용시

참조페이지	2	3	2	1	5	2	3	5
페이지 프레임	2	2	2	2	2	2	2	2
		3	3	3	3->5	5	5	5
				1	1	1	1->3	3
부재발생	O	O		O	O		O
	(1)				(2)	(3)

총 부재수 = 5

 

(1) 참조 페이지를 각 페이지 프레임에 차례로 적재시키되, 이미 적재된 페이지는 해당 위치의 페이지 프레임을 사용한다.

(2) 사용할 페이지 프레임이 없을 경우 현재 시점에서 가장 오랫동안 사용되지 않은 페이지 3을 제거하고 5를 적재한다.

(3) 같은 방법으로 나머지 참조 페이지를 수행

 

 

* FIFO와 LRU의 차이, 부재수 계산하는 방법을 꼭 기억하시면 1점 먹고 들어갑니다! 요령만 알면 쉬워요!

 

 

LFU(Least Frequently Used)

사용 빈도가 가장 적은 페이지를 교체

 

 

 

NUR(Not Used Recently)

LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지 교체

최근의 사용여부를 확인하기 위해 각 페이지 마다 두 개의 비트, 참조비트(Reference)와 변형 비트(Modified Bit, Dirty Bit)가 사용된다.

참조비트	0	0	1	1
변형비트	0	1	0	1
교체순서	1	2	3	4

* 교체 순서 기억하세요!

* 기출 예상 개념입니다!

 

 

SCR(Second Chance Replacement, 2차 기회 교체)

가장 오랫동안 주기억 장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 알고리즘으로 FIFO 기법의 단점을 보완한 기법.