4. 프로그래밍 언어 활용 - 응용 SW 기초 기술 활용(기억장치 관리)

도서 개발 공부/정보 처리 기사 필기 2022. 4. 14. 10:00

151. 기억장치 관리

1) 기억장치 계층 구조

상위의 기억장치일수록 접근 속도가 빠르지만 가격도 증가하며 용량은 작음
주 기억장치 : 각기 자신의 주소를 갖는 word나 byte로 구성되어, 주소를 이용해 접근하는 기억장치
레지스터, 캐시, 주 기억장치의 데이터는 CPU가 직접 접근 가능
보조 기억장치의 데이터는 주 기억장치에 적재(load)되어야 CPU가 접근 가능

2) 기억장치 관리 전략

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

1. 반입 전략 (Fetch Strategy)

: 보조 기억장치의 프로그램이나 데이터를 주 기억장치에 적재하는 시기를 결정하는 전략

요구 반입 (Demand Fetch) : 실행중인 프로그램이 특정 프로그램이나 데이터 등의 참조를 요구할 때 적재하는 방식
예상 반입 (Anticipatory Fetch) : 실행중인 프로그램이 참조를 요구할 프로그램이나 데이터 등을 미리 예상하여 적재하는 방식

2. 배치 전략 (Placement Strategy)

: 주 기억장치 내에서 보조 기억장치의 프로그램이나 데이터를 적재할 위치를 결정하는 전략

최초 적합 (First Fit) : 프로그램/데이터가 들어갈 수 있는 크기의 빈 영역 중, 첫번째 분할 영역에 배치하는 방식
최적 적합 (Best Fit) : 프로그램/데이터가 들어갈 수 있는 크기의 빈 영역 중, 단편화를 가장 적게 남기는 영역에 배치하는 방식
최악 적합 (Worst Fit) : 프로그램/데이터가 들어갈 수 있는 크기의 빈 영역 중, 단편화를 가장 많이 남기는 영역에 배치하는 방식

※ 단편화

: 주 기억장치의 분할 영역 내에 프로그램/데이터가 적재될 때 그 크기가 영역보다 크거나 작아서 생기는 빈 공간

내부 단편화 : 영역이 할당된 프로그램/데이터의 크기가 영역 크기보다 작아서 남게 되는 빈 공간
외부 단편화 : 프로그램/데이터의 크기가 영역 크기보다 커서 할당될 수 없어서 남게 되는 빈 공간

3. 교체 전략 (Replacement Strategy)

: 주 기억장치의 모든 영역이 사용 중인 상태에서 새 프로그램/데이터를 배치하고자 할 때 할당을 교체할 영역을 결정하는 전략

ex) FIFO, OPT, LRU, LFU, NUR, SCR, etc.

152. 주 기억장치 할당 기법

: 실행하고자 하는 보조 기억장치의 프로그램/데이터를 주 기억장치에 할당할 때, 어떻게 할당할지 방식을 결정하는 기법

1) 연속 할당 기법

: 프로그램을 주 기억장치에 연속으로 할당하는 기법

1. 단일 분할 할당 기법

: 주 기억장치를 운영체제 영역과 사용자 영역으로 나누고, 한 순간에는 한 사용자만 사용자 영역을 이용하는 기법

가장 단순한 기법으로 초기의 운영체제에서 주로 이용
경계 레지스터 (Boundary Register) : 운영체제 영역을 보호하기 위해 사용자 영역의 시작 주소를 기억하는 레지스터
프로그램의 크기가 작을 경우 사용자 영역이 낭비됨
초기에는 주 기억장치보다 큰 프로그램은 실행할 수 없었으나 이후 오버레이 기법으로 이를 해결

- 오버레이 기법 (Overlay) : 주 기억장치보다 큰 사용자 프로그램을 실행하기 위한 기법

한 프로그램을 여러 조각으로 분할한 후 필요한 조각을 차례로 주 기억장치에 적재하여 프로그램을 실행
프로그램이 실행되며 주 기억장치의 공간이 부족해지면 가지고 있는 조각 중 불필요한 조각이 위치한 곳에 새로운 조각을 중첩해 적재
프로그램을 분할하는 작업은 프로그래머가 수행함 -> 프로그래머는 시스템 구조나 프로그램 구조를 알아야 함

- 스와핑 기법 (Swapping) : 하나의 프로그램 전체를 주 기억장치에 할당해 사용하다 필요에 따라 다른 프로그램과 교체하는 기법

Swap Out : 주 기억장치의 프로그램이 보조 기억장치로 이동하는 것
Swap In : 보조 기억장치의 프로그램이 주 기억장치로 이동하는 것
하나의 프로그램이 완료될 때까지 Swap Out과 Swap In이 반복됨
이후 가상 기억장치의 페이징 기법으로 발전

2. 다중 분할 할당 기법

: 주 기억장치의 사용자 영역을 여러 영역으로 나누어 여러 프로그램에 할당하는 기법

- 고정 분할 할당 기법 (MFT; Multiple contiguous Fixed parTition Allocation, 정적 할당 기법)

: 주 기억장치의 사용자 영역을 여러 개의 고정된 크기를 가진 영역으로 분할하고, 준비상태 큐의 프로그램을 각 영역에 할당해 수행하는 기법

실행할 프로그램은 전체가 주 기억장치에 위치해야 함
프로그램이 분할된 영역보다 커서 들어가지 못하는 경우가 발생
영역은 일정한데 반해 프로그램의 크기는 다양하므로 내부/외부 단편화가 발생하고 공간 낭비가 큼
실행할 프로그램의 크기를 미리 알고 있어야 함
다중 프로그래밍을 위해 이용된 기법이나 현재는 이용되지 않음
분류
- 절대 번역과 적재 : 프로그램이 할당될 분할 영역을 어셈블러나 컴파일러가 지정하는 방식
- 재배치 번역과 적재 : 프로그램이 할당될 분할 영역이 미리 지정되지 않고 순서대로 할당되는 방식

- 가변 분할 할당 기법 (MVT; Multiple contiguous Variable parTition Allocation, 동적 할당 기법)

: 프로그램을 주 기억장치에 적재할 때 필요한 만큼의 크기로 영역을 분할하는 기법

고정 분할 기법의 단편화 문제를 줄이기 위한 방식
주 기억장치의 공간 낭비가 감소하며 다중 프로그래밍 정도를 높일 수 있음
고정 분할 기법에 비해 실행될 프로세스 크기에 대한 제약이 적음
할당된 영역들 사이에서 단편화가 발생

2) 분산 할당 기법

: 프로그램을 특정 단위의 조각으로 나누어 주 기억장치 내에 분산하여 할당하는 기법

가상 기억장치의 내용을 주 기억장치에 할당하기 위한 기법으로 가상 기억장치 관리 기법이라고도 함
페이징 기법과 세그멘테이션 기법으로 분류

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

1) 가상 기억장치

: 보조 기억장치의 일부를 주 기억장치처럼 사용해 용량이 작은 주 기억장치가 큰 용량을 가진 것처럼 하는 기법

프로그램을 여러 개의 작은 블록 단위로 나누어 가상 기억장치에 보관하고 프로그램 실행 시 필요한 블록만 주 기억장치에 불연속적으로 할당하여 처리
- 블록 : 보조 기억장치와 주 기억장치 간에 전송되는 데이터의 최소 단위
주 기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용하는 기법
주 기억장치의 이용률과 다중 프로그래밍 효율을 높일 수 있음
주소 매핑 (Address Mapping) : 가상 기억장치의 주소를 주 기억장치의 주소로 바꾸는 주소 변환 작업
- 인위적 연속 (Artifical Contiguity) : 연속된 가상 주소가 반드시 연속적인 실 기억주소로 변환되지 않아도 됨
블록 단위로 나누어 프로그램을 사용 -> 연속 할당 방식에서 발생하는 단편화 해결 가능

1. 페이징 기법 (Paging)

: 가상 기억장치 내의 프로그램과 주 기억장치의 영역을 동일한 크기로 나누고 나눠진 프로그램 조각을 주 기억장치의 분할 영역에 적재하여 실행하는 기법

페이지 : 프로그램을 일정한 크기로 나눈 단위
페이지 프레임 : 페이지와 같은 크기로 분할된 주 기억장치의 영역 단위
외부 단편화는 발생하지 않음 : 적재되는 페이지의 크기는 반드시 페이지 프레임의 크기 이하임
내부 단편화는 발생 가능 : 프로그램이 반드시 모두 동일한 크기로 나눠지지는 않음 ex) 17K -> 6K + 6K + 5K
페이지 맵 테이블 (Page Map Table) : 주소 변환에 사용하기 위해 페이지의 위치 정보를 나타내는 표
- 페이지 맵 테이블의 사용으로 비용은 증가되지만 처리 속도는 감소

2. 세그멘테이션 기법 (Segmentation)

: 가상 기억장치 내의 프로그램을 다양한 크기의 논리적 단위로 나눈 후 주 기억장치에 적재하여 실행하는 기법

세그먼트 (Segment) : 프로그램을 배열, 함수 등의 논리적인 단위로 나눈 단위
- 각 세그먼트는 고유한 이름과 크기를 가짐
기억장치의 사용자 관점을 보존하는 관리 기법
기억공간의 절약이 궁극적인 목적
세그먼트 맵 테이블 (Segment Map Table) : 주소 변환에 사용하기 위해 세그먼트의 위치 정보를 나타내는 표
기억장치 보호 키 (Storage Protection Key) : 세그먼트를 적재할 때 다른 세그먼트 영역을 침범하지 않기 위해 사용
내부 단편화는 발생하지 않음 : 세그먼트 크기만큼 주 기억장치 내의 영역을 할당
외부 단편화는 발생 가능 : 세그먼트가 할당된 영역 사이에 외부 단편화 발생 가능

- 세그멘테이션 기법의 주소 변환 방식

1. 각 주소의 형식

가상 주소 : 세그먼트 번호 (s) + 변위값 (d) (변위값 : 세그먼트 내에서 실제 내용이 위치하고 있는 곳까지의 거리)
실 기억주소 : 실제 기억주소 (세그먼트 기준번지 + 변위값)
세그먼트 맵 테이블 : 세그먼트 번호 (s) + 세그먼트 크기 (L) + 기준 번지 (b)

2. 주소 변환 순서

가상 주소의 세그먼트 번호을 이용해 세그먼트 맵 테이블에서 해당 세그먼트의 기준 번지와 세그먼트 크기를 구함
가상 주소의 변위값과 세그먼트의 크기를 비교
변위값 ≤ 세그먼트 크기 : 기준번지와 변위값을 합하여 실 기억주소로 만든 뒤 주 기억장치에 접근
변위값 > 세그먼트 크기 : 다른 세그먼트의 영역을 침범하므로 실행 권한을 OS에 넘기고 트랩 발생

2) 페이지 교체 알고리즘

: 필요한 페이지를 가상 기억장치에서 주 기억장치로 적재해야 하고 주 기억장치의 모든 페이지 프레임이 사용 중일 때, 교체할 페이지 프레임을 결정하는 알고리즘

페이지 부재 (Page Fault) : CPU가 접근한 가상 페이지가 주 기억장치에 없는 상태
- 페이지 부재가 발생하면 해당 페이지를 보조 기억장치에서 주 기억장치로 적재해야 함

1. OPT (Optimal Replacement, 최적 교체)

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

페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘
프로세스가 앞으로 사용할 페이지를 알아야 함 -> 실제로는 구현이 거의 불가능한 알고리즘

2. FIFO (First In First Out, 선입선출)

: 가장 먼저 들어온, 즉 가장 오래 있었던 페이지를 교체하는 기법

이해가 쉽고 프로그래밍 및 설계가 간단함

3. LRU (Least Recently Used)

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

각 페이지마다 카운터나 스택을 두어 페이지 부재 발생 시점에서 가장 오래전에 사용한 페이지를 교체

4. LFU (Least Frequently Used)

: 사용 빈도가 가장 적은 페이지를 교체하는 기법

활발하게 사용되는 페이지는 사용 횟수가 많아서 교체되지 않음

5. NUR (Not Recently Used)

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

최근에 사용하지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로 함
LRU에서 나타나는 시간적 오버헤드를 줄일 수 있음
최근 사용 여부 확인을 위해 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)를 사용
- 참조 비트와 변형 비트의 값에 따라 교체할 페이지의 우선순위를 결정

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

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

154. 가상 기억장치 기타 관리 사항

: 가상 기억장치를 구현할 때 시스템 성능에 영향을 미치는 사항들

1) 페이지 크기

: 프로그램이 나누어지는 일정한 단위인 페이지의 크기에 따라 시스템에 미치는 영향이 다름

- 페이지의 크기가 작을 때

단편화 감소
페이지를 주 기억장치로 적재하는 시간이 감소
불필요한 내용이 주 기억장치에 적재될 확률이 적음 -> 효율적인 워킹 셋 유지
Locality에 더 일치 -> 기억장치 효율이 높음
페이지 맵 테이블의 크기가 커짐 -> 매핑 속도가 늦어짐
디스크 접근 횟수 증가 -> 전체적 입출력 시간 증가

- 페이지의 크기가 클 때

페이지 맵 테이블의 크기가 작음 -> 매핑 속도가 빨라짐
디스크 접근 횟수 감소 -> 전체적 입출력 시간 감소
단편화 증가
페이지를 주 기억장치로 적재하는 시간이 증가
프로세스에 불필요한 내용까지도 주 기억장치에 적재될 확률이 큼

2) Locality (지역성, 구역성)

: 프로세스가 실행되는 동안 주 기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 경향이 있다는 이론

스레싱을 방지하기 위한 워킹 셋 이론의 기반이 됨
프로세스가 집중적으로 사용하는 페이지를 알아내는 방법 중 하나
캐시 메모리 시스템의 이론적 증거

1. 시간 구역성 (Time Locality)

: 프로세스가 실행되며 하나의 페이지에 일정 시간 동안 집중적으로 접근하는 현상

한번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높음
ex) 반복문, 순환문, 스택, 서브 루틴, 카운팅이나 집계에 이용되는 변수, etc.

1. 공간 구역성 (Space Locality)

: 프로세스가 실행되며 일정 위치의 페이지에 집중적으로 접근하는 현상

참조한 페이지의 근처에 존재하는 페이지를 계속 참조할 가능성이 높음
ex) 배열 순회, 순차적 코드 실행, 서로 가까이에 할당되는 관련된 변수, 같은 영역 내의 변수, etc.

3) 워킹 셋 (Working Set)

: 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

프로그램의 locality 특징을 이용한 개념
자주 참조되는 워킹 셋을 주 기억장치에 상주시켜 페이지 부재를 줄이고 기억장치 사용을 안정화
시간에 따라 프로세스가 참조하는 페이지가 변하므로 워킹 셋 역시 시간에 따라 변화함

4) 페이지 부재 빈도 (PFF; Page Fault Frequency)

: 페이지 부재가 일어나는 횟수

페이지 부재 빈도 방식 : 주 기억장치의 페이지 프레임 수를 늘리거나 줄여 페이지 부재율을 적정 수준으로 유지하는 기법
- 프로세스 실행 초기에는 임의의 수의 페이지 프레임 할당
- 페이지 부재율 > 상한선 : 페이지 프레임 추가 할당
- 페이지 부재율 < 하한선 : 페이지 프레임 일부 회수

5) 프리페이징 (Prepaging)

: 프로세스 처음에 비어있는 주 기억장치로 인한 과도한 페이지 부재를 방지하기 위해 필요할 것이라고 예상하는 모든 페이지를 한꺼번에 적재하는 기법

6) 스래싱 (Thrashing)

: 프로세스의 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상

다중 프로그래밍 시스템이나 가상 기억장치 사용 시스템에서 페이지 부재가 자주 일어나 나타나는 현상
하나의 프로세스에서 발생한 스래싱으로 전체 시스템의 성능이 저하됨
다중 프로그래밍 정도가 높아짐에 따라 CPU 이용률도 함께 증가하지만, 일정 수치 이상이 되면 스래싱이 발생해 CPU 이용률이 급격히 감소

- 스래싱 현상 방지 방법

다중 프로그래밍 정도를 적정 수준으로 유지
페이지 부재 빈도(PFF)를 조절하여 사용
워킹 셋을 유지
부족한 자원을 증설하고 일부 프로세스 중단
CPU 성능에 대한 자료를 지속적으로 관리, 분석하여 임계치를 예상

저작자표시 비영리 변경금지 (새창열림)

'도서 개발 공부 > 정보 처리 기사 필기' 카테고리의 다른 글

4. 프로그래밍 언어 활용 - 응용 SW 기초 기술 활용(인터넷, OSI 참조 모델, 네트워크 프로토콜) (0)	2022.04.15
4. 프로그래밍 언어 활용 - 응용 SW 기초 기술 활용(프로세스) (0)	2022.04.14
4. 프로그래밍 언어 활용 - 응용 SW 기초 기술 활용(운영체제) (0)	2022.04.13
4. 프로그래밍 언어 활용 - 프로그래밍 언어 활용(라이브러리, 예외 처리) (0)	2022.04.13
4. 프로그래밍 언어 활용 - 프로그래밍 언어 활용(절차적 언어, 객체 지향 언어 , 스크립트 언어, 선언형 언어) (0)	2022.04.12

캐티시 :: 끊임없는 개발 공부와 연습, 그 지도