[운영체제] Chapter 8. Memory Management 1 ~ 4

조희연·2022년 1월 24일

운영체제

Study

목록 보기

15/15

강의 주소 : 이화여대 반효경 교수님 운영체제 강의 (2014년)

Chapter 8. Memory Management 1 ~ 4

8.1 Logical vs Physical Address

1. Logical address(virtual address)

프로세스마다 독립적으로 가지는 주소 공간
각 프로세스마다 0번지부터 시작
CPU가 보는 주소는 logical address

2. Physical address

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

주소 바인딩 : 주소를 결정하는 것
Symbolic Address(프로그래머 입장) -> Logical Adress - 이 시점은 언제? -> Physical Address

8.2 주소 바인딩

1. Compile time binding

컴파일 시점에 이미 물리적 주소가 결정됨 : 비효율적
시작 위치 변경시 재컴파일해야 함
컴파일러가 absolute code 생성(논리적 주소 = 물리적 주소)

2. Load time binding

프로그램이 실행되어 메모리에 올라갈 때 물리적 주소가 결정됨
컴파일러가 relocatable code 생성

3. Execution time binding(Run time binding)

프로그램이 실행되어 메모리에 올라갈 때 물리적 주소가 결정되고, 프로그램 수행 중 물리적 주소를 옮길 수 있음
CPU가 메모리 주소를 참조할 때마다 binding을 점검해야 함 : HW적 지원 필요(MMU)
현재 사용하는 컴퓨터 시스템에서 지원하는 방식

8.3 MMU(Memory-Management Unit)

logical address를 physical address로 변환해주는 HW device
relocation register과 limit register를 이용해 주소 변환이 이루어진다.
프로그램이 메모리에 올라가있는 시작 위치(14000) + logical address(346) = 14346
limit register는 프로그램의 최대 크기(3000)를 담고 있다. -> 더 큰 주소(3000 이상)를 요청할 경우(= 악의적 프로그램)를 막기 위해 trap이 걸리고 OS가 이를 처리
사용자 프로그램
- logical address만을 다룬다.
- 실제 physical address를 볼 수 없으며 알 필요가 없다.

8.4 몇가지 용어

1. Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
memory utilization의 향상
가끔씩 사용되는 많은 양의 코드의 경우 유용
OS의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

2. Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
프로세스의 크기가 메모리보다 클 때 유용
OS의 지원 없이 사용자에 의해 구현
작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현 = Manual Overlay

3. Swapping

프로세스를 일시적으로 메모리에서 backing store(하드디스크)로 쫓아내는 것
Backing store(swap area) : 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
Swap in & Swap out
- 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스 선정
- priority-based CPU scheduling algorithm
- Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함
- Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
- swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임

4. Dynamic Linking

Linking(프로그램 작성 후 link해 실행파일을 만듬)을 실행 시간까지 미루는 기법
Static linking
- 라이브러리가 프로그램의 실행 파일 코드에 포함됨
- 실행 파일의 크기가 커짐
- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비(예 : printf 함수의 라이브러리 코드)
Dynamic linking
- 라이브러리가 실행시 연결됨
- 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드룰 둠
- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
- OS의 도움 필요

8.5 Allocation of Physical Memory(물리적 메모리를 어떻게 관리할것인가?)

메모리는 일반적으로 두 영역으로 나누어 사용
- OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역 사용
- 사용자 프로세스 영역 : 높은 주소 영역 사용
사용자 프로세스 영역 할당 방법
- Contiguous allocation(연속 할당)
  - Fixed partition allocaiton
  - Variable partition allocation
- Noncontiguous allocation(불연속 할당) : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감
  - Paging
  - Segmentation
  - Paged Segmentation

Contigous Allocation 방법

Contiguous Allocation

고정 분할(Fixed partition) 방식

물리적 메모리를 몇 개의 영구적 분할로 나눔(분할 크기가 모두 동일한 방식과 서로 다른 방식 존재)
분할당 하나의 프로그램 적재
- 프로그램 A가 실행되면 크기가 같은 분할1에 할당
- 프로그램 B가 실행되면 분할3에 들어가게 됨 : 낭비되는 메모리 조각 발생(외부/내부 조각)
융통성이 없음
- 동시에 메모리에 load되는 프로그램 수가 고정됨
- 최대 수행 가능 프로그램 크기 제한

가변 분할(Variable partition) 방식

프로그램 크기를 고려해 할당
분할의 크기, 개수가 동적으로 변함
기술적 관리 기법 필요
외부 조각 발생

Contiguous Allocaiton의 Hole

Hole : 가용 메모리 공간
다양한 크기의 hole들이 메모리의 여러 곳에 흩어져 있음
프로세스가 도착하면 수용가능한 hole 할당
OS는 다음의 정보 유지
- 할당 공간, 가용 공간(hole)

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size가 n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
- First-fit : size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
- Best-fit : size가 n 이상인 가장 작은 hole을 찾아서 할당 -> hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함
- Worst-fit : 가장 큰 hole에 할당 -> 역시 모든 리스트를 탐색해야 함
-> First-fit이 best-fit과 worst-fit 보다 속도와 공간 이용률 측면에서 효과적으로 알려짐(실험적 결과)

Compaction

external fragmentation(외부 조각) 문제를 해결하는 한 방법
사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
매우 비용이 많이 드는 방법
최소한의 메모리 이동으로 compaction하는 방법 -> 매우 복잡
Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

Noncontiguous allocation 방법

8.6 Paging

1. Paging이란?

Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
일부는 backing storage에, 일부는 physical memory에 저장
Basic Method
- physical memory를 동일한 크기의 frame으로 나눔
- logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
- 모든 가용 frame들을 관리
- page table을 사용해 logical address를 physical memory로 변환
- page table은 각 프로세스마다 존재
- External fragmentaion 발생 X, Internal fragmentation 발생 가능(프로그램의 크기가 page의 배수가 아닐 수 있음)

2. 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 접근 1번
속도 향상을 위해 associative register, translation look-aside buffer(TLB)라 불리는 고속의 HW cache 사용 : 메인메모리와 CPU 사이에 존재
TLB는 page table의 일부의 데이터를 저장하고 있음
TLB를 통해 접근할 경우 메모리를 한번만 접근해도 됨 : TLB 전체를 검색해야 하기 때문에 시간이 오래 걸림 -> parallel(병렬적) search가 가능하도록 associative register 활용

3. Associative Register

page table 중 일부가 associative register에 보관되어 있음
만약 해당 page #가 associative register에 있는 경우 곧바로 frame #을 얻음
그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
TLB는 context switch때 flush(remove old entries)

4. Two-Level Page Table

현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
- 32 bit address 사용 시 : 2^32G(4GB)의 주소 공간
- page size가 4K(보통 4K)일때 1M개의 page table entry가 필요
- 각 page table entry가 4B일때 프로세스당 4M의 page table 필요
- 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
page table 자체를 page로 구성
시간과 공간에 있어 모두 손해지만 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 null(대응하는 안쪽 테이블이 만들어지지 않음)
예시)

4. Multilevel Paging and Performance

Address space가 더 커지면 다단계 페이지 테이블 필요
각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physicall address 변환에 더 많은 메모리 필요
TLB를 통해 메모리 접근 시간을 줄일 수 있음 -> 크게 오버헤드가 들지 않는다.

5. Memory Protection
페이지 테이블의 각 entry마다 아래의 bit를 둔다.

Protection bit
- page의 연산에 대한 접근 권한(read/write/read-only)
Valid
- 0번 페이지가 2번 물리적 주소에 올라가 있다.
- 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있다.
Invalid
- 프로세스가 그 주소 부분을 사용하지 않거나 backing store(swap area)에 내려가 있다.
- 해당 주소의 frame에 유효한 내용이 없음을 뜻한다.

6. Inverted Page Table

page table이 매우 큰 이유
- 모든 프로세스별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
- 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry 존재
Inverted page table
- 프로세스마다 page table이 존재하는 것이 아닌, 시스템 안에 딱 하나 존재
- page table의 entry가 물리적 주소의 페이지 프레임 개수만큼 존재 -> page table의 공간을 줄이고자 but 시간에 대한 오버헤드 증가
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address) : physical address를 보고 logical address로 변환
- 단점 : 테이블 전체를 탐색해야 함 -> associative register 사용(expensive)

7. Shared Page

-> 프로세스 p1, p2, p3를 같은 프로그램에서 돌린다면 code 부분은 같다. -> data 부분만 변경되기 때문에 공유할 수 있는 코드는 같은 프레임으로 매핑

Shared code
- Re-entrant Code(Pure code)
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림(text editors, compilers, window systems)
- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함 -> ed1 ~ ed3이 같은 위치에 있어야 한다.
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무 곳에 와도 무방

8.7 Segmentation

1. Segmentation이란?

프로그램은 의미 단위인 여러 segment로 구성 -> 크기가 모두 다름
작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
크게는 프로그램 전체를 하나의 세그먼트로 정의
일반적으로 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
Segment는 다음과 같은 logical unit들이다.
- main(), function, global variables, stack, symbol table, arrays

2. Segmentation Architecture(HW)

-> 논리주소를 [s : 세그먼트 번호] & [d : 세그먼트 오프셋]으로 나눈다.

Logical address는 segment-number, offset으로 구성
Segment table(each table entry has)
- base : starting physical address of the segment(세그먼트 시작 위치)
- limit : 세그먼트 길이
Segment table base register(STBR) : 물리적 메모리에서 segment table의 위치
- limit보다 d가 더 큰 값일 경우, trap이 걸림
Segment table length register(STLR) : 프로그램이 사용하는 segment의 수
- s(세그먼트 번호)가 STLR보다 큰 값일 경우, trap이 걸림