Logical vs Physical Address

• logical address=(virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 logical address임
• pysical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩
  • 주소를 결정하는 것
  • symbolic address(ex. 변수 선언) -> logical address -> physical address
  • logical에서 Physical로 넘어가는 시점은 언제인가?

주소 바인딩 (address binding)

• compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경 시 재 컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
  • 현대에는 쓰이지 않는 방식(?확실하지 않음)
• load time binding
  • loader의 책임 하에 실행 시작 지점에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
• Execution(Run) time binding (=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
  • 하드웨어적인 지원이 필요
    • ex. base and limit refisters, MMU

Memory-Management Unit (MMU)

• Dynamic Relocation
  
• Hardware(MMU) Support for address Translation
  
  • relocation register ( = base register) : 접근할 수 있는 물리적 메모리 주소의 최솟값
  • limit register : 논리적 주소의 범위
• MMU (memory-management unit)
  • 운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터
  • local address를 physical address로 매핑해 주는 hardware device
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register ( = relocation register)의 값을 더한다.
• user program
  • logical address만을 다룬다
  • 실제 physical address를 볼 수 없으며 애초에 알 필요가 없다

몇 가지 용어

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 Load하는 것
• memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)
• loading : 메모리로 올리는 것

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 떄 유용
• 운영체제의 지원 없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 '수작업'으로 프로그래머가 구현
  • manual Overlay
  • 프로그래밍이 매우 복잡
• dynamic loading과 같은 의미이며, 더 이전에 쓰인 개념

Swapping

• swapping
  • 프로세스를 일시적으로 메모리에서 backing store로 '모두' 쫓아내는 것
• Backing store (=swap area)
  • 디스크
    • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• swap in / swap out
  • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm
    • priority가 낮은 프로세스를 swapped out 시킴
    • Priotiry가 높은 프로세스를 메모리에 올려 놓음
  • compile time 또는 load time binding 원래 메모리 위치로 swap in 해야하는 비효율이 존재함
  • run time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있어 효율적임
  • swap time은 대부분 transfer time (swap되는 양에 비례하는 시간)임 (seek time X)

Dynamic Linking

• Linking을 실행시간(execution time)까지 미루는 기법
• Static Linking ( = static library )
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (ex. printf 함수의 라이브러리 코드)
• Dynamic Linking ( = shared library ) (.so, .dll와 같은 실행 파일)
  • 라이브러리가 실행 시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation (연속 할당)
    • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
    • Fixed partition allocation
    • variable partition allocation
  • Noncontiguous allocation (불연속 할당)
    • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging
    • Segmentation
    • Paged Segmentation

Contiguous allocation

• 1. 고정 분할 방식
  • 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
  • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
  • 분할당 하나의 프로그램을 적재할 수 있음
  • 융통성이 없음
    • 동시에 메모리에 load되는 프로그램의 수가 고정됨
    • 최대 수행 가능 프로그램 크기 제한
  • 내부 조각(internal fragmentation) 발생 : 프로그램 B에 할당되었지만 사용되지 않는 공간이 생겨 메모리가 낭비된다 (물론 외부 조각도 발생함)
• 2. 가변 분할 방식
  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법이 필요
  • 내부 조각은 발생하지 않지만 여전히 외부 조각 발생
• 외부 조각
  • 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
• 내부 조각
  • 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간
• Hole
  • 가용 메모리 공간
  • 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
  • 프로세스가 도착하면 수용가능한 hole을 할당
  • 운영체제는 다음의 정보를 유지
    • 할당 공간
    • 가용 공간(hole)

Dynamic Storage-Allocation Problem

비어있는 hole이 여러개 있다면 다음 프로세스는 어느 곳에 적재시켜야할까?

• 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
• First-fit
  • size가 n이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • size가 n이상인 가장 작은 hole을 찾아서 할당
  • hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
• Worst-fit
  • 가장 큰 hole에 할당
  • 역시 모든 리스트를 탐색해야함
  • 상태적으로 아주 큰 hole들이 생성됨

compaction

• 외부 조각 문제를 해결하는 한 가지 방법
  • 외부 조각이 프로그램 크기보다 분할의 크기가 작아서 발생하는 문제라면, 흩어져있는 외부 조각들을 한 데 모으자 !
• 사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 마드는 곳
• 매우 비용이 많이 드는 방법
• 최소한의 메모리 이동으로 compaction하는 방법은 매우 복잡한 문제이다.
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치가 가능해야하므로 run time binding에서만 수행된다