Logical versus Physical Address

  • Logical address( = virtual address)
    • 프로세스마다 독립적으로 가지는 주소 공간
    • 각 프로세스마다 0번지부터 시작
    • CPU가 보는 주소는 logical address임
  • Physical address
    • 메모리에 실제 올라가는 위치

💡 주소 바인딩: 주소를 결정하는것
Symbolic Address(변수이름, 함수이름) → Logical Address → Physical Address

  • 그렇다면 논리 주소가 물리적인 주소로 결정되는 시점이 언제인가?

주소 바인딩(Address Binding) - 물리적인 메모리가 결정되는 시점

(* 현대의 OS는 논리주소가 담긴 실행파일이 통으로 메모리에 올라가지 않지만, 이 챕터에서는 그런 상황을 가정하여 설명)

3가지 바인딩 유형

컴파일러가 논리 주소가 부여된 실행파일을 생성하는 과정은 동일

  1. Compile time Binding → 현대의 컴퓨터 시스템에서는 거의 사용하지 않음
    • 물리적 메모리 주소가 컴파일 시 알려짐
    • 시작 위치 변경 시 재 컴파일
    • 컴파일러 코드는 절대코드(absolute code)생성
  2. Load time Binding
    • 실행이 시작 되서 메모리에 올라갈 때
    • Loader의 책임하에 물리적 메모리 주소 부여
    • 컴파일러가 재배치 가능 코드(relocatalbe code)를 생성한 경우 가능
  3. Execution time Binding(Runtime Binding)
    • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음(실행되는 도중 주소가 변경 될 수 있음)
    • CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
    • 하드웨어적인 지원이 필요
      • ex) base and limit registers, MMU

MMU(Memory-Management Unit)

Logical Address를 Physical Address로 맵핑해 주는 Hardware Device

  • MMU Scheme: 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다
  • limit register: 프로세스의 논리적 주소 범위 정보 저장
  • relocation register: 접근할 수 있는 물리적 메모리 주소의 최소값
  • 사용자 프로그램은 Logical Address만을 다루며, 실제 Physical Address를 볼 수 없으며 알 필요가 없다.

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 load 하는 것

  • memory utilization의 향상
  • 가끔씩 사용되는 많은 양의 코드의 경우 유용(ex. 오류 처리 루틴)
  • 운영체제의 특별한 지원 없이 프로그램 자체에서 구현가능(OS가 라이브러리를 통해 지원 가능)
  • Loading의 의미 → 메모리로 올리는 것
  • 주의: 운영체제가 관리하는 프로세스가 메모리에 올라갔다 다시 내려가는 동작(페이징 기법)이랑은 본질적으로 다름 → 하지만 요즘에는 용어를 혼용하기도 함

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 것

  • 프로세스의 크기가 메모리보다 클 때 유용
  • 운영체제의 지원 없이 사용자에 의해 구현
  • 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현
    • “Manual Overlay”라고도 일컫음
    • 프로그래밍이 매우 복잡

Swapping

프로세스 전체를 일시적으로 메모리에서 backing store로 쫓아내는 것

주의 : 페이징과는 프로세스 전체를 swap 한다는 점에서 본질적으로 다르지만, 용어를 혼용하기도 함

  • Backing store(swap Area): Disk
    • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장공간
  • Swap in / Swap out
    • 일반적으로 중기 스케줄러(swapper)에 의해 swap out시킬 프로세스 선정
    • priority based CPU scheduling algorithm
      • priority가 낮은 프로세스를 swapped out 시킴
      • priority가 높은 프로세스를 swapped in 시킴
    • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in을 해야함(그렇기 때문에 Runtime Binding에서의 효율이 더 좋다 → 빈 메모리 영역 아무 곳에나 올릴 수 있으므로)
    • swap time은 프로그램 전체를 스왑하는 큰 작업이기에, 대부분 transfer time(swap 되는 대상의 양에 비례하는 시간 ↔ seek time)이 차지

Dynamic Linking

Linking을 실행시간(execution time)까지 미루는 기법

  • Linking: 여러군데에 존재하는 파일들을 묶어서 실행파일로 만들어 내는 것

Static Linking

  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
    • ex) printf 함수의 라이브러리 코드

Dynamic Linking

  • 라이브러리가 실행시 연결됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요
  • SYN → shared library, 윈도우 - dll, 리눅스 - shared object

Allocation of Physical Memory

  • 메모리는 일반적으로 두 영역으로 나뉘어 사용
    1. OS 상주 영역
      • Interrupt vector와 함께 낮은 주소 영역 사용
    2. 프로세스 영역
      • 높은 주소 영역 사용
  • 2가지 할당 기법을 배운다. → 연속 할당과 불연속 할당
    • 연속할당
      • Fixed 파티션 할당
      • Variable 파티션 할당
    • 불연속 할당
      • 페이징
      • 세그멘테이션
      • 페이지드 세그멘테이션(혼합)

Contiguous Allocation(연속 할당)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

Fixed partition allocation(고정 분할)

  • 물리적 메모리를 몇 개의 영구적 분할(파티션)로 나눔
  • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
  • 분할당 하나의 프로그램 적재
  • 융통성이 없음
    • 동시에 메모리에 로드되는 프로그램의 수가 고정됨
    • 최대 수행 가능 프로그램 크기 제한
  • Internal fragmentation 발생(external fragmentation도 발생)

Variable partition allocation(가변 분할)

  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • External fragmentation 발생

  • Hole(홀)
    • 가용 메모리 공간
    • 다양한 크기의 hole들이 메모리 여러곳에 흩어져 있음
    • 프로세스가 도착하면 수용가능한 홀을 할당
      • 할당공간, 가용공간(hole)운영체제는 다음의 정보를 유지

  • Dynamic Storage-Allocation Problem: 가변 분할 방식에서 크기 n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
    1. First-fit
      • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
    2. Best-fit
      • Size가 n 이상인 가장 작은 hole을 찾아서 할당
      • Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
      • 많은 수의 아주 작은 hole들이 생성됨
    3. Worst-fit
      • 가장 큰 hole에 할당
      • 역시 모든 리스트를 탐색해야 함
      • 상대적으로 아주 큰 hole들이 생성됨
      → 실험적인 결과로, First-fit과 Best-fit이 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐
  • compaction
    • 외부조각 문제를 해결하는 한가지 방법
    • 사용 중인 메모리 영역을 한군데로 몰고 hole들을 한곳으로 몰아 큰 block를 만드는 것
    • 매우 비용이 많이드는 방법임
    • 최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제)
    • Compaction은 프로세스의 주소가 실행시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.(런타임 바인딩)

2

Noncontiguous Allocation(불연속 할당)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음(단지 레지스터 2개로 동작하는 MMU로는 수행이 어려움)

Paging(균등하게 자름)

페이지 테이블

  • 어디에 있어야 할까?: 메인 메모리에 상주한다
  • page-table base register(BTBR)가 page table을 가리킨다.
  • page-table length register(PTLR)가 테이블 크기를 보관
  • 모든 메모리 접근 연산에는 2번의 메모리 엑세스가 필요(page table접근 한번, 실제 data/instruction 접근 1번)
    • 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라고 불리는 고속의 lookup hadware cache사용

d는 오프셋이므로 변경되지 않음
P라는 주소가 TLB에 있는지 검색해서 확인하는 과정을 거침

  • Associative Register(TLB): Parallel Search가 가능
    • TLB에는 page table 중 일부만 존재
  • Address translation
    • page table 중 일부가 associative register에 보관되어 있음
    • 만약 해당 page #가 associative register에 있는 경우 곧바로 frame #을 얻음
    • 그렇지 않은 경우 main memory에 있는 page table로부터 frame#을 얻음
    • TLB는 context swiching이 일어날 때 flush됨(remove od entires) - page table은 프로세스 마다 존재하기에 다른 프로세스로 cpu가 넘어가면 모든 엔트리를 비워야함
  • Effective Access Time
    • Associative register lookup time = e
    • memory cycle time = 1
    • Hit ratio = alpha (associative register에서 찾아지는 비율)
    • alpha가 거의 1에 가까운 값이므로, 2보다 훨씬 작은 값을 얻어 속도 향상을 확인할 수 있음, miss되면 메모리에 접근을 2번 해야함

Two-Level Page Table

공간을 줄이는게 목적이다. (* 시간은 더 걸림)

  • 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원, 32 bit address 사용시: 2^32(= 4G)의 주소 공간
    • page size가 4K일때 1M개의 page table entry 필요(사용되지 않는 영역을 위해서도 전부 메모리의 크기만큼 엔트리를 가지고 있어야 한다 → 배열(테이블) 구조이므로 인덱스 접근을 위해)
    • 각 page entry가 4B시 프로세스 당 4M의 page table 필요
    • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

→ page table 자체를 page로 구성

→ 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)이기 때문에, 공간 절약이 가능하다.

2의 12승은 4K이므로 4K size 페이지 표현을 위해 12bit(2^12=4K) page offset이 사용됨

 

Multilevel Paging and Performance

  • Address space가 더 커지면 다단계 페이지 테이블 필요
  • 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요(4단계 테이블을 사용하면 4번 접근해야 하므로 4배의 시간이 걸림)
  • 그렇기에 TLB를 통해 메모리 접근 시간을 줄일 수 있음
  • 4단계 페이지 테이블을 사용하는 경우
    • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
    • TLB hit ratio가 98%인 경우
      • effective memory access time = 0.98 * 12 + 0.02 * 520 = 128 nanoseconds
      • 결과적으로 주소 변환을 위해 28ns만 소요된다

Memory Protection

  • Page table의 각 entry 마다 아래의 bit를 둔다.
  • Protection bit
    • page에 대한 접근 권한(read/write/read-only)
  • Valid-invalid bit
    • Valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
    • Invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)
      1. 프로세스가 그 주소 부분을 사용하지 않는 경우
      2. 해당 페이지가 메모리에 올라와 있지 않고 swap area(disk)에 있는 경우

v와 i 비트 정보를 가지고 사용하는지 안하는지를 나타냄

Inverted Page Table(역방향 페이지테이블 → 공간 오버헤드를 줄이기 위해서)

시스템 안에 페이지테이블을 하나만 둔다. 물리적 메모리의 프레임 갯수만큼 페이지 테이블의 엔트리가 존재하게 됨(밑의 그림에서 f)

물리 → 논리 순으로 찾기 때문에 역방향 페이지 테이블이라고 한다.

  • page table이 매우 큰 이유
    1. 모든 프로세스 별로 그 논리 주소에 대응하는 모든 페이지에 대해 page table entry가 존재
    2. 대응하는 page가 메모리에 있든 아니든 간에 페이지 테이블에는 엔트리로 존재한다
  • Inverted page table이란?
    1. Page 프레임 하나당 페이지 테이블에 하나의 엔트리를 둔 것 (system - wide)
    2. 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시(process-id, process의 logical address - 실제 logical address는 프로세스 마다 별도로 있는 것이기 때문에.)
    • 단점 : 테이블 전체를 탐색해야 함 (공간 overhead는 이득이지만, 시간적으로는 trade-off)
      • 조치 : associative register 사용(expensive) - 병렬적으로 동시에 탐색할 수 있게

Shared pages

같은 프로그램이 여러개 실행될 경우 / IPC랑은 다른점에 유의!!! 커뮤니케이션 목적이 아니고 read-only임

  • Shared Code
    • Re-entrant Code(= Pure code) / 재진입 가능 코드
    • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림(eg. 텍스트 에디터, 컴파일러, 윈도우 시스템즈)
    • Shared Code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
  • Pirvate code and data
    • 각 프로세스들은 독자적으로 메모리에 올림
    • logical address space의 아무 곳에 와도 무방

Segmentation(의미 단위 기준으로 자름)

  • 프로그램은 의미 단위인 여러개의 segment로 구성
    • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
    • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
    • 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
  • Segment는 다음과 같은 logical unit 들임
    • main()
    • function
    • global variables
    • stack
    • symbol table, arrays

Segmentation Architecture

  • Logical address는 다음의 두가지로 구성
    1. segment-number(s)
    2. offset(d)
  • Segment table
    • each table entry has:
      • base - starting physical address of the segment
      • limit - length of the segment
  • segment-table base register(STBR)
    • 물리적 메모리에서의 segment table의 위치
  • segment-table length register(STLR)
    • 프로그램이 사용하는 segment의 수
      • segment number s is legal if s < STLR

Segment 장단점

Q. page보다 공간적으로도 유리한가?

yes, 페이징은 일반적으로 페이지 개수가 너무 많기 때문에 테이블로인한 메모리 낭비가 심하다.

1. Protection(장)

  • 각 세그먼트 별로 protection bit가 있음
  • each entry:
    • Valid bit = 0 → illegal segment
    • Read/Write/Execution 권한 bit

2. Sharing(장)

  • shared segment - 일반적으로 코드영역 같은 경우 같은 프로그램이면 공유해도 상관 없기 때문에!
  • same segment number - 같은 논리적인 주소상에 있어야 하므로 세그먼트 번호가 같아야 함

→ segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적이다 (eg. 의미 단위로 권한부여 등)

3. Allocation(단)

  • first fit/ best fit
  • external fragmentation 발생

→ 세그먼트들의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생(외부조각, hole)

Paged Segmentation(위 방법들을 혼합)

  • 세그먼트 당 페이지 테이블이 존재함(페이징은 프로세스당 페이지테이블)

STBR에서 세그먼트 테이블을 찾음 → 세그먼트가 갖고 있는 페이지 테이블의 시작위치를 찾음

다단계 테이블과 같이 d를 p와 d`로 나누게 됨

  • 기존 세그먼트기법에서 발생하는 Allocation 문제가 발생하지 않는다.
  • 기존에 갖는 장점은 그대로 가능(의미 단위로 필요한 일들은 세그먼트 차원에서 해주기 때문)
저작자표시

'CS > OS' 카테고리의 다른 글

[운영체제](반효경) 11강. File System  (0) 2022.10.14
[운영체제](반효경) 10강. Virtual Memory  (0) 2022.10.14
[운영체제](반효경) 8강. Deadlock  (0) 2022.08.09
[운영체제](반효경) 7강. Process Synchronization  (0) 2022.08.09
[운영체제](반효경) 6강. CPU Scheduling  (0) 2022.08.09

티스토리툴바