[TIL] CSAPP 9장 공부2 - 동적 메모리 할당

728x90

1. 아침 문제 풀이

1. 1764번 - 듣보잡

import sys

N, M = map(int, sys.stdin.readline().split())
dic = {} #듣도 못한 사람 저장
for _ in range(N) :
    dic[sys.stdin.readline().strip()] = 1

count = 0
result = []
for _ in range(M) :
    b = sys.stdin.readline().strip() #보도 못한 사람
    if b in dic : # 딕셔너리에 키값으로 존재하면
        #듣도보도 못한 사람이다.
        count += 1
        result.append(b)

print(count)
result.sort()
for i in range(count) :
    print(result[i])

전에 풀었던 문제로 저번과 같이 시간 초과를 먼저 경험했다.
리스트를 사용하여 구현하니 시간 초과가 떴다.
예전에 list보다 dictionary가 시간 복잡도가 빠르다는 것을 공부했던 것같아서 dict을 사용하니 통과했다.

★ list 원소 탐색 시간 복잡도 ★
: 처음부터 리스트를 순차적으로 탐색하므로 O(n)
★ dictionary의 key 탐색 시간 복잡도 ★
:python에서 딕셔너리는 HashTable로 구현되어있다. 해시 함수를 사용하므로 O(1)

< 참고 >
https://velog.io/@kimwoody/Python-리스트와-딕셔너리의-주요-연산-시간-복잡도

2. 가상 메모리 정리

※ 같이 공부하는 분들과 이야기하다가 안다고 생각했지만 정리가 잘 안되어 있어 다시 한번 정리한다. ※

1. 등장 배경

RAM이 용량이 가장 큰 애플리케이션의 주소 공간보다 커야 실행이 가능했다.
얼마나 많은 메모리가 필요한지가 아니라 최소 얼마만큼의 메모리가 필요한지에 집중했다.
- 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에서 착안
- 메모리 접근은 순차적이고 지역화가 되어있어 필요한 만큼만 RAM에 올려두고 사용하자는 의견
- 나머지 올라가지 않은 것들은 DISK에 저장해 둔다.
쉽게 말하자면 보조기억 장치를 이용해 RAM의 용량이 충분한 것처럼 사용하는 것이다.
- 빠르고 작은 기억장치(RAM)을 크고 느린 기억장치(디스크)와 병합하여, 하나의 크고 빠른 기억장치(가상 메모리)처럼 동작!

🔗 전에 정리한 가상 메모리 : https://soo-note.tistory.com/68

🔗 참고 블로그 : https://ahnanne.tistory.com/15

3. 동적 메모리 할당

컴퓨터 프로그래밍에서 실행 시간동안 사용할 메모리 공간을 할당하는 것
< 참고 > https://ko.wikipedia.org/wiki/동적_메모리_할당

1. Heap 영역

프로그래밍 환경에서 원시 자료형이 아닌 보다 큰 크기의 데이터를 담고자 동적으로 할당하는 메모리 공간
메모리 할당을 요청하면 할당기 힙 공간 안에서 사용 가능한 곳을 찾아 예약을 해두어 다른 스레드나 프로그램이 사용하지 못하도록 한다.
bkr : 커널이 힙의 꼭대기를 가리키는 변수

🗒️ 정적 메모리 할당 🗒️

메모리의 크기가 하드코딩이 되어 있어 프로그램이 실행될 때 이미 해당 메모리의 크기가 결정

stack 영역에 할당된다.

프로세스가 시작할 때부터 끝날때 까지 유지

장점 : 운영체제에 의해 자동으로 공간 해제가 이루어져 메모리 누수와 같은 문제를 신경쓰지 않아도 된다.

단점 : 메모리의 크기를 나중에 조절할 수 없다. 동적할당에 비해 최대 메모리에 제약을 받는다.

< 참고 > https://ko.wikipedia.org/wiki/정적_메모리_할당

할당기
- 명시적인 할당
  - 명시적으로 할당된 블록을 반환해줄 것을 요구
  - malloc() 함수로 할당받은 메모리는 free()함수로 반환
- 묵시적인 할당
  - 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지 할당기가 검출할 수 있을 것을 요구
  - Garbage Collector
    - 동적 할당된 메모리 영역 가운데 더 이상 사용할 수 없게 된 영역을 탐지하여 자동으로 해제하는 기법
    - 더이상 사용할 수 없는 영역 = 어떤 변수도 가리키지 않게 된 영역
    - https://ko.wikipedia.org/wiki/쓰레기_수집_(컴퓨터_과학)
- 할당기 요구사항
  - 응용 프로그램은 각각의 가용 블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환 요청을 할 수 있다.
  - 어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬
  - 힙 영역에만 저장
  - 가용블록만 조작하거나 변경할 수 있다.
동적 메모리를 사용하는 이유
- 프로그램을 실제 실행시키기 전에 자료구조의 크기를 알 수 없는 경우들이 존재한다.
- 런타임에 동적으로 할당하여 메모리를 효율적으로 사용한다.

2. malloc

#include <stdlib.h>

void *malloc(size_t size);

return pointer or NULL;

블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size byte를 갖는 메모리 블록의 포인터 반환
반환값
- 메모리 할당에 성공하면, 할당된 메모리 블록의 포인터 반환 (8 byte)
- 실패하면, NULL반환 및 errno 설정
malloc함수는 할당받은 메모리를 초기화하지 않는다.
calloc : 할당받은 메모리를 0으로 초기화
realloc : 할당된 블록의 크기 변경

3. free

#include <stdlib.h>

void free(void *ptr);

할당된 힙 블록을 반환하는 함수
ptr : 할당된 블록의 시작을 가리킨다.

4. 단편화 (Fragmentation)

가용 메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다.

내부 단편화(Internal Fragmentation)
- 할당된 블록이 데이터 차제보다 클 때 발생
- 일정 크기의 페이지에 프로세스 할당 시, 프로세스의 크기가 페이지보다 작을 경우 발생
- 예를 들어 정렬 제한사항을 만족시키기 위해서 블록의 크기를 증가시켰을 경우 발생
- (블록의 크기 - 데이터의 크기)의 합 = 낭비되고 있는 메모리 크기
외부 단편화(External Fragmentation)
- 여유 공간이 여러 조각으로 나뉘는 현상
- 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용 블록은 없는 경우 발생

< 참고 >

🔗 https://jeong-pro.tistory.com/91

5. 메모리 할당 정책

1. first fit

가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택
장점 : 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다.
단점 : 리스트의 앞부분은 작은 가용 블록들을 남겨두는 경향이 있어 큰 블록을 찾는 경우에 검색 시간 증가

2. next fit

이전에 검색이 종료된 지점부터 가용 리스트를 검색한다.
이전 검색에서 가용블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안
장점 : first fit보다 매우 빠르다.
단점 : first fit보다 최악의 메모리 이용도를 가진다.

3. best fit

모든 가용 블록을 검사하며 크기가 맞는 가장 작은 블록 선택
장점 : 위의 두 정책보다 더 좋은 메모리 이용도를 가진다.
단점 : 힙을 완전히 다 검색해야한다.
힙을 모두 검색하지 않는 best-fit 정책을 단순화를 위한 Segregated Free List

6. 묵시적 가용 리스트(Implicit Free List)

블록 경계를 구분하고 할당된 블록과 가용 블록을 구분하는 데이터 구조 필요
Heap Block Format
- Header : 가용 상태를 나타내기 위해 최소 중요 비트 사용
- Date : 요구한 데이터
- Padding : optional, 외부 단편화를 극복하기 위한 할당기 전략 또는 정렬 요구사항을 만족하기 위해 사용

묵시적 리스트
- 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결
- 장점 : 단순하다
- 단점 : 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록 수에 비례한다.
- 더블 워드 정렬
  - 1 word = 4byte / 2 word = 8byte
  - 조건
    - 할당되는 블록의 크기는 항상 8의 배수
    - 블록 크기의 하위 3비트는 항상 0
가용 블록 분할
- 어느 한 블록을 선택했는데 크기가 잘 안맞는다.
- 만약 그 블록 전체를 사용하는 정책을 결정하면 내부 단편화가 발생한다.
- 선택된 가용 블록을 할당한 블록과 나머지 새로운 가용 블록으로 분할한다.
추가적인 힙 메모리 획득
- 할당기가 요청한 블록을 찾을 수 없다면 sork 함수를 호출하여 추가적인 힙 메모리 요청
오류 단편화(False Fragmentation)
- 할당기가 할당한 블록을 반환할 때 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 존재할 수 있다.
- 가용블록들이 인접해 있는데 서로 다른 블록으로 생각해 메모리 할당에 실패할 수 있다.
- 연결(Coalescing) : 인접 가용 블록들을 통합

CSAPP 그림  9.38 3워드의 데이터를 갖는 두개의 인접한 블록이 서로 다른 가용 블록으로 인식된다.

경계 태그(footer)
- 상수 시간에 이전 블록을 연결
- 각 블록의 끝부분에 footer 추가
- footer = 이전 블록의 헤더
- 단점 : header와 footer를 유지해야하므로 오버헤드가 발생할 수 있다.