운영체제(8) Main memory

  

1. Memory manager

 
<Requirements>
-> Minimize executable memory access time(실행 가능한 메모리 엑세스 시간 최소화)
-> Maximize executable memory size(실행 메모리 크기 최대화)
-> Executable memory must be cost-effective(메모리는 비용 효율적이어야 함)
 
<Today's memory manager>
-> primary memory(기본 메모리)를 프로세스에 할당한다. 
-> 비용 효율적인 메모리 구성을 사용하여 엑세스 시간을 최소화한다. 
-> static(정적) or dynamic(동적) 기법을 사용할 수 있다. 
 
<Memory Management Techniques>
 

 
 

2. Memory hierarchy(메모리 계층구조)

 
메모리를 속도, 용량, 비용 간의 절충 관계를 고려하여 필요에 따라 여러 가지 종류로 나타낸 구조.
계층 구조에서 위쪽으로 올라갈수록 CPU 코어에 가까워지고, CPU가 해당 메모리에 더 빨리 접근할 수 있다. 
-> 그러나 그만큼 더 많은 비용이 들고, 저장 용량이 적다. 

아래로 갈수록 Larger storage, 위로 갈수록 Faster access

another picture of Memory hierarchy

 
<Exploiting the hierarchy>
(1) Upward move
    copy operation(복사 작업)이다. 
    상위 메모리에 할당이 필요하다. 또한 Image는 상위 메모리와 하위 메모리 모두에 존재한다. 
    ** Update는 상위 메모리에 먼저 적용된다. 
(2) Downward move
    destructive(파괴적)이다. 
    상위 메모리의 Image는 삭제하고, 하위 메모리의 Image는 업데이트된다. 
-> 자주 사용하는 정보를 계층의 높은 위치에 배치하고, 자주 사용하지 않는 정보를 아래에 배치한다. 
-> 프로세스 변경 단계에 따라 재구성한다. 
 
* 9페이지 그림을 이해해보자. 
 
 

3. Binding of Instructions and Data to Memory

 
<주소의 종류>
(1) Physical address(물리적 주소) : 데스크탑으로 직접 볼 수 있고 만질 수 있는 물리 메모리의 주소. 
    -> 실제로 올라가는 위치. 
(2) Logical address(virtual address) : 프로세스마다 독립적으로 갖는 공간. CPU가 보는 주소. (시작 : 0번지)
    -> 프로그램 내에서 '상대적으로 얼마나 떨어져 있는가' 등으로 표현하는 메모리.
    -> 실제로 프로그램이 실행되렴녀 이 논리 주소를 절대 주소(물리 주소)로 변환하는 과정을 거쳐야 한다.
        이 작업을 수행하는 하드웨어가 MMU(Memory management unit)이다. 
(3) Symbolic address : 프로그래밍을 할 때 변수를 지정하면 변수의 이름을 통해 값에 접근하는 방법. 
 
<Address binding>
data의 주소를 결정하는 것. 물리적 메모리의 어느 부분에 적재할 지 결정한다. 
When to binding에 따라 3가지 종류로 나뉜다. 
(1) Compile time binding
    컴파일할 때 바인딩이 이루어진다. 
    (컴파일을 하는 순간, 프로그램이 해당 번지에 올라가서 수행됨이 결정된다.)
    프로그램 내부에서 사용하는 주소 = physical 주소
    [단점] 물리적 메모리가 많이 비었어도 이미 주소가 결정됐기에 변경할 수 없다. 비효율적이다. 
    -> 시작 위치가 변경되면 코드를 다시 컴파일 해야 한다. 
    -> absolute code :  어셈블리어가 정한 위치에 물리적으로 고정되어 위치되는 코드. 
(2) Load time binding
    프로그램이 실행되었을 때 바인딩이 이루어진다. 
    컴파일러가 재배치 가능하다.(= 메모리 위치 알 수 없다.) -> relocatable code라고도 부른다. 
    프로그램 내부에서 사용하는주소 != physical 주소
    [장점] compile time binding과 다르게 multi programming이 가능하다. 
    [단점] 메모리 로딩할 때 시간이 많이 걸린다. (수많은 메모리 참조 코드를 다 수정해야 함)
(3) Execution time binding
    실행할 때 주소를 바꾼다. 
    프로세스가 실행할 동안, 다른 메모리 세그먼트로의 이동이 있는 경우 실행 시간까지 지연되는 바인딩. 
    CPU가 주소를 참조할 때마다 새로 binding 상태를 점검해야 한다.
    하드웨어적 지원이 필요하다. (MMU)
-> compiler(컴파일러) : 특정 프로그래밍 언어의 코드 전체를 다른 언어로 옮기는 언어 번역 프로그램
-> binding(바인딩) : 변수나 예약어 등 프로그래밍 언어를 구성하고 있는 여러 것에 속성을 부여하는 행위
 
 

4. Creating an Executable program

 
Compiler : individual source file을 object file로 변환시키는 역할. 
Linker : 여러 개의 object file을 묶어서 하나의 executable file로 만들어주는 역할.
Loader : main memory에 object file의 내용을 다 layout하고, context를 build하고 수행시킬 수 있도록 함.
-> OS의 한 툴로, fork()와 exec()를 사용한다. 
 
<Address space>
OS는 abstraction of physical memory를 생성한다. 
Address space(주소 공간)에는 실행 중인 프로세스에 대한 모든 내용이 포함된다. 
(ex) 프로그램 코드, 힙, 스택 등을 다 포함. 
 
<Virtual address>
running program의 모든 주소는 virtual(가상)이다. 
-> OS가 가상 주소를 물리적 주소로 변환한다. 

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {

    printf("location of code : %p\n", (void *) main); //'%p'는 위치를 프린트한다. 
    printf("location of heap : %p\n", (void *) malloc(1));
    int x = 3;
    printf("location of stack : %p\n", (void *) &x);
    
    return x;
}

 
<Memory API : malloc()>
heap에 메모리 영역을 할당한다. 
-> Argument가 size_t size : 메모리 블록의 크기(바이트), size_t : 부호 없는 정수 유형
-> Return 값이 Success : malloc에서 할당한 메모리 블록에 대한 void 형식 포인터, Fail : null 포인터

#include <stdlib.h>

void* malloc(size_t size)

 
<Other Memory API : calloc()과 realloc()>
(1) calloc()
    반환하기 전에 heap에 메모리를 할당하고, 0으로 설정한다. 
    -> Argument가 size_t num : 할당할 블록 수, size_t size : 각 블록의 크기(바이트)
    -> Return 값이 Success : calloc에 의해 할당된 메모리 블록에 대한 void 형식 포인터, Fail : null 포인터

#include <stdlib.h>

void* calloc(size_t num, size_t size)

(2) realloc()
    메모리 블록의 크기를 변경한다. 
    -> 재할당을 통해 반환도니 포인터는 ptr과 같거나, 새 포인터일 수 있다. 
    -> Argument가 void *ptr : 메모리 블록에 대한 포인터, size_t size : 메모리 블록의 새 크기(바이트)
    -> Return 값이 Success : 메모리 블록에 대한 void type 포인터, Fail : null 포인터

#include <stdlib.h>

void* realloc(void *ptr, size_t size)

 
<sizeof()>
routine과 macro는 숫자를 직접 입력하는 대신, malloc의 size를 사용한다. 
매크로가 뭔지 잊어버렸다면 이 링크를 클릭!(참고하세요)

int *x = malloc(10*sizeof(int));
prinft("%d\n", sizeof(x));
// The actual size of 'x' is known at run-time. answer : 4

int x[10];
prinft("%d\n", sizeof(x));
// The actual size of 'x' is known at run-time. answer : 40

 
<Memory API : free()>
malloc 호출에 의해 할당된 메모리 영역을 해제한다. 
-> Argument는 void *ptr; : malloc으로 할당된 메모리 블록에 대한 pointer
-> Return 값은 none

#include <stdlib.h>

void free(void *ptr)

// Double free -> Undefined error
int *x = (int *)malloc(sizeof(int)); // allocated
free(x); // free memory
free(x); // free again -> invalid space를 free했으므로 error 발생함

 
<Allocate Memory code example>
strcpy 함수는 안에서 malloc이 되지 않는다. Incorrect, Correct code를 각각 보자. 

// Incorrect code
char *src = "hello"; // char string constant
char *dst; // unallocate되었음
strcpy(dst, src); // segfault 일어난 다음 die

// Incorrect code, but work properly
char *src = "hello"; // char string constant
char *dst (char*)malloc(strlen(src)); // 문자열에는 NULL(end of string mark)가 존재하므로 +1도 해줘야 한다. 
strcpy(dst, src); // work properly

// Correct code
char *src = "hello"; // char string constant
char *dst (char*)malloc(strlen(src) + 1); // allocate되었음
strcpy(dst, src); // work properly

 
<System calls>
malloc library call은 brk sys call을 사용한다. 
-> brk : 프로그램의 break를 확장하기 위해 호출된다. 
    (break : address space에서 the end of the heap 위치)
-> sbrk는 brk와 유사한 additional call이다. 
-> 프로그래머는 절대 brk나 sbrk 중 하나를 직접 호출해서는 안 된다. (?) 무슨 의미여

#include <unistd.h>

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

-> mmap system call은 anonymous(익명) 메모리 영역을 생성할 수 있다. 

#include <sys/mman.h>

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

 
<Dynamic loading과 Dynamic linking>
(1) Dynamic loading
    호출될 때까지 루틴이 로드되지 않는다. 
    메모리 공간 활용도를 향상하기 위해, 사용하지 않는 루틴은 로드되지 않는다. 
    [[자주 발생하지 않는 사례]를 처리하기 위해 많은 양의 코드가 필요한 경우]에 유용하다. 
    -> OS가 특별히 지원해 주는 것은 없다. 
(2) Dynamic linking
    실행 시간까지 Linking이 연기된다. 
    stub(스텁, 작은 코드 조각)은 적절한 memory-resident library routine을 찾는 데 사용된다. 
    stub은 자신을 routine의 주소로 바꾸고, routine을 실행한다. 
    -> [routine이 프로세스의 메모리 주소에 있는지 확인하기 위해] OS가 필요하다. 

Addressing Requirements for a Process

 
 

5. Memory leak

 
프로그램의 메모리가 부족하여 결국 중단되는 현상. 
동적으로 할당한 메모리가 free(할당 해제) 될 수 없는 상태를 의미한다. 
-> 메모리를 할당하여 사용한 후 free를 해주지 않을 경우 메모리 사용량이 계속 증가한다.
    결국 시스템의 메모리가 부족해져 OS가 프로그램을 강제 종료시킬 수 없게 된다. 
-> memory leak에 대한 더 많은 지식은 이 링크를 클릭!
 
<Dangling pointer>
포인터가 여전히 해제된 메모리 영역을 가리키고 있다면, 이러한 포인터를 댕글링 포인터라고 한다. 
댕글링 포인터가 가리키는 메모리는 더이상 유효하지 않다. 
premature free(조숙한 해제, 너무 급한 해제)라고 부르기도 한다. 

 
 

6. Contiguous memory allocation

 
연속적 메모리 할당, MMU를 통해 논리적 주소를 물리적 주소로 변환할 때 단순 덧셈을 하여
물리적 주소도 논리적 주소처럼 연속적으로 할당하는 것을 의미한다. 
-> logical address가 연속적이면, physical address도 연속적으로 배치된다. 
-> MMU : CPU 코어 안에 탑재되어 가상 주소를 실제 메모리 주소로 변환해주는 장치
 
<Memory protection>
잘못된 메모리 주소를 참조하지 않도록 막아주는 역할.
연속적 메모리 할당을 할 시, 각 프로세스들은 각자의 메모리 영역을 넘어서서 다른 것을 침범하면 안 된다.
따라서 Memory protection이 필요하다. 이때 두 가지 레지스터가 사용된다. 
(1) limit register : 상한 레지스터의 제한 값보다 큰 가상 주소에 memory protection fault(trap)을 발생시킨다.
(2) base(relocation) register : 프로세스에 starting address를 제공한다. 
    -> [physical address] = [starting address] + [logical address]

 
<3 types of contiguous allocation>
base reg과 limit reg를 활용하여 프로세스마다 구역을 할당한다. 어디에 구역을 할당할 것인가...
hole : 메모리 상의 빈 공간, 이 hole들은 다양한 크기로 메모리 곳곳에 뚫려 있다. 
우리는 이 hole들 사이에서 특정 프로세스를 어디다가 넣어줄 것인지를 고민해야 한다. 
(1) First fit : 프로세스를 할당해주기에 충분히 큰 hole이 발견되면, 처음 발견된 거기에 바로 할당한다. 
(2) Best fit : 할당 가능한 여러 hole 가운데 가장 작은 hole에 할당한다. (Best fit size hole에 할당)
(3) Worst fit : 할당 가능한 여러 hole 가운데 가장 큰 hole에 할당한다. 
 
<Contiguous allocation의 장점>
MMU가 매우 간단하다. 더하기 하나만 하면 된다. 
-> memory protection fault를 체크할 때 '이 값이 특정 값 이상인가 아닌가'만 비교해주면 된다. 
-> 하드웨어 만들기가 매우 쉽다. 
 
<Contiguous allocation의 단점>
Fragmentation에 관한 단점이 존재한다. 
-> 이를 개선하기 위해 paging이 등장했다. 
-> Fragmentation이란? 
    RAM에서 메모리의 공간이 작은 조각으로 나뉘어져, 작은, 쓸 수 없는 메모리들이 중간중간 발생.
    External fragmentation : 메모리 공간은 넉넉하나 연속적(contiguous)으로 남아있지 X -> 할당되지 X.
    (compaction, 압축을 통해 이를 감소할 수 있다. 사용가능한 모든 메모리를 하나로 합쳐준다.)
    Internal fragmentation : 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 영역의 공간이 남는 현상.
-> fragmentation에 대해 더 자세히 알려면 여기를 클릭!
 
<Two memory allocation strategies>
무슨 내용인지 정확히 모르겠으나 존재함.

 

 
 

7. Partitioning과 Buddy system

 
메모리 관리의 실전 방법 중 하나. 
기본적으로 프로세스의 크기만큼 물리 메모리에 충분한 공간이 있음을 가정한다. 
-> 물리 주소 공간에 공간이 부족한 경우엔 페이지 교체 정책을 !!
 
<Fixed partitioning>
메인 메모리를 여러 Partition(파티션)으로 나누고, 파티션 크기보다 작은 프로세스를 할당할 수 있도록 한다.
-> 하나의 프로세스가 하나의 파티션을 차지하기 때문에 Internal fragmentation이 발생할 수 있다.
-> 하나의 프로그램이 파티션의 크기보다 클 경우, 애초에 메모리 할당이 불가능하다. 
    이런 경우에는 overlay 기법을 사용해야 한다. 
    overlay : 메인 메모리의 공간이 부족할 때 큰 프로세스를 돌리는 방법. 
-> 메모리 관리 알고리즘은 크게 두 가지로 나뉜다. 
    (1) Use of multiple queues :
         각 프로세스를 자신보다는 크지만 가장 작은 파티션에 넣기 위해 각각의 파티션에 대한 큐를 만든다.
         특정 partition에만 프로세스가 몰리는 현상이 발생할 수도 있다. 
    (2) Use of a single queue : 하나의 큐에 프로세스를 저장하고, 수용 가능한 가장 작은 파티션에 할당한다. 
    * 설명이 부족한 것 같으니 조금 더 공부해보자.. 
 
<Dynamic partitioning>
contigous memory allocation의 한 형태이다.
프로세스에게 연속적이면서도 동적으로 partition을 할당하는 방식이다. (각 파티션의 길이가 유동적이다.)
각 프로세스는 자신의 크기만큼 파티션 size를 할당받기 때문에 internal fragmentation이 없다. 
Best fit, First fit, Worst fit, Next fit(마지막 hole부터 스캔) 등의 방법이 있다. 

 
<Buddy system>
Fixed, Dynamic partitioning 기법의 fragmentation 발생 이슈를 보완하기 위한 방법이다. 

(1) 메인 메모리는 항상 2^N size로 할당한다. 

(2) 사용 가능한 가장 큰 메모리부터 시작해서 Binary로 절반씩 쪼개면서 조건에 해당하는 공간을 찾는다. 

(3) 조건 : If 프로세스 메모리 크기가 K라면, 2^(U-1) < K <= 2^U 인 U를 찾고, 2^U 만큼의 공간에 프로세스 할당.

    [ex] 프로세스의 크기가 1000B라면, 512B < 1000B < 1024B이기 때문에 1024B 사이즈의 메모리에 할당.
(4) 프로세스가 종료되고, If 같은 parent를 갖는 Buddy 공간이 비어있다면 Merge한다.  

int n = ceil(log(size)/log(2)); // 자신의 블록 사이즈
int buddyAddr = index^(1<<n); // 자신의 주소 bit 중에서 n번째 bit만 역으로 만들어주면, buddy의 주소가 된다.

챗지피티가 틀린 부분 : fixed에서 내부 단편화가, dynamic에서 외부 단편화가 일어난다. ㅋ

 

8. Paging

 
프로세스의 logical address space는 비연속적일 수 있다. 
프로세스는 물리적 메모리가 사용가능할 때마다 할당된다. 
(1) physical memory를 frame(고정된 크기 블록, 크기는 2의 거듭제곱, 범위는 512 ~ 8192 byte)으로 나눈다. 
(2) logical memory를 page(동일한 크기 블록)으로 나눈다. 
(3) 모든 사용 가능한 frame들을 추적한다. 
    -> n page 크기의 프로그램을 실행하려면, n개의 free frame들을 찾고 프로그램을 load해야 한다. 
(4) [logical address -> physical address로 변환할] page table(페이지 테이블)을 설정한다. 
(5) Internal fragmentation.
 
<Address translation scheme>
CPU에서 생성된 주소는 다음과 같이 나뉜다. 
-> Page number(p) : 실제 메모리에 있는 각 page의 기본 주소를 포함하는 페이지 테이블의 인덱스로 사용.
-> Page offset(d) : 기본 주소와 결합되어 메모리 장치로 전송되는 physical 메모리 주소.

Address translation Architecture

 

Paging example

 
<Implementation of Page table>
Page table은 main memory에 보관된다. 
-> PRBR(page-table base register) : page table
-> PRLR(page-table length register) : page talbe의 size
이 방식에서는 모든 data/instruction accress에 2개의 메모리 엑세스가 필요하다. 
(하나는 page table용이고, 다른 하나는 data/instruction용이다.)
두 가지 메모리 엑세스 문제는 TLBs라는 특수한 고속 검색 하드웨어 캐시를 사용하여 해결할 수 있다. (?!)\
 
<Overlays>
항상 필요한 instruction과 data만 메모리에 저장한다. 
When 프로세스가 [할당된 메모리 양]보다 클 때 필요하다. 
OS의 특별한 지원이 필요 X, 오버레이 구조의 프로그램이 설계는 복잡하다.
 
<Swapping>
프로세스를 [메모리 부족 상태]에서 [백업 저장소]로 일시적으로 swap한 다음,
계속 실행하기 위해 다시 메모리로 가져올 수 있다. 
-> Backing store(백업 저장소) : 모든 메모리 이미지의 복사본을 수용 가능한, 빠른 디스크. 
-> Roll out, Roll in : 우선순위 기반 스케줄링 알고리즘에 사용. 순위 낮은 애가 높은 애 load, 자기는 swap됨.
-> Major part of swap time : transfer time, 총 전송 시간은 스왑된 메모리 양에 정비례한다.

 
 

9. Memory Mgmt Strategies

 
-> Fixed - Partition은 only batch systems에서만 사용한다.
-> Variable - Partition은 어디에서나 사용된다. (가상 메모리만 제외하고 어디에서나)
-> Swapping systems : timesharing 잘 알려짐, dynamic address relocation에 의존, 현재 날짜
-> Dynamic loading(virtual memory) : 메모리 계층 활용, Paging(현대 시스템 대부분), Segmentation(미래)
 
 
 
 
 
 
 
 
TMI : flash memory과  SD 카드의 단점 = 읽기보다 쓰기가 더 느리다. cell 하나에 write의 제한이 있다. 
TMI : address space에서 heap, stack이 공간 공유하는 이유? 
    -> 프로그램 안에서 malloc, 지역변수를 얼마나 쓸 지 모르므로 유연한 동작을 위해 공유한다.