KOCW - 운영체제(이화여대 반효경 교수)
8장 CPU 메모리 관리

메모리 관리

Logical vs Physical Address

Logical address(=virtual address)

• 프로세스마다 독립적으로 가지는 주소 공간

• 각 프로세스마다 0번지부터 시작

• CPU가 보는 주소는 logical address

Physical address

• 메모리에 실제 올라가는 위치

주소 바인딩(Address Binding)

Compoile time binding

• 컴파일 시 물리적 메모리 주소가 결정이 됨
• 컴파일러는 절대 코드(absolute code) 생성

Load time binding

• 논리적인 메모리 주소가 물리적인 메모리 주소로 바뀌는 시점이 프로그램 실행 시점에 결정됨
• 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능

Run time binding

• 프로그램이 시작된 이후에도 프로세스의 메모리 상 위치가 바뀔 수 있음
• Run time binding은 그때그때 주소가 바뀌기 때문에 주소변환이 필수.
• 주소변환은 하드웨어적인 지원이 필요하다

CPU의 메모리 접근

CPU는 논리적인 주소를 바라보기 때문에 메모리에 접근할때마다 주소 전환(logical -> physical)이 필요하다.

Memory-Management Unit(MMU)

logical address를 physical address로 매핑해주는 Hardware device

• 위 그림은 가상 메모리가 물리적인 메모리에 올라가 있는 것을 나타낸다. 가령 process p1의 346번 데이터를 읽으려고 할 때, 물리 메모리에서의 주소는 relocation register에 기록된 물리 메모리에서의 시작 위치 14000과 가상 메모리의 주소인 346을 더한 14346이 346번 데이터의 물리 메모리 주소가 되겠다.

• 사용자 프로그램의 경우 logical address만을 다룬다.

Hardware Support for Address Translation

• Limit register : 논리적 주소의 범위

• Relocation register : 접근할 수 있는 물리적 메모리 주소의 최소값

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질때 메모리에 load 하는 것

• memory utilization

• 프로그램 자체에서 구현 가능(특별한 지원 없이)

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 사용자에 의해 구현(운영체제 지원 X)

Swapping

• 프로세스를 메모리에서 쫓아내는 것

swap in/swap out

• swapped out의 경우 파일을 읽고 쓰는 것과 다르게 메모리에 있는 프로세스의 주소 공간을 통째로 도려내고 다시 넣는 작업이기 때문에 I/O 량이 많다

Dynamic Linking

• Linking을 실행 시간까지 미루는 기법

• 라이브러리를 연결하는 작업

Dynamic Linking(shared library) .dll

• 라이브러리가 실행파일에 존재하지 않고 별도의 파일로 존재하다가 이 프로그램 실행 중 라이브러리 호출 시점에 라이브러리의 위치 정보를 불러내는 stub() 이라는 코드 실행

Static Linking(static library)

• 라이브러리가 실행파일에 포함된 경우

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용

  	* OS 상주 영역

  • 사용자 프로세스 영역

Contiguous allocation (연속 할당)

• 프로그램의 시작 위치에서 논리적인 주소만큼 더해주면 됨

고정 분할 방식(fixed partition)

• 메모리를 여러 개의 파티션으로 미리 나누어 놓음. 각각의 파티션에는 프로그램이 들어갈 수 있음.

• 내부 조각 : 어떤 프로그램에 메모리가 할당되었을 때 남는 부분(즉 낭비되고 있는 부분을 말함, 분할의 크기가 커서 생기는 문제)

• 외부 조각 : 어떤 프로그램에 메모리가 할당되었을 때 메모리가 작아서 프로그램이 못들어가는 부분(분할의 크기가 작아서 생기는 문제)

가변 분할 방식

• 메모리를 미리 나눠놓지 않고 계속해서 파티션을 바꾸는 방식

Hole

• 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다. 이 공간에 대한 정보들(할당 공간, 가용 공간(hole))을 운영체제는 계속해서 가지고 있다.

• hole은 기본적으로 가용 메모리 공간

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

1. First-fit : Size가 n이상인 hole들 중 가장 먼저 찾아지는 hole에 할당

2. Best-fit : Size가 n이상인 hole들중 가장 작은 hole을 찾아서 할당

   • 모든 홀을 탐색해야 하는 overhead가 있음

3. Worst-fit : 가장 큰 hole에 할당

   • 2와 마찬가지로 모든 홀을 탐색

compaction

• 외부조각을 한데 모아서 프로그램이 들어갈 수 있는 hole을 만드는 방법

• 조각을 합치기 위해서 프로그램들을 이동시키기 때문에 비용이 많이 소요됨

• 최소한의 메모리 이동으로 compaction -> 매우 복잡한 문제

• Run time binding만 가능함(프로그램의 주소가 실행중에 재배치 되어야 하기 때문에)

Noncontiguous allocation (불연속 할당)

• 논리적인 주소 공간이 잘려서 물리적 메모리에 산발적으로 할당되는 경우

Paging

• Process의 virtual memeory를 동일한 사이즈의 page 단위로 나눔

• Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨

• 외부조각 발생 X, 내부 조각은 발생 가능

• 마지막 자투리 공간이 내부 조각이 될 수 있음

• page table에 있는 인덱스를 통해 물리 메모리 주소를 파악하고 접근

• 메모리 주소는 바이트 단위로 매겨짐

  	* 1바이트일 경우 2가지 정보 구분

  • 2바이트일 경우 4가지 정보 구분

Implementation of Page Table

• Page table은 main memory에 상주

• Page-table base register(PTBR)가 page table을 가리킴

• Page-table length register (PTLR)가 테이블 크기를 보관

• 모든 메모리 접근 연산에는 2번의 memory access가 필요(page table 1번, data/instruction 접근 한번) -> 시간이 더 오래 걸림

• translation look-aside buffer(TLB) : 주소 변환을 빠르게 하기 위한 캐시 메모리

• page table의 일부 정보를 TLB에 저장해서 현재 접근하는 데이터의 주소가 TLB에 있을 경우 바로 메모리에 접근, 속도 향상을 꾀한다.

• TLB는 문맥 교환시에 flush됨(다른 프로세스의 TLB정보를 채우기 위해 기존 프로세스의 TLB 정보 전부 삭제) -> 오버헤드 발생

page table과 TLB의 자료구조

• page table의 경우 시작 객체의 위치만 알면 현재 접근하려는 객체의 위치를 바로 계산할 수 있다(배열의 자료구조를 가짐)

• TLB의 경우 인덱스로 접근하는 것이 아닌 논리적인 위치(페이지 번호)와 물리적인 위치(프레임 번호) 두 곳에 대한 데이터 모두가 필요하다.

• associative register : TLB를 순차적으로 순회할 경우 너무 오래걸리기 때문에 parrallel search가 가능한 associaative register의 도움을 받아서 TLB를 탐색

Effective Access Time

EAT = 2 + Associative register lookup time - Hit ratio(associative register에서 찾아지는 비율)

Two-level Page Table

• 페이지의 개수는 프로세스마다 100만개가 넘어감, 각 엔트리마다 4byte가 넘어감.

• 32 bit 주소 사용시 4G의 주소 공간

  	* page size가 4K일 경우 1M개의 page table entry 필요

  • 각 page entry가 4B시 프로세스당 4M의 page table 필요

-> 기존 page Table은 공간 낭비가 심함

Two-Level Page Table

• outer-page table 사용하면?

  	* 사용이 안되는 공간 : null 처리 -> 안쪽 페이지 테이블(하나에 4KB)

Address-Translation Scheme

• p1 : outer page table에서 몇 번째 entry인지 알려주는 번호(10비트)

• p2 : 안쪽 page table에서 몇 번째 entry인지 알려주는 번호(1024개를 구분하기 위한 번호, 10비트)

• d : physical 메모리에서의 위치

• outer page table의 시작 위치는 Page-table base register가 가지고 있다.

valid / Invalid Bit in a Page Table

Page table의 각 entry마다 아래의 bit를 둔다

• invalid -> 이 페이지가 메모리에 안올라가 있는 경우 or 프로그램이 올라가있는 페이지지만, 프로그램이 페이지를 사용 안하고 있는 경우(사용은 하는데 메모리에 올라와 있지 않은 경우)

• protection bit : page에 대한 접근 권한

  	* page가 어떤 권한을 가지고 있는지 표시하는 bit (read/write/read-only)

Inverted Page Table(역방향 페이지 테이블)

기존의 page table 주소 변환은 logical memory address -> physical memory address

-> 위 방법은 각 page마다 page table이 존재해야 하기 때문에 메모리 낭비가 심함.

Inverted Page Table의 경우는 physical memory의 주소로부터 logical memory의 주소를 얻을 수 있음

• 하지만 이는 page table을 처음부터 쭉 순회해야되기 때문에 매우 비효율적임. 따라서 한 번에 여러 곳을 순회할 수 있는 하드웨어적인 장치가(parrellel search가 가능한 assistor 필요함)

Shared Pages

• 동일한 프로그램을 세 번 실행시킨 경우(프로세스 세개) -> 동일한 코드가 여러 개 메모리에 올라가면 낭비 -> shared page를 통해서 해결

Shared code

• read-only로 하여 같은 프로그램 프로세스 간 하나의 코드만 메모리에 올린다.

• Re-entrant Code(=Pure code)

• 동일한 logical address에 있어야 한다 -> 프로세스 별로 다른 물리 메모리에 올라갈 수는 있지만 한 실행 파일 안에 있는 logical address는 같아야 한다.

• 각 프로세스들은 독자적으로 메모리에 올림

Segmentation

프로그램을 구성하는 의미 단위

• 크게 code, data, stack가 하나의 세그먼트로 정의됨

• Logical address : <segment-number(세그먼트 번호), offset(세그먼트 내에서 얼마나 떨어져 있는가)>

Segmentation Hardware

• 각각의 entry들이 세그먼트의 시작 위치만 달고 있는게 아니라 세그먼트의 길이정보도 담고 있음(segment table의 limit)

• segment-table base register(STBR) : 물리적 메모리에서의 segment table의 위치

• segment-table length register(STLR) : 프로그램이 사용하는 segment의 수(segment 개수를 넘어서는 접근 시도를 막기 위한 정보 기억 레지스터)

• 문제점(연속할당 방식의 문제점과 유사함) : 프로세스마다 크기가 다르기 때문에 빈 hole의 크기가 프로세스보다 작으면 비어있음에도 불가능하고 프로세스가 메모리에 올라가지 못함 -> segment 또한 길이가 제각각이기 때문에 못올라갈 수도 있음

예시

• 위 그림같은 경우 0번 segment는 길이가 1000이고 물리적 메모리 1400번부터 놓여져있다고 이해하면 됨. 그 밑에 있는 세그먼트들 또한 이러한 방식으로 물리적 주소를 알아내면 된다.

Segmentation Architecture

세그먼트마다 크기가 다르기 때문에 빈 공간(외부 조각)을 어떻게 활용할 것인지에 대한 대책이 필요함

• first fit / best fit

• segment = 의미 단위 -> 보안에 유리(code나 stack 같이 의미로 나뉘어져 있기 때문에 read/read only 등 읽기 쓰기 권한을 의미에 맞게 설정할 수 있음)

• segment table과 paging table은 각각 존재한다는 점에서 공통점을 갖지만, paging의 경우에는 메모리 낭비가 훨씬 심하다.

Paged Segmentation

• segmentation과의 차이점 : segment가 여러 개의 페이지로 구성 -> 세그먼트가 페이지 크기의 배수가 됨 -> segment를 페이지 단위로 쪼개서 물리적 메모리에 올라가게 함

• 동일 크기의 page 단위로 물리적 메모리에 올라가기 때문에 기존 segmentation에서 발생하던 Allocation(외부 조각 발생)과 같은 문제가 발생하지 않음

• 공유나 보안 또한 segment이기 때문에 문제가 발생하지 않음