0. Introduction

• 해당 내용은 운영체제와 정보기술의 원리 -반효경 지음- 와 kocw 이화여자대학교 운영체제 - 반효경 교수 -를 보고 정리한 내용이다.
• 정확하지 않은 내용이 있다면 말씀해주시면 감사하겠습니다.

• 이번 chapter 내용인 메모리 관리는 물리적인 메모리 관리로, 주요 내용은 address binding이다.
• address binding에서의 OS의 역할은 없고, 다 HW가 해야한다.
• address binding을 할 때마다 OS에게 CPU 제어권을 양도해도, 결국 물리적 메모리에 instruction을 실행하는 건 CPU다. 그래서 HW가 해야한다.

1. 주소(address) 바인딩

1.1 주소란??

• 서로 다른 위치를 구분하기 위해 사용하는 일련의 숫자
• 크게 논리적 주소와 물리적 주소로 나뉠 수 있다.

• Memory는 주소를 통해 접근하는 저장장치다.
• 컴퓨터 시스템은 32bit 혹은 64bit의 주소체계를 사용하는데,
  • 32bit는 2^(32) 가지, 64bit는 2^(64) 가지의 서로 다른 메모리 위치를 구분할 수 있다.
• byte 단위로 메모리 주소를 부여한다.

1.2 논리적 주소, 물리적 주소

• 논리적 주소(logical address, virtual address)란?

  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address
    • Why? 물리적 메모리에 올라오는 위치는 달라도 코드 상의 내용은 compile 시 내용.

• 물리적 주소(physical address)란?

  • 메모리에 실제로 올라가는 위치
  • 물리적 주소의 낮은 주소 영역에는 kernel이 올라간다.
  • 물리적 주소의 높은 주소 영역에는 user process들이 올라간다.

• 프로세스가 실행되기 위해서

  • 해당 프로그램이 물리적 메모리에 올라가 있어야 한다.
  • 해당 논리적 주소가 물리적 메모리의 어느 위치에 매핑되는지 확인해야 한다.

1.3 주소 바인딩(address binding)

logical address를 physical address로 연결시켜서, physical address를 결정하는 작업

• Symbolic address –(compile)–> Logical address –(address binding)–> Physical address

• 주소 바인딩 방식 3가지: 물리적 메모리 주소가 결정되는 시기에 따라 분류된다.

  • 컴파일 타임 바인딩(compile time binding)
  • 로드 타임 바인딩(load time binding)
  • 실행시간 바인딩(execution time binding or run time binding)

    방식 이름	compile time binding	load time binding	run time binding
    시기	컴파일 시	프로그램 실행이 시작 시 (변경 가능 X)	프로그램 실행이 시작 시, (변경 가능 O)
    swapping 효과	좋지 않음	좋지 않음	좋음

• Compile time binding

  • 컴파일 시, 논리적인 주소와 물리적인 주소 다 생성된다.
  • compiler는 절대 코드 를 생성한다.
    • 그래서 program이 올라가 있는 물리적 메모리의 시작위치를 변경할려면 컴파일을 다시 해야 한다.
  • 물리적 주소의 0번지부터 시작한다.
  • 현대의 시분할 컴퓨터 환경에서는 잘 사용하지 않는 기법

• Load time binding

  • 컴파일 시에는 논리적인 주소만 결정된다.
  • 이를 실행하고 나서, 메모리가 비어있는 곳부터 올린다.
  • 로더(loader)의 책임 하에 물리적 메모리 주소 부여
    • Loader: user program을 memory에 적재시키는 프로그램
  • compiler가 재배치 가능 코드 를 생성한 경우 가능

• Run time binding

  • Load time binding 처럼 실행 시, physical address가 생성된다.
  • 실행을 시작한 후에도 물리적 메모리상의 위치(물리적 주소)를 옮길 수 있는 방식
  • CPU가 주소 참조 시, address mapping table을 이용해 원하는 데이터가 물리적 메모리의 어느 위치에 존재하는지 확인한다.
  • MMU(Memory Management Unit) 라는 하드웨어적 지원이 필요

1.4 MMU 기법(MMU scheme)

기준 레지스터를 사용하여 logical에서 physical address로 mapping해주는 HW device

• 가정

  • 프로그램의 주소 공간이 메모리의 한 장소에 연속적으로 적재되는 걸 가정한다.

• MMU scheme

  • 사용자 프로세스가 CPU에서 수행되여 생성해내는 모든 논리적 주소값에 대해 base register(= relocation register) 의 값을 더하여 물리적 주소값을 얻어낸다.
  • base register = CPU가 사용하려는 프로세스의 물리적 메모리 시작 주소

• user program

  • logical address 만을 다룬다.
  • 실제 physical address 를 볼 수 없으며, 알 필요가 없다.

• 예시

  • CPU가 논리적 주소: 123번지 정보를 요청
  • 기준 레지스터(=재배치 레지스터): 23000
  • 물리적 주소 = 123 + 23000 = 23123
  • 물리적 주소 23123번지에서 CPU가 요청한 정보를 찾는다.
  • 논리적 주소란 기준 레지스터로부터 얼마나 떨어져 있는지를 나타내는 것

• 동일한 논리적 주소

  • 프로세스는 각 자신만의 고유한 주소 공간을 가진다.
  • 그래서 동일한 논리적 주소라고 할 지라도, 서로 다른 내용을 담는다.
  • MMU 기법에서 프로세스가 바뀔 때마다 기준 레지스터의 값을 바뀌는 프로세스에 해당되는 값으로 재설정한다.

• 메모리 보안

  • Problem
    • 가상 메모리에 기준 레지스터를 더했을 때, 해당 프로세스의 주소 공간을 벗어나는 경우, 다른 프로세스 영역에 침범하거나, kernel 영역을 변경해 치명적인 결과를 초래할 수 있다.
  • Solution
    • 한계 레지스터(limit register) 를 사용하여, 프로세스 자신의 주소 공간을 넘어서는 메모리 참조를 하는지 확인한다.
      • 한계 레지스터(limit register): 논리적 주소의 범위
    • 벗어날 경우, trap을 발생시켜 해당 프로세스를 강제종료시킨다.

2. 메모리 관리와 관련된 용어

2.1 동적 로딩(Dynamic loading)

• 다중 프로그래밍 환경에서 메모리를 효율적으로 사용하기 위한 기법
• 프로세스의 주소 공간 전체를 메모리에 다 올려놓는 게 아닌, 해당 부분이 불릴 때에마다 그 부분만 메모리에 적재하는 방식: 연속 할당에 해당되지 않는다.

• loading: 물리적 메모리로 올리는 것
• 부분적으로만 올리는 이유
  • 실제 프로그램의 코드 중 상당 부분 = 가끔씩 사용하는 방어용 코드 -> 주소 공간 전체 loading -> 메모리 낭비 초래
• 동적 로딩 -> 더 많은 프로그램 로딩 가능 -> 메모리 이용 효율성 향상
• 운영체제 지원 없이 개발자가 코드로 구현 가능하고, OS는 라이브러리를 통해 지원 가능

2.2 중첩(overlays)

메모리보다 큰 프로세스를 실행하기 위해서, 프로세스의 주소 공간을 분할해 실제 필요한 부분만을 메모리에 적재하는 기법

• 중첩과 동적 로딩의 차이점: 목적
  • 동적 로딩의 목적: 메모리에 multi-process를 실행하기 위한 용도
  • 중첩의 목적: single-process를 실행하기 위한 환경에서 메모리 용량보다 큰 프로세스를 실행하기 위한 용도
  • 운영체제의 지원 없이 프로그래머가 직접 구현해야 한다.

2.3 스와핑(Swapping)

프로세스의 주소 공간 전체를 메모리에서 backing store로 쫓아내는 것

• 스왑 영역(Swap area)란??

  • 다른 말로 백킹 스토어(backing store) 라고 한다.
  • 디스크 내의 파일 시스템과는 별도로 존재하는 일정 영역으로,
    • 파일 시스템 은 전원이 나가도 유지되어야 하는 비휘발성 저장공간이지만,
    • 스왑 영역 은 프로세스가 수행 중인 동안에만 디스크에 일시적으로 저장하는 휘발성 영역이다.
    • 프로세스 실행이 종료되면 메모리에서 디스크로 내려놓는다. (swap out)
  • 그리고, 다음과 같은 특징을 가져야 한다.
    • 다수의 사용자 프로세스를 담을 수 있을 만큼 충분히 큰 저장 공간이다.
    • 어느 정도의 접근 속도가 보장되야 한다.

• Swap in & out

  • Swap in: disk -> memory 올리는 작업
  • Swap out: memory -> disk 내리는 작업

• 스와핑이 일어나는 과정

  • 첫 번째: Swapper라 불리는 중기 스케쥴러 에 의해 swap out할 process를 선정.

    • 선정 기준: priority
      • priority가 낮은 프로세스를 swap out
      • priority가 높은 프로세스를 swap in

  • 두 번째: 선정된 process를 메모리에 올라간 주소 공간 전체 내용을 disk swap area로 아웃시켜서 메모리의 프로세스 수를 조절한다.

    • 즉, Swapper로 멀티 프로그래밍 정도(degree of multi-programming)를 조절한다.

    • 메모리에 많은 프로그램이 올라오면 할당되는 메모리 양이 지나치게 적어져, 시스템 전체 성능이 감소되기 때문이다.

  • Swap time

    • Swap time: swapping에 소요되는 시간
    • Transfer time: 데이터를 읽고 쓰는 전송 시간
    • Swap time은 디스크를 탐색하는 것보다 disk sector에서 transfer time이 대부분을 차지한다.
    • 즉, transfer time 은 swap 되는 양에 비례

• address binding에 따른 swapping

  • compile time binding & load time binding: 다시 swap in 시, 원래 존재하던 메모리 위치로 다시 올라가야 해서 swapping의 효과가 좋지 않다.
  • runtime binding은 추후 빈 메모리 영역 아무 곳에나 프로세스를 올리기 때문에, swapping으로 인한 효과가 좋다.

2.4 동적 연결(Dynamic linking)

• 연결(linking)이란??

  • 목적 파일(object file)과 이미 컴파일된 라이브러리 파일을 묶어서 하나의 실행파일을 생성하는 과정
    • Object file: 프로그래머가 작성한 source code를 컴파일하여 생성된 파일

• 정적 연결(static linking)과 동적 연결(dynamic linking)의 차이: 첫 번째

  • 정적 연결: 프로그래머가 작성한 코드와 라이브러리가 모두 합쳐진 상태에서 실행파일이 생성되는 방식으로, 연결된 상태에서 실행파일을 생성하는 방식

    • 라이브러리가 프로그램의 실행 파일 코드에 포함되어, 실행파일의 크기가 상대적으로 크다.

  • 동적 연결 : 라이브러리를 포함하지 않는 생성된 실행 파일이 라이브버리 호출 시 , 연결이 이뤄지는 방식

    • 그래서 라이브러리의 위치를 찾기 위해 라이브러리 호출 부분에 stub 이라는 작은 코드를 둔다.
    • 이 stub을 통해 해당 라이브러리 루틴이 메모리에 이미 존재하는지 먼저 살펴본다.
      • 메모리에 이미 존재 -> 그 메모리 위치에서 직접 참조
      • 메모리에 없음 -> 디스크에서 읽어옴

• 정적 연결(static linking)과 동적 연결(dynamic linking)의 차이: 두 번째

  • 정적 연결: 첫 번째 차이점으로 인해 동일한 라이브러리를 각 프로세스가 개별적으로 메모리에 적재해야 하므로, 물리적 메모리가 낭비된다.

    • 동일한 라이브러리 코드여도 각 프로세스의 주소 공간에 독자적으로 존재하는 코드이므로 별도의 적재가 필요하다.
    • 그 결과, 메모리 낭비가 심하다.

  • 동적 연결: 라이브러리를 호출하면 되므로 메모리에 한 번만 적재하여 낭비 X

    • 공용으로 쓰는 라이브러리를 shared library 라 한다.

• Summary

  특징	정적 연결	동적 연결
  연결 시기	실행 파일 생성 전	실행 파일 생성 후, 호출
  적재 횟수	각 프로세스 개별적으로	메모리에 한 번만
  실행 파일에 라이브러리 포함 유무	O	X
  메모리 낭비 발생	O	X

3. 물리적 메모리의 할당 방식

• 물리적 메모리 할당 방식과 사용자 영역 관리 방식은 다음과 같다.

3.1 연속할당(Contiguous allocation) 방식

프로세스를 메모리에 올릴 때, 주소 공간을 여러 개로 분할하지 않고, 메모리의 한 곳에 연속적으로 적재하는 방식

• 이에 해당하는 자료구조의 예에는 배열(array) 가 존재한다.
• 고정분할 방식 과 가변분할 방식 으로 나눠진다.
• 연속적으로 할당하기 때문에 물리적 메모리 주소로 mapping 하는 게 쉽다.
• 연속 할당 기법에서는 프로세스의 주소 공간 전체를 담을 수 있는 가용공간을 찾아야 한다.
  • 가용 공간(hole) : 사용되지 않은 메모리 공간으로, 메모리 내의 여러 곳에서 산발적으로 존재할 수 있다.
• 이 가용공간(hole)은 물리적 메모리 내부에 산발적으로 존재하기 때문에, 효율적으로 관리하기 위해서 운영체제는 사용 중인 공간과 가용 공간에 대한 정보를 각각 유지한다.

3.1.1 고정분할(Fixed partition) 방식

물리적 메모리를 영구적인 분할(partition)로 미리 나누어두고, 각 분할에 오직 하나의 프로세스만을 적재해 실행하는 방식

• 이에 따라 다음과 같은 특징을 가진다.

  • 미리 나누는 분할의 크기는 다 동일할 수도 있고, 다르게 할 수도 있다.
  • 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되었다.
  • 수행 가능한 프로그램의 최대 크기 또한 제한된다.
  • 외부 조각(external fragmentation)과 내부 조각(internal fragmentation)이 발생한다.

• 외부 조각과 내부 조각에 대해 알아보자.

  조각 종류	외부 조각	내부 조각
  When	프로그램 크기 > 분할 크기	프로그램 크기 < 분할 크기
  할당 유무	할당하지 않은 조각	할당된 조각

  • 외부 조각:
    • 프로그램의 크기가 분할 크기보다 커서 프로그램을 적재하지 못하여 발생하는 메모리 공간
    • 하지만, 분할 크기보다 작은 프로그램이 도착하면 이 외부조각에 적재할 수 있다.
  • 내부 조각:
    • 하나의 분할에 프로그램을 적재한 후, 남아서 사용되지 않는 메모리 공간
    • 남은 공간에 충분히 적재할 수 있는 프로그램이 있을지라도, 이미 할당된 조각이므로 다른 프로그램에 할당할 수 없다.

3.1.2 가변분할(Variable partition) 방식

• 미리 분할시키는 것이 아닌 프로그램이 실행될 때마다 메모리에 순서대로 차곡차곡 쌓는 방식
• 그래서, 분할의 크기, 개수가 동적으로 변한다.
• 현대의 컴퓨터가 사용하는 방식

• 분할의 크기를 프로그램 크기보다 일부러 크게 할당하지 않기 때문에, 내부조각이 발생하지 않는다.

• Problem 1:외부조각

  • 메모리에 존재하는 프로그램이 종료될 경우, 중간에 빈 공간이 발생하는데,
  • 이 공간이 새로 시작하는 프로그램보다 작을 경우 외부조각이 발생할 가능성이 있다.

• Solution 1: Compaction (윈도우에서 디스크 조각 모음이 이에 해당되는 방법)

  • 외부조각 같은 hole을 해결하는 방법으로 컴팩션(compaction) 을 사용한다.
    • Compaction이란???
      • 물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한 쪽으로 몰고, 가용 공간들을 다른 한쪽으로 모아서 하나의 큰 가용공간을 만드는 방법
  • 메모리 위치를 상당 부분 이동해야 해서 비용이 매우 많이 들기 때문에, 최소한의 메모리 이동으로 얻을려고 한다.
  • 또한, 수행 중인 프로세스의 물리적 메모리 위치를 옮겨야 하므로, 실행 도중 프로세스 주소를 동적으로 바꿀 수 있는 run time binding 방식을 지원하는 환경에서만 수행할 수 있다.

• Problem 2: 동적 메모리 할당 문제(Dynamic storage-allocation problem)

  • size가 n인 프로세스를 메모리 내 가용 공간 중 어떤 위치에 올릴 지 결정하는 문제

• Solution 2: 3가지

  • 아래 3가지 방법들 중 첫 번째와 두 번째가 속도와 공간 이용률 측면에서 효과적이다.
  • 최초적합(first-fit) 방법
    • size가 n 이상인 것 중 가장 먼저 찾아지는 hole에 프로세스를 할당하는 방법으로,
    • 시간적인 측면에서 효율적이다.
  • 최적적합(best-fit) 방법
    • size가 n 이상인 가장 작은 hole을 찾아 새로운 프로그램을 할당하는 방법으로,
    • 모든 hole의 리스트를 탐색하므로 시간적 오버헤드가 발생하지만,
    • 공간적인 측면에서는 효율적이다.
  • 최악적합(Worst-fit) 방법
    • 가장 크기가 큰 hole을 찾아 새로운 프로그램을 할당하는 방법으로,
    • 시간적 오버헤드가 발생하고, 가용 공간을 빨리 소진한다.

3.2 불연속할당(Noncontiguous allocation) 기법

물리적 메모리의 여러 위치에 분산되어 올라가는 메모리 할당 기법

• 이를 사용하는 자료구조의 예시로는 연결 리스트 가 있다.

• 프로그램을 분할하는 기준에 따라 여러 방법으로 나눠진다.

  • 페이징(paging) 기법: 동일한 크기로 나누어 메모리에 올리는 기법
  • 세그먼테이션(segmentation) 기법: 크기는 일정하지 않지만, 의미 단위로 나누어 메모리에 올리는 기법
  • 페이지드 세그먼테이션(paged segmentation) 기법: segmentation을 기본으로 한 후, paging 기법으로 나누어 메모리에 올리는 기법

• 그러면 다음 챕터에서 위 3가지 기법들에 대해 알아보자.

Reference

• 운영체제와 정보기술의 원리
• kocw 이화여자대학교 운영체제 - 반효경 교수 -