CHAPTER 01 - 운영체제의 특징(2)

2024년도 수제비 실기책(6판) 내용 

---

3. 운영체제 핵심 기능 파악

1) 메모리 관리 기법

(1) 개념

 

• 프로그램의 실행이 종료될 때까지 메모리를 가용한 상태로 유지 및 관리하는 방법

(2) 기법(반배할교)

기법	설명	세부 기법
반입 기법	- 주 기억장치에 적재할 다음 프로세스의 반입 시기를 결정하는 기법 - 메모리로 적재 시기 결정(When)	- 요구 반입 기법 - 예상 반입 기법
배치 기법	- 디스크에 있는 프로세스를 주기억장치의 어느 위치에 저장할 것인지를 결정하는 기법 - 메모리 적재 위치 결정(Where)	- 최초 적합(First-fit) - 최적 적합(Best-fit) - 최악 적합(Worst-fit)
할당 기법	- 실행해야 할 프로세스를 주기억장치에 어떤 방법으로 할당할 것인지 결정하는 기법 - 메모리 적재 방법 결정(How)	- 연속 할당 기법 - 분산 할당 기법
교체 기법	- 재배치 기법으로 주기억장치에 있는 프로세스 중 어떤 프로세스를 제거할 것인지를 결정하는 기법 - 메모리 교체 대상 결정(Who)	- 프로세스의 Swap In/Out - FIFO, Optimal, LRU, LFU, 시계 알고리즘, MFU

 

(3) 메모리 배치 기법

기법	설명
최초 적합(First Fit)	프로세스가 적재될 수 있는 가용 공간 중에서 첫 번째 분할에 할당하는 방식
최적 적합(Best Fit)	- 가용 공간 중에서 가장 크기가 비슷한 공간을 선택하여 프로세스를 적재하는 방식 - 공백 최소화 장점이 있음
최악 적합(Worst Fit)	프로세스의 가용 공간 중에서 가장 큰 공간에 할당하는 방식

 

[1] 예시

150MB

360MB

400MB

700MB

200MB

• 위와 같은 공간이 있을 때, 프로세스 A(215MB) -> 프로세스 B(171MB) -> 프로세스 C(86MB) 적재 시 아래와 같이 적재 됨

1. 최초 적합(First Fit)

150MB	360MB	400MB	700MB	200MB
프로세스 C	프로세스 A	프로세스 B

 

2. 최적 적합(Best Fit)

150MB	360MB	400MB	700MB	200MB
프로레스 C	프로세스 A			프로세스 B

 

3. 최악 적합(Worst Fit)

150MB	360MB	400MB	700MB	200MB
	프로세스 C	프로세스 B	프로세스 A

 

(4) 메모리 할당 기법(연단다 분폐세)

 

[1] 주기억장치 할당 기법의 종류

종류	설명	기법
연속 할당 기법	- 실행을 위한 각 프로세스를 주기억장치 공간 내에서 인접되게 연속하여 저장하는 방법 - 프로세스를 주기억장치에 연속으로 할당하는 기법	- 단일 분할 할당 기법(오버레이, 스와핑) - 다중 분할 할당 기법(고정 분할 할당 기법, 동적 분할 할당 기법)
분산 할당 기법	- 하나의 프로세스를 여러 개의 조각으로 나누어 주기억장치 공간 내 분산하여 배치하는 기법 - 주로 가상기억장치에서 사용	- 페이징 기법 - 세그먼테이션 기법 - 페이징/세그먼테이션 기법

 

[2] 페이징 기법(Paging)

 

• 가상기억장치 내의 프로세스를 일정하게 분할하여 주기억장치의 분산된 공간에 적재시킨 후 프로세스를 수행시키는 기법

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

 

• 가상기억장치 내의 프로세스를 가변적인 크기의 블록으로 나누고 메모리를 할당하는 기법
• 분할 형태가 배열이나 함수와 같은 논리적인 다양한 크기의 가변적인 크기로 관리함

[4] 페이징/세그먼테이션 혼용기법

 

• 외부 단편화 및 내부 단편화 최소화를 위하여 세그먼테이션 기법과 페이징 기법을 결합한 페이징/세그먼테이션 기법이 개발되었음

(5) 교체 기법

 

[1] 개념

 

• 주기억 장치에 있는 프로세스 중 어떤 프로세스를 제거할 것인지 결정하는 기법
• 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 기법

[2] 유형

세부 기법	설명
FIFO (Fist In First Out)	각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와 가장 오래 있던 페이지를 교체하는 기법(선입선출)
LRU (Least Recently Used)	- 사용된 시간을 확인하여 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 기법 - 프로그램의 지역성의 원리에 따라서 최근에 참조된 페이지는 앞으로도 참조될 가능성이 크고, 최근에 참조되지 않은 페이지를 앞으로도 참조되지 않을 가능성이 크다는 전제로 구현된 알고리즘
LFU (Least Frequently Used)	- 사용된 횟수를 확인하여 참조 횟수가 가장 적은 페이지를 선택하여 교체하는 기법 - 기억장치에 저장된 페이지 중에서 사용한 횟수가 가장 적은 페이지를 교체하는 알고리즘
OPT (OPtimal Replacement)	- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법 - 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘
NUR (Not Used Recently)	- LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법 - 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 크다는 것을 전제로, LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있음 - 최근의 사용 여부를 확인하기 위해서 페이지마다 참조 비트와 변형 비트 사용
SCR (Second Chance Replacement)	- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법으로 FIFO 기법의 단점을 보완하는 기법 - 페이지마다 참조 비트를 두고, FIFO 기법을 이용하여 페이지 교체 수행 중 참조 비트가 0일 경우에 교체를 수행하는 기법

 

(6) 교체 기법 알고리즘 계산

 

[1] FIFO(First-In-First-Out; 선입선출)알고리즘 : 주기억장치 페이지에 순차적으로 참조 스트링이 들어오고, 페이지 교체는 가장 먼저 들어온 페이지부터 교체하는 알고리즘

 

• 프로세스에 3개의 페이지 프레임이 고정으로 할당되어 있고, 초기에 3개의 페이지 프레임들이 모두 비어 있다고 가정
• 다음의 참조 스트링을 처리하는 동안 알고리즘별 페이지 부재가 몇 회 발생하는지 계산
• 순서 : 0 1 2 3 0 1 4 0 1 2 3 4 
• 페이지 부재 9회

참조 스트링	0	1	2	3	0	1	4	0	1	2	3	4
주기억 장치 상태 (페이지 프레임)	0	1	2	3	0	1	4	4	4	2	3	3
		0	1	2	3	0	1	1	1	4	2	2
			0*	1*	2*	3*	0	0	0*	1*	4	4
페이지 부재 Page Fault	f	f	f	f	f	f	f			f	f

** 별표 표기(*)는 교체 대상 페이지

 

[2] LRU(Least Recently Used)알고리즘 : 사용된 시간을 확인하여 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 알고리즘

 

• [1]번과 동일한 조건으로 참조 스트링을 처리하는 동안 페이지 부재가 몇 회 발생하는지 계산
• 순서 : 2 3 2 1 5 2 3 5
• 페이지 부재 : 5회

참조 스트링	2	3	2	1	5	2	3	5
주기억 장치 상태 (페이지 프레임)	2	3	2	1	5	2	3	5
		2	3	2	1	5	2	3
				3*	2	1*	5	2
페이지 부재 Page Fault	f	f		f	f		f

 

• 페이지 프레임을 보면 FIFO와 다르게 참조 스트링의 값이 페이지 프레임에 있으면 순서가 변경됨

** 별표 표기(*)는 교체 대상 페이지

 

[3] LFU(Least Frequently Used)알고리즘 : 사용된 횟수를 확인하여 참조 횟수가 가장 적은 페이지를 선택하여 교체하는 알고리즘

 

• 프로세스에 4개의 페이지 프레임이 고정으로 할당되어 있고, 초기에 4개의 페이지프레임이 모두 비어있다고 가정
• 다음 참조 스트링을 처리하는 동안 페이지 부재가 몇 회 발생하는지 계산
• 순서 : 2 3 1 3 1 2 4 5
• 페이지 부재 : 5회

참조 스트링	2	3	1	3	1	2	4	5
주기억 장치 상태 (페이지 프레임)	2	3	1	3	1	2	4	5
		2	3	1	3	1	2	2
			2	2	2	3	1	1
							3	3
페이지 부재 Page Fault	f	f	f				f	f

 

• 가장 사용이적은 4가 빠지고 5가들어와 버림

(7) 메모리 단편화

 

• 분할된 주기억장치에 프로세스를 할당, 반납 과정에서 사용되지 못하고 낭비되는 기억장치가 발생하는 현상

[1-1] 내부 단편화 : 분할된 공간에 프로세스를 적재한 후 남은 공간, 고정 분할 할당 방식 또는 페이징 기법 사용 시 발생하는 메모리 단편화

 

[1-2] 해결 방안

해결방안	설명
슬랩 할당자 (slab Allocator)	페이지 프레임을 할당받아 공간을 작은 크기로 분할하고(캐시 집합) 메모리 요청시 작은 크기로 메모리를 할당/해제하는 동적 메모리 관리 기법
통합 (Coalescing)	인접한 단편화 영역을 찾아 하나로 통합하는 기법
압축 (Compaction)	메모리의 모든 단편화 영역을 하나로 압축하는 기법

 

[2-1] 외부 단편화 : 할당된 크기가 프로세스 크기보다 작아서 사용하지 못하는 공간, 가변 분할 할당 방식 또는 세그먼테이션 기법 사용 시 발생하는 메모리 단편화

 

[2-2] 해결 방안

해결방안	설명
버디 메모리 할당 (Buddy Memory Allocation)	요청한 프로세스 크기에 가장 알맞은 크기를 할당하기 위해 메모리를 2ⁿ의 크기로 분할하여 메모리를 할당하는 기법
통합 (Coalescing)	인접한 단편화 영역을 찾아 하나로 통합하는 기법
압축 (Compaction)	메모리의 모든 단편화 영역을 하나로 압축하는 기법

 

(8) 페이징 기법의 문제 및 해결방안

 

[1] 페이징 기법의 문제점 - 스레싱(Thrashing)

 

• 어떤 프로세스가 계속적으로 페이지 부재가 발생하여 프로세스의 실제 처리 시간 보다 페이지 교체 시간이더 많아지는 현상
• 오류율이 클수록 스레싱이 많이 발생한 것이고, 스레싱으로 인해 전체 시스템의 성능 및 처리율을 저하됨
• 페이지 부재가 계속 증가하여 기억장치 접근 시간이 증가함

[2-1] 페이징 기법의 문제점 해결방안 - 워킹세트(Working Set)

 

• 각 프로세스가 많이 참조하는 페이지들의 집합을 주기억장치 공간에 계속 상주하게 하여 빈번한 페이지 교체 현상을 줄이고자 하는 기법

장점	단점
멀티 프로그래밍 정도를 높일 수 있고(Page Hit) 증가, CPU 활용률을 최적화 할 수 있음	워킹 세트 추적관리가 복작하고, 워킹 세트 크기 설정의 모호함이 발생

 

[2-2] 페이징 기법의 문제점 해결방안 - 페이지 부재 빈도(PFF; Page-Fault Frequency)

 

• 페이지 부재율의 상한과 하한을 정해서 직접적으로 페이지 부재율을 예측하고 조절하는 기법
• 페이지 부재 비율에 따라 페이지 프레임 개수를 조절

장점	단점
페이지 부재 발생 시 실행하여 부하가 적고, 직접적으로 페이지 부재율 조절이 가능한 기법	프로세스를 중지 시키는 과정이 발생하고 페이지 참조가 새로운 지역성으로 이동할 수 있음

 

(9) 지역성(Locality; 국부성, 구역성, 국소성)

 

[1] 개념

 

• 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 특성
• 프로세스가 집중적으로 사용하는 페이지를 알아내는 방법의 하나로, 가상기억장치 관리의 이론적인 근거가 되었음
• 지역성은 스레싱을 방지하기 위한 워킹 셋 이론의 기반이 되었음
• 참조 지역성(Locality of Reference)이라고도 불리며 3가지 유형이 존재함

[2] 유형

유형	설명	사례
시간(Temporal) 지역성	- 최근 사용되었던 기억장소들이 집중적으로 액세스하는 현상 - 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높은 특성	Loop(반복, 순환), 스택(Stack), 부프로그램(Sub Routine), Counting(1씩 증감), 집계(Totaling)에 사용되는 변수(기억장소)
공간(Spatial) 지역성	- 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상 - 참조된 메모리 근처의 메모리를 참조하는 특성	배열순회, 프로그래머들이 관련된 변수(데이터 저장 기억장소)들을 서로 근처에 선언하여 할당되는 기억 장소, 같은 영역에 있는 변수 참조
순차(Sequential) 지역성	- 데이터가 순차적으로 액세스 되는 현상 - 프로그램 내의 명령어가 순차적으로 구성된 특성 - 공간 지역성에 편입되어 설명되기도 함	순차적 코드 실행

 

• 지역성을 활용하여 기억/저장 장치의 계층적 구조와 캐시 메모리, 가상 메모리의 기법들로 효율성의 극대화가 가능함