장영

segregated free list seg-list 방법은 free 블록들을 사이즈 에 대해 리스트를 각각 마련하는 방식이다. 서로다른 size 값이 n개라면, n개의 가용 리스트를 두어 각 가용 블럭들을 분류해서 기억하는 것이다. 사이즈 별로 연결리스트를 만들어야 하기 때문에 여러개의 연결리스트가 필요하며 여러개의 연결리스트 포인터가 존재한다.(힙에저장) 예를들어 37만큼의 메모리를 할당하고자 하면 위 그림에서 32~64 사이즈 연결리스트를 선택하게 되고 연결리스트에서 적절한 free블록을 찾게 된다. 위와 같이 대부분의 seg-list에서 연결리스트 사이즈는 2의 제곱수를 기준으로 한다. 해당 연결리스트에서 적절한 사이즈의 블록을 찾지 못하면, 다음 크기의 연결리스트로 넘어서 찾게된다. 이렇게 연결..

Explicit Free List implicit free list가 모든 블록(할당 + free)을 탐색하며 해당 블록이 할당되었는지, 아니면 free인지 확인하며 필요한 동작을 수행했다면, explicit free list는 오직 free 블록만 탐색하게 된다. 이러한 free 블록을 탐색할 수 있도록 이중 연결 리스트로 구성되는데, 이를 통해서 앞으로만 탐색하는 것이 아니라 뒤로도 탐색하는 것이 가능해진다. free 블록의 payload 부분은 사용하지 않는 상태로 되기 때문에 이 공간을 활용한다. 해당 블록에, 전의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) predecessor과 뒤의 free 블록의 주소로 갈 수 있는(주소값을 담고 있는) successor를 넣게 된다. 이를 통..

Malloc - lab 📌heap 동적 메모리 할당기는 힙이라는 가상 메모리를 관리한다. 이러한 힙 영역에는 할당된 블록과 가용블록이 있다. 할당기의 종류 명시적 할당기(explicit allocator) : 메모리 할당과 해제를 직접적으로 관리하고 조작하는 할당기 단점 : 메모리 누수 , 무효 표인터(이전에 참조하던 메모리 위치를 가리키지만 이제는 무효화된 포인터를 나타냄) 암시적 할당기(implicit allocator) : 프로그래밍 언어 또는 런타임 라이브러리에 내장되어 있어서 개발자가 명시적으로 메모리 할당 및 해제를 관리하지 않아도 되는 메모리 할당 방식 단점 : 런타임 오버헤드 문제, 성능 문제 Malloc pacakge 📌malloc void *malloc(size_t size) 할당 성공..

📌클래스의 멤버가 저장되는 영역 및 메모리 차지 우선 클래스는 멤버 변수와, 멤버 함수를 가질 수 있고, 정적 그리고 비정적 멤버 변수, 함수를 가질 수 있다. 클랙스 타입의 객체 또는 인스턴스 자체의 크기는 비정적 멤버 변수만 영향을 미친다. 즉, 멤버 변수로 int형 변수 1개를 가지면 이 클래스의 인스턴스 sizeof는 4바이트, 2개를 가지면 8바이트, 비정적 멤버 변수는 객체 생성과 동시에 생성된다. 객체 내의 지역변수와 동일하므로 스택에 저장된다. 또한 비정적 멤버 변수는 클래스 내에서 공유되는 변수가 아닌 하나의 객체마다 할당되는 변수이다. 만약 클래스 내에 정적 멤버 변수를 선언했다면 이 변수는 객체 생성 시 할당되는 것이 아니라 프로그램 시작시 데이터 영역에 생성된다. 따라서 정적 멤버 ..

📌동적 메모리 할당 컴퓨터 프로그래밍에서 실행 중에 사용할 메모리 공간을 할당하는 것을 의미 정적 할당 : 컴파일시점에 소스 코드를 읽고 메모리 공간을 확보하는 것 동적 할당 : 컴파일 시점이 아닌 프로그램이 실행되는 중인 런타임에 필요한 만큼의 메모리 공간을 확보하는 것을 의미한다. 💡동적할당을 하는 이유? char name [100]; name 배열은 최대 100개 까지 저장이 가능할 것이다. 그런데 막상 프로그램을 실행 시켜서 10글자만 입력했다. 그렇다면 90바이트는 어떻게 될? 그냥 낭비가 되는것이다. 반대로 100글자를 저장할 수 있는데 110글자를 입력하려고 한다. 이것 또한 문제이다. 위와 같은 문제를 해결해주는 것이 바로 동적 메모리 할당이다. 동적으로 할당한다는 말은, 프로그램이 시작된..

링커 📌링킹 여러개의 코드와 데이터를 모아서 이를 연결하여, 메모리에 로드될 수 있고 실행될 수 있는 한 개의 파일로 만드는 작업이다. 💡링커의 링킹 과정 대부분의 컴파일 시스템은 사용자를 대신해 언어 전처리기, 컴파일러, 어셈블러, 링커를 필요에 따라 호출하게 만들어졌다. 이를 컴파일러 드라이버라고 한다. 예 ) gcc 드라이버 이렇게 만들어진 object file들을 링커가 링킹해서 실행파일로 만듭니다. 이 object파일은 재배치 가능한 목적 파일 📌정적연결 unix_ld와 같은 정적 링커들은 재배치 가능한 목적파일들과 명령줄 인자들을 입력으로 받아서 로드될 수 있고 실행될 수 있는 완전히 링크된 실행가능 목적파일을 출력으로 생성한다. 입력인 재배치가능 목적파일을은 다양한 코드와 데이터 섹션들로 이..

데이터의 형식 📌어셈블리 자료형 파이썬과 같은 매우 고급진 언어에서는 list, map, string 등과 같은 편리한 자료형들이 있다. C는 정수, 실수 자료형만 있고, 그 외 struct, array와 같은 기초적인 자료형들이 있다. 그렇다면, 어셈블리어는 어떨까 ? 어셈블리어는 오직 정수, 실수 자료형만 존재하며 array가 없다. 물론 명시된 array가 없을뿐, c와 array 표현방식이 같다. 왜냐하면 연속하는 메모리 공간을 사용하면 array라고 생각할 수 있기 때문이다. 어셈블리 정수 자료형은 1,2,4,8byte 짜리가 존재 실수 자료형은 IEEE 754(부동소수점 표현)에 맞춰 4, 8, 10byte가 존재 포인터는 전부 정수자료형으로 표현된다. 즉 정수 자료형은 값을 의미할 수도, 주..

📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌rotatiom/recolor Rotation 을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있고, 각각의 경우에 알맞게 Recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다. RB tree 의 삭제 과정과, 삭제 후에 delete_fix_up 과정을 거치면서 RB tree의 특성을 만족시키도록 수정하는 과정들을 확인하려고 한다...

📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌삽입 레드-블랙 트리에서 새로운 노드를 삽입할때 ,새로운 노드는 항상 red 만약 트리가 레드블랙 트리의 특성을 위반한다면, 두가지 방법을 통해 트리의 구조를 조정한다. recolor rotation 📌삽입 과정 키 값이 20인 노드를 삽입하는 과정을 생각해보자. target Node를 20으로 설정하고 시작. key = 20인 노드가 들어갈 위치 탐색 key = 20 < 28 이고,..

rotation 📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌회전(rotaion) 레드-블랙 트리의 삽입(insert), 삭제(delete) 연산 과정에서 트리가 수정되기 때문에 레드-블랙 트리의 특성을 위반할 수 있다. 이런 특성을 복구해주기 위해서 트리내의 일부 노드들의 색깔과 포인터를 변경해야 한다. 포인터를 변경하기 위해 회전을 사용하고, 이것으로 이진 검색트리 특성을 보전한다. ✏️삽입/삭제 과정에서 노드의 추가/삭제 ..