[중간정리] 7주차 - 페이징과 세그멘테이션, 메모리 할당 정책, DMA, C언어(포인터), 힙 정렬

페이징과 세그멘테이션

페이징 (Paging)

가상 메모리를 고정 크기의 블록인 페이지(Page)로 나누고, 물리 메모리도 같은 크기의 프레임(Frame)으로 구분하여 매핑하는 방식

• 장점
  • 외부 단편화(External Fragmentation)를 효과적으로 제거 가능하다
  • 메모리 관리가 단순해진다
  • 페이지 단위로 메모리 보호 및 공유가 용이하다
• 단점
  • 내부 단편화(Internal Fragmentation)가 발생할 수 있다
  • 페이지 테이블 관리에 추가적인 메모리가 필요하다

세그멘테이션 (Segmentation)

가상 메모리를 논리적 의미를 가진 가변 크기의 블록, 즉 세그먼트(Segment) 단위로 나누어 관리하는 방식 (예: 코드, 데이터, 스택 등)

• 장점
  • 프로그램의 논리적 구조에 맞게 메모리를 최적화하여 사용 가능하다
  • 세그먼트 단위로 메모리 보호 및 공유가 용이하다
• 단점
  • 외부 단편화(External Fragmentation)가 발생할 수 있다
  • 세그먼트별 크기와 위치를 관리해야 하므로 메모리 관리가 복잡해질 수 있다

 

메모리 할당 정책에 따라 블록 할당하기

문제 요구사항

메모리 블록: A (10), B (50), C (25), D (30), E (40)

메모리 요청: 1 (30), 2 (25), 3 (25), 4 (10)

정책 별 할당 순서

• First Fit: B - C - D - A
• Next Fit: B - C - D - E
• Best Fit: D - C - E - A

 

DMA (Direct Memory Access)

CPU의 중재 없이 DMA 컨트롤러를 통해 입출력 장치가 메모리와 직접 데이터를 주고받을 수 있도록 하는 메커니즘

DMA가 성능에 미치는 이점

• CPU의 부하가 감소하여 전체 시스템의 효율성이 증가한다
• 데이터 전송 속도가 향상되므로, 전반적인 시스템 응답 시간이 단축된다

 

C코드 (포인터) 문제 해결하기

#include <stdio.h> 
int main(int argc, char *argv[]) 
{ 
    int arr[2][3] = {1,2,3,4,5,6}; 
    int (*p)[3] = NULL; 
    p = arr; 
     
    printf("%d\n", *(p[0] + 1) + *(p[1] + 2)); 
    printf("%d\n", *(*(p + 1) + 0) + *(*(p + 1) + 1)); 
    return 0; 
}

문제 요구사항

해당 코드의 출력 구하기

문제 해석

• p는 3개의 int를 담고 있는 배열에 대한 포인터 (int (*)[3])
• arr은 타입이 int[2][3]이지만, 문맥상 첫 번째 행을 가리키는 int (*)[3] 으로 변환된다
  • 따라서 p = &arr[0]

1. p[0] = *(p + 0) = arr[0] 행의 시작 주소 = &arr[0][0] / 같은 방식으로 p[1] = &arr[1][0]
   • p[0] + 1 = &arr[0][1]
   • p[1] + 2 = &arr[1][2]
   • 참고로 p[2]는 할당한 유효 메모리 범위를 벗어나게 되므로 접근 금지
2. (p + 1) = &arr[1] 이고, *(p+1) 은 arr[1]의 첫 원소 주소, 즉 &arr[1][0]
   • *(p+1) + 0 = &arr[1][0] + 0 = &arr[1][0]
   • *(p+1) + 1 = &arr[1][0] + 1 = &arr[1][1]

정답 출력

8
9

 

 

힙 정렬

문제 요구사항

1 2 4 4 3 5 5 6 의 입력을 받아 힙 정렬을 할 때, 힙 정렬이 진행되는 과정을 배열로 표현하기

문제 해석

힙 정렬은 힙의 특성을 이용해 원소들을 나열하는 정렬 방식이다. 정렬을 시작하기 전, 먼저 힙 트리를 구성한다. 이후 루트를 삭제하고 이를 제일 마지막 원소로 대체한 뒤, 다시 힙 트리를 구성하는 것을 반복한다.

 

이때 정렬 과정 중 힙을 배열로 쉽게 나타내기 위해서는, 먼저 힙 트리를 그린 다음 계층마다 왼쪽에서 오른쪽으로 순서대로 적으면 된다. 예를 들어 위 문제 요구사항에서 받은 입력을 힙 트리로 변환한 뒤 배열로 표현하면 다음과 같다.

입력받은 데이터를 힙으로 표현한 배열

 정렬 결과

초기 데이터: 1 2 4 4 3 5 5 6

0회차: 6 5 5 4 3 2 4 1

1회차: 5 4 5 1 3 2 4 6

2회차: 5 4 4 1 3 2 5 6

3회차: 4 3 4 1 2 5 5 6

4회차: 4 3 2 1 4 5 5 6

5회차: 3 1 2 4 4 5 5 6

6회차: 2 1 3 4 4 5 5 6

final  : 1 2 3 4 4 5 5 6