contents
Memory
•
메모리는 주소를 통해서 접근하는 매체
◦
Logical address(= virtual address)
◦
Physical address
•
프로그램이 실행되면 독자적인 주소 공간이 형성 → Logical address
Logical address(= virtual address)
•
프로세스마다 독립적으로 가지는 주소 공간
•
각 프로세스마다 0번지부터 시작
•
CPU가 보는 주소는 logical address
Physical address
•
메모리에 실제 올라가는 위치
•
실제로 프로그램이 실행되기 위해선 Physical address에 올라가야 함
•
물리적인 메모리는 하나로 0번지부터 통으로 관리
◦
물리적인 메모리 안에서, 아래에는 운영체제 커널, 상위 주소에는 여러 프로그램들이 섞여서 올라감
프로세스들은 0번지부터 시작하는 독자적인 주소 공간이 있지만 실행이 되려면 물리적인 메모리 어딘가로 올라가야 하고 주소가 바뀌게 된다.(주소 변환, 주소 바인딩)주소 바인딩
: 물리적인 메모리 주소를 결정하는 것
•
주소는 언제 결정되는가? (Logical → Physical)
Symbolic Address → Logical Address → WHEN → Physical address
◦
Symbolic Address : 사용자가 메모리의 주소값을 찾을 때, 숫자로 접근하는 것이 아닌 변수명으로 접근하게 된다.
◦
컴파일 이전에는 Symbolic address 상태
◦
프로그래머가 메모리를 사용하지만 프로그래머 입장에서는 숫자가 아닌 Symbol로 된 address를 사용하게 되고 이게 Complie이 되면 숫자로 된 주소로 바뀌게 된다.
◦
시간이 되면 물리적인 메모리에 올라가야 하니깐 주소 변환이 이루어져야 한다.
주소 바인딩을 하는 타이밍 3가지
1.
complie time binding
컴파일 시에 주소 변환
•
Physical address에 올릴 때에는 이미 결정되어 있는 주소로(Logical address) 올리게 된다.
•
다른 비어있는 메모리 공간이 있더라도 0번지부터 올라가게 됨
•
컴파일 타임에 미리 결정되기 때문에 대단히 비효율적인 방법
•
시작 위치가 변경되면 컴파일 다시해야 함(절대 코드이기 때문)
•
컴파일러는 절대 코드(absolute code) 생성
◦
절대 코드 : complie time binding은 Logical address가 그대로 물리적 메모리에 올라오기 때문에 절대 코드라고 불린다.
•
지금의 컴퓨터 시스템에서는 사용하지 않는 방법
◦
컴퓨터 내부에서 한 개의 시스템만 돌아가는 때에는 다른 프로그램이 같이 올라갈 일이 없어서 컴파일할 때 물리적인 메모리 주소를 결정해서 올리는 방법이 사용됨
2.
load time binding
프로그램이 시작되어서 메모리에 올라갈 때 물리적인 메모리 주소가 결정됨(Loader 책임하에 부여)
•
컴파일 타임에는 Logical address만 정해진 상태
•
실행시키게 되면 물리적인 메모리의 빈 공간(ex. 500)부터 0번지 메모리를 올린다.
•
컴파일러는 재배치 가능 코드(relocatable code)를 생성한다.
3.
execution time binding(= run time binding)
시작된 이후에도 물리적인 메모리 주소 변환
•
load time binding과 동일하게 실행시키면 물리적인 메모리 공간에 올라감
•
일단 물리적 메모리 공간에 바인딩(ex.300번지)이 되었다가 실행되는 도중에 해당 내용이 다른 주소 루트로 이동(ex.700번지)할 수 있다.
→ 경우에 따라서 메모리에서 쫓겨날 수 있고 다시 올릴 때는 비어 있는 메모리에 바인딩을 해서 올리게 된다.
•
CPU가 주소를 참조할 때마다 binding를 점검해야 한다.(address mapping table)
◦
내용이 메모리에 어디에 올라가 있는지 주소 변환을 그때그때 해야한다.
◦
하드웨어적인 지원 필요(MMU - 그때 그때 주소 변환을 해줌)
현대의 컴퓨터는 run time binding를 지원한다. CPU가 바라보는 주소는 ‘Logical address’이다.•
올라갈 때 시작 위치는 바뀌지만 컴파일된 주소 자체까지 바꿀 수 없다. → 아니면 바꾸기 위해서 재컴파일
•
위치는 바뀌지만 Logical한 주소 변경은 힘듦
•
명령문을 실행하려고 할 때 20, 30번지 메모리 내용을 CPU로 읽어들이려고 하는데 그 주소가 Logical Address
◦
CPU가 메모리 몇 번지에 있는 내용을 달라고 하면 그 때 주소 변환을 해서 물리적인 메모리 위치를 찾아서 그 내용을 읽어서 CPU한테 전달
MMU(Memory-Management Unit)
logical address를 physical address로 매핑해주는 Hardware device(주소 변환을 해주는 하드웨어 자원)
•
그때그때마다 내용들이 어디에 올라가 있는지 주소 변환을 새로해주는 방법이 없어서 하드웨어적인 지원이 필요
•
기본적인 MMU에서는 limit Register, base register를 가지고서 주소 변환을 합니다.
◦
Relocation(base) register는 프로그램의 시작 위치를 가지고 있음
◦
Limit Register는 프로그램의 크기를 가지고 있음
→ 이 프로그램이 만약 악의적인 프로그램이라서 본인의 크기가 3000임에도 4000번지에 있는 내용을 달라고 할 수 있다. 이런 경우 크기 범위를 벗어나는 곳에서 physical memory 위치가 잡히게 된다. 있지도 않은 주소 범위를 가지고 달라고 하면 다른 프로그램이 존재하는 메모리를 달라고 한 것
CPU가 메모리 346번지에 있는 값을 달라고 함 | logical address |
주소 변환을 해야 함 | MMU에서 진행 |
시작 위치(relocation register) + 논리적 주소 ⇒ 물리적 메모리 주소 | Physical memory |
•
MMU Scheme
사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(= relocation register)의 값을 더한다.
•
User Program
◦
logical address만을 다룬다.
◦
실제 physical address를 볼 수 없으며 알 필요가 없다. → 요청이 됐을 때 MMU가 변환을 해서 얻게 되는 개념
•
악의적인 메모리 접근 문제를 해결하기 위한 방법
CPU에서 logical address를 요구한다 |
해당 논리 주소가 프로그램 크기보다 큰 논리 주소(limit register의 값)를 요구한 건 아닌지 확인하기 |
만약 크다면, trap이 걸림. 운영체제에게 CPU 재제권이 넘어간다. trap이 걸린 이유를 확인함(악의적인 메모리 공간 넘어감) |
크기 이내의 값이라면, relocation register의 값을 더해서 주소변환을 한 다음에 physical memory 어딘가에 있는 내용을 읽어다가 CPU에게 전달 |
Some Terminologies
1.
Dynamic Loading(Loading = 메모리로 올리는 것)
프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
→ 프로그램 필요 일부를 올리는 방법
•
memory utilization의 향상
•
가끔씩 사용되는 많은 양의 코드의 경우 유용 → 계속 올리면 비효율적이기 때문에
◦
오류 처리 루틴
•
필요하면 올라가고 필요없으면 메모리에서 내려가는 것은 오리지널 Dynamic Loading의 개념은 아니다. → 운영체제가 해주는 Paging System에 의한 것(운영체제가 직접 관리)
•
운영체제의 특별한 지원없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능) → 프로그래머가 Dynamic Loading를 해보도록 하는 개념
◦
Dynamic Loading를 프로그래머가 쉽게 하도록 운영체제가 라이브러리 형태로 Dynamic Loading를 지원해준다.
◦
Paging 기법과 Dynamic Loading의 개념은 다르다.
◦
프로그래머가 명시하지 않고 운영체제가 알아서 올려두고 쫓아내는 것도 Dynamic Loading에 섞어 쓰기도 한다.
•
라이브러리를 사용하기 때문에 사용자가 어떻게 올리고 내리는지는 굳이 알 필요가 없다.
2.
Dynamic Linking
Linking : 여러군데 존재하던 컴파일될 파일들을 묶어서 하나의 실행 파일을 만드는 과정
Static linking
•
라이브러리가 내 프로그램 실행 파일 코드에 포함
•
내 코드든, 라이브러리 코드든 내 프로그램 주소 공간 안에서 실행이 됨
•
실행 파일의 크기가 커짐
•
동일한 라이브러리를 각 프로세스가 메모리에 올리기 때문에 메모리 낭비가 심함.
Dynamic linking
•
실행 파일에는 라이브러리가 별도의 파일로 존재하고, 그 라이브러리 위치를 찾을 수 있는 작은 코드(stub, 포인터 역할)를 두고 라이브러리 자체는 포함하지 않는 것
•
프로그램이 실행되다가 라이브러리 호출하는 곳에 이르면 라이브러리가 어디 있는지 찾는다.
◦
필요하면 메모리에 올리고(디스크에서 가져옴), 이미 메모리에 올라와 있다면 해당 메모리 주소에 가서 이 라이브러리를 실행을 함
◦
이미 메모리에 올라와 있는 라이브러리는 메모리에 계속 올려두고 공유해서 사용이 가능해지게 됨
•
Dynamic linking를 해주는 라이브러리 = DLL = shared library(object)
•
운영체제의 도움 필요
3.
Overlays
메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림(Dynamic Loading과 동일)
→ 초창기 컴퓨터 시스템의 메모리가 작았음, 프로그램 하나를 메모리에 올리는 것도 어려움
→ 큰 프로그램을 쪼개서 메모리에 올리는 방식으로 사용
•
운영체제의 지원없이 사용자에 의해 구현
•
초창기 시스템에서는 프로그래머가 수작업으로 코딩을 했다. (manual overlay) → 프로그래밍 매우 복잡
4.
Swapping
프로세스를 일시적으로 메모리에서 backing store(메모리에서 쫓아내진 것들을 저장하는 공간)로 쫓아내는 것 ⇒ 하드 디스크
•
backing store(= swap area)
◦
하드 디스크 : 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
•
Swap In / Out
일반적으로 중기 스케줄러(Swapper)에 의해 swap out 시킬 프로세스 선정
◦
중기 스케줄러가 일부 프로그램을 골라서 통째로 메모리에서 디스크로 쫓아냄.
◦
어떤 프로그램을 쫓아내는가?
▪
priority가 낮은 프로세스
◦
Swapping 시스템이 지원이 되기 위해서는?
▪
Swapping이 효율적으로 동작하기 위해서는 Run time binding이 지원되어야 할 것
priority-based CPU scheduling algorithm
•
priority가 낮은 프로세스를 swapped out시킴
•
priority가 높은 프로세스를 메모리에 올려 놓음
Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함
Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)
◦
디스크는 디스크 헤더가 움직이는 시간이 대부분을 차지
Allocation of Physical Memory
물리적인 메모리를 어떻게 관리할 것인가?
•
낮은 주소 부분에 운영 체제 커널이 항상 상주
•
높은 주소 영역에는 사용자 프로그램들이 올라감
◦
사용자 프로그램들이 올라가는 영역을 관리하는 방법
1.
Contiguous allocation(연속 할당)
프로그램이 메모리에 올라갈 때 통째로 올라가게 됨
•
각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
2.
Noncontiguous allocation(불연속 할당)
프로그램을 구성하는 주소 공간을 잘게 쪼개는 게 가능
•
하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감
•
현대의 시스템은 불연속 할당을 채택
•
여러 가지 기법
◦
Paging
▪
프로그램의 주소 공간을 같은 크기의 page로 잘라서 page 단위로 메모리 여기저기에 올라감
◦
Segmentation
◦
Paged Segmentation
Contiguous allocation(연속 할당)
1.
고정 분할(Fixed parition) 방식
프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나누어 놓는 것
•
낭비되는 조각이 발생하게 된다. → 외부 조각, 내부 조각
외부 조각(external fragmentation)
내부 조각(internal fragmentation)
•
융통성이 없음
◦
동시에 메모리에 load되는 프로그램의 수가 고정됨
◦
최대 수행 가능 프로그램 크기 제한
2.
가변 분할(Variable partition) 방식
프로그램이 들어갈 사용자 메모리 영역을 미리 나눠놓지 않는 것
•
프로그램이 실행될 때마다 차곡차곡 메모리에 올리는 방식
◦
프로그램의 크기를 고려해서 할당
◦
분할의 크기, 개수가 동적으로 변함
•
미리 메모리 공간을 나눠두지 않았기 때문에 내부 조각(internal fragmentation)이 생기지 않는다.
•
프로그램이 실행하다가 종료하면 홀 발생
홀(hole)
•
가용 메모리 공간 중 어디다가 새로운 프로그램을 집어 넣어야 하는가?
Dynamic Storage(Memory)-Allocation Problem
: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole를 찾는 문제
Dynamic Storage-Allocation Problem
1.
First-fit
Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
•
hole 중에서 가장 처음 발견되는 hole에다가 할당하는 것
2.
Best-fit
n 이상인 hole들 중에서 가장 작은 hole을 찾아서 할당(프로그램 크기와 가장 근접)
•
hole를 다 살펴본 다음에 프로그램 크기하고 가장 잘 맞는 hole에다가 프로그램을 올려두는 것
•
hole들을 탐색하는 시간 부담이 존재
3.
Worst-fit
가장 큰 hole에다가 프로그램을 할당
•
가장 큰 hole를 찾기 위해서 전체 hole들을 탐색해야 함
•
어리석인 방법 → 큰 홀에는 지금 실행하는 프로그램보다 더 큰 프로그램이 들어갈 수도 있다. 또한 지금 실행하는 프로그램에 적합한 hole이 있을텐데 큰 홀에다가 넣는 것은 적절하지 않다.
First-fit과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려져있다.
•
first-fit은 hole를 찾는 overhead가 적어서 좋다.
•
best-fit은 제일 적당한 hole를 찾아서 넣기 때문에 미래를 위해서 좋은 방식이다.
Compaction
external fragmentation 문제를 해결하는 한 가지 방법
•
사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳(중간중간 작은 hole)으로 몰아 큰 block를 만드는 것
•
hole이 작아서 사용을 못하는 문제를 해결 가능하다.
•
매우 비용이 많이 드는 방법
example) 디스크 조각 모음 → 파일의 데이터를 이동시킴
◦
compaction같은 경우는 ‘바인딩을 다 점검해야하고 하는 문제 발생', 프로그램 하나가 아니고 전체 프로그램의 바인딩에 관련된 문제가 된다.
•
최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제)
•
Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.
◦
Run-time binding이 지원돼야지만 compaction이 가능하다.
현대의 프로그램은 연속 할당보다는 불연속 할당이다.
Paging
프로그램을 구성하는 주소 공간을 같은 크기의 페이지 단위로 자른 것이다. 페이지 단위로 물리적 메모리에 올려두거나 패킹 스테이지에 내려두는 것
•
물리적 메모리도 페이지 하나가 들어갈 수 있는 단위로 쪼개져 있음(페이지 프레임)
◦
페이지 프레임 하나 하나에는 페이지들이 올라갈 수 있음
•
hole들의 크기가 균일하지 않아서 생기는 문제, 홀들을 한 곳으로 모으는 솔루션이 필요가 없게 된다.
◦
어차피 물리적 메모리에서 비어있는 공간이 곧 페이지 프레임이 비어있는 것이기 때문에 프로그램의 어떤 페이지든지, 비어있는 위치 어디든 들어갈 수 있다.
•
불연속 할당을 하면 주소 변환이 복잡해진다.
◦
MMU에서 주소 변환을 할 때, 단지 시작 주소만 더해서 주소 변환을 하는 것이 아니고 짤려진 각각의 페이지가 물리적인 메모리 어디에 올라가있는지를 확인해야 한다.
◦
즉, 주소 변환을 페이지 별로 해야해서 주소 바인딩이 더 복잡해지는 게 특징
Paging
•
Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
•
virtual memory의 내용이 page 단위로 불연속적으로 저장됨
•
일부는 backing storage에, 일부는 physical memory에 저장
•
방법
◦
physical memory를 동일한 크기의 frame으로 나눔 → page frame
◦
logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
◦
모든 가용 frame들을 관리
◦
page table을 사용하여 logical address를 physical address로 변환
▪
단순히 Register를 사용하는 주소 변환으론 안되기 때문에 page table 사용
◦
external fragmentation 발생 안 함 → 같은 크기로 잘라놨기 때문에
◦
internal fragmentation 발생 가능
▪
페이지 단위로 virtual memory를 썰다보니깐 마지막에 가서는 페이지 하나보다 남는 자투리가 작을 수 있다.
▪
빈 공간이 약간은 생길 수 있기 때문에 internal fragmentation이 발생할 수 있다.
▪
페이지 크기를 잘게 썰게 되면 내부 조각의 영향력이 줄어든다.
Segmentation
어떤 의미있는 단위로 자르는 것
프로그램을 구성하고 있는 주소 공간이라는 것이 코드, 데이터, 스택이라는 의미있는 공간으로 구성이 되어 있다.
•
코드 Segmentation
◦
각각의 함수들(의미 단위)을 segment로 만들기도 가능
•
데이터 Segmentation
•
스택 Segmentation
각각의 Segment를 필요시에 물리적 메모리 다른 위치에 올려둘 수 있도록 함
•
이 때도 Segment 단위로 주소 변환을 해줘야 함
•
Segment는 의미 단위로 자른 것이기 때문에 크기가 균일하진 않다.
•
프로그램을 통째로 메모리에 올릴 때 Dynamic Storage-Allocation Problem이 Segmentation에서 발생하게 된다.
통째로 메모리에 올리진 않는다. 잘라서 산발적으로 올릴 수 있다.