[운영체제] Memory Management - 1

Memory Management (메모리 관리)

멀티프로그래밍 시스템에서는 주기억장치의 "사용자" 부분이 다수의 프로세스들을 수용하기 위해 더 여러 개로 나뉘게 되는 과정을 Memory Management(메모리 관리)라고 한다.

 

메모리는 사용가능한 처리기 시간을 소비하기에 충분한 수의 프로세스들이 준비 상태에 있도록 할당되어야 한다.

 

 

 

메모리 관리가 만족시켜야 하는 요구 조건은 다음과 같다.

• Relocation (재배치)
• Protection (보호)
• Sharing (공유)
• Logical organization (논리적 구성)
• Physical organization (물리적 구성)

 

 

 

Relocation (재배치)

- 프로그래머는 자신의 프로그램이 수행될 때 주기억장치에 다른 어떤 프로그램들이 존재할지를 미리 알 수 없다.

 

- 처리기의 사용 효율을 극대화하기 위해, 활성화된 프로세스들을 주기억장치로 swap-in 하거나 주기억 장치에서 swap-out 하기를 원한다. -> 다시 swap-in이 될 때, 이전과 동일한 위치로 적재돼야 한다고 주장하기 어려우므로, 메모리의 다른공간으로 프로세스를 relocate(재배치)할 필요가 있다.

 

- 프로그램 코드의 메모리 참조부분을 실제 물리주소로 변환할 수 있어야 한다.

  (물리 주소는 주기억 장치 내의 프로그램의 현재 위치이다.)

 

위 그림은 프로세스의 이미지를 묘사하고 있다.

프로세스의 이미지는 주기억장치의 연속된 영역을 차지하고 있다고 가정하자.

 

운영체제는 PCB의 위치와 execution stack(실행 스택)의 위치, 또한 프로그램 시작점(entry point)을 알아야 한다.

 

운영체제는 메모리를 관리하고 이 프로세스를 주기억장치로 적재하는 책임을 맡고 있기 때문에 이 주소들은 쉽게 얻어진다.

하지만 처리기는 프로그램 내부의 메모리 참조를 다뤄야만 한다.

 

 

 

 

Protection (보호)

 

프로세스는 다른 프로세스에 의한 원치 않는 간섭, 의도적 또는 우연히 발생할 수 있는 간섭으로부터 보호되어야 한다.

 

• 다른 프로세스에 속한 프로그램들은 허가 없이 임의의 프로세스의 메모리를 참조해서는 안된다.
• 재배치가 가능하게 되면 주기억장치 내의 프로그램 위치를 예측할 수 없기 때문에, 보호를 보장하기 위해 컴파일시간에 확실한 주소를 알아내는 것은 불가능하다.
• 한 프로세스가 생성하는 모든 메모리 참조가 오직 그 프로세스에게 할당된 메모리 공간만을 참조한다는 것을 실행 시간에 검사받아야 한다.
• 메모리 보호는 운영체제(소프트웨어)가 아니라 프로세서(하드웨어)에 의해서 이루어져야 함을 유념해야 한다.          (운영체제는 프로그램이 만들어 내는 모든 메모리 참조를 예측할 수 없다.)

 

Sharing (공유)

 

• 주기억장치의 같은 부분을 접근하려는 여러 개의 프로세스들을 융통성 있게 허용해야 한다.
• 각 프로세스들이 프로그램의 사본을 각각 가지는 것보다 프로그램 사본 하나를 모든 프로세스들이 참조하도록 하는 것이 바람직하다.

 

 

 

Logical Organization (논리적인 구성)

 

• 대부분의 프로그램들은 모듈이라는 단위로 구성되는데 일부 모듈은 수정이 가능하고 일부 모듈은 수정이 불가능하다.
• - 각 모듈의 작성과 컴파일은 독립적으로 이루어져 있으며, 서로 다른 모듈 간에 이루어지는 참조는 수행시간에 시스템에 의해 해결된다.
• - 비교적 적은 overhead로 각 모듈마다 서로 다른 보호 등급을 적용할 수 있다.
• - 프로세스들 간에 모듈을 공유할 수 있는 기법을 제공할 수 있다.

 

Physical Organization (물리적인 구성)

 

• 컴퓨터 메모리는 주기억장치와 보조기억장치라고 불리는 적어도 2개의 계층으로 구성된다.

주기억장치는 상대적으로 비싼 비용, 빠른 접근을 제공하고 휘발성이다.

 

보조기억장치는 가격이 저렴하고, 주기억장치보다 느리고 비휘발성이다.

 

-> 용량이 작은 주기억장치가 현재 사용중인 프로그램과 데이터를 저장

    용량이 큰 보조메모리는 프로그램과 데이터를 장기간 저장하는데 사용된다.

 

•  두 계층 구조에서 주기억장치와 보조기억장치 사이의 정보흐름을 어떻게 구성하느냐가 시스템의 중요한 관심 대상이 된다. (프로그래머에게 책임을 전가하지 않음)

1. 사용가능한 주기억장치의 용량이 프로그램과 데이터에 비해 부족할 수 있기 때문

2. 프로그램 작성 시에 프로그래머는 사용가능한 공간의 양과 위치를 알 수 없기 때문

 

 

 

Frame : 메인 메모리의 고정된 길이 블록

Page : 보조기억장치에 있는 고정 길이의 블록

Segment : 보조기억 장치에 있는 가변 길이의 데이터 블록

 

 

 

 

Memory Partitioning (메모리 분할)

 

메모리 관리의 주된 작업은 처리기에 의해 실행될 프로세스를 주기억장치로 가져오는 것이다.

 

최근 멀티프로그래밍 시스템에서는 가상 메모리라고 알려진 정교한 기법을 사용하는데, 이 가상 메모리는 Segmentation과 Paging 기법을 이용한다. 

 

하지만 이 가상 메모리 기법을 사용하지 않는 간단한 기법중 하나인 분할(Partitioning)에 대해 알아보자.

 

 

 

Fixed Partitioning (고정 분할)

대부분 메모리 관리 기법에서 운영체제는 주기억장치의 일부 고정된 부분을 차지하고, 나머지 부분은 다수의 프로세스들의 사용을 위한 것이라고 가정한다.

 

- 한 프로세스의 크기가 분할의 크기보다 작거나 같다면 사용 가능한 파티션 중 하나에 적재된다.

 

모든 파티션이 사용 중이고, 준비 또는 실행 상태의 프로세스가 없다면 운영체제는 한 파티션의 프로세스를 swap-out 시킨다.

 

 

균등 분할

- 프로그램이 파티션 보다 클 경우 오버레이를 사용하는 프로그램을 설계하여 프로그램의 필요한 부분만 주기억장치에 있도록 해야한다.

 

- 주기억 장치 이용이 매우 비효율적이다. 매우 작은 크기의 프로그램이라도 전체의 파티션을 차지한다.

 이처럼 파티션 내부 공간의 낭비가 발생하는 현상을 internal fragmentation(내부 단편화) 라고 한다.

 

비균등 분할을 사용하면 두 문제를 완전히 해결할 수는 없어도 영향을 줄이는 것은 가능하다.

 

 

 

 

 

 

Placement algorithm (배치 알고리즘)

 

균등 분할에서는 모든 파티션들이 같은 크기이므로 어떤 파티션을 사용하던지 차이가 없다.

 

준비 상태에 있지 않은 프로세스가 모든 파티션을 차지하고 있다면 새로운 프로세스를 위한 공간을 만들기 위하여 프로세스들 중 하나가 swap-out 되어야 한다. 어떤 것을 swap-out 하느냐는 스케줄링 정책에 의해 결정된다.

 

 

비균등 분할에서는 두가지 방법이 가능하다.

 

1) 각 프로세스의 용량에 맞는 가장 작은 파티션을 할당해주는 것

-> internal fragmentation을 최소화 시키는 파티션에 적재

 

2) 하나의 큐로 모든 프로세스를 처리하는 방법

-> 운영체제 소프트웨어의 기능을 최소로 하고 처리 오버헤드 역시 최소로 한다.

 

* 시스템 생성시간에 미리 정해진 파티션의 수에 의해 시스템 내에서 활성화된 프로세스들의 개수가 제한을 받는다.

* 시스템 생성시간에 파티션의 사이즈가 미리 정해지기 때문에 크기가 작은 작업들의 경우 파티션 공간을 효율적으로 활용 불가능해진다.

 

 

 

 

다음과 같이 정리할 수 있다.

장점

구현이 간단하다 : 운영체제에 오버헤드가 거의 없다.

 

단점

내부단편화로 인한 비효율적인 사용

최대 활성 프로세스의 수가 고정 됨.

 

 

 

 

 

Dynamic Partitioning (동적 분할)

 

 - 파티션의 크기와 개수는 가변적이다.

프로세스가 주기억장치로 적재될 때 정확히 요구된 크기의 메모리만 할당받는다.

 

- 모든 파티션 영역 이외의 메모리가 점차 사용할 수 없는 조각으로 변하는 현상을 external fragmentation(외부 단편화)라고 한다.

 

- 이 외부 단편화를 극복하는 방법으로는 Compaction(메모리 집약)이 있다. 

운영체제는 프로세스가 사용하는 파티션을 이동시켜 각 파티션이 연속적이 되도록 인접하게 만들고 메모리의 모든 빈 공간이 하나의 블록이 되도록 한다.

-> 시간이 많이 걸리며, 처리기 시간을 낭비하는 단점이 있음.

 

 

(a) : 운영체제만이 주기억장치에 적재되어 있다.

 

(b),(c),(d) : 처음 세 개의 프로세스들은 운영체제가 끝난 곳으로 부터 적재되기 시작해서 각 프로세스들에게 맞는 공간을 차지

 

(e) : 운영체제는 프로세스 2를 swap-out하여 메모리를 확보한다.

 

(f) : 이 영역은 새로운 프로세스 4가 적재되기 충분한 공간을 가진다.

 

(g) : 프로세스 2를 위한 충분한 빈 공간이 없기 때문에 프로세스 1을 swap-out

 

(h) : 2번 프로세스를 불러들인다.

 

 

 

 

Placement Algorithm (배치 알고리즘)

 

Compaction (메모리 집약)은 많은 시간이 소모되는 작업이기 때문에 운영체제는 프로세스에게 메모리를 할당하는 방법을 현명하게 결정해야 한다.

 

동적 분할에서는 다음과 같은 알고리즘이 있다.

• Best-fit (최적적합)
• First-fit (최초적합)
• Next-fit (순환적합)

 

 

Best-fit 

• 요청된 크기와 가장 근접한 크기의 메모리를 선택
• 가장 작은 블록을 찾아 배정하기 때문에 가장 작은 단편들을 만들게 되어 성능이 제일 안좋음
• Compaction이 더 자주 수행됨.

First-fit

• 메모리의 처음부터 검사해서 크기가 충분한 첫 번째 사용 가능한 메모리 블록을 선택한다.
• 가장 간단하며,가장 빠르고, 성능이 제일 좋다.
• 메모리의 앞부분에 여러 개의 작은 자유 메모리들을 만들어내는데, 최초적합 조사를 할 때마다 이들이 매번 검사되어야 한다.

Next-fit

• 가장 최근에 배치되었던 메모리의 위치에서부터 검사를 시작해 크기가 충분한 다음위치의 사용 가능한 메모리 블록을 선택
• 메모리의 마지막 부분에 있는 사용 가능한 블록으로부터의 배정이 자주 일어난다. -> 메모리 공간의 끝에 있는 가장 큰 크기의 메모리를 짧은 시간 내에 작은 크기로 조각 낸다. 그렇기 때문에 Compaction이 더 자주 일어난다.

 

 

Buddy System

 

고정 분할과 동적 분할의 결합

 

 

 

 

 

 

 

Relocation (재배치)

- 메모리 참조를 위한 상대적인 주소들은 적재된 프로세스의 시작주소를 기준으로 결정되는 주기억 장치 내의 절대 주소로 바뀌게 된다.

 

- 프로세스는 생존 기간 동안 다른 파티션에 적재될 수 있다. (Swapping에 의해)

 

- Compaction을 할 경우 주기억장치에 있는 프로세스들은 옮겨지게 된다. 그러므로 프로세스에 의해 참조된 명령어와 데이터의 위치는 고정되지 않는다.

 

 

 

Appendix: Loading & Linking

 

프로그램을 주기억장치로 적재하고 프로세스 이미지를 만드는 것

 

 

Loader는 적재 모듈을 주기억장치의 주소 x의 위치로 적재한다. 

프로그램을 적재할 때, 주소 지정 요구 조건을 만족해야하는데,  3가지 접근 방법이 있다.

1) Absolute Loading

2) Relocatable Loading

3) Dynamic Run-Time Loading

 

 

프로그래밍 시점 : 모든 실제 물리주소들을 프로그래머가 프로그램 자체에 직접 명시한다.

 

컴파일 또는 어셈블리 시점 : 프로그램에서는 기호 주소 참조를 사용하고 이 기호 주소들은 컴파일러나 어셈블러에 의해서 실제 물리주소로 변환된다.

 

적재 시점 : 컴파일러 또는 어셈블러는 상대 주소를 생성한다. 로더는 이것들을 프로그램이 적재될 때 절대 주소로 변환한다.

 

실행 시점 : 적재된 프로그램은 상대 주소 형태를 유지한다. 이 상대주소들은 처리기 하드웨어에 의해 동적으로 절대 주소로 변환된다.

 

 

Absolute Loading (절대 로딩)

주어지는 적재 모듈이 주기억장치 상에서 항상 같은 위치에 적재되도록 한다.

 

그러므로 Loader에 전달된 적재 모듈의 모든 참조들은 주기억장치의 특정 또는 절대 주소를 가리킨다.

 

예를 들어, 위 그림에서 x의 위치가 1024번지라면, 적재 모듈의 첫 번째 워드는 메모리 1024번지에 적재된다. 

-> 적재 전에 메모리 참조를 특정 주소와 연관시키는 방식은 적재 모듈이 주기억장치의 한 영역 이외에는 적재될 수 없다는 단점을 가짐.

 

 

 

 

 

Relocatable Loading (재배치 로딩)

적재 시점에 모듈이 적재될 위치를 결정하는 방법

-> 메모리 참조를 표현할 때 실제의 주기억장치 주소(절대주소)가 아닌 프로그램의 시작과 같은 지점을 기준으로 계산한 상대적인 위치로 표현

 

만일 어떤 모듈이 x라는 위치로부터 적재된다면 loader는 적재 작업을 하면서 각 메모리 참조에 x값을 더하기만 하면 된다.

 

 

 

Dynamic run-time Loading (동적 수행시간 로딩)

절대 주소를 계산하는 작업을 실행 중에 실제로 필요한 시점까지 뒤로 연기하는 것

-> 적재 모듈은 모든 메모리 참조가 상대주소로 표현된 채로 주기억장치로 적재된다. 명령어가 실제로 실행되기 전까지 절대 주소는 계산되지 않는다.

 

 

 

Linking (링킹)

 

여러 목적 모듈을 입력으로 하여 loader에게 넘겨주기 위한 적재 모듈을 생성하는 목적

 

 

 

Load time : 외부 참조는 적재 모듈이 주기억장치로 적재될 때 까지 해결되지 않는다. 적재 시에, 참조된 동적 링크 모듈은 적재 모듈에 추가되며 이 전체 패키지가 주기억장치 또는 가상 메모리로 적재된다.

 

Run time : 외부 참조는 처리기가 외부 호출을 실행하기 전까지 해결되지 않는다. 실행 시에, 프로세스는 중단되고 참조된 모듈을 호출 프로그램에 링크시킨다.

 

 

 

모듈 A는 모듈 B의 함수를 호출한다. 이 모듈들이 적재 모듈로 결합될 때 모듈 B를 참조하는 이 기호 주소는 전체 적재 모듈 안에서 모듈 B가 시작하는 위치를 참조하도록 변환된다.

 

 

 

 

Addresses

프로세스에 의해 참조된 위치는 고정되지 않는다. 

-> 프로세스 생성이나 실행에 사용되는 주소를 몇가지 유형으로 구분한다.

 

Logical Address (논리주소)

- 현재 데이터가 적재된 메모리와는 독립적인 메모리 위치에 대한 참조

- 이 주소는  실제 메모리 접근을 위해서 반드시 그전에 물리주소로 변환되어야 한다.

 

Relative Address (상대주소)

- 논리주소의 특별한 예

- 알려진 지점, 주로 처리기의 한 레지스터의 값으로 부터 상대적인 위치를 의미하는 주소

 

 

Physical Address (물리주소)

- 주기억장치 안에서의 실제 위치를 말한다.

 

 

 

 

 

 

Base register : 프로세스가 실행 상태가 되면 특정 레지스터에 프로그램이 적재되어 있는 주기억장치의 시작주소가 적재되는데 이 레지스터를 베이스 레지스터라고 부름

 

Bounds register : 프로그램의 마지막 위치를 가리키는 경계 레지스터

 

이 값들은 프로그램이 메모리로 처음 적재될 때나 프로세스 이미지가 swap-in 될 때 올바른 값으로 설정되어야 한다.

 

 

 

프로세스를 실행하는 동안에는 상대 주소가 이용되는데, 상대 주소에는 명령어 레지스터의 내용, 분기와  호출 명령에서 나타나는 주소, 적재나 저장 명령에서 나타나는 데이터 주소들이 포함된다.

 

이 상대주소는 처리기에 의해 2가지 처리과정을 거친다.

 

1. 베이스 레지스터 값이 이 상대주소에 더해져서 절대주소로 변환된다.
2. 절대 주소가 경계 레지스터 값과 비교한다.
3. 경계 범위 안에 있다면 실행되고 그렇지 않다면 운영체제로 인터럽트가 발생된다.