메모리 관리[OS]

08 메모리 관리

용어

• 블럭\(_{block}\)
  • 보조기억장치와 주기억장치간의 데이터 전송 단위
  • 크기 : 보통 1 KB내외 (128B ~ 4KB)
• 워드\(_{word}\)
  • 주기억장치와 프로세서 레지스터간의 데이터 전송 단위
  • 크기 : 보통 16 비트 ~ 64 비트

프로세스의 주기억장치 사용

• 새로운 프로세스 생성 시
  • 주기억장치 할당
  • 프로그램 코드, 데이터, 스택 등을 주기억장치에 적재

기억장치 계층 구조

레지스터 ↔ 캐시 ↔ 메모리 ↔ 저장소

배경

• CPU 스케줄링의 결과
  • CPU 사용률 향상
  • 사용자에 대한 컴퓨터의 반응 속도 향상
• 시스템 성능의 향상을 위해
  • 메모리에 여러 개의 프로세스를 적재 필요
• 프로그램의 실행과정
  • 프로그램은 디스크에 이진 실행 파일로 저장
  • 실행을 위해, 프로그램은 메모리에 적재하여 프로세스 내에 저장
  • 메모리관리 기법에 따라 프로세스는 실행되는 동안 디스크와 메모리 사이를 이동
  • 디스크 내의 프로세스는 실행되기 위해 입력큐에서 메모리로의 이동을 대기
• 입력 큐
  • 프로그램을 실행하기 위해 대기하는 디스크 상의 프로세스들의 집합

메모리의 구조

• 논리적 주소
  • 프로그래머가 프로그래밍에 사용하는 공간
• 물리적 주소
  • 실제 데이터나 프로그램을 저장하는 공간

논리적, 물리적 주소

• 물리적 공간(물리적 주소)
  • 실제 데이터나 프로그램이 저장되는 공간
  • 메모리 칩 또는 디스크 공간으로 생성. 사용되는 단위는 바이트\(_{Byte}\)
  • 논리적 주소보다 크거나, 작거나, 같을 수 있음.
• 논리적 공간(논리적 주소)
  • 가상주소
  • 프로그래머가 프로그래밍에 사용하는 공간
  • 목적코드\(_{Object \ Code}\)가 저장된 공간과 프로그램에서 사용하는 자료 구조 등이 해당됨.
  • 논리적 메모리 크기는 각 시스템에서 정의한 워드의 길이에 따라 다름.
• 컴파일 시간과 적재시간 주소-바인딩 방법에서는 동일한 논리 및 물리 적인 주소를 생성
• 실행 시간 주소-바인딩 방법에서는 다른 논리(가상) 및 물리 주소를 생 성

메모리 장치의 주소 변환

• 메모리관리 장치MMU\(_{Memory \ Management \ Unit}\)
  • 논리(가상) 주소와 물리 주소의 연결시키는 하드웨어
• 메모리 관리 방식에 따라 여러 방식으로 구분
  • 고정 분할
  • 동적 분할(가변 분할)
  • 페이징\(_{Paging}\)
  • 세그먼트\(_{Segment}\)
  • 페이지화된 세그먼트 방식 등

메모리의 구조와 매핑

1. 컴파일 시간

   프로세스가 메모리에 적재될 위치를 컴파일 과정에서 알 수 있다면 컴파일러는 물리적 주소 생성 가능

2. 적재 시간

   프로세스를 메모리의 어디에 적재해야 할지 컴파일 과정에 알려주지 않으면 컴파일러는 대체 가능한 상대 주소 생성.

   상대 주소는 프로그램의 시작 주소가 0으로 생성되므로 최종 바인딩을 적재시간까지 연기.

   시작 주소가 변하면 단지 변화된 값을 반영하려고 사용자 코드를 재적재(정적 대치)

3. 실행 시간

   프로세스 실행 도중 메모리의 한 세그먼트에서 다른 세그먼트로 이동한다면 바인딩은 수행 시간 까지 연기(지연)

   이런 주소 체계는 기본 및 경계(한계) 레지스터등 특수 하드웨어의 지원 필요

   현재 범용 운영체제 대부분 실행 시간에 바인딩 방법

사용자 프로그램의 다단계 처리

• 주소 바인딩\(_{address \ binding}\)
• 논리적 주소 → 물리적 주소
• 사용자 프로그램들은 실행되기까지 여러 단계를 거침
• 명령어와 데이터의 주소가 위의 단계에 따라 다른 방법으로 표현될 수 있음
• 원시 프로그램: 주소는 일반적으로 기호로 표현 (int A;)
• 컴파일러: 기호 주소를 재배치 가능 주소로 바인딩 (예: 모듈 처음부터 14바이트)
• 링킹 편집기나 로더: 이 재배치 주소를 절대 주소로 바인드 (74014)

재배치 레지스터를 사용한 동적 재배치

항상 같은 위치의 메모리 주소를 사용할 수 없음.

→ 메모리 공간에서 빈 공간에 프로그램을 올리기 때문

때문에, MMU 방법에서, 재배치 레지스터의 값이 메모리로 보내지는 순간에 사용자 프로세스에 의해 생성되는 모든 주소에 더해진다.

위 그림의 동작 순서는 아래와 같다.

• CPU에서 논리 주소 346을 제공
• 재배치 레지스터에 저장된 14000을 제공받은 논리 주소에 더함
• 메모리의 물리 주소는 MMU + 논리 주소 = 14346번째를 참조하게 됨

이를 통해 프로그램이 실행될 때마다 메모리에 적재되는 위치가 달라져도 논리 주소를 사용하면 프로세스는 메모리에 접근이 가능해짐

주기억장치 구성 정책

• 주기억장치를 동시에 할당 받을 수 있는 프로세스의 수
  • 한 번에 한 사용자 프로그램만을 주기억장치에 적재 가능
    • 다중프로그래밍 정도 (multiprogramming degree)= 1
  • 동시에 여러 사용자 프로그램이 적재 가능
    • 다중프로그래밍 정도 (multiprogramming degree) = k
      • k개의 프로세스에게 동시에 주기억장치 할당 가능
• 각 프로세스에게 할당되는 주기억장치의 양
  • 다중프로그래밍 정도가 2 이상인 경우
  • 분할영역\(_{partition}\)의 크기에 따라서
    • 동일한 크기로 할당
    • 다른 크기로 할당
• 주기억장치 분할 방법
  • 다중프로그래밍 정도가 2 이상인 경우
  • 고정 분할\(_{fixed \ partition}\) 또는 정적 분할\(_{static \ partition}\)
    • 초기의 분할 형태를 이후 변형 않는 방법
  • 가변 분할\(_{variable \ partition}\) 또는 동적 분할\(_{dynamic \ partition}\)
    • 초기의 분할 형태를 이후 필요에 따라 변형시키는 방법
• 각 프로세스에게 할당된 분할영역의 교체 가능성
  • 실행중인 프로세스가 다른 분할 영역으로 이동하여 실행할 수 있도록 하는 정책
    • 유연성\(_{flexibility}\) 제공
    • 실행할 프로그램 코드가 재배치가능\(_{relocatable}\)해야 함
    • 컴파일러, 어셈블러, 링커/로더 등의 기능 지원 필요
  • 실행 중인 프로세스가 다른 분할 영역으로 이동하여 실행할 수 없도록 하는 정책
  • 할당 받은 분할 영역의 교체가 필요한 경우
    • 프로세스가 주기억장치를 완전히 반납 후 지연 상태\(_{suspended \ state}\)에 있다가 다시 주기억장치를 할당 받고자 할 경우에 발생
• 프로세스에게 할당되는 주기억장치 영역의 연속성
  • 연속\(_{contiguous}\) 할당 정책
  • 비연속\(_{discontiguous}\) 할당 정책
    • 관리상의 오버헤드
    • 최근의 주기억장치 관리 정책 경향

연속 메모리 할당\(_{Contiguous \ Memory \ Allocation}\)

• 연속적인 메인 메모리 공간에 할당
• 프로그램이 여유 메모리보다 큰 경우의 문제
• 낮은 오버헤드
• 메모리 분할
  • 운영체제 공간과 사용자 공간으로 나눔
• 메모리를 분할하여 여러 개의 프로그램을 수용하여 다중 프로그래밍 가능

단일프로그래밍 시스템

• 단일프로그래밍\(_{uniprogramming}\) 시스템
  • 항상 시스템 내에 하나의 프로세스만 존재
    • 모든 시스템 자원의 독점 사용 → 자원 관리 기법 단순(상호배제, 교착상태 문제 X)
  • 주기억장치 관리 기법이 매우 단순
    • 커널 공간을 제외한 모든 공간을 사용 → 사용하지 않는 공간 낭비 발생
  • MS-DOS

문제점

• 프로그램의 크기가 주기억장치의 가용 공간보다 클 경우
  • 해결

    • 중첩 구조\(_{overlay \ structure}\) 사용

      

      • 프로그램을 논리적 영역으로 나눔
      • 사용자 프로그램의 일부만 주기억장치에 적재/실행
      • 나머지는 필요할 경우 기존의 적재된 프로그램을 교체
      • 공통 루틴을 통해 중첩 영역에 사용되는 모듈들을 교체
  • 컴파일러, 링커, 로더의 지원 필요
• 사용자 프로세스로부터 커널을 보호하는 기법 필요
  • 해결

    • 경계 레지스터\(_{boundary \ register}\) 사용

      

      • 목적: 사용자 프로세스가 직접 커널 공간의 침범을 방지
      • 저장 내용: 커널 공간과 사용자 공간의 경계 주소 값
      • 방법: 사용자 프로세스가 주기억장치에 접근 시 주소 값을 비교 (경계 레지스터의 값보다 큰 경우 허용)
• 시스템 자원의 낭비/시스템 성능의 저하
  • 원인
    • 프로세스가 하나만 존재
      • 사용자 공간에 남는 공간 발생(메모리보다 작은 경우)
      • 사용되지 않는 프로그램 적재
      • 다른 프로세스를 실행하기 위해 교체 필요 → 교체비용 증가
      • 입출력 동작 시 프로세서는 유휴 상태
  • 해결
    • 다중 프로그래밍 기법 사용
      • 동시에 여러 프로그램들 적재되도록 함

고정 분할 다중 프로그래밍

• FPM: \(_{Fixed \ Partition \ Multiprogramming}\)
  • 주기억장치의 사용자 공간을 미리 여러 개의 영역으로 분할
  • 각 분할 영역에는 항상 하나의 프로그램만 적재 가능
    • 하나의 프로그램이 두 개 이상의 분할 영역 사용 불가
  • 분할 영역의 수가 k 일 경우
    • 시스템의 다중프로그래밍 정도 = 최대 k
  • 메모리를 고정된 크기로 분할

  • 고정분할 다중프로그래밍 시스템의 예

    

  문제점

  • 단일 프로그래밍에서 발생한 문제와 유사함
  • 사용자 프로그램의 크기가 최대 분할 영역의 크기보다 큰 경우
    • 중첩 구조를 사용하여 해결
  • 커널과 다른 프로세스들에게 할당된 분할 영역들에 대한 보호 필요
    • 경계 레지스터를 사용하여 해결
  • 각 분할 영역마다 낭비되는 공간 발생
    • 단편화\(_{fragmentation}\)
      • 공간이 낭비되는 현상
    • 내부 단편화\(_{internal \ fragmentation}\)
      • 분할 영역 내에서 발생하는 공간의 낭비 현상
    • 외부 단편화\(_{external \ fragmentation}\)
      • 분할한 용량보다 프로그램의 크기가 클 경우 분할한 용량에 적재하지 못함

다중프로그래밍 시스템에서의 커널 및 사용자 영역 보호

• 한계 및 재배치 레지스터 사용
• 각 논리 주소들은 한계 레지스터보다 작아야 한다
• MMU은 재배치 레지스터의 값을 더함으로써 논리 주소를 동적으로 매핑하여 메모리에 보낸다

고정 분할 다중프로그래밍 기법 요약

• 주기억장치 공간을 미리 분할
• OS 입장에서 주기억장치 관리 용이
• 오버헤드 작음
• 시스템 자원의 낭비 초래 가능
  • 분할 영역의 개수가 고정되므로 작은 규모의 프로세스들만 실행되는 경우 비효율적임
• 각 분할 영역마다 내부 단편화 현상 발생 가능

가변 분할 다중프로그래밍

가볍게 보기만 하면 될 듯

• VPM: \(_{Variable \ Partition \ Multiprogramming}\)
  • 프로세스들이 필요한 공간만 차지
  • 초기의 메모리는 사용자공간 전체를 하나의 블록으로 설정
  • 프로세스들의 활동에 따라 분할 형태를 동적으로 변화 시킴
  • 내부 단편화 방지
    • 프로세스가 필요한 크기만 기억공간 할당
  • 프로세스들은 연속 공간을 할당 받음
  • 관리 오버헤드 증가

메모리 배치 기법\(_{placement\ policies}\)

• 오른쪽 상태에서 16MB 프로세스 추가 적재
  • 분할영역 4와 6에 가능
  • 어디에 적재할 것인가?

    • 메모리 배치 기법에 따라서

      

• 목적
  • 프로세스가 추가로 적재될 때, 적재 가능한 공간이 두 곳 이상 존재
  • 어느 공간에 프로세스를 배치할지 결정

방법

• 최초 적합\(_{first-fit}\)
  • 상태 테이블의 처음부터 차례로 각 분할 영역 정보를 검사
  • 프로그램의 용량보다 크면서 비어 있는 첫 번째 분할 영역에 적재
  • 매우 단순하고 오버헤드 적음

  

• 최적 적합\(_{best-fit}\)
  • 모든 빈 분할 영역들을 검사하여 용량이 새로운 프로그램의 크기보다 큰 분할 영역들 중 가장 작은 용량의 분할 영역에 적재
  • 알맞은 분할 영역 찾는 시간이 오래 걸림
  • 용량이 큰 빈 공간들을 확보 가능
  • 단편화 현상 발생

  

• 최악 적합\(_{worst-fit}\)
  • 주기억장치 상태 테이블 전체를 검사
  • 모든 비어 있는 분할 영역들 중 가장 용량이 큰 분할 영역에 적재
  • 최적적합 방식의 단편화 현상 극소화 가능
  • 대용량의 빈 분할 영역 확보 불가능

  

• 순환 최초 적합\(_{next-fit}\)
  • 최초 적합 전략과 유사
  • 주기억장치 상태 테이블의 직전 검사 마지막 부분부터 검사 시작
  • 테이블의 마지막에 도달 시 다시 테이블의 처음부터 검사
  • 주기억장치의 각 영역 사용 빈도 균등화
  • 오버헤드 적음

VPM의 외부 단편화 문제 해결(별로 중요치 않음)

• 통합\(_{coalescing \ holes}\) 작업
  • 인접한 홀(빈 분할 영역)을 합병하여 큰 홀 생성
• 메모리 압축\(_{storage \ compaction}\) 작업
  • 모든 작업을 기억장치의 한쪽 끝으로 이동시켜 모든 빈 공간이 그 반대 방향으로 이동되어 하나의 큰 기억 장소를 만든다
  • 모든 빈 분할 영역들을 하나로 통합
  • 프로그램의 적재 공간이 부족할 경우 수행
  • 주기억장치 내의 모든 프로세스들의 재배치 작업 수행 필요
  • 많은 작업 시간 소요
    • 많은 시스템 자원을 소비하는 결과 초래

버디 시스템

• 단편화 현상을 해결하는 방법
• 큰 버퍼들을 반복적으로 이등분하여 작은 버퍼들을 만들며, 가능할 때마다 인접한 빈 버퍼들을 합치는 과정 반복, 버퍼를 나눌 때 각각을 서로의 버디라고 함

기억장소교체\(_{Swapping}\)

• 실행이 종료되지 않은 프로세스가 할당 받은 기억장소를 중간에 반납 받을 수 있도록 하는 기법
• 예
  • 순환 할당 프로세서 스케줄링 알고리즘을 가진 다중 프로그래밍 환경.
  • 프로세서에 할당된 시간이 지나면, 메모리 관리 장치가 방금 끝난 프로세스
    • (P1)를 보조기억장치로 이동, 다른 프로세스(P2)를 사용가능 공간 안으로 이동시킴.

  

• 롤인\(_{Roll-in}\), 롤 아웃\(_{Roll-out}\)
  • 낮은 우선순위 프로세스는 높은 우선순위 프로세스가 적재되어 실행될 수 있도록 스왑 아웃
• 스왑 과정
  • 주소 바인딩 방법에 따라 다름.
  • 바인딩이 어셈블 시간이나 적재시간에 이루어지면 프로세스는 다른 위치로 이동 불가
  • 수행시간에 바인딩이 이루어지면 교체 가능
• 스와핑 시간
  • 대부분은 전송 시간
  • 전체 전송 시간은 스왑되는 총 메모리 양에 직접적으로 비례
  • 효과적인 프로세서 사용을 위해 각 프로세스에 대한 수행시간이 교체시간 보다 길어야 함