mojo's Blog

간단한 "implicit free list" 를 기반으로 한 malloc 코드이다. first-fit 과 next-fit 를 사용하며 boundary tag 를 이용하여 coalesce 를 한다. 그리고 블럭들은 doubleword(8 byte) 단위로 정렬이 되어야 하며 최소 블럭 사이즈는 16 byte 여야 한다. ※ define 에 대한 설명 /* * If NEXT_FIT defined use next fit search, else use first fit search */ #define NEXT_FITx /* $begin mallocmacros */ /* Basic constants and macros */ #define WSIZE 4 /* Word and header/footer size (by..

※ Implicit Memory Management : Garbage Collection Garbage Collection : 힙이 할당된 storage 를 자동으로 회수한다. 많은 dynamic langauges 에서 공통적으로 : Python, Ruby, Java, Perl, ML, Lisp, Mathematica C 및 C++ 에 대한 Variants ("conservative" 가비지 수집기)가 있다. 그러나 모든 가비지를 반드시 수집할 수는 없다. void foo() { int *p = malloc(128); return ; /* p block is now garbage */ } 위 코드는 memory leak 을 유발하는 함수이다. 이러한 상황은 다음과 같이 나타낼 수 있다. stack에 fo..

※ Keeping Track of Free Blocks Method 1: 길이를 사용한 implicit list 으로 모든 블록을 연결한다. Method 2: 포인터를 사용하는 free blocks 중에 explicit list 이다. Method 3: Segregated free list 다양한 크기 클래스에 대한 서로 다른 free lists Method 4: 크기별로 정렬된 Blocks 각 free 블록 내에 포인터가 있는 균형 잡힌 트리(Red-Black tree)와 key로 사용된 길이를 사용할 수 있다. 1번 방법 같은 경우는 포인트된 모든 영역을 전부 스캔해야하는 점에서 시간적인 문제가 존재한다. 2번 방법 같은 경우는 free 된 영역만을 scan 하기 때문에 시간적인 문제는 줄지만 fre..

※ Dynamic Memory Allocation 프로그래머는 malloc 와 같은 dynamic memory allocator 를 사용하여 런타임때 VM 을 획득한다. 크기가 런타임에만 알려진 데이터 구조용이다. Dynamic memory allocator 는 힙으로 알려진 프로세스 가상 메모리 영역을 관리한다. Allocator 는 힙을 할당되거나 free 할 수 있는 가변 크기 블록의 모음으로 유지 관리한다. Allocator 의 종류로는 다음과 같다. Explicit allocator : 응용프로그램이 공간을 할당하고 free 가능 예: malloc 및 free in C Implicit allocator : 응용 프로그램이 공간을 할당하지만 free 는 하지 않음 예: Java, ML 및 Lisp..

※ Exploiting parallel execution 지금까지는 스레드를 사용하여 I/O 지연을 처리했다. 예를 들어, 클라이언트당 하나의 스레드를 사용하여 다른 스레드를 지연시키는 것을 방지한다. Multi-core/Hyperthreaded CPU는 또 다른 기능을 제공한다. 병렬로 실행되는 스레드에 작업 분산 독립적인 작업이 많은 경우 자동으로 발생 예를 들어, 많은 응용 프로그램을 실행하거나 많은 고객에게 서비스를 제공한다. 또한 코드를 작성하여 하나의 큰 작업을 더 빨리 진행할 수 있다. 다중 병렬 하위 그룹으로 구성함으로써 Hyperthreading 이란? 하이퍼스레딩은 Intel 이 동시 멀티스레딩을 구현한 기술이다. 물리상 실행 장치 한 개에 가상 실행 장치(virtual 또는 logic..

※ Using Semaphores to Coordinate Access to Shared Resources Basic idea : 스레드는 세마포어 작업을 사용하여 다른 스레드에 일부 조건이 참임을 알린다. counting semaphores 을 사용하여 리소스 상태를 추적하고 다른 스레드에 알림 mutex 를 사용하여 리소스에 대한 액세스 보호 Two classic exmaples : The Producer-Consumer Problem The Readers-Writers Problem ※ Producer-Consumer Problem Common synchronization pattern : 생산자는 빈 슬롯을 기다렸다가 버퍼에 아이템을 삽입하고 소비자에게 알린다. 소비자가 아이템을 기다렸다가 버퍼에..