메모리

메모리란: 데이터를 저장하는 장치(기억장치)
메모리의 종류: 레지스터, 캐시, 메인 메모리, 보조기억장치(HDD)

• 레지스터와 캐시는 CPU(HW)에 의해 관리됩니다.
• 메인 메모리와 보조기억장치는 OS(SW)에 의해 관리됩니다.

Block: 보조기억장치와 메인 메모리 사이의 데이터 전송 단위를 블록이라 합니다. 1~4KB의 크기 가집니다.
Word: 레지스터와 메인 메모리 사이의 데이터 전송 단위를 Word라고 합니다. 16~64bits의 크기를 가집니다. 컴퓨터의 32비트,64비트를 결정하는 기준이 바로 Word입니다.

Address Binding

Address Binding이란 프로그램의 논리 주소를 실제 메모리의 물리 주소로 매핑(mapping)하는 작업을 말합니다.
Binding 시점에 따라 Compile time binding, Load time binding, Run time binding으로 나뉩니다.

• 소스코드가 메모리에 올라와 실행되기 까지의 과정을 살펴보면 다음과 같습니다.

Source code - compiler -> Object module - Linker -> Load module - Loader -> memory

Compiler: 소스코드를 오브젝트 모듈로 변환하는 역할을 담당합니다.
Linker: 오브젝트 모듈을 다른 라이브러리들과 묶어서 실행 가능한 형태의 Load module로 만드는 역할을 담당합니다.
Load module: 실행파일입니다. (.exe파일이 load module입니다.)
Loader: load module을 memory에 올려주는 역할을 담당합니다.

compile time binding

코드를 컴파일할 때 주소를 정해줍니다.
프로세스가 메모리에 적재될 위치를 컴파일러가 미리 알고 있어야 하며, 프로그램이 메모리에 적재되는 위치가 변하지 않아야 compile time binding이 가능합니다.
프로그램 전체가 메모리에 올라가 있어야 사용할 수 있는 방법입니다.

load time binding

컴파일 시점에 메모리의 어디에 프로그램이 적재될지 모르는 상황에 사용됩니다.
컴파일 시점에는 기준점으로부터 얼마나 떨어져 있는지를 상대주소로 저장해 둡니다.
메모리 적재 시점에 시작주소와 상대주소를 실제 코드상의 주소로 재설정하는 방법입니다.
프로그램 전체가 메모리에 올라가 있어야 사용할 수 있는 방법입니다.

run time binding

프로세스가 실제로 실행되는 시점에(ready상태에서 running상태로 바뀔 때)address를 결정합니다.
프로세스가 다른 메모리 위치로 이동하게 될 수도 있습니다.
run time binding을 위해서는 HW의 도움이 필요합니다. 논리적 주소를 물리적 주소로 매핑하는 하드웨어 장치로 MMU(Memory Management Unit)가 있습니다.
대부분의 OS가 주소할당에 run time binding을 사용하고 있습니다.

기타: Dynamic loading

하나의 프로그램 안에서 사용되는 부분만 메모리에 올려서 사용하는 방법입니다.
모든 루틴(function)을 교체 가능한 형태로 디스크에 저장해 두고 실행을 호출하기 전까지는 루틴을 메모리에 적재하지 않습니다.
루틴이 호출되는 시점에 address binding을 수행합니다.
dynamic loading을 활용하면 메모리 공간을 효율적으로 사용할 수 있습니다.

Memory Allocation(메모리 할당)

Continuous Memory Allocation(연속 할당)

프로세스(context)를 하나의 연속된 메모리 공간에 할당하는 정책을 말합니다. (프로세스를 쪼개지 않고 있는 그대로 메모리에 올리는 방법)
연속 할당은 메모리에 동시에 올라갈 수 있는 프로세스의 수, 각 프로세스에게 할당되는 메모리 공간의 크기, 메모리 분할 방법에 대해 고려해야 합니다.
또한 프로세스를 올릴 때 커널 영역을 침범하지 않도록 주의해야 합니다. 커널을 침범하지 않기 위해 boundary register와 boundary address를 이용합니다.

uni-programming

• 하나의 프로세스만 메모리 상에 존재합니다.
• 가장 간단한 메모리 관리 기법입니다.
• 프로세스의 크기가 메모리의 크기보다 더 큰 경우 프로세스를 실행할 수 없게 됩니다.
  이를 해결하는 방법은 Overlay structure로 메모리에 현재 사용해야 하는 영역만 적재하는 방법입니다.
  continuous memory allocation은 시스템적으로 프로세스를 자르지 않기 때문에 사용자가 이를 직접 잘라 메모리에 적재해야 합니다. (복잡+불편)
• 낭비가 발생합니다.

multi-programming

Fixed Partition Multi-programming(FPM)

• 메모리 공간을 고정된 크기로 미리 분할해 사용합니다.
• 하나의 프로세스는 하나의 partition에 적재됩니다.
• partition의 수 == multiporgramming degree
• partition table에 partition, start address, size, current process ID 등의 값이 변수로 기록됩니다.
• 커널의 보호와 프로세스끼리의 침범을 막기 위해 boundary register, boundary address를 사용합니다.
• 메모리 관리가 편리하지만 Internal fragmentation, External fragmentation이 발생합니다.

Variable Partition Multi-programming(VPM)

• partition이 유동적으로 변할 수 있습니다.
• 프로세스를 처리하는 과정에서 메모리 공간을 동적으로 분할해 할당합니다.
• 프로세스가 필요한 만큼만 메모리를 잘라 제공해 주겠다는 개념입니다.
• 내부 단편화가 발생하지 않습니다.
• 프로세스 배치 전략
  • first-fit(최초적합): 앞에서부터 메모리를 탐색하다가 해당 프로세스가 들어갈 수 있는 공간을 처음 만나면 해당 공간에 프로세스를 적재합니다.
    간단하고 오버헤드가 적지만 공간 효율이 떨어지는 방법입니다.
  • best-fit(최적적합): 프로세스가 들어갈 수 있는 partition중 가장 크기가 작은 곳을 선택합니다. 모든 partition은 검사해야 하기 때문에 탐색시간이 오래 걸립니다.
    크기가 큰 partition을 많이 유지할 수 있다는 장점이 있지만, 작은 크기의 사용하지 못하는 partition이 발생한다는 단점이 존재합니다.
  • worst-fit(최악적합): 프로세스가 들어갈 수 있는 partition중 가장 큰 곳을 선택합니다. 모든 partition은 검사해야 하기 때문에 탐색시간이 오래 걸립니다.
    작은 크기의 partition의 발생을 줄일 수 있다는 장점이 있지만, 큰 크기의 partition을 확보하기 힘들다는 단점이 존재합니다.

Non-continuous Memory Allocation(가상 메모리)

메모리에 올라가는 프로세스가 non-continuous하다(연속적이지 않다)는 의미로, 사용자 프로세스를 여러 개의 block으로 분할하고 실행 시 필요한 block만 메모리에 적재하는 방법입니다.
이때 block은 메모리에 연속적으로 배치되지 않으며, 메모리에 적재되지 않은 block들은 swap device에 대기하게 됩니다.

paging system

page: 프로세스를 동일한 크기로 분할했을 때 그 하나의 프로세스를 page라고 합니다.
page frame: 페이지와 같은 크기로 잘려진 메모리 상의 공간을 page frame이라고 합니다.
프로세스를 같은 크기의 블록(page)으로 분할하는 방법입니다.
페이지들은 최초에 swap device에 저장되어 있으며, 실제로 사용될 page들만 메모리에 적재됩니다.
이때 page들은 연속해서 메모리에 적재되지 않고 서로 떨어져서 적재됩니다.
페이지는 논리적인 분할(작업단위로 나눠논 것)이 아니라 일정 크기를 기준으로 나눠지게 됩니다.
segmentation보다 페이지 공유/보호 과정이 복잡하지만, 프로세스 관리가 단순하고 효율적입니다.
외부단편화는 발생하지 않지만 내부단편화는 발생할 수 있습니다.
윈도우 운영체제에서 사용되는 방식입니다.

address mapping

1. Direct Mapping(직접 사상)
   가상의 주소 v는 p(page number)와 d(displacement in block)를 통해 계산됩니다.
   블록의 정보들은 PMT(Page Map Table)에서 관리됩니다.
   page number, residence bit, secondary storage address, page frame number를 column으로 가집니다.
   Block Mapping과 유사한 방법입니다.
   secondary storage address: 페이지가 스왑 영역의 어디에 저장되어있는지를 나타내는 변수입니다.
   page frame number: 메모리의 몇 번 위치에 페이지가 적재되어 있는지를 나타냅니다.

p를 가지고 PMT에 가서 블록의 실제 위치를 찾습니다.
PMT에서 확인한 결과 p가 메모리에 적재되어 있지 않다면(residence bit == 0) swap device에서 해당 블록을 메모리에 가져와 적재시킵니다. 또한 해당 정보를 PMT에 기록합니다.
PMT에서 찾은 블록의 메모리 위치에 d를 더해 실제주소를 찾아냅니다

문제점: 메모리에 2번 접근해야 합니다.(PMT를 확인하기 위해 한 번, 실제 물리공간에 접근하기 위해 한 번) 또한 PMT를 위한 메모리 공간이 별도로 필요합니다.

2. Associative mapping
   메모리가 아닌 TLB(Translation Look-aside Buffer)에 PMT를 적재해 두는 방법입니다.
   TLB를 사용하면 메모리에 한번만 접근하면 되기 때문에 오버헤드가 적고 속도가 빠르다는 장점이 있습니다. 하지만 TLB는 비용이 비싸 큰 공간을 확보하기 어렵습니다.

p를 가지고 TLB에 가서 블록의 실제 위치를 찾습니다.
TLB에서 찾은 블록의 메모리 위치에 d를 더해 실제주소를 찾아냅니다

3. hybrid direct/associative mapping
   HW비용은 줄이고, Associative mapping의 장점을 활용하기 위해 등장한 방법입니다.
   작은 크기의 TLB를 사용하고 전체 PMT는 메모리(커널)에 저장합니다.
   PMT에 있는 페이지 중 최근에 사용된 page들은 TLB에 저장하는 형식으로 동작합니다.

p를 가지고 TLB에 가서 블록의 실제 위치를 찾습니다.
TLB에서 확인한 결과 p가 메모리에 적재되어 있지 않다면(residence bit == 0) swap device에서 해당 블록을 메모리에 가져와 적재시킵니다. 또한 해당 정보를 TLB에 기록합니다.
TLB 혹은 PMT에서 찾은 블록의 메모리 위치에 d를 더해 실제주소를 찾아냅니다

페이징 시스템이 메모리를 관리하는 방법

frame table

페이지 크기로 잘라둔 page frame을 관리하기 위한 테이블 입니다.
하나의 entry당 하나의 page frame정보를 가지고 있습니다.
page frame number, allocated, PID, link를 column변수로 가지며 AV라는 포인터가 존재합니다.

AV는 가장 처음으로 비어있는 page frame을 가르키고 있습니다.
link는 해당 page frame 다음으로 비어있는 page frame에 대한 정보를 나타냅니다.
즉, frame table은 linkedlist형태로 page frame의 빈공간을 관리합니다.

page sharing

여러 프로세스가 특정 page를 공유하는 걸 page sharing이라고 합니다.
non-continuous allocation이기 때문에 이러한 공유가 가능합니다.
코드를 공유하는 procedure page sharing, 데이터를 공유하는 data page sharing이 존재합니다.

page protection

여러 프로세스가 page를 공유할 때 보안과 관련된 문제가 발생할 수 있습니다. protection bit를 이용해 접근권한을 관리하는 걸 page protection이라고 합니다.

segmentation system

프로그램을 논리적인 block으로 분할하는 방법을 segmentation system이라고 합니다.
논리적으로 분할하기 때문에 block의 크기가 서로 다릅니다.
메모리를 미리 분할해 둘 수 없습니다.(VPM과 유사)
Segmentation sharing과 protection이 용이합니다.
크기가 다르기 때문에 address mapping 및 메모리 관리가 복잡합니다.
내부단편화는 발생하지 않지만 외부단편화는 발생할 수 있습니다.

address mapping

가상의 주소 v는 s(segment number)와 d(displacement in block)를 통해 계산됩니다.
블록의 정보들은 SMT(Segment Map Table)에서 관리됩니다.
segment number, residence bit, secondary storage address, segment address, segment legnth, protection bits를 column으로 가집니다.
PMT와 달리 segment length, protection bits가 추가되어 있습니다.

• 세그먼트마다 크기가 다르기 때문에 이를 저장하기 위한 segment length컬럼이 추가되었습니다.
• 세그먼트에 대해 프로세스가 가지는 권한을 표시하기 위해 protection bits칼럼이 추가되었습니다.

p를 가지고 SMT에 가서 블록의 실제 위치를 찾습니다.
SMT에서 확인한 결과 p가 메모리에 적재되어 있지 않다면(residence bit == 0) swap device에서 해당 블록을 메모리에 가져와 적재시킵니다. 또한 해당 정보를 PMT에 기록합니다.
d가 segment보다 큰 경우 segment overflow exception이 호출됩니다.
허가되지 않은 연산을 시도하는 경우 segment protection exception이 호출됩니다.
SMT에서 찾은 블록의 메모리 위치에 d를 더해 실제주소를 찾아냅니다

페이징 기법에서 PMT에 원하는 메모리 정보가 없는 경우를 paging fault, 세그먼트 기법에서 SMT에 원하는 메모리 정보가 없는 경우를 segment fault라고 합니다.

paging vs segmentation

• paging system: 같은 크기로 분할하기 때문에 단순하고 오버헤드가 적습니다. 공유 및 보호가 복잡하다는 단점이 존재합니다.
• segmentation system: 논리적인 단위로 분할하기 때문에 오버헤드가 큽니다. 공유 및 보호가 유리하다는 장점이 존재합니다.

hybrid paging/segmentation system

paging과 segmentation을 결합한 방법입니다.
프로그램을 일단 논리적인 단위인 segment로 분할하고, 각 segment를 다시 고정된 크기의 page로 분할하는 방법입니다.
실제 메모리에는 page단위로 적재됩니다.

address mapping

가상의 주소 v는 s(segment number)와 p(page number), d(displacement in block)를 통해 계산됩니다.
SMT와 PMT가 모두 사용됩니다.
세그먼트가 직접 메모리에 올라가지 않기 때문에 SMT에서 residence bit변수는 존재하지 않습니다.
메모리에 총 3번의 접근을 시도합니다(SMT에서 값을 찾기 위해 1번, PMT에서 값을 찾기 위해 1번, 실제 메모리에 접근하기 위해 1번)

fragmentation(단편화)

메모리의 낭비가 발생하는 현상입니다.

내부 단편화

partition의 크기가 process의 크기보다 커 발생하는 낭비입니다.

외부 단편화

process의 요구 메모리보다 더 큰 메모리 영역이 존재하지만, 연속된 공간이 아니기 때문에 프로세스를 메모리에 적재하지 못하는 현상입니다.

외부 단편화 해결방법

• Coalscing holes(공간 통합)

  • 인접한 빈 공간을 하나의 partition으로 통합하는 방법입니다. (FPM에서는 불가능한 방법입니다.)
  • 어떤 프로세스가 메모리를 해재하는 시점에 근처에 빈공간이 존재한다면 통합을 진행합니다.
  • 오버헤드가 적지만 공간이 확보되기까지 오랜 시간이 걸릴 수 있습니다.

• Storage Compaction(메모리 압축)

  • 모든 빈 공간을 하나의 공간으로 통합하는 방법입니다.
  • 프로세스를 재배치해야 하기 때문에 작업중인 프로세스가 멈췄다가 다시 실행되는 high overhead가 발생합니다. 메모리 압축은 자주 사용하는걸 지양해야 합니다.

Address Mapping

virtual address를 real address로 변환하는 과정을 non-continuous allocation의 address mapping이라고 합니다.
프로그램을 설계할 때 메모리가 분할되어 적재될 껄 고려한다면 아주 복잡해 집니다. 그렇기 때문에 연속적으로 연결되어 있는 것 같은 가상의 주소를 이용합니다.

• Virtual address(Relative address, Logical address): 연속된 메모리의 할당을 가정할 수 있게 만들어주는 주소입니다.

• Real address(Absolute address, Physical address): 프로세스가 적재된 실제 메모리의 주소를 의미합니다.

address mapping 기법

block mapping

사용자의 프로그램을 block단위로 분할해 관리합니다.
가상의 주소 v는 b(block number)와 d(displacement in block)를 통해 계산됩니다.
블록의 정보들은 BMT(Block Map Table)에서 관리됩니다.
block number, residence bit, real address를 column으로 가집니다.

b를 가지고 BMT에 가서 블록의 실제 위치를 찾습니다.
BMT에서 확인한 결과 b가 메모리에 적재되어 있지 않다면(residence bit == 0) swap device에서 해당 블록을 메모리에 가져와 적재시킵니다. 또한 해당 정보를 BMT에 기록합니다.
BMT에서 찾은 블록의 메모리 위치에 d를 더해 실제주소를 찾아냅니다.

References

• https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN