일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 프로그래밍
- SJF
- FIFO
- STCF
- scheduling
- 문법
- Fair-Share Scheduling
- 프로그래밍언어
- sceduling
- Stride scheduling
- 컴퓨터 구조
- Computer Architecture
- 컴퓨터
- Round robin
- C언어
- PIM
- Operating System
- 스케줄러
- scheduler
- Process
- DRAM
- System Call
- computer architercure
- Segmenation
- 어셈블리
- 운영체제
- Process in Memory
- virtual memory
- MLFQ
- Today
- Total
Nyong!
6. Virtual Memory 본문
Why memory virtualization?
-> 프로세스를 동시에 실행하기 위하여!
- 여러 process들이 memory를 공유할 때, '가장 간단한' 방법은 하나의 process가 memory를 전부 사용하는 방법이다. 이 방법을 사용한다면, 하나의 process가 실행되는 동안 다른 process들은 모두 disk에 저장되어야 한다.
- disk는 memory에 비해 매우 느리다. 따라서 disk에서 읽고 쓰며 process들이 context switching을 한다면 context switching overhead가 너무 크다.
따라서, OS는 여러 process를 memory에 동시에 저장한다. 그리고 이를 위하여, memory virtualization을 사용한다.
Address Space Mapping to Phyical Memory

여러개의 Process가 memory 상에 동시에 존재한다면, 다음 그림과 같이 process들이 physical memory에 mapping된다고 생각할 수 있다.
Goals and Benefits of Memory Virtualization
- Virtual memory를 사용하는 첫번째 이유 : Isolation
- OS는 프로세스 간의 memory 간섭이 일어나지 않게 해야한다.
- OS는 프로그램들에게 가상화된 주소를 제공한다.
- Virtual memory is transparent to user processes.
- 프로그램은 physical memory의 존재를 모른다.
- 프로그램은 그 자신의 code와 data가 모두 memory에 존재한다고 생각한다.
- OS는 프로그램을 속이면서 효율적으로 physical memory를 관리한다.
- Memory virtualization없이 memory에 모든 process를 올리면 physical memory size의 한계로 인해 제약이 생긴다.
- TLB와 같은 hardware의 도움을 받는다.
Virtual-to-Physical Memory Address Translation
- 모든 memory reference는, virtual memory -> physical memory의 translation이 필요하다.
- process는 virtual memory만을 사용할 수 있고, data는 physical memory에 저장되어야 한다. OS가 process가 요청한 virtual memory를 physical memory로 translation해준다.
- 다음과 같은 가정을 하고 memory address translation에 대해 알아보겠다.
- virtual memory space는 실제 메모리에 들어갈 수 있을만큼 충분히 작다.
- 모든 메모리 segment는 같은 크기를 갖는다.
Dynamic Memory Allocation
Dynamic memory allocation은 base와 bound를 이용하여 구현된다.
다음 그림에서 나타나듯이, physical address = virtual address + base이고, bound보다 큰 메모리 주소는 에러가 난다.

Hardware Supports for Address Translation
- Memory management unit(MMU)
- 모든 memory reference는 하드웨어가 virtual address에 base를 더해서 이루어진다.
- 단순히 더하는것 뿐만 아니라, bound를 통해서 이용가능한 주소인지도 확인한다.
- Base와 bound를 저장하는 레지스터가 존재하고, base와 bound 값은 OS가 kernel mode에서 바꿀 수 있다.
- Exceptions
- 프로그램이 bound 밖의 memory 접근을 시도하거나 base, bound 레지스터 값을 바꾸려고 하면, hardware는 exception을 일으킨다.
- Exception이 일어나면, 현재 프로세스가 멈추고, OS가 control 갖는다. 그리고 kernel mode로 바뀐 뒤, trap handler가 실행된다.
- 그 뒤 OS가 프로세스를 종료한다.
Exception이 일어나는 과정은 다음 그림을 통해 확인할 수 있다.

Internal fragmentation and Segmentation
- Internal fragmentation
- Virtual memory address space 전체를 physical memory에 그대로 mapping 한다면, stack과 heap 영역 사이에, 버려지는 공간이 생긴다.
- 프로세스에게 할당 되었지만, 쪼개지고 사용될 수 없는 메모리가 생기는 것을, internal fragmentation(내부 단편화)이라고 부른다
- Interernal fragmentation은, dynamic allocation의 가장 큰 한계이다.
- Segmentation
- virtual memory address space 전체를 physical memory에 그대로 mapping 하는 대신, segment 별로 나누어 mapping 할 수 있다.
- 이때, 각각의 segment는 각각의 base와 bound를 갖는다.
Segmentation
segment 별로 나누어서 virtual memory address를 physical memory에 mapping한다.

14-bit virtual space(16KB address space)의 예시이다.상위 2bit는 segment type을 결정한다. 나머지 12bit는 offset을 나타낸다.
process별로 갖고 있는 segment의 base에 offset을 더하면, physical address를 구할 수 있다.
External Fragmentation
- External fragmentation이란, memory space의 중간에 메모리가 할당되는 것이다.
- 프로세스들이 가변적인 크기의 메모리 할당 및 해제를 반복하면 피해갈 수 없는 문제이다.

External fragment에 대한 간단한 예시이다. 변수 a,b,c,d에 메모리가 할당된 뒤, a, c가 메모리가 해제되어, 메모리상에 사용할 수 있는 메모리는 10KB가 되었다. 이 상황에서 변수 e에 6KB 크기의 메모리를 할당하려고 하면, 사용하지 않는 메모리가 10KB가 됨에도 불구하고 연속된 6KB의 메모리가 존재하지 않아 할당할 수 없게 된다.
Free list
Free list는 사용 가능한 memory chunck들의 리스트이다.

Free list : splitting

malloc이 실행되면, free list에서 요청받은 메모리 사이즈만큼 메모리를 할당하고, 남은 메모리 부분은 free list에 그대로 남는다.
Free list : Coalescing

연속되는 free list의 memory chunk들은 그대로 남아 있으면, 충분한 남은 메모리가 있음에도 불구하고 큰 메모리 공간을 할당하지 못하는 경우가 생길 수 있다.(위의 예시에서, 연속되는 12KB의 free memory가 있지만 합쳐지기 전에는 9KB 이상의 메모리를 할당할 수 없다.)
할당된 메모리를 해제할 때, 연속되는 free list들을 합쳐서 큰 메모리 할당도 가능하게 한다.
Handling Free List : best fit

모든 free list를 탐색하여 할당해야 하는 메모리 사이즈에 가장 가까운 free block에 할당한다.
예시를 보면 2KB를 할당해야 하는 상황에서 4KB와 6KB의 free memory block가 있고, 4KB free memory block에 새롭게 2KB를 할당한다.
버려지는 메모리를 줄일 수 있지만, 조그만 free block들이 많이 생긴다.
Handling Free List : Worst fit

모든 free list를 탐색하여, 가장 큰 free memory block에 메모리를 할당한다.
Free memory block들의 개수를 최소화한다.
First fit & Next fit
위의 두 방식은, list를 처음부터 끝까지 모두 탐색해야하기 때문에, 시간이 오래 걸린다는 단점이 있다.
First fit과 next fit은 수행 속도를 개선한다.
First fit : Head 부터 출발하여, 할당하고 싶은 메모리를 할당할 수 있는 free memory block을 만나면 바로 할당한다.(ex. 2KB를 할당해야 하는 상황에서, 2KB보다 큰 block을 만나면 바로 할당한다.)
Next fit : First fit과 같은 방식이지만, Head부터 출발하지 않고, 마지막으로 메모리를 할당했던 block에서 탐색을 시작한다.(마지막으로 할당했던 block을 표시하는 pointer가 필요하다.)
Segregated Free List
프로세스들의 요청에 따라 메모리를 할당할 때, 모든 프로세스가 동일한 사이즈의 메모리만을 사용한다면, 메모리 할당 문제는 쉬워지고, 실제로 프로세스들이 자주 사용하는 메모리 사이즈가 있다.
자주 사용되는 메모리 사이즈의 free memory block을 segregated free list를 통해 따로 관리를 하고, 그 외의 memory 사이즈에 대한 할당은 general memory allocator이 담당한다.

Binary Buddy Allocation
Binary buddy allocation은 메모리 공간을 2로 나누면서 현재 할당하려는 메모리 사이즈에 맞는 사이즈를 찾고, 할당하는 방법이다.
메모리가 해제되면, 인접한 같은 사이즈의 메모리가 free인지 확인하고, free라면 합쳐진다.
free memory chunks들의 관리가 쉽고 메모리 탐색이 O(logn)으로 빠르지만(지금까지 알아본 방법은 모두 O(n)이다.), internal fragmentation이 발생한다.
'Study > Operating System' 카테고리의 다른 글
8. Threads and Race condition (0) | 2022.02.17 |
---|---|
5. Scheduling(0) - Long/Short/Medium scheduler (0) | 2022.02.11 |
4. Scheduling (2) - Job Scheduling (0) | 2022.02.11 |
3. Scheduling (1) - system call, interrupt, context switching (0) | 2022.02.10 |
2. Process (0) | 2022.02.09 |