기억 장치 관리 (Memory Management) Lecture #8 기억 장치 관리 (Memory Management) 신라대학교 컴퓨터공학과 운영체제

기억장치 관리(Memory Management) 주기억장치에 다수의 프로세스를 적재하기 위하여 운영체제와 하드웨어에 의해 수행되는 작업 단지 몇 개의 프로세스만을 주기억장치에 적재한다면 모든 프로세스가 I/O 동작으로 대기 상태가 될 수 있으며 이 때에 CPU는 유휴(idle) 상태가 된다 반대로 많은 프로세스를 주기억장치에 적재한다면 CPU의 유휴상태를 줄일 수 있다 메모리 부족을 스와핑(swapping)을 통해 해결 빈번한 swapping은 시스템 부하를 유발 가능한 많은 프로세스를 주기억장치에 적재할 수 있도록 주기억장치를 효과적으로 할당하여야 한다 신라대학교 컴퓨터공학과 운영체제

기억장치 관리 요구 사항(1) 재배치(Relocation) 프로그램이 재배치될 수 있어야 한다 프로그램은 실행될 때에 주기억장치에 적재되는 위치를 알 수 없다 프로세스는 swapping으로 인해 종종 주기억장치에서 재배치 된다 프로그램 코드에서 기억장소 참조(주소)는 프로그램이 실행되어 기억장소에 접근할 때에 실제 물리적인 기억장소 주소로 변환되어야 한다 신라대학교 컴퓨터공학과 운영체제

기억장치 관리 요구 사항(2) 보호(Protection) 프로세스가 권한이 없이 다른 프로세스가 사용하는 기억장소를 접근하지 못하도록 하여야 한다 프로그램이 재배치 될 수 있기 때문에 프로그램 번역 시간에 프로그램이 사용하는 주소를 검사하는 것은 불가능하다 프로그램 주소는 실행시간에 하드웨어에 의해 검사되어야 한다 신라대학교 컴퓨터공학과 운영체제

기억장치 관리 요구 사항(3) 공유(Sharing) 여러 개의 프로세서가 주기억장치의 공통의 영역을 별도의 보호 없이 접근할 수 있도록 허용되어야 한다 협력하는 프로세스들은 동일한 데이터를 공유할 필요가 있다 각 프로세스가 자신의 프로그램 코드 영역을 가지는 것보다는 하나의 프로그램 코드 영역을 접근하도록 하는 것이 보다 효율적이다 신라대학교 컴퓨터공학과 운영체제

기억장치 관리 요구 사항(4) 논리적인 구조(Logical Organization) 프로그램은 각기 다른 특성을 가진 여러 개의 모듈 (module) 로 구성된다 프로그램 모듈(instruction module)은 단지 실행 가능하고 수정되지 않는다 데이터 모듈(data module)은 읽기만 하거나 읽고 쓸 수 있다 각 모듈은 개별적으로 사용되거나 공용으로 사용될 수 있다 사용자 프로그램을 효율적으로 다루기 위해서는 운영체제와 하드웨어가 프로그램의 모듈 형태를 지원하여야 한다 모듈 단위 개발 이점 보호 및 공유 이점 신라대학교 컴퓨터공학과 운영체제

기억장치 관리 요구 사항(5) 물리적인 구조(Physical Organization) 기억장치가 계층적인 구조를 갖는다 주기억장치는 현재 사용중인 프로그램과 데이터를 저장한다 보조기억장치는 프로그램과 데이터를 오랫동안 보관하기 위해 저장한다 주기억장치와 보조기억장치 사이에 정보를 옮기는 것이 기억장치 관리 기능의 핵심 부분이다 이 기능을 프로그래머가 수행하도록 한다는 것은 상당히 비효율적 신라대학교 컴퓨터공학과 운영체제

간단한 기억장치 관리 기법 현재 모든 운영체제는 가상 기억장치(Virtual Memory) 기법을 채택하고 있다 실행중인 프로세스 이미지에 현재 접근하는 일부분만을 주기억장치에 두는 기법 간단한 기억장치 관리 기법 가상 기억장치 기법 이전의 기억장치 관리 기법 실행중인 프로세스 이미지를 전체 주기억장치에 두는 기법 fixed partitioning dynamic partitioning simple paging simple segmentation 신라대학교 컴퓨터공학과 운영체제

고정 분할 기법 (Fixed Partitioning)(1) 주기억장치를 겹치지 않는 영역(partitions) 들의 집합으로 분할하여 할당하고 관리하는 기법 Partitions는 동일한 크기를 가지거나 다른 크기를 가질 수 있다 신라대학교 컴퓨터공학과 운영체제

고정 분할 기법(2) Partition 크기보다 작거나 같은 프로세스를 해당 partition에 적재한다 모든 partition이 사용되고 있으면 운영체제는 스와핑(swapping)을 통해 필요한 기억공간을 구한다 Partition 크기보다 더 큰 프로그램은 중첩 (overlay) 기법을 이용하여 작성되어야 한다 프로그램 실행할 때에 단계별로 필요한 모듈만을 partition에 적재한다 다음 단계에서 다른 모듈이 필요하면 이전에 할당된 partition에 중첩하여 적재한다 신라대학교 컴퓨터공학과 운영체제

고정 분할 기법(3) 주기억장치 사용이 비효율적이다 Partition 크기보다 작은 프로그램이 하나의 partition 전체를 차지한다 예: 2MB 프로그램을 8MB partition에 할당하면 6MB 기억공간을 사용하지 못하게 된다 내부 단편화(internal fragmentation) 여러 가지의 다른 크기 partition을 사용하여 내부 단편화를 줄일 수 있으나 여전히 같은 문제를 내포하고 있다 동일 크기 partition 기법은 초기 IBM’s OS/MFT (Multiprogramming with a Fixed number of Tasks) 에서 사용 신라대학교 컴퓨터공학과 운영체제

고정 분할 기법에서의 배치 알고리즘 (Placement Algorithm with Partitions)(1) 동일 크기 partition(Equal-size partitions) 사용 가능한 partition이 있으면 프로세스를 그 partition에 배치한다 모든 partition의 크기가 동일하므로 어떤 partition 을 사용할 것인지를 문제가 되지 않는다 모든 partition이 대기 상태의 프로세스들에 의해 사용되고 있으면 새로운 프로세스를 위해 대기 상태의 프로세스를 swapping한다 신라대학교 컴퓨터공학과 운영체제

배치 알고리즘(2) 다른 크기 partition (Unequal-size partitions): use of multiple queues 각 프로세스를 크기를 만족하는 partition 중에서 제일 작은 partition에 배치한다 각 partition 크기 별로 대기열(queue)를 둔다 내부 단편화(internal fragmentation)를 최소화 문제점: 일정한 크기 영역에 해당하는 프로세스가 없는 경우에는 대기열이 비게 되며 해당 partition은 사용하지 못한다 신라대학교 컴퓨터공학과 운영체제

배치 알고리즘(3) 다른 크기 partition : use of a single queue 각 프로세스를 크기를 만족하는 partition 중에서 제일 작은 partition에 배치한다 내부 단편화를 허용하면서 다중 프로그래밍 레벨을 증가시킨다 신라대학교 컴퓨터공학과 운영체제

동적 분할 기법(Dynamic Partitioning) 각 프로세스에게 요구하는 만큼의 기억장소를 할당한다 주기억장치가 서로 다른 크기의 partition으로 분할된다 외부 단편화(external fragmentation) 문제 발생 주기억장치에 작은 크기의 단편들이 생성되어 큰 프로그램을 배치하지 못한다 기억장치 압축(memory compaction) 이 필요 단편화된 기억장소를 모아 하나의 연속적인 블록을 구성 IBM’s OS/MVT (Multiprogramming with a Variable number of Tasks)에서 사용 신라대학교 컴퓨터공학과 운영체제

동적 분할 기법 예제(1) 3개의 프로세스를 배치한 후에 64K의 기억 공간 단편이 발생 – 다른 프로세스가 사용하기에는 작은 공간 각 프로세스는 대기 상태가 되고, 운영체제는 프로세스 4를 배치하기 위해 프로세스 2를 swapping 한다 신라대학교 컴퓨터공학과 운영체제

동적 분할 기법 예제(2) 96K 크기의 단편이 발생 운영체제가 프로세스 2를 위해 프로세스 1을 swapping – 96K 크기의 단편이 발생 기억장치 압축(Compaction)으로 256K 크기의 블록을 생성하여야 한다 신라대학교 컴퓨터공학과 운영체제

동적 할당 기법의 배치 알고리즘(1) 프로세스에 할당할 사용 가능한 기억공간 블록을 결정하는 알고리즘 가능한 알고리즘: 목표: 기억공간 압축(compaction) 회수를 줄여야 한다(time consuming) 가능한 알고리즘: Best-fit: 크기를 만족하는 블록 중에 가장 작은 블록을 선택 First-fit: 크기를 만족하는 블록 중에 첫번째 블록을 선택 Next-fit: 이전의 배치된 블록이후로 크기를 만족하는 첫번째 블록을 선택 신라대학교 컴퓨터공학과 운영체제

신라대학교 컴퓨터공학과 운영체제

동적 할당 기법의 배치 알고리즘(2) Next-fit 알고리즘은 기억장치 끝부분에서 가장 큰 블록을 할당하는 경우가 발생한다 First-fit 알고리즘은 기억장치 시작부분 근처에 할당하는 경향이 있다 Next fit 알고리즘보다는 단편화가 적게 발생한다 Best-fit 알고리즘은 가장 작은 블록을 찾는다 더 작은 기억공간 단편을 만들게 된다 주기억장치 단편화가 빨리 발생한다 일반적으로 compaction이 종종 필요로 하게 된다 신라대학교 컴퓨터공학과 운영체제

동적 할당 기법의 재배치 알고리즘 (Replacement Algorithm) 주기억장치에 있는 모든 프로세스가 대기 상태가 되면 운영체제는 어떤 프로세스를 재배치할 것인지를 결정하여야 한다 하나의 프로세스를 swapping하고 새로운 프로세스를 재배치한다 가상 기억장치(Virtual Memory) 기법에서 검토 LRU(Least Recently Used) FIFO(First-In First-Out) 신라대학교 컴퓨터공학과 운영체제

Buddy System(1) 고정 분할 기법과 동적 분할 기법의 단점을 해결하기 위해 제안된 기법 Unix SVR4에서는 kernel memory allocation을 위해 수정된 알고리즘을 사용 2^{K} (L <= K <= U) 크기의 기억공간 블록이 사용 가능 2^{L} : smallest size of allocatable block 2^{U} : largest size of allocatable block (generally, the entire memory available) 신라대학교 컴퓨터공학과 운영체제

Buddy System(2) 배치 알고리즘 2^{U} 크기의 전체 메모리 블록에서 시작한다 S 크기의 메모리가 요구되면 : 만약 2^{U-1} < S <= 2^{U} 이면 2^{U} 크기의 전체 메모리 블록을 할당한다 아니면, 2^{U-1} 크기의 두 개의 buddies 로 나눈다 만약 2^{U-2} < S <= 2^{U-1} 이면 두 개의 buddy 중에 하나를 할당한다 그렇지 않으면, 두개의 buddy 중에 하나를 다시 작은 크기의 buddy로 나눈다 위의 과정을 S 보다 크거나 같은 블록이 생성될 때까지 반복한다 두 개의 buddy가 할당되어 있지 않으면 합쳐 더 큰 하나의 buddy를 생성한다 신라대학교 컴퓨터공학과 운영체제

Buddy System(3) 운영체제는 여러 개의 buddy 리스트를 유지한다 i 번째 리스트는 2^{i} 크기의 buddy 리스트 i 번째 리스트에서 이웃하는 한 쌍의 buddy가 발생하면 두 개의 buddy를 i 번째 리스트에서 삭제하고 하나의 buddy로 합쳐 (i+1) 번째 리스트에 추가한다 2^{i-1} < k <= 2^{i}인 크기 k의 기억공간 할당이 요구되면 : 먼저 i 번째 리스트를 검사한다 i 번째 리스트가 비어 있으면 (i+1) 번째 리스트를 검사한다 적절한 크기의 기억공간을 찾을 때까지 위의 과정을 반복한다 신라대학교 컴퓨터공학과 운영체제

Buddy System(4) : 예제 신라대학교 컴퓨터공학과 운영체제

Buddy Systems (5) 평균적으로 25%의 내부 단편화가 발생한다 프로그램이 기억장치 안에서 움직이지 않는다 각 메모리 블록은 최소한 50%는 사용한다 프로그램이 기억장치 안에서 움직이지 않는다 기억장치 관리를 단순화 한다 기억장치의 크기 M가 2의 승수인 경우에 효율적 M = 2^{U} “bytes” 각 블록의 크기가 2의 승수가 된다 예: M = 10 이면, 할당할 수 있는 블록의 최소 크기는 5 이다 신라대학교 컴퓨터공학과 운영체제

재배치(Relocation) 프로그램은 재배치 가능하여야 한다 Swapping과 메모리 압축(compaction) 등으로 프로세스를 실행되는 동안 주기억장치에서 옮겨 다닌다 프로세스의 물리적인 메모리 접근을 고정할 수 없다 프로세스의 물리적 주소는 실행 시간에 결정된다 재배치 문제는 메모리 접근을 위한 주소를 logical address 와 physical address 로 분리함으로 해결할 수 있다 신라대학교 컴퓨터공학과 운영체제

주소 종류(Address Types) 주기억장치의 기억공간은 주소를 가지며, 주소를 이용하여 주기억장치를 접근한다 물리적 주소(physical address or absolute address) 실제 주기억장치의 물리적인 위치 논리적 주소(logical address) 주기억장치의 물리적인 구조와는 독립적으로 메모리에 대한 참조 주소 컴파일러는 프로그램을 번역할 때에 메모리 참조를 논리적 주소로 생성한다 상대 주소(relative address) 논리적 주소의 하나의 예 프로그램 시작 위치로부터의 상대적인 주소 신라대학교 컴퓨터공학과 운영체제

상대 주소 주기억장치 Process A 500 1000 program 1500 data ADD ax, [500] 신라대학교 컴퓨터공학과 운영체제

주소 변환(Address Translation) 대부분의 경우 프로그램 모듈에서 사용되는 논리적 주소는 상대 주소를 사용한다 실행될 때에 프로그램 모듈은 상대 주소 형태의 메모리 참조를 가지고 주기억장치에 적재된다 프로그램의 명령어가 실행될 때에 실제 물리적 주소가 계산된다 적절한 성능을 위해 상대주소에서 절대주소로의 변환이 하드웨어에 의해 이루어져야 한다 신라대학교 컴퓨터공학과 운영체제

주소 변환 하드웨어 예(1) 하드웨어 구조: base register / bound register 프로세스가 실행 상태가 되면: base register (in CPU) 프로세스의 시작 물리적 주소 bound register  프로세스의 마지막 물리적 주소 프로세스가 실행하여 상대 주소를 통해 메모리에 접근하면: Base register 값에 상대 주소 값을 더하여 실제 물리적 주소를 생성한다 생성된 물리적 주소가 bound register 값을 넘어가는지를 검사한다 hardware protection 기능을 제공 프로세스는 프로세스 이미지 내의 메모리만 접근하게 된다 신라대학교 컴퓨터공학과 운영체제

주소 변환 하드웨어 예(2) 신라대학교 컴퓨터공학과 운영체제

페이징 기법(Simple Paging) 주기억장치를 동일한 크기의 고정된 블록으로 분할한다 프레임(Frames 또는 Page Frames) 상대적으로 블록 크기는 작다 각 프로세스는 프레임과 동일한 크기의 블록으로 나눈다 페이지(Pages) : 고정된 크기의 프로세스 블록 프로세스 페이지를 사용 가능한 주기억장치 프레임에 할당한다 하나의 프로세스는 주기억장치의 연속된 영역에 할당될 필요가 없다 프로세스 페이지를 연속되지 않은 프레임에 할당하고 프로세스에 대한 프레임 정보를 유지한다 신라대학교 컴퓨터공학과 운영체제

페이징 기법 예제(1) Now suppose that process B is swapped out 신라대학교 컴퓨터공학과 운영체제

페이징 기법 예제(2) 프로세스 A와 C가 대기 상태가 되면 기억장치 관리자는 5 페이지로 구성되어 있는 새로운 프로세스 D을 적재한다 프로세스 D는 연속된 메모리 영역에 적재되지 않는다 외부 단편화(external fragmentation)가 발생하지 않는다 각 프로세스의 마지막 페이지에서 내부 단편화가 발생한다 신라대학교 컴퓨터공학과 운영체제

페이지 테이블(Page Tables) 운영체제는 각 프로세스을 위하여 페이지 테이블(page table) 을 유지한다 페이지 테이블의 각 항목은 해당된 프로세스 페이지가 물리적으로 배치된 프레임 번호로 구성된다 페이지 번호를 인덱스로 사용하여 페이지 테이블을 접근하면 할당된 프레임 번호를 구할 수 있다 사용 가능한 프레임을 관리하기 위해자유 프레임 리스트를 유지한다 신라대학교 컴퓨터공학과 운영체제

페이징 기법의 논리적 주소(1) 프로그램에서 각 논리적 주소는 페이지 번호(page number) 와 페이지 안에서의 상대 위치(offset) 로 구성된다 논리적인 주소 = (page number, offset) 하나의 CPU register에 현재 실행중인 프로세스의 페이지 테이블의 시작 물리적 주소가 저장된다 논리적 주소(페이지 번호, 오프셋)가 나타나면 CPU는 페이지 테이블을 접근하여 논리적 주소를 물리적 주소 (프레임 번호, 오프셋)로 변환한다 신라대학교 컴퓨터공학과 운영체제

페이징 기법의 논리적 주소(2) 페이지 크기를 2의 승수로 두면 논리적 주소는 상대 주소가 된다 예제 : 16 비트 주소, 1KB의 페이지 크기를 가정 10 bits  offset, 6 bits  page number 16 비트 주소 : 16 비트의 논리적 주소가 프로세스의 시작 위치에서의 상대적인 위치를 나타내는 상대 주소가 된다(그림 참조) 페이지 번호 오프셋( offset) 15 10 9 신라대학교 컴퓨터공학과 운영체제

신라대학교 컴퓨터공학과 운영체제

페이징 기법의 논리적 주소(3) 페이지 크기로 2의 승수를 사용함으로써 프로그래머, 컴파일러, 링커 등은 페이지 구조를 인식할 필요가 없다 논리적 주소를 상대 주소로 사용하면 자연스럽게 페이지 번호와 오프셋으로 표현된다 실행 시간의 주소 변환은 하드웨어로 쉽게 구현된다 논리적 주소 (n,m)에 대해 페이지 테이블에서 프레임 번호 k을 가져와 오프셋 m가 결합하여 물리적 주소 (k,m)를 구한다 신라대학교 컴퓨터공학과 운영체제

페이징 기법의 주소 변환 신라대학교 컴퓨터공학과 운영체제

세그먼트 기법(Simple Segmentation)(1) 각 프로그램은 각기 다른 크기의 블록의 집합으로 나눈다 세그먼트(Segments): 프로그램을 구성하는 서로 다른 크기의 블록 프로세스를 주기억장치에 적재할 때에 세그먼트 단위로 메모리를 할당한다 서로 다른 세그먼트는 메모리 내에서 독립적으로 어디든지 배치할 수 있다 내부 단편화(internal fragmentation)가 없다 각 세그먼트는 명령어나 데이터가 채워져 있다 외부 단편화(external fragmentation)가 생긴다 작은 세그먼트를 사용함으로써 줄일 수 있다 신라대학교 컴퓨터공학과 운영체제

세그먼트 기법(Simple Segmentation)(2) 페이징 기법과 반대로 세그먼트는 프로그래머가 볼 수 있다 프로그램의 논리적인 구성을 구현할 수 있다 프로그램은 여러 개의 모듈로 구성된다: 예) 프로그램 모듈, 데이터 모듈 등 프로그램을 구성하는 각각의 모듈을 세그먼트로 구현함으로써 모듈별로 처리가 가능하다 운영체제는 각 프로세스 별로 세그먼트 테이블 (segment table)을 유지한다 세그먼트 테이블의 항목은 다음과 같이 구성된다 세그먼트의 시작 물리적 주소 세그먼트의 길이 (for protection) 신라대학교 컴퓨터공학과 운영체제

세그먼트 기법의 논리적 주소 세그먼트 기법에서의 논리적 주소 세그먼트 번호 (segment number)와 세그먼트 내에서의 상대 위치(offset)으로 구성 논리적 주소 = (세그먼트 번호, 오프셋) 프로세스가 실행 상태가 되면 CPU register는 프로세스의 세그먼트 테이블의 시작 주소를 저장한다 물리적 주소로의 변환 논리적 주소 (segment number, offset) = (n,m)가 주어지면 CPU는 세그먼트 테이블에서 세그먼트 시작 주소 k과 세그먼트 길이 l을 찾아온다 물리적 주소는 오프셋 m에 세그먼트 시작 주소 k값을 더하여 구한다 하드웨어는 주소가 사용가능한지를 검사하기 위해 오프셋 m을 세그먼트 길이 l과 비교한다 신라대학교 컴퓨터공학과 운영체제

세그먼트 기법의 주소 변환 신라대학교 컴퓨터공학과 운영체제

페이징 기법과 세그먼트 기법의 비교 세그먼트 기법 페이징 기법 메모리 보호 주소 변환을 위해 더 복잡한 하드웨어를 요구 심각한 외부 단편화 문제를 야기 페이징 기법 단지 작은 내부 단편화가 발생한다 프로그래머에게 보이지 않지만 (transparent) 세그먼트 기법은 프로그래머에게 보인다(visible) 메모리 보호 세그먼트 기법은 프로그램을 논리적으로 세그먼트로 구성할 수 있으며 각각 다른 종류의 보호 모드를 적용할 수 있다 세그먼트 별로 다른 보호 모드를 사용하기 위해서는 세그먼트 테이블에 보호 모드 비트(protection bit)을 추가하여야 한다 신라대학교 컴퓨터공학과 운영체제