이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.
이번 챕터에서는 Memory Management에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다
논리적 주소, 물리적 주소
메모리는 주소가 매겨진다(논리적 주소, 물리적 주소)
| 논리적 주소(Logical address, virtual address)
- 프로그램이 시작되면 독자적인 주소공간을 가지게 된다
- 각 프로세스마다 0번지부터 시작하게 된다
- CPU가 보는 주소는 논리적 주소이다
| 물리적 주소(Physical address)
- 메모리에 실제 올라가는 위치
- 운영체제 커널이 0번지, 상위 주소부터는 여러 프로그림이 섞여서 올라가게 된다
주소 바인딩
주소를 결정하는 것
- 프로그래머 입장에서는 숫자로 주소를 이용하는 것이 아니라 변수, 함수로 이용을 한다(symbolic address)
- 이것이 compile 되면 독자적인 숫자 주소로 변환이 된다(logical address)
- 이것이 실행이 되려면 물리적인 주소로 변해야한다
| 논리적 주소 -> 물리적 주소 시점 (물리적 메모리 주소가 정해지는 시점)
전체 프로그램의 논리 구조가 메모리 위에 올라간다고 가정(옛날 OS 방식)
- 주소 바인딩 방식은 크게 compile time binding, load time binding, run time binding 으로 나눌 수 있다
- 현재 사용하는 시스템은 run time binding을 지원한다
- CPU는 logical address를 바라보고 실행하기 때문에 물리적 메모리에 올라갈 때 시작 위치는 바뀌지만 코드상의 logical address 는 남아있게 된다(변하지 x)
1. compile time binding
- 컴파일 시점에 이미 물리적 주소가 정해짐(물리적 메모리 주소가 컴파일 시 알려짐)
- 논리적인 주소는 이미 물리적인 주소라는 것(이미 결정돼있는 주소인 논리적 주소를 이용해야 한다는 것)
- 시작 위치 변경 시 재컴파일 해야함
- 프로그램이 처음 들어갈 때 무조건 물리적 주소의 0번지에 들어가게 된다
1) 굉장히 비효율적이다
2) 컴퓨터 안에서 하나의 프로그램만 실행할 때는 위 방식을 사용했다
3) 절대 코드라고 부른다
2. load time binding
- Loader의 책임하에 물리적 메모리 주소 부여
- 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
- 프로그램이 시작돼서 메모리에 올라갈 때 물리적인 메모리 주소가 결정되는 것
(ex 실행시킬 때 메모리 500번지가 비어있는 것을 보았다 -> 500번지에 올린다) - 재배치 가능 코드
3. run time binding(Execution time binding)
- 실행 시 주소가 결정되는 것은 같으나, 실행 도중에 주소가 바뀔 수 있다는 것을 말한다
(프로그램이 실행되다 경우에 따라서는 메모리에서 쫓겨날수도 있고, 바인딩될 수도 있다) - CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
- 하드웨어 자원이 필요하다(ex base and limit registers, MMU)
| MMU(Memory-Management Unit)
- logical address를 physical address로 매핑해주는 Hardware device
- MMU scheme : 사용자 프로세스가 CPU에서 수행되며 생성해내는 주소값에 대해 base register(relocation register)의 값을 더한다
- User Program 은 logical address만 다루며 physical address는 볼 수 없고 알 필요도 없다
- 기본적인 MMU는 레지스터 두개를 가지고 주소 변환을 진행한다
| Dynamic Relocation
- MMU의 가장 간단한 주소 변환
- relocation register(base register), limit register 총 두개의 register을 이용해 주소 변환을 하게 된다
1) relocation register(base register)
- 물리적 시작 위차 + 논리적 시작 위치를 해주게 된다
- 접근할 수 있는 물리적 메모리 주소의 최솟값
ex) 0~346번까지의 주소를 CPU가 요청하고, 물리적 시작 위치는 14000번 부터 올라가게 되는 상황
2) limit register
- 프로그램의 크기를 담아놓는다(논리적 주소의 범위)
- 악의적으로 크기보다 큰 위치에 있는, 본인에게 할당되지 않은 logical address를 달라고 할 수 있다
- 요청한 위치가 해당 프로그램 영역의 바깥이 될 것이다(다른 프로그램의 메모리 위치)
- limit register보다 logical address가 크면 트랩(software interrupt)를 건다
-> 운영체제는 트랩이 왜 걸렸는지 확인한 후 이 프로그램이 악의적으로 본인의 메모리 주소가 아닌 곳을 보려 했다면 프로그램을 abort 시킴 - limit register 이내라면, base register의 값을 더해서 주소 변환을 한 후 물리적인 메모리 어딘가에 있는 내용을 읽어 CPU에 전달해주게 된다
Some Technologies
Dynamic Loading, Dynamic Linking, Overlays, Swapping
| Dynamic Loading
- 메모리를 해당 루틴이 길어질 때 마다 동적으로 메모리에 올리는 것
- 현대에는 페이징 시스템으로 필요할 때마다 동적으로 올리기도 한다
- memory utilization의 향상
- 가끔씩 사용되는 많은 양의 코드의 경우 유용하다(ex 오류 처리 루틴)
- 원래는 운영체제가 라이브러리 형태로 제공을 해줘 프로그래머가 직접 다이나믹 로딩을 하도록 하나, 지금은 운영체제가 직접 올리고 쫓아내는 것을 말하기도 한다
(<-> static loading : 프로그램 전체를 올려놓는 것 )
| Dynamic Linking
Linking을 실행 시간까지 미루는 기법
- Linking : 여러군데 컴파일 된 파일을 묶어놓은 것
Static Linking
- 라이브러리가 프로그램의 실행파일 코드에 포함됨
- 실행 파일의 크기가 커짐
- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
Dynamic Linking
- 라이브러리가 실행 시 연결(link) 됨
- 실행 파일에는 내 코드만 있고 라이브러리를 찾을 포인터만 내 파일 안에 넣고 라이브러리는 직접 넣는 것이 아니다
- 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
- 운영체제의 도움이 필요
- shared library(리눅스), dll (윈도우) 등의 shared file을 가지고 있다
| Overlays(Manual Overlay)
- 메모리에 프로세스 중 실제 필요한 정보만을 올림
- 프로세스의 크기가 메모리보다 클 때 유용
- 오버레이는 초창기 컴퓨터의 메모리가 작기 때문에 하나의 프로그램도 올리기 어려웠고, 그 때문에 큰 프로그램을 수작업으로 쪼개서 올리는 코딩을 한 것 (운영체제 도움 없이 사용자가 직접 구현
| Swapping
- 프로세스를 일시적으로 메모리에서 Backing store(하드디스크)로 쫓아내는 것
- 용량이 방대한 swapping system은 transfer time도 중요하다
- 요즘에는 프로그램이 다 쫓겨나는 것이 아니라 페이징되어 일부분만 쫓겨나는 경우도 있다
Backing Store(=Swap Area, 하드디스크)
- 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
Swap in / Swap out
- Swap in : 하드디스크로 쫓겨난 프로세스가 다시 메모리로 올라오는 것
- Swap out : 메모리에서 통째로 쫓겨나서 하드디스크로 가는 것
- 일반적으로 중기 스케쥴러(Swapper)에 의해 Swap out 시킬 프로세스를 선정한다
- compile time binding, load time binding 에서는 원래 메모리 위치로 swap in 해야함
- Runtime(Execution time) binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음 (swapping이 효율적으로 되기 위해서는 Runtime Binding이 지원돼야함)
- swap time은 대부분 transfer time(swap 되는 양에 비례하는 시간임)
priority-based CPU scheduling algorithm
- 우선순위가 낮은 프로세스를 swapped out 시킴
- 우선순위가 높은 프로세스를 메모리에 올려놓음
Allocation of Physical Memory
| 메모리 영역
메모리는 일반적으로 두 영역으로 나누어 사용
- OS 상주 영역 : interrupt vector 과 함께 낮은 주소영역 사용
- 사용자 프로세스 영역 : 높은 주소영역 사용
| 사용자 프로세스 영역의 할당 방법
Contiguous allocation (연속 할당)
- 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
- Fixed partition allocation, Variable partition allocation
- 프로그램이 통째로 올라가기 때문에 주소 변환이 간단하다
Noncontiguous allocation(불연속 할당)
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
- paging, Segmentation, Paged Segmentation
- 프로그램을 구성하는 주소 공간을 잘게 쪼개서 올린다
Contiguous Allocation
고정 분할 방식
- 물리적 메모리를 몇 개의 영구적 분할(partition)으로 나눔
- 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
- 분할당 하나의 프로그램 적재
- 융통성 없음(동시에 메모리에 load 되는 프로그램의 수가 고정, 최대 수행 가능 프로그램 크기 제한)
- 사용자 프로그램이 올라갈 구간을 미리 정해놓는다 (Internal fragmentation, external fragmentation 모두 발생해 메모리 조각 낭비됨)
가변 분할 방식
- 프로그램의 크기를 고려해서 할당
- 분할의 크기, 개수가 동적으로 변함
- 기술적 관리 기법 필요
- Externel fragmentation 발생
| External Fragmentation / Internal Fragmentation
- External fragmentation(외부 조각)
- 프로그램 크기보다 분할의 크기가 작은 경우
- 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
- Internal fragmentation(내부 조각)
- 프로그램 크기보다 분할의 크기가 큰 경우
- 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
- 특정 프로그램에 배정되었지만 사용되지 않는 공간 (남은 공간)
| Hole
- 가용 메모리 공간
- 작은 hole들이 여기저기 산발적으로 생기게 되고, 프로세스가 도착하면 수용 가능한 hole을 할당한다
- 운영체제는 물리적 메모리에서 사용되는 부분(할당 공간)과 비어있는 공간(가용 공간/hole)의 정보를 유지한다
- 프로그램이 끝나면 메모리를 홀에 편입시키고 프로그램이 실행되면 메모리를 홀에서 떼어서 줘야한다
| Dynamic Storage-Allocation Problem
- 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
- First fit 과 Best fit 이 Worst fit 보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려져있다
1) First fit
- 젤 먼저 발견되는 hole에 집어넣는 방식
2) Best fit
- hole을 다 살펴 본 다음에 이 프로그램에 가장 잘 맞는 hole에 넣는 것이다(프로그램 홀과 가장 크기가 근접한 경우)
- Size n 이상인 가장 작은 hole을 찾아서 할당
- Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색 해야 함(탐색 시간이 오래 걸린다)
- 많은 수의 아주 작은 hole 들이 생성된다
3) Worst fit
- 가장 큰 hole에 할당한다
- 모든 hole의 리스트를 탐색 해야 한다(탐색 시간이 오래 걸린다)
- 상대적으로 아주 큰 hole들이 생성되게 된다
| Compaction
- 메모리 공간을 다 밀어서 외부 조각으로 생긴 홀들을 하나로 뭉쳐서 사용 가능
- 실행 중인 프로그램의 메모리를 한 곳에 몰아넣어야 하는 것이기 때문에 매우 비용이 많이 든다(모든 프로그램의 바인딩을 확인)
- Runtime binding이 지원이 될 때만 compaciotn을 사용할 수 있다
- 그래서 최소한의 프로그램을 이동시켜 홀을 만드는 것이 좋다
실제의 방식은 불연속 할당을 이용하기 때문에 비교적 위의 문제들에서 자유롭다
Noncontiguous Allocatoin
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
- Paging, Segmentation, Paged Segmentation 등이 있다
Paging
- 프로그램을 구성하는 주소 공간을 같은 크기로 페이지에 잘라서 메모리에 올리거나 backing store에 내려놓거나 하는 방식
- 페이지 프레임 : 물리적인 공간도 페이지가 들어갈 수 있도록 잘라 놓는 것
- hole의 크기에 따른 문제는 사라지나, 주소 변환이 복잡해진다(MMU)
- 잘려진 각각의 페이지가 물리적인 주소 어디에 올라가있는지 확인해야한다(Address Binding)
Segmentation
- 프로그램의 주소 공간을 같은 크기로 자르는 것이 아니라 의미 있는 단위로 자르는 것을 말한다
- code segmentation, data segmentation, stack segmentation 이렇게 잘라 각각의 segmentation을 물리적 위치의 다른 곳에 올려놓을 수 있도록 한다
- 함수들을 다른 segment로 자르면 물리적인 다른 위치에 넣을 수 있는 것이다
- 의미 단위로 자르는 것이기 때문에 크기가 균일하지 않으며, dynamic allocation program의 문제가 발생하게 된다
나는야 누워있는 개발머신