내용 출처
KOCW 반효경 교수님 <운영체제> 강의
책 <운영체제와 정보기술의 원리>
반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,
교수님의 저서 <운영체제와 정보기술의 원리>에서 추가할 만한 내용을 이와 같은 인용문 형식으로 추가함.
이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.
논리적 주소 vs 물리적 주소
- Logical Address = Virtual Address
- 프로세스마다 독립적으로 가지는 주소 공간
- 각 프로세스마다 0번지부터 시작
- CPU가 보는 주소는 logical address다.
- Physical Address
- 메모리에 실제 올라가는 위치
- 보통 물리적 메모리의 낮은 주소 영역에는 운영체제가 올라가고, 높은 주소 영역에는 사용자 프로세스들이 올라간다.
주소 바인딩 : 주소를 결정하는 것
Symbolic Address -> Logical Address -> Physical Address
프로그래머는 숫자가 아닌 symbol로 된 주소인 symbolic address를 사용한다. 이것이 컴파일 되면 숫자로 된 주소인 logical address가 된다. 그런데 프로세스가 실행되려면 해당 프로그램이 physical address에 올라가야 한다. 그래서 논리적 주소를 물리적 메모리 주소로 연결시켜주어야 하는데, 이러한 작업을 주소 바인딩이라고 한다.
그렇다면 논리적 주소는 언제 물리적 주소로 결정되는가?
주소 바인딩 (Address Binding)
-
Compile time binding
- 물리적 메모리 주소가 컴파일 시에 이미 결정된다.
- 시작 위치가 변경될 때마다 재컴파일된다.
- 프로그램이 절대주소로 적재된다는 의미에서 이를 절대코드(absolute code)를 생성하는 바인딩 방식이라고도 한다.
- 비효율적이므로 현재는 거의 사용되지 않는다.
-
Load time binding
- 프로그램이 시작되어 메모리에 올라갈 때 물리적 메모리 주소가 결정된다.
- Loader : 사용자 프로그램을 메모리에 적재시키는 프로그램
- 컴파일러가 재배치가능 코드(relocatable code)를 생성한 경우 가능하다.
- 위치가 고정된 것이 아니라, 실행시 물리적 메모리의 비어있는 위치 중 어디든 올라갈 수 있다.
-
Execution time binding = Run time binding
- load time binding과 같이 실행 시 물리적 주소가 결정되지만, 실행 도중에도 물리적 메모리 주소가 바뀔 수 있다.
- 따라서 CPU가 주소를 참조할 때마다 주소 매핑 테이블을 이용해 binding을 점검해야 한다.
- 하드웨어적인 지원이 필요하다.
(앞선 2가지 binding과 달리 그때 그때 주소 변환을 해주어야 하기 때문에 주소변환용 하드웨어가 필요한데, 이것이 MMU다.)
앞서 이야기한 것처럼 CPU가 보는 주소는 logical address다. 실행파일이 메모리에 올라갈 때 시작 주소는 바뀌지만, 그 안의 코드 상의 주소는 logical address로 남아있게 된다. (위 그림에서도 load time binding을 하면 500번지부터 시작하지만, 그 안의 Add 20, 30와 같은 코드 내의 주소는 바뀌지 않는다.) 그래서 CPU가 메모리 주소를 요청하면, 주소 변환을 해서 물리적 메모리 위치를 찾은 뒤 그 내용을 읽어서 CPU에 전달한다.
Memory Management Unit (MMU)
logical address를 physical address로 매핑해주는 하드웨어 장치
-
MMU scheme
- 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소 값에 대해 base register의 값을 더한다.
-
user program
- 논리적 주소만을 다룬다.
- 실제 물리적 주소를 볼 수 없으며 알 필요가 없다.
논리적 주소 : 0 ~ 3000번지
물리적 주소 : 14000 ~ 17000번지
주소 변환 방법 : 물리적 주소의 시작 위치에 요청한 논리적 주소를 더해준다.
(14000 + 346 = 14346)
[운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터]
-
base register = relocation register
프로그램의 시작 위치, 즉 접근할 수 있는 물리적 메모리 주소의 최소값을 지정한다. -
limit register
프로그램의 크기, 즉 현재 CPU에서 수행 중인 프로세스의 논리적 주소의 최대값을 저장하고 있다. CPU가 요청한 프로세스의 논리적 주소값이 이 값보다 크다면, 트랩을 발생시켜 해당 프로세스를 강제종료시킨다.
Dynamic Loading
- 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때마다 메모리에 load한다.
- memory utilization이 향상된다.
- 가끔씩 사용되는 많은 양의 코드에 대하여 유용하다.
(ex. 가끔 사용되는 오류 처리 루틴을 미리 다 올리지 않아도 된다.) - 운영체제의 지원 없이 프로그램 자체에서 구현 가능하며, 운영체제가 라이브러리를 통해 지원할 수도 있다.
현재 컴퓨터 시스템에서는 운영체제가 직접 필요한 부분만 메모리에 올려주는데, 이는 paging 기법이라고 한다. 반면 dynamic loading은 프로그래머가 명시하는 방식이다. 하지만 현재는 운영체제가 관리하는 방식도 dynamic loading이라고 부르기도 한다.
Overlays
- 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올린다.
- 프로세스의 크기가 메모리보다 클 때 유용하다.
- 운영체제의 지원없이 사용자에 의해 구현된다.
- 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현한 것이다. (= Manual Overlay)
동적로딩은 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 용도인 반면, 중첩은 단일 프로세스만을 메모리에 올려놓는 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 어쩔 수 없는 선택이었다.
Swapping
프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
-
Backing store = swap area
많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간 -
Swap In / Swap Out
- swap in : 디스크에서 메모리로 올리는 작업
- swap out : 메모리에서 디스크로 내리는 작업
- 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스를 선정한다.
- priority-based CPU scheduling algorithm
- priority는 CPU 수행 가능성에 따라 정해진다.
- priority가 낮은 프로세스를 swapped out시킨다.
- priority가 높은 프로세스를 메모리에 올려 놓는다.
- compile time binding 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 한다.
- run time binding에서는 빈 메모리 영역 아무 곳에나 올릴 수 있다.
- swap time은 대부분 transfer time (swap되는 양에 비례하는 시간)이다.
Dynamic Linking
Linking을 실행 시간까지 미루는 기법
연결(linking)이란 프로그래머가 작성한 소스 코드를 컴파일하여 생성된 목적 파일(object file)과, 이미 컴파일된 라이브러리 파일(library file)들을 묶어 하나의 실행파일을 생성하는 과정을 말한다.
동적연결(dynamic linking)은 컴파일을 통해 생성된 목적 파일과 라이브러리 파일 사이의 연결을 프로그램의 실행 시점까지 지연시키는 기법이다.
-
Static Linking
- 라이브러리가 프로그램의 실행 파일 코드에 포함된다.
- 실행 파일의 크기가 커진다.
- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리가 낭비된다. (ex. printf 함수의 라이브러리 코드)
-
Dynamic Linking
- static linking과 달리 라이브러리 코드가 실행 파일 코드에 포함되지 않는다.
- 라이브러리는 별도의 파일로 존재하며, 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾을 수 있는 stub이라는 작은 코드만을 실행 파일에 둔다.
- 해당 라이브러리가 이미 메모리에 존재하면 그 주소의 메모리 위치에서 직접 참조하며, 그렇지 않을 경우 디스크에서 동적 라이브러리 파일을 찾아 읽어온 후 수행하게 된다.
- 운영체제의 도움이 필요하다.
cf) shared library : dynamic linking을 해주는 라이브러리
(ex. 리눅스의 shared object, 윈도우의 DLL 파일)
물리 메모리의 할당
메모리는 일반적으로 두 영역으로 나뉘어 사용한다.
- OS 상주영역 : interrupt vector와 함께 낮은 주소 영역을 사용한다.
- 사용자 프로세스 영역 : 높은 주소 영역을 사용한다.
[사용자 프로세스 영역의 할당 방법]
-
Contiguous allocation (연속 할당)
- 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
- Fixed partition allocation
- Variable partition allocation
-
Noncontiguous allocation (불연속 할당)
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가도록 하는 것
- Paging
- Segmentation
- Paged Segmentation
Contiguous allocation (연속 할당)
- 고정 분할 방식 (Fixed partition allocation)
- 물리적 메모리를 몇 개의 영구적인 분할로 미리 나누어 관리한다.
- 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다.
- 분할당 하나의 프로그램을 적재한다.
- 융통성이 없다.
- 동시에 메모리에 load되는 프로그램의 수가 고정된다.
- 최대 수행 가능 프로그램 크기가 제한된다.
- 내부 조각 및 외부 조각이 발생할 수 있다.
- 가변 분할 방식 (Variable partition allocation)
- 매 시점 프로그램의 크기에 맞게 메모리를 분할해서 사용한다.
- 분할의 크기 및 개수가 동적으로 변한다.
- 기술적 관리 기법이 필요하다.
- 내부 조각은 발생하지 않지만, 외부 조각이 발생할 수 있다.
내부 조각(internal fragmentation)
분할의 크기보다 작은 프로그램이 적재되는 경우 남는 공간
외부 조각(external fragmentation)
프로그램에 할당되지는 않았지만 그 크기가 작아 프로그램을 올리지 못하는 메모리 영역
- Hole
- 가용 메모리 공간 (비어있는 메모리 공간)
- 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다.
- 프로세스가 도착하면 수용 가능한 hole을 할당한다.
- 운영체제는 어느 부분이 프로그램에 의해 사용되는 할당 공간이고, 어느 부분이 비어 있는 가용 공간(hole)인지의 정보를 유지한다.
동적 메모리 할당 문제 (Dynamic Storage-Allocation Problem)
가변 분할 방식에서 size n인 프로세스를 할당할 가장 적절한 hole을 찾는 문제
-
First-fit (최초적합)
- Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다.
-
Best-fit (최적적합)
- Size가 n 이상인 가장 작은 hole을 찾아서 할당한다.
- hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 한다.
- 다수의 매우 작은 hole들이 생성될 수 있다.
-
Worst-fit (최악적합)
- 가장 큰 hole에 프로그램을 할당한다.
- Best-fit과 마찬가지로 모든 리스트를 탐색해야 한다.
- 상대적으로 아주 큰 hole들이 생성된다.
Compaction = 한 곳으로 몰기
- 외부 조각 문제를 해결하는 한 가지 방법
- 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 방식
- 매우 비용이 많이 드는 방법
- 프로세스의 주소가 실행되는 중간에 동적으로 재배치가 가능한 경우에만 수행될 수 있으므로, run-time binding이 지원되는 경우에만 가능하다.
