Virtual Memory and Adress Translation

1. Computer Data Storages
2. Memory Virtualization
3. Adress Translation

 

---

1.  Computer Data Storages

우리가 예전에 살펴보았던 Memory는 Object Code, Program, Os data, Stack등을 포함한 Virtual한 Memory 였습니다. 실제로는 Physical Memory는 Virtual Memory처럼 간단하지 않습니다. 그렇다면 실제 Data를 저장하는 저장장치들은 무엇일까요?

---

RAM

RAM은 Random Acess Memory의 약자입니다.

 

Key Features of RAM

1. RAM은 Chip으로 Package 되어 있습니다
2. 램의 저장 단위는 보통 Cell로 Cell당 One bit가 저장됩니다
3. 여러개의 램 칩이 Memory를 구성합니다 (DIMM구조)

Static RAM (SRAM)

1. 각 셀은 4개 혹은 6개의 Transistor circuit으로 One bit를 저장합니다.
2. 전원이 켜진 동안에는 안정적으로 값을 저장하고 있습니다.
3. EMI(전기 노이즈), Radiation(방사선) 등에 민감하지 않습니다.
4. DRAM보다 비싸고 빠릅니다.

Dynamic RAM (DRAM)

1. 각 셀은 한개의 캐퍼시터로 One bit를 저장합니다. (한개의 트랜지스터가 사용됩니다.)
2. 전원이 켜진 동안에도 10-100 ms동안 계속해서 Refresh해주어야 합니다.
3. EMI(전기 노이즈), Radiation(방사선) 등에 민감합니다.
4. SRAM보다 싸고 느립니다.

SRAM과 DRAM은 전부 Volatile Memory 에 해당합니다. (전기가 날아가면 전부 지워짐)

---

Non - Volatile Memories

Kinds of Non-Volatile Memories

1. Read Only Memory (ROM) : 생산될때 프로그램 되어서 나옵니다.
2. Programmable ROM (PROM) : 한번만 프로그램 할 수 있습니다.
3. Erasable PROM (EPROM) : UV나 X-Ray로 통째로 지울 수 있습니다.
4. Electric Erasable PROM (EEPROM) : 전기로 통째로 지울 수 있습니다.
5. NAND Flash : EEPROMs 이면서 부분적으로 지울 수 있습니다.
6. Optane : Phase Change Memory 입니다. 열을 가함에 따라 비정질상태와 결정질상태로 바뀌는 칼코게나이드 유리의 독특한 특성을 이용하여 데이터를 저장합니다.

Uses for Non-Volatile Memories

1. 펌웨어는 ROM에 저장됩니다. (BIOS, Controllers for Disks)
2. Solid State Disk (SSDs)
3. Disk caches

---

SRAM vs DRAM vs Optane vs NAND Flash

저장장치 비교표

* Flash 가 Transistor 1개에 1개 이상의 bit를 저장할 수 있는 이유는 Multi-level-cell technologies 가 있기 때문입니다.

---

Memory Hierarchy

메모리 계층 구조란, 메모리를 여러가지 종류로 나누어서 효율성을 높이는 방법입니다. 

이 방법이 효율성을 높여주는 이유는 Locality 덕분입니다.

 

Locality는 프로그램은 최근에 사용하였던 데이터와 가까이 있거나(Spatial Locality) 아니면 그냥 최근에 사용하였던 데이터를 사용할 가능성이(Temporal locality) 높은 성질을 의미합니다. 예를 들어 아래 코드를

 

sum = 0;
for (i = 0; i < n; i++)
    sum += a[i];
return sum

Data references 측면에서 보면 Stride 1로 계속해서서 주변 Data를 reference 하고 있으니 Spatial locality를 가진 것이고 sum을 계속해서 reference하고 있으니 Temporal locality를 가진다고 볼 수 있습니다.

 

Instruction references 의 측면에서 보면 다음에 실행할 코드는 당연히 그 전에 실행했던 코드의 다음에 있기 때문에 Spatial locality를 가지고 for 문을 반복해서 돌기 때문에 Temporal locality를 가진다고 볼 수 있습니다.

Memory Hierarchy

피라미드의 각 아래 계층에서 Reference된 내용을 그 위의 계층으로 올려주는 구조가 바로 Memory Hierarchy 입니다.

---

2.  Virtual Memory

이런 저장 장치들을 바로 Physical Memory라고 합니다. 이게 어떻게 Virtual Memory를 구성할까요?

---

Physical Memory

Physical memroy는 array of bytes로 취급됩니다.

프로그램은 모든 데이터 구조들을 메모리에 저장합니다.

 

Read 연산은 mov A, %eax로,

Write 연산은 mov %eax, A 로요.

---

How to Use Physical Memory

만약에 한개의 프로그램만을 Direct로 Physical memory에 올린다고 생각합시다. 이 방법은 실제로 임베디드 시스템이나 아주 초기의 Operating System에서 사용하던 방법입니다.

그렇다면 어떤 이슈가 발생할까요?

 

1. CPU 사용률이 안좋습니다. (CPU Utliziation)
2. Memory 공간이 낭비됩니다. (Memory efficiency)

 

그래서 지금은 여러개의 프로그램을 Physical Memory에 올리는 방식을 사용합니다. 그렇게 되면 올린 여러개의 프로그램 중 하나를 짧게 사용해도 오버헤드가 크지 않고 그 다음에 바로 다른 프로그램을 사용할 수 있습니다.

Memroy efficiency 와 CPU Utliziation이 모두 높은 방법이죠. 이 방법도 이슈가 있습니다.

 

1. 접근 권한이 없는 프로세스가 잘못 다른 프로세스의 메모리공간에 접근할 수 있습니다. ( Protection Issue )
2. 로드 될 때마다 메모리 주소가 바뀌는데, 이것을 관리해 주어야 합니다.

---

Virtual Memory

이 아래의 이슈를 올바르게 관리하는것이 바로 Memory Virtualization을 해주는 것입니다.

OS가 Physical Memory를 Virtualize 해준다는 것은 OS가 각각의 모든 프로세스에게 가상의 메모리 공간을 따로 부여하는 것입니다. 각 프로세스가 전체 메모리 공간을 쓰는것처럼 보이게 해준다는 의미이죠.

 

Memory Virtualization은 즉 Physical Memory를 Virtual Memory로 변환하는 과정입니다.

 

Virtual Memory 란 Virtual address space와 Adress translation이 합쳐진 것입니다.

 

Virtual address space

1. 각 프로세스는 개인의 virtual adress space를 가집니다.
2. 프로그램은 memory가 virtualized 되어 있는지 신경 쓸 필요가 없습니다.
3. 다른 프로그램이 메모리를 레퍼런스 하는것이 다른 프로그램의 메모리에 영향을 주지 않습니다.

Address translation

1. Physical memory는 공유되는 자원입니다, 고로 OS에서 관리해 주어야합니다.
2. OS는 각 프로그램의 Virtual address를 Physical address에 시간과 공간을 효율적으로 쓰면서 Mapping해 주어야 합니다.

---

Benefits of Virtual Memory

Virtual Memory를 통해 Physical Memory를 관리하면 어떤 이점이 있을까요?

 

Memory efficiency

• 많은 프로그램들이 한개의 메모리에서 동시에 돌아갈 수 있습니다. 

Protection

• 프로세스에게 독립된 메모리 공간을 보장합니다.
• 잘못된 메모리 접근을 막아줍니다. (errant access)

Ease of programming

• 각 프로세스는 다 동일한 구조의 linear address space를 갖습니다.
• 이는 관리, 및 개발에 용이합니다.

---

3. Address Translation

---

Design Goal

Address Translation의 디자인 목표는 다음과 같습니다

Transparency

• 프로그램은 자신의 Memory가 Virtualized 되어있는지 신경 쓸 필요가 없습니다.

Protection

• OS는 다른 부적합 프로세스로부터 errant memory access를 막아야합니다.

Flexibility

• 시스템이 프로그래밍 하기 쉬워야합니다.

---

Address Translation with Hardware

CPU안에는 Memory Mangement Unit (MMU) 가 있어 Address translation을 도울 수 있습니다.

이것이 없으면 느리기 때문에 Hardware의 도움읠 받아 Addres Translation을 해야합니다.

MMU의 작동

---

Dynamic Relocation

Dynamic relocation은 Base Register와 Bound Register를 통해 Address를 Translation합니다.

자세하게 설명하자면 이와 같이 동작합니다.

1. 각 프로그램이 각각의 Virtual Address에 맞게 Compile 됩니다.
2. 프로그램이 동작하기 시작할때, OS가 base와 bound 값을 설정해 줍니다.
3. MMU가 계속해서 주소를 변환합니다.

그리고 OS는 다음과 같은 일이 일어날때마다 조치를 취해주어야 합니다.

1. 프로세스가 돌기 시작할때 (메모리 빈 공간을 찾아주어야합니다)
2. 프로세스가 종료되었을때 (메모리를 반환해주어야 합니다)
3. 컨텍스트 스위치가 발생했을때 (어디에 저장되어있는지, 즉 base와 bound를 PCB안에 기록해주어야합니다)

Dynamic Relocation의 문제점은 Virtual Memory 전체인 16kb가 생각보다 크고 대부분은 사용되고 있지 않다는 점입니다. 그러나 이것이 Physical Memory를 사용하고 있기에 이는 메모리 낭비입니다.

또 16-bit Linux Machine같은 경우 128TB의 Virtual adress space를 제공하는데 이럴 경우 Physical memory에 Fit될 수 없으니 Dynamic Relocation으로는 돌리기 불가능합니다.

 

 

 

---

Segmentation

Segmentation는 Dynamic allocation의 약점을 보안하기 위해서 만들어진 Address Translation 방식입니다.

 

일단 첫번째로 Virtual Address Space에서 연속적으로 저장되는 부분을 전부 따로 나누어야 합니다. 이를 Segment라고 하고 그렇게 Code, Stack, Heap으로 나눠진 각 Segment의 Base와 Bound를  전부 따로 부여합니다.

 

이것은 Segment의 Virtual Address입니다

앞의 몇 비트를 어떤 Segment를 가르키는지로 사용하고, 나머지는 Offset이 됩니다.

Code 는 00, Heap은 01, Stack은 11 입니다.

 

 

앞의 Segment bit로 Segment Table을 찾고 그것의 Size 와 Base를 알아낸 뒤 만약 Offset이 Size보다 크다면 Segment Falut를 출력하고 아니라면 Base+Segment를 Physical Address로 하여  Main memory에 접근합니다.

 

고로 아까 Dynamic Allocation과 다른 점은 Virtual Address + Base 가 아닌 Offset + Base(Grow Positive)가 바로 Physical Address가 된다는 점입니다.

 

Segment의 또 다른 기능은 Sharing을 Support 하는 것입니다. 이것을 위해서 protection bit를 지원합니다.

 

이런 Segment에도 문제점이 있습니다. 바로 Fragmentation이라는 것입니다.

만약 각각 8KB씩 떨어진 3개의 24KB짜리 빈 공간이 있고 Size 20KB의 Segment를 Segmentation하려고 해도 연속된 공간이 아니라 Fragment되어 있기 때문에 Memory를 낭비하게 됩니다.

 

그래서 우리는 남는 Space를 Management 해야합니다.