[운영체제] 8. Meomory-Management Strategies 메모리 관리 기법

Computer Science/OS 2022. 12. 2. 03:44

728x90

Background

프로세스와 메모리와의 관계

프로그램이 실행되기 위해서 메인 메모리에 적재되어야 함.
CPU가 직접 접근할 수 있는 저장소는 메모리와 레지스터
레지스터는 1 CPU clock에 접근 가능 (속도 빠름)
메모리 접근에는 여러 clock cycle 필요 (속도 느림)
메모리와 CPU 레지스터 중간에 캐시 메모리 존재
정확한 실행 보장하기 위해 메모리 보호 필요하다.

주기억 장치 관리 정책 분야

반입 정책 : 하드 디스크에 어떤 모듈을 메인 메모리에 적재할 것인가를 결정

요구 반입(demand loading) vs 예상 반입 (X, 예측 어려움)

배치 정책 (placement policy) : 반입한 모듈을 메인 메모리 어디에 저장할 것인가?

최초 적합, 최적 적합 등

교체 정책 (replacement policy) : 메인메모리 공간 부족할 경우, 어느 모듈을 하드디스크로 보낼 것인지 결정

Binding of Instructions and Data to Memory

(언제 명령어와 물리적 주소값이 결정(Binding)되는가 - 물리적 주소 값의 확정 시간)

Compile time binding : compile time에 프로세스가 위치할 메모리의 위치를 알 수 있는 경우 (컴파일 시 메인 메모리의 어떤 위치(주소)에 적재되는지 알 수 있음)
Load time binding : 프로그램이 메모리 적재될 때 결정되는 경우
Execution time binding : 프로세스가 실행되는 동안 메모리 내에서 옮겨질 수 있는 경우 (현재 사용)
- 실행 시간에 논리적 주소에 해당되는 물리적 주소 값이 결정된다.
- 실행 시간에 논리적 주소를 물리적 주소 값으로 변환 필요 (MMU, Memory Managed Unit 이용)

ex ) 시스템 과부하 상태에 우선순위 낮은 프로세스 swap out 되었다가 다시 swap in 되는 경우 프로세스가 원래 메모리 주소로 돌아오지 않고 달라진다.

* binding : 주소 값이 확정되는 시간을 의미

Logical vs. Physical Address Space

논리적 주소 공간이 물리적 주소 공간으로 바인딩된다는 개념이 메모리 관리의 중심이 되는 개념이다.

논리적 메모리 주소 (Logical address == virtual address) : CPU는 항상 논리적 주소만을 참조할 수 있다.
물리적 메모리 주소 (Physical address) : 실제 명령어나 데이터가 저장되는 메인 메모리의 주소 값

Logical(virtual) and physical addresses differ in execution-time address-binding scheme.

실행시간에 논리주소가 물리 주소로 번역되므로 논리 주소와 물리 주소는 다르다.

논리적 주소는 모두 0부터 시작
물리적 주소는 실제 데이터 저장되는 실제 메모리 주소
멀티 프로그래밍에서 논리적 주소는 물리적 주소와 일치하기 어렵다.

메모리 관리 단위(Memory Management Unit, MMU)

CPU가 발생시킨 논리적 주소를 빠르게 물리적 주소로 계산해준다.
사용자 프로그램은 논리적 주소만을 고려한다. (물리적 데이터 위치에 전혀 신경 쓸 필요가 없다.)

* 논리적 주소를 물리적 주소로 매핑 -> OS가 관리.

논리적 주소 346을 MMU의 재배치 레지스터 (relocation register) 14000 값 더해져, 실제 물리적 메모리 14346에 매핑된다.

Dynamic Linking (동적 연결)

Linking postponed until execution time. 실행시간까지 연결(Linking)을 연기하는 것.

* Linking이란 함수 호출 부분과 실행 코드를 연결시키는 의미

stub가 실제 라이브러리의 위치를 저장하고 있다.

* 외부와 인터페이스만을 남기고, 실행코드는 후에 연결.

실행 시간에 stub는 실제 실행 모듈로 변환된다. (라이브러리가 시작되도록 stub가 라이브러리 시작 주소로 치환된다.)

정적 연결 (Static Linking)
- 프로그램 코드, 라이브러리 등 한번에 정적으로 연결된다.
동적 연결 (Dynamic Linking) = shared librarie 공유 라이브러리.
- 프로그램 코드에서 필요한 라이브러리를 별도로 호출해서 사용한다.
- DDL(Dynamically Linked Libraries) : 프로그램 실행 시 사용자 프로그램에 연결된 시스템 라이브러리.

Swapping - 디스크로 임시 이동

swapping은 우선순위 스케줄링에 사용 가능. 낮은 우선순위 -> swap out

메인 메모리 -> HDD로 이동 : swap out, roll out

HDD -> 메인 메모리 : swap in, roll in

Backing store : 하드 디스크

Contiguous Allocation (연속 할당)

cf) Non-contiguous Allocation (비연속 할당) = Page 단위 할당

프로그램이 연속적인 메인 메모리 공간에 할당된다.

Resident operating system : 상주하는 운영체제 관련 프로그램은 낮은 번호의 주소 공간에 위치됨
User processes : 사용자 프로세스는 높은 메모리 주소 공간에 위치됨
Base register : 프로세스의 시작 주소 값을 저장
Limit register : 프로세스의 크기 값(Size)을 저장
MMU : 실행 시간(execution time)에 물리 주소를 계산한다. (논리적 주소 값을 물리적 주소 값으로 계산)

Multi-programming에서의 연속 할당

메인 메모리를 나누어 여러 프로그램을 적재하여 실행

고정 분할 방식 : partition 크기가 고정 (부팅 시에 고정)
가변 분할 방식 : partition 크기를 필요한 만큼만 할당

기억 장치 단편화(fragmentation) 발생

내부 단편화(internal fragmentation) 필요한 공간보다 할당된 파티션이 커서, 낭비되는 공간
외부 단편화(external fragmentation) 할당되지 않았으나 각 크기가 너무 작아 사용할 수 없는 공간

고정 분할 (Fixed partition) 할당

메인 메모리가 고정 크기 4개의 파티션 할당됨. (고정 분할 단편 파티션은 컴퓨터 부팅 시 지정)

작업 1 -> 분할 4에 할당

작업 2 -> 분할 2에 할당

작업 3 -> 분할 3에 할당

작업 4 -> 미할당

내부 단편화(internal fragmentation) 발생함. 비효율 발생.

가변 분할 할당 (variable partition)

p1, p2, p3, p4 메인 메모리에 순차적으로 할당된다.

-> p1 종류 후에 p5 할당

-> p3 종료 후에 p6 할당

-> 가용 공간의 합이 250k이나, p7의 할당 수용 불가

(외부 단편화 발생) 각 파티션 할당 공간 외부에 단편화가 발생함.

Dynamic Storage-Allocation 방법 (동적 저장공간 할당 방법)

First-fit : 사용 가능 공간이 생길 때 바로 할당 (가장 처음 partition에 할당)

Best-fit : 남은 메모리 공간이 가장 작은 최적의 방법으로 할당

Worst-fit : 가장 큰 파티션에 할당

Partition allocation algorithm

입력되는 프로그램과 데이터를 주기억장치의 어느 곳에 넣을지를 결정

최초 적합 기법 (first-fit strategy) : 수용할 수 있는 주기억장치의 첫 번째 유용한 공백을 우선적으로 선택
최적 적합 기법 (best-fit strategy) : 작업에 가장 적합한 공간을 선택함으로써 기억장치의 단편화를 최소로 하는 방법
최악 적합 기법 (worst-fit strategy) : 프로그램을 가장 큰 공백에 배치

Partition allocation example

Fragmentation (단편화) 문제

외부 단편화 (External Fragmentation)

내부 단편화 (Internal Fragmentation)

공간을 확보하기 위한 전략

Memory coalescing (메모리 연합)
compaction (집약) - 외부 단편화 모아 줄이기

Memory coalescing(연합) & compaction(집약)

coalescing(연합) : 연속된 두 개의 사용 공간을 합치는 것. (단편화 + 프로세스 사용 완료되어 반환된 메모리 공간)
compaction(집약) : 사용 가능한 공간을 이동하여, 하나의 큰 공간을 만드는 것.
- 시간이 너무 오래 걸린다.
- 집약 시행 중 사용자 프로세스 실행 불가.

프로세스 주소 공간과 메인 메모리 mapping

두 개의 프로세스가 메인 메모리에 할당되어 실행 중

새로운 프로세스 (크기 : 150)을 실행하려면 -> 메모리 집약 (compaction)

메모리 compaction 실행 후

compaction 실행 도중에는 프로그램 실행이 중단된다. (자원 낭비)

-> 해결책 : page 단위로 나눠서 할당 (비연속 할당) 사용

페이지 단위 할당 - compaction(집약) 불필요 (Non-contiguous Allocation)

*가장 보편적인 메모리 할당 기법

사전에 약속된 페이지 단위로 할당하면 compaction 불필요하다 (집약 안 해도 자유로운 할당 가능)

대신 각 프로세스에 자신의 페이지를 메모리 frame에 매핑시키는 페이지 테이블(Page Table)이 필요하다.

프로그램의 크기를 page 단위로 분할

page 단위의 메인 메모리 할당 (비연속 할당)

Paging (페이징)

프로세스의 물리적 주소 공간을 비연속적으로 허용하는 메모리 관리 체계
외부 단편화(external fragmentation) 회피
운영체제와 하드웨어 사이에서 협력하여 구현

페이징의 기본적인 방법

물리적인 메모리를 고정된 크기의 블록(frames)으로 분할
- size is power of 2, between 512 bytes and 8,192 bytes
논리적인 메모리를 같은 크기의 블록(pages)으로 분할

프로그램 n개의 페이지, 메인 메모리의 n개의 프레임을 찾아서 적재한다.

논리적 Page number를 Page Table이용 물리적 frame number로 변환하여 매핑한다.

프로그램의 크기가 페이지 크기의 정수배가 아니므로, 할당된 맨 마지막 페이지에서 내부 단편화 발생한다.

ex) Page : 4 kbytes, Program : 17 kbytes -> 3 kbytes의 내부 단편화 발생

Address Translation Scheme

CPU에 의해서 생성된 모든 주소는 2가지 부분으로 나뉜다.
- 페이지 번호(page number, p)
- 페이지 오프셋(page offset, d)

Paging Hardware : 주소 번역 메커니즘

페이지 번호 이용하여 frame number를 찾는다. p -> f

Paging Model of Logical and Physical Memory

페이지 번호 p를 추출한 다음 폐지가 번호 p는 페이지 테이블의 인덱스로써 사용
페이지 테이블로부터 페이지 번호 p에 따른 프레임 번호 f를 추출
페이지 번호 p를 프레임 번호 f로 변경

다음 그림은 논리적 주소의 페이지들을 물리적 메모리 주소의 프레임에 올리는 그림이다.

page size = 16이라 가정,

가상 주소 -> 물리 주소

Paging Example

다음 그림은 4byte 크기의 페이지를 가진 16byte 크기를 가진 논리적인 주소를 이용하여 페이지 테이블에 매핑하여 물리적인 주소 공간에 올리는 그림입니다. n = 2^2 = 4, m = 2^4 = 16이 된다.

Paging -- Calculating internal fragmentation

Free Frame (= main memory page)

실행할 시스템에 프로세스가 도착한 경우

실행할 시스템에 프로세스가 도착한 경우에 메모리 할당을 위해 페이지로 표현된 크기가 검사 된다. 페이지들을 비어있는 프레임 리스트에 매핑시켜 메모리에 할당되며, 그 결과 비어있는 프레임은 15번만 있다.

Implementation of Page Table (페이지 테이블 구현)

페이지 테이블은 메인 메모리에 있어야 한다.

PTBR(Page-Table Base Register) : 페이지 테이블의 시작 위치를 가리키는 포인터
PTLR(Page-Table Length Register) : 페이지 테이블의 크기를 나타냄
페이지 테이블 자체는 메인 메모리에서 유지
프로세스 간의 문맥 교환할 때 빠르지만 메모리 접근 시간은 느리다.
페이지 테이블 이용하기 위해 메모리 접근이 2번 필요하다 (단점)
- 페이지 테이블 엔트리를 위해서 한번
- 실제 데이터(프레임 블록)를 위해서 한번

메모리 두 번 액세스 너무 느리기 때문에 TLBs 캐시 메모리를 두어 주소 번역(virtual P -> physical P)을 고속화한다.

* TLBs (Translation Look-aside Buffers)

Associative Memory

Paging Hardware With TLB

다음 그림은 TLB가 있는 페이징 하드웨어 구조이다.

TLB는 페이지 테이블의 캐시 역할 수행
하드웨어인 캐시 메모리를 사용

Effective Access Time (TLB를 사용한 효율적인 메모리 접근 시간)

Associative Lookup = ε nano-second (TLB에서 걸린 시간)

Assume memory cycle time is N nano-second (메모리 접근 시간)

( ε ≪ N )

TLB에 의해 번역된 비율 (Hit ratio = a), 0≤a≤1

Memory Protection (페이징을 통한 메모리 보호)

Valid (v) or Invalid (i) bit In A Page Table

Shared Pages (공유 페이지, 메인 메모리의 페이지 - 메모리 공유)

페이징의 장점은 멀티프로그래밍 환경에서 공통 코드를 공유할 수 있다.
표준 C 라이브러리 libc를 모든 프로세스가 각자의 libc 복사본을 프로세스 주소 공간에 가지고 있다고 가정. 이는 매우 비효율적이다. 그래서 만약 libc 라이브러리 같은 코드처럼 Reentrant Code라면 공유할 수 있다.

여러 프로세스가 동일한 실행코드를 공유, 각 데이터는 분리됨.

ex) 두 개의 문서를 편집한다고 해도, 메모장 프로그램을 2개 적재할 필요가 없다.

Page Table이 동일한 메모리 Frame을 가리켜 공유하고 있다.

Segmentation

하나의 프로그램을 논리적 단위(segmentation)로 나누어 할당.

cf) page는 물리적 단위

User's View of a Program

Logical VIew of Segmentation

전체 프로그램을 세그먼트 단위로 할당. 각 세그먼트는 물리적 size가 다 다르다.

Segmentation Architecture

Logical address는 <segment-number, offset>으로 구성.

여기서 offset은 세그먼트 안에서의 위치를 나타낸다. 세그먼트 별로 서로 다른 physical memory 위치에 올라가 있기 때문에 세그먼트 별로 주소 변환을 해야 하므로 Segment table을 두고 있다.

주소 변환에 사용되는 기존의 두 레지스터(base, limit)는 다음과 같이 사용된다.

* page와 달리 segment는 크기가 다르므로, 크기의 명시가 필요하다.

Segment-table base register(STBR) - physical memory에서의 세그먼트 테이블의 위치 시작 주소 값
Segment-table length register(STLR) - 프로그램이 사용하는 세그먼트의 수 (세그먼트 테이블 길이 저장)

*Segment table도 메인 메모리에 존재한다.

Segmentation Hardware

trap: 원래 할당된 세그먼트의 범위를 벗어나서 액세스 하는 경우 발생

단점 - Allocation

세그멘테이션 기법은 External fragmentation(외부 단편화)이 발생한다.

세그먼트의 길이가 모두 동일하지 않기 때문에 가변 분할 방식에서의 동일한 문제점들이 발생하는 것이다.

따라서 first bit / best fit과 같은 방법을 사용한다.

장점

세그먼트는 의미 단위로 쪼개기 때문에 공유와 보안에 있어서 페이징 기법보다 훨씬 효과적이다.

Protection - 각 세그먼트 별로 protection bit가 존재해서 의미 단위 별로 read/write와 같은 권한을 줄 수 있다.
Sharing - 마찬가지로 의미 단위인 세그먼트를 공유하는 것이 훨씬 효과적이다.

Example of Segmentation