Memory API, Segmentation

지난시간에 했던거 복습

 

Virtual memory

 

1. time sharing

=> fork() 를 띄우면 DRAM 에 올리고 다른 녀석을 fork() 하면 DRAM 에 있던걸 Disk 로 내리고 다시 DRAM

    으로 올리는 작업... 딱 봐도 overhead가 상당하군?

 

2. static relocation (space sharing)

=> 올릴 때 OS가 program을 rewrite 한다. (주소 0x1000, 0x2000 와 같이 설정했었지)

     문제는 privacy 와 location change 가 안된다는 점

 

3. Dynamic relocation

=> MMU(Memory Management Unit로 hardware) 를 이용함

     그리고 Base + Bounds register 를 통해 physical address 를 리턴하거나 Process kill 을 했었지 

 

process의 virtual address를 physical address로 변경하기 위해 MMU 을 이용해서 변환해줬다.

(MMU 안에 Base + Bounds register 존재)

 

process A, B가 존재할 때 실제 시작주소가 따로 있다. (PCB(Process Control Block) 안에 해당 주소들이 존재함)

 

---

 

Memory API

 

 

 

 

대략적인 그림을 이해하도록 하고 malloc () 함수부터 차례대로 살펴보도록 한다.

 

 

malloc()

 

 

#include <stdlib.h>

void* malloc(size_t size)

 

Allocate a memory region on the heap.

 

Argument

- size_t size : size of the memory block (in bytes)

- size_t is an unsigned integer type.

 

Return

- Success : a void type pointer to memory block allocated by malloc

- Fail : a null pointer

 

 

 

sizeof()

 

 

Routines and macros are utilized for size in malloc insted typing in a number directly.

 

int *x = malloc(10 * sizeof(int));
printf("%d\n", sizeof(x));

// 출력 결과 : 4

 

위 경우는 run-time 일 때 size 결정이 가능하다.

 

만약 compiler 가 똑똑하다면 parsing 하는 과정속에서 40 byte를 할당하는 것을 알 수 있었을 것이다.

(하지만 그렇지 못하니... 기본적으로 sizeof(int) 를 반환하는 거군)

 

int x[10];
printf("%d\n", sizeof(x));

// 출력 결과 : 40

 

위 경우는 compile-time 일 때 size 결정이 가능하다.

 

 

free()

 

 

#include <stdlib.h>

void free(void* ptr)

 

Free a memory region allocated by a call to malloc.

 

Argument 

- void *ptr : a pointer to a memory block allocated with malloc

 

Return => none

 

 

 

 

int *x = (int *)malloc(sizeof(int));
free(x);
free(x);

 

위 경우는 free() 가 두 번 호출된 경우이다.

 

어떠한 문제점이 발생할까?

 

 

다음과 같은 문구가 뜨면서 프로그램이 종료된다.

 

 

free() 된 영역에 다시 한번 free() 를 할 경우 이상한 일이 발생한다는 것은 확실해졌다.

 

int *x = (int *)malloc(sizeof(int));
free(x + 12);

 

위 경우는 엉뚱한 곳을 free 하는 경우다. 어떠한 일이 발생할까?

 

 

위와 동일한 문구가 뜨면서 프로그램이 종료된다.

 

정확하게 free() 를 해주도록 하자.

 

 

Forgetting to allocate memory

 

 

char *src = "hello";
char *dst;
strcpy(dst, src);

 

위 코드는 잘못된 코드이다. 왜 그럴까?

 

=> dst 에 대한 할당이 이뤄지지 않음.

    만약에 char dst[100]; 이였다면 copy가 일어났겠지만

    char *dst; 자체는 allocate된 영역이 존재하지 않으므로 segfault 문구가 뜨면서 die를 한다. 

 

 

char *src = "hello";
char *dst = (char *)malloc(strlen(src));
strcpy(dst, src);

 

위 코드는 맞는 코드 같지만 아쉽게도 잘못된 코드이다. 왜 그럴까?

 

=> 실제로 src의 문자열은 "hello" 가 아니라 "hello\0" 이다. 

     즉, \0 까지 담기 위해 strlen(src) + 1 만큼의 공간이 필요하다.

 

 

위 경우처럼 \0 를 포함하지 않고 malloc을 하는 경우에 다른 영역에 무언가를 침범해서 동작하다가

overwrite 하면서 값이 바뀔 수 있다.

 

예를 들어서 value = 10 이 strlen(src) + 1 영역에 배치가 되었다고 한다면 결국 value = '\0' 으로 바뀌게 된다.

 

그래서 이렇게 프로그램을 작성하면 어디서 코드가 잘못 된건지 모를뿐만 아니라 정상적으로 계속 작동하다가 

이상한 곳에서 프로그램이 종료되는 어처구니 없는 현상이 발생하게 된다. 

 

즉, 디버깅이 힘들어서 위 같은 경우가 일어나지 않도록 '\0' 을 챙겨주도록 하자.

 

 

Forgetting to Initialize

 

 

int *x = (int *)malloc(sizeof(int));
printf("*x = %d\n", *x);

 

위 코드는 잘못된 코드이다. 

 

넘 당연하게도 할당은 했으나 할당한 영역에 값을 채워주지 않았기 때문에 어처구니 없는 값이 출력된다.

 

 

Memory Leak

 

 

while(1)
    malloc(4);

 

다음 코드는 무한루프로 memory allocate 가 일어나는 것을 알 수 있다.

 

문제는 계속해서 무한루프를 돌지 않고 어느 시점에서 OS가 die 를 시키도록 한다.

 

memory allocate 가 일어나는 동시에 free를 시켜준다면 계속해서 프로그램이 돌 수 있다.

 

 

 

dangling pointer

 

 

연결리스트로 여러개 연결된 노드들 사이에 중간 노드를 하나 free() 한다고 가정하자.

 

이때 free() 이외에 어떠한 operation 이 이뤄지지 않을 때 다음 노드는 free() 이전 노드에서

도달하지 못하는 일이 발생한다.

 

이러한 경우를 dangling pointer 라고 부른다.

 

 

 

calloc() and realloc()

 

 

#include <stdlib.h>

void *calloc(size_t num, size_t size)

 

memory를 할당함과 동시에 0으로 싸그리 초기화 하는 함수라서 malloc() 과 차이가 있다.

 

malloc() 함수 같은 경우는 garbage value를 뿜었다면,

calloc() 함수 같은 경우는 0을 뿜는다.

 

#include <stdlib.h>

void *realloc(void *ptr, size_t size)

 

Change the size of memory block.

 

- void *ptr : Pointer to memory block allocate with malloc, calloc or realloc- size_t size : New size for the memory block(int bytes)

 

 

System Calls : brk, sbrk

 

#include <unistd.h>

int brk(void *addr);
void *sbrk(intptr_t increment);

 

There leakc of heap space -> Ask OS to expand heap.

 

break : The location of the end of the heap in address space.

 

malloc uses brk system call.

- brk is called to expand the program's break.

- sbrk is similar to brk.

- Programmers should never directly call either brk or sbrk.

 

 

여기서 Heap space를 4 Kbyte의 chunk 단위로 늘려준다는 점을 알아두자.

 

왜 4 Kbyte의 chunk 단위로 늘리는 걸까?

 

=> 너무 크게 잡아버리면 메모리를 비효율적으로 사용하게 되는 문제가 있다.

     그래서 적당한 크기만큼을 요청하는데 4KB 이다.

 

sbrk() 함수는 break address 를 통해서 크기를 늘려주고 increment 라는 parameter를 받아와서 

정할 수 있다.

 

 

System Calls : mmap

 

 

#include <sys/mman.h>

void *mmap(void *ptr, size_t length, int prot, int flags,
              int fd, off_t offset)

 

Allocate a memory region of length at ptr.

 

If fd is not negative, associate the region to fd starting at offset.

 

 

 

 

file-backed region 은 힙 영역에 저정되는건지 아니면 구분되는 영역인건가?

 

=> heap 영역은 아니고 code, data, stack, heap space 별도를 위한 region 으로 사용

안되는 공간에다가 mapping 을 한다.

 

즉, heap 영역과 별도로 구분이 되는 영역을 의미한다.

 

 

---

Segmentation

 

 

Segmentation은 dynamic relocation 에서 사용되는 그 방법의 한계를 극복하기 위해 나타난 것이다.

 

What is segmentation?

 

- A segment is just a contiguous portion of the address space.

- Insted of having just one base and bounds pair in MMU, why not have a base

   and bounds pair perlogical segment?

- A process can have three or four logically-different segments : Code(Data), Stack and Heap

 

Segmentation allows the OS to place each one of those segments (Code, Stack, and Heap)

in different parts of physical memory, and thus avoid filling physical memory with unused

virtual address space.

 

Each segment can independently

 

- be placed separately in physical memory

- grow and shrink

- be protected (separate read/write/execute protection bits)

 

segment (Code, Stack, and Heap) 끼리 contiguous 하지 않지만 Code 끼리, Stack 끼리, Heap 끼리는

contiguous 한다는 점을 알아두자.

 

그리고 code, stack, heap 을 나눠서 base bound 를 각각 가지도록 한다.

 

 

Segmented Addressing

 

 

Process now specified segment and offset within segment.

 

How does process designate a particular segment?

=> Use part of logical address select segment

     - Top bits of logical address select segment

     - Low bits of logical address select offset within segment

 

 

 

Segmentation Implementation

 

 

MMU contains Segment Table (per process)

- Each segment has own base and bounds, protection bits.

 

 

ex ) Translate logical addresses to physical address.

 

(1) 0x0240 : segment가 0 이므로 0x0240 + 0x2000 = 0x2240 (physical address)

(2) 0x1108 : segment가 1 이므로 0x0108 + 0x0000 = 0x0108 (physical address)

(3) 0x3002 : segment가 3 이므로 0x0002 + 0x0000 = 0x0002 (Physical address) 인데

                  Bounds 를 넘었으므로 밑 코드의 RaiseException(~) 를 호출한다.

 

 

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
offset = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else 
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)

 

SEG_MASK = 0x3000

SEG_SHIFT = 12  (Segment 를 가져오기 위함)

OFFSET_MASK = 0xFFF

 

Segment, offset을 정해서 해당 Offset이 현재 Segment에 대한 Bounds 를 넘어서면 RaiseException 을

호출하고 그 외에는 Physical Address를 현재 Segment에 대한 Base 값을 더해서 구할 수 있다.

 

 

Segment 이 1이면 Base register 값은 0x400 이 되고 2이면 Base register 값은 0x1600 이 된다.

여기서는 Segment 1이 heap 영역이고 2가 stack 영역이라고 지정되어 있다.

 

 

Advantages

 

(1) Enables spared allocation of address space.

     - Stack and heap can grow independently

     - Heap : If no data on free list, dynamic memory allocator request more from OS

     - Stack : OS recognizes reference outside legal segment, extends stack implicitly

 

(2) Different protection for different segments

 

(3) Enables sharing of selected segments

 

(4) Supprots dynamic relocation of each segment

 

 

Disadvantages of Segmentation

 

 

Each segment must be allocated contiguously

=> May not have sufficient physcial memory for large segments,

     resulting in external fragementation.

 

 

 

 

왼쪽 사진을 보면 나중에 segment가 system 에서 지워졌다가 빼졌다가를 반복하면서

중간 중간에 fragmentation 이 일어나는 것을 볼 수 있다. (not in use)

 

이러한 현상을 external fragmentation 이라고 하는데 이를 해결하기 위해 contiguous 하게

모으는 경우를 compaction 이라고 부른다.

 

compaction 하는 과정에서 overhead가 존재할 수 있겠지만 어쩔 수 없다!

=> 메모리 공간의 효율을 높이기 위한 최선의 방법이다.