[CS기초] 7주차 개념 정리

7주차 개념 정리

아래의 내용을 코드 블럭 우측 상단의 Copy 버튼을 눌러 복사한 뒤, 퀴즈 로봇(신명훈 학우 제작)의 프롬프트에 붙여넣기하면 핵심 개념들에 대한 퀴즈를 풀어볼 수 있습니다.

 

□ 힙 정렬
힙의 특성을 이용하여 정렬하는 알고리즘
■ 힙의 특징
	• 힙은 '부모의 값이 자식의 값보다 항상 크다'를 항상 만족하는 완전 이진 트리 (최대 힙)
	• '크다'가 '작다'로 바뀌어도 성립 (최소 힙)
	• 힙에서 최댓값(또는 최솟값)은 항상 루트에 위치한다
	• 형제 노드 간에는 대소 관계를 따지지 않는다. (부모-자식 관계만 만족하면 됨)

■ 힙 정렬 과정
	1. 루트 노드를 삭제한다. 루트 노드는 마지막 원소가 대체한다.
	2. 이후 규칙을 만족할 때까지 힙을 재조정한다.
		a. 최대 힙 기준, 루트 노드를 두 자식 중 더 큰 원소와 교체한다.
		b. 교체 후에도 자식 값이 더 크다면 새로운 두 자식 중 더 큰 원소와 교체한다.
		c. 자식 값이 작거나 리프 위치에 도달하면 재조정을 끝낸다
	3. 힙이 빌 때까지 1~2의 과정을 반복한다.
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 가상 메모리(Virtual Memory)와 페이징(Paging)
■ 가상 메모리
물리 메모리의 한계를 극복하고, 각 프로세스마다 독립적인 메모리 공간을 제공하기 위한 운영체제의 메모리 관리 기법.
물리 디스크 일부를 마치 논리적인 메모리처럼 활용함으로써 이를 구현한다.
▶ 가상 메모리의 핵심 목적
	• 추상화
	• 보호성
	• 효율성

■ 페이징
가상 메모리를 작은 고정 크기 블록인 페이지(Page)로 나누고,
물리 메모리 역시 동일한 크기의 프레임(Frame)으로 나눠 매핑하는 방식
▶ 페이징의 동작 원리
	1. 프로세스가 메모리를 페이지 단위로 요청
	2. 운영체제는 각 페이지를 물리 메모리의 빈 프레임에 할당
	3. MMU가 페이지 테이블을 통해 가상 페이지 주소를 물리 프레임 주소로 변환해 메모리에 접근
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 동적 메모리 할당 (힙, sbrk, malloc, free)
■ 동적 메모리 할당
프로그램 실행 도중에 필요한 메모리 크기를 결정하고, 이를 운영체제로부터 요청하여 사용하는 것
▶ 힙(Heap) 영역
프로그램 메모리 영역 중 하나로, 동적 할당을 위해 사용되는 공간. 아래에서 위로 확장된다.
	• 명시적하고 할당(malloc)하고 해제(free)해야 한다.
	• 사용 중 메모리 누수와 단편화 문제가 발생할 수 있다
▶ sbrk(intptr_t increment)
힙 영역의 끝 주소를 증가(확장)시키는 시스템 호출 함수
	• 전통적인 메모리 할당 방법으로, increment만큼 데이터 세그먼트(힙)의 크기를 늘린다
	• sbrk(0)은 현재 힙의 끝을 반환한다
▶ malloc과 free
	• malloc(size_t size): size 바이트만큼 힙에서 메모리를 할당하고 그 포인터를 반환하는 함수
		○ 필요한 크기의 블록을 찾아 반환하거나, 적절한 블록이 없으면 sbrk로 힙을 확장
		○ 실패 시 NULL 반환
	• free(void *ptr): malloc 등으로 할당된 메모리 블록의 주소를 받아 이를 해제하는 함수
		○ 이미 해제된 메모리를 다시 해제(double free)하면 안됨
		○ 해제 후 해당 포인터 사용시 use-after-free 에러 발생 -> NULL로 초기화해줘야 함
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 메모리 단편화(Memory Fragmentation)
프로그램 실행 중 메모리를 동적으로 할당하고 해제하는 과정에서 메모리가 비효율적으로 조각나거나,
공간을 제대로 활용하지 못하게 되는 현상.
■ 메모리 단편화의 종류
▶ 외부 단편화(External Fragmentation)
	• 사용 가능한 메모리 공간이 작은 크기로 여러 곳에 흩어지게 되는 현상
	• 총 사용 가능 메모리는 충분하지만, 연속적인 공간이 부족해 할당에 실패하는 문제 발생
▶ 내부 단편화(Internal Fragmentation)
	• 메모리 블록 내부에 낭비되는 공간이 생기는 현상
	• 할당된 메모리 블록이 실제 요구된 크기보다 커서 남는 공간이 생김
	• 주로 고정 크기 메모리 블록을 사용하는 할당 방식에서 발생

■ 메모리 단편화의 해결 방법
	• 압축(Compaction)
	• 페이징(Paging)
	• 세그먼테이션(Segmentation)  ※ Segmentation Fault와 관련 없음
	• 풀링(Pooling)
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 메모리 할당 정책 (Memory Allocation Policies)
사용 가능한 메모리 블록들 중 요청된 크기에 가장 적합한 블록을 선택하는 전략
■ First Fit (최초 적합)
메모리를 앞에서부터 탐색하여 요청한 크기 이상의 첫 번째 빈 공간을 찾아 할당하는 방법
	• 탐색 시간이 짧아 빠른 할당이 가능
	• 다만, 메모리 앞부분에 단편화가 집중될 수 있음

■ Next Fit (다음 적합)
이전 할당이 이루어진 위치에서부터 다음으로 넘어가며 요청 크기 이상의 첫 번째 빈 공간을 찾아 할당하는 방법
	• 탐색을 고르게 하여 단편화가 집중되는 현상 완화 가능
	• 메모리 전체를 골고루 사용 가능하지만, 오히려 전체적인 공간 효율성이 떨어질 수 있음
		○ 단편화가 골고루 생겨버리는 문제가 발생할 수도 있음

■ Best Fit (최적 적합)
요청된 크기를 만족하는 빈 공간 중 가장 크기가 작은 빈 공간을 찾아 할당하는 방법
	• 메모리 공간 낭비가 가장 적고 효율적
	• 빈 공간 탐색 시간이 길어져 성능이 저하될 수 있음
────────────────────────────────────────────────────────────────────────────────────────────────────
□ Implicit Free List / Explicit Free List
■ Implicit Free List (암시적 가용 리스트)
모든 블록이 포인터 없이 암묵적으로 연결되어,
메모리 블록 각각의 크기 정보를 통해 다음 블록 위치를 추측하면서 순회하는 구조.
	• 힙 전체를 순회하면서 할당된 블록과 가용 블록 모두를 거치면서 할당이 가능한지 검사한다
	• 구조가 간단하고 관리가 쉽지만, 빈 블록 탐색 시 성능이 저하될 수 있음

■ Explicit Free List (명시적 가용 리스트)
free block끼리만 포인터(pred, succ)를 사용해 명시적으로 연결되어, 포인터를 통해 free block만 순회하는 구조.
	• 필요 시 할당되지 않은 free 리스트만을 빠르게 탐색해 할당이 가능한지 검사한다
	• 탐색 속도가 매우 빠르지만, 포인터 공간을 추가로 소모하고 free list의 관리가 필요함
────────────────────────────────────────────────────────────────────────────────────────────────────
□ Demand-Zero Memory
프로그램에 메모리를 요청할 때, 실제 메모리 페이지를 즉시 할당하지 않고,
실제 접근하는 순간에 초기화된 메모리를 제공하는 메커니즘
■ 작동 방식
	1. 프로세스가 메모리 공간을 요청
	2. 운영체제는 물리 메모리를 바로 할당하지 않고, 가상 메모리 상의 해당 주소를 '존재하지 않는 페이지'로 예약
	3. 프로세스가 해당 가상 메모리 영역에 처음 접근
	4. 해당 가상 메모리에 매핑된 물리 메모리가 없으므로 Page Fault 발생
	5. 운영체제가 개입하여 0으로 초기화된 깨끗한 물리 페이지를 할당하고, 해당 가상 주소에 매핑
	6. 이후 접근이 정상적으로 이루어짐
■ Demand-Zero의 필요성
	• 효율성 (물리 메모리 절약 가능)
	• 보안성 (이전 사용 값이 없는, 초기화된 메모리 제공)
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 시스템 콜 (System Call)
시스템 자원에 직접 접근할 권한이 없는 사용자 프로세스가,
해당 권한이 필요한 작업을 운영체제에게 요청하는 공식적인 인터페이스
■ 시스템 콜의 동작 과정
	• 사용자 모드에서 요청 -> 커널 모드 진입 -> 요청 처리 -> 사용자 모드 복귀

■ 시스템 콜의 필요성
	• 보안성 (임의의 하드웨어 조작 방지)
	• 안정성 (하나의 프로세스 오류로부터 전체 시스템 보호)
	• 일관성 (모든 프로세스가 동일한 인터페이스를 통해 자원을 사용)
────────────────────────────────────────────────────────────────────────────────────────────────────
□ DMA (Direct Memory Access)
CPU의 개입 없이,
DMA 컨트롤러가 대신 메모리와 I/O장치(디스크, 네트워크 등) 간에 직접 데이터를 주고받게 하는 메커니즘
■ DMA의 필요성
	• CPU는 고속, 고가치의 연산과 제어 작업에 최적화된 자원
	• 그런데 메모리-I/O장치 간 데이터 복사는 저속, 저가치의 반복적인 작업에 불과
	• 이를 CPU가 직접 처리하게 되면, 보다 중요한 작업이나 제어에 자원을 쓸 수 없게 되어 전체 시스템 효율이 저하됨

■ DMA의 동작 방식
	1. CPU가 DMA 컨트롤러에게 데이터 전송 작업 지시
	2. DMA 컨트롤러가 메모리와 I/O장치 간 데이터 전송을 직접 수행
	3. 전송 완료 후, DMA 컨트롤러가 CPU에 인터럽트를 발생시켜 완료를 알림
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 이더넷(Ethernet)
MAC 주소를 이용해 컴퓨터 간 데이터를 정확히 전송하는,
LAN 구축의 기본이 되는 표준 유선 통신 규약(프로토콜)
■ 이더넷의 특징
	• 프레임 기반 통신
	• MAC 주소 사용
	• CSMA/CD 기술 (충돌 감지 방식 통신. 현재는 스위치 방식을 사용)
	• 속도 발전 (초기 10Mbps. 현재는 10Gbps 이상)
	• 물리 매체 (초기 동축 케이블. 현재는 UTP 케이블(랜선)을 주로 사용)