1. Backgrounds

1.1 Memory Device

1.1.1 device 종류

device = 데이터 저장 공간

아래 4개의 device가 하나의 컴퓨터에 존재

• processor register(= cpu reg)

ex)

rcx, rdx ... (16개)

%xmm0 ~ %xmm15 (16개)

%ymm0 ~ %ymm15 (16개)

• cache memory
• main memory 주기억장치
• auxiliary memory 보조기억장치

1.1.2 storage hierarchy

비교

보조기억장치로 갈수록

저장 용량이 커짐 / 가격 저렴

cpu reg에 가까울수록

cpu에서 데이터 불러오는 속도 빠름

cpu 메모리 호출 단위

• 캐시/메인 메모리 : word(4B)단위로 읽어감
• 보조기억장치 : block(4KB)단위로 읽어감

//4KB = 4B*1000

보조기억장치 데이터 읽어가기 위해서는

보조기억장치 -> 주기억장치로 데이터 옮겨 놓고

cpu는 주기억장치 접근해서 정보 가져감

1.1.3 cache memory

캐시메모리, 프로세서 레지스터

= 사실상 하드웨어 관리 대상 (OS 관리대상 아님)

[탄생배경]

cpu 데이터 읽어가는 소요시간

• cpu reg 접근 : 0~1cycle 필요
• memory 접근 : 50~200 cycle 필요 + 메모리에 접근하는 동안 stall(cpu 대기)

∴ memory 접근 오래걸림 -> cache memory 탄생

[cache memory]

1. 자주 사용하는 데이터 저장
2. main memory보다 접근시간 빠름

• main mem : dram
• cache mem : sram

(sram 처리 속도 더 빠름)

[cpu 내에 cache]

• 종류

L1 L2 각 코어마다 존재

L3 코어끼리 공유

L1 data + instruction 나눠짐

• 속도

(접근 속도 빠름: 자주사용하는 데이터)

L1 4cycle > L2 >L3 50cycle

(접근 속도 느림)

1.1.4 storage 발전

cpu 속도개선이 더 큼

따라서 memory - cpu 속도 차이는 점점 커짐

1.2 address binding

1.2.1 프로그램 개발 과정

https://ssinyoung.tistory.com/2

소스코드-<컴파일러:기계어로 변환>-object module -<링커:오브젝트파일 + 라이브러리 결합>-load module(실행파일)-<*로더>-memory binary image-<실행>

• 로더

실행파일을 실행 전, 메인 메모리에 옮겨 놓음

할당->연결->재배치->적재

• 할당 : 메모리에 옮겨놓을 공간 확보
• 연결 : 프로그램을 할당된 주소로 연결
• 재배치 : 프로그램이 사용하는 보조기억장치의 데이터의 주소 기억장치에 재배치 ( MMU Reallocation )
• 적재 : 프로그램을 실제 메모리에 옮겨 놓음

1.2.2 system library

system library에서

실행파일 정보(ex: 라이브러리함수)를 불러와

실행파일에 결합시킴

1)링커/로더가 실행

라이브러리 함수를 불러옴

2）dynamic linking (DLL)

• 실행파일을 run하면서

라이브러리 함수 호출 될 때 정보 불러옴

• 실행파일을 실행시키기 위해서는

실행파일 정보를

main memory로 옮겨놓은 후 실행해야함

• 메모리에 실행 이미지 옮기려면

메인 메모리 (커널)에 메모리 옮길 자리 있는지 확인해야함

따라서 이때 운영체제 메모리 관리함

• 실행파일이 메모리에 적재될 수 있는지에 영향 미치는 요인 : 컴파이러, 링커 ...

1.2.3 address binding 종류

[compile time binding]

컴파일할 때부터 메모리 어디에 들어가서 실행돼야하는지 지정 (메모리 주소가 고정됨)

[load time binding]

실행파일을 만들 때 시작번지=0 초기설정

메모리 몇 번지에 들어가도 실행 가능

but address constant relocation 필요

(allocation address에 맞게 주소 수정)

“jump” allocation address + 360

“load” allocation address + 1204

[run time binding]

relocation 없음

대신 cpu mmu에서 *address 자동 보정

따라서 run하면서 주소 자동 배정

• address 자동 보정

logical address(기본 주소)

• allocation address(할당 주소)

= physical address(실제 주소)

• 관여 reg

1)relocation register

= allocation address 저장

2)limit register

= 프로그램 크기 저장

프로그램 크기값 a가짐(limit)

1.2.4 dynamic linking ( DLL )

실행단계에서 링킹함

• static linking : 링킹단계에서

Object module-library 결합

• dynamic linking : 실행단계에서

Object module-library 결합

주로 라이브러리 함수 호출될 때 링킹

[장점]

1)라이브러리 함수 적게 결합 -> 실행파일 크기 작아짐 -> 디스크 차지 공간 작아짐

２）메모리에 공간따로 생성하지 않고

shared data 공간에서 함수 데이터 공간 공유 (code sharing)

따라서 메인 메모리 공간 절약

[stub]

= dynamic linking 실행 방법

소스프로그램에서 함수 직접 호출하지 않고

함수 호출 부분에

프로그램 실행 시 호출하라는 명령을 넣음

이 명령 부분을 stub이라 부름

1.3 ETC

1.3.1 overlay structure

• 메인 메모리 공간을 두 개 이상의 프로그램이

공유할 수 있도록 하는 기법

• 주기억장치의 공간보다 큰 크기의 프로그램을 불러와 실행하려고 할 때 사용하는 기법

1. ex)

주기억장치 빈 공간 : 8MB

프로그램 총 필요공간 : 10MB

BUT

pass1 종료 후 -> pass2 실행

따라서 10MB 동시 차지하지 않고 번갈아 공간 사용

• overlay driver가 관리
• main memory에 실행파일 가져올 때

주소 겹치게 불러오기 때문에

주소 보정 추가적인 처리 필요

1.3.2 swapping

개요

메모리 차지/반납 : swap in / swap out

swap out 당하는 프로세스

• swap device(swap file system)로 이동

고려사항

1. time slice > swap time

swap time

: 메인메모리->보조기억장치로

이미지 이동하는 데에 걸리는 시간

(보조기억장치 접근 시간은 오래 걸림)

∴ time slice < swap time 이면

cpu 활용도에 문제 생김

2. pending IO

입출력하는 도중에 swap out 당한다면

입출력하는 데이터 전달할 곳 사라짐

해결법 : IO 데이터 kernel buffer로 전달

kernel buffer에 데이터 모아놨다가 필요할 때 사용

swap file system

• 보통 file system

블록들이 산발적으로 저장돼있고(discontiguous)

저장된 주소 정보는 커널에 저장돼있음

• swap file system

swap out된 파일들을 연속된 공간에 저장(contiguous)

2 Memory Management

• contiguous allocation 기반 메모리 관리 기법

실행파일 전체를 연속으로(그대로) 메모리에 적재

• discontiguous allocation 기반 메모리 관리 기법

실행파일을 조각내서 조각을 메모리에 불연속적으로 적재

메모리 관리 효율 높아짐

• virtual memory 기반 메모리 관리 기법

실행파일을 조각내서 일부만 메모리에 적재하고 실행

2.1 Contiguous Memory Allocation

[고려사항]

1)메모리에 로딩되는 프로세스 개수 정하기

• 한번에 로딩하기에 메모리 공간 고려해야함
• *multigprogramming degree(메모리 할당받는 프로세스 개수)에 영향
• multigprogramming degree

의미1. 시스템 내의 프로세스 개수

의미2. 메모리를 할당받은 프로세스 개수(메모리 관리)

2)프로세스마다 할당할 메모리 공간

[contiguous memory allocation 사용하는 메모리 관리 기법]

1)FPM

(fixed(static) partition multiprogramming)

2)VPM

(variable(dynamic) partition multiprogramming)

2.1.1 Uniprogramming

메모리에 프로세스 하나밖에 없음

커널을 제외한 user space 모두 한 프로세스 할당

[이슈1] 프로그램 size(m) > user space size(M)

• 해결법

ME하도록 프로그램을 섹션을 두 개로 나누고

overlay structure 적용

[이슈2] 커널 protection

커널 공간 접근 금지해야함

커널의 접근은 system call을 통해서만 해야함

• 해결법

boundary address(커널&user space 경계 주소값)

• boundary reg에 저장

boundary address 이상의 주소 접근하는지 검사

[이슈3] cpu utilization/performance 하락

프로세스가 하나밖에 없기 때문에

프로세스가 입출력하는 동안에 cpu 놀고 있음

따라서 utilization / performance 떨어짐

• 해결법

multiprogramming 사용

2.1.2 FPM

Fixed Partition Multiprogramming

메모리 공간을 여러 고정된 파티션으로 나눔

원칙

1 process ↔ 1 partition (일대일 대응)

• 한 프로세스는 한 파티션만 사용
• 한 파티션은 한 프로세스에 의해서만 사용됨

∴

if > 파티션의 개수 k

then > multiprogramming degree (메모리 할당받은 프로세스 개수) k

fixed partition

1. 구조

파티션의 크기 및 위치가 고정됨

1. data structure

커널에 파티션에 대한 정보 가지고 있음

: 시작주소/크기 ...

program relocation

프로세스 실행하다 나갔다가 다시 들어올 때

기존 partition이 차 있다면

다른 partition 배정 받아야한다

따라서 다른 partition으로 배정받기 위해서는

• relocatable transition/loading 필요
• relocatable transition/loading

= load time / runtime binding 주소 재배정 가능

하지만 compile binding은 주소 고정이라 재배정 불가능

protection method 1

커널 접근 + 다른 파티션 접근 막야함

따라서 boundary address

= 커널&user space 사이의 boundary address

• 각 파티션 사이의 boundary address 포함

protection method 2

run-time binding에 적용하는 보호 방법

reloc.reg : 시작주소

limit.reg : 프로그램 크기 a

logical address : 0~a 사이

• context switcing(프로세스 변경)할 때

reloc.reg, limit.reg 값 업데이트

protection method :

logical address > a라면 “trap”(에러처리)을 함으로써 프로그램크기(a)를 넘어서 다른 파티션 접근 못하게 함

FPM 문제점 : fragmentation

메모리 공간 낭비

• internal fragmentation

파티션 내부에서 낭비되는 공간

파티션에서 프로세스가 사용하지 않는 공간은 낭비됨

• external fragmentation

파티션 외부에서 낭비되는 공간

입력 프로세스 크기가 맞지 않아 파티션 할당 못 받음

따라서 파티션이 통째로 낭비됨

요약

1. 파티션 정보가 고정되기에 메모리 관리 간단

• 간단하니까 overhead 작음

1. internal/external fragmentation

• utilization 문제

2.1.3 VPM

Variable Partition Multiprogramming

• internal fragmentation 없애는 기법
• 파티션의 상태가 계속 바뀌는 기법

VPM 파티션 관리

전체 메모리 공간 = 하나의 파티션으로 만듦

들어오는 프로세스에 따라 파티션 변형

예)

프로세스 크기에 맞게 파티션 배정

B프로세스가 나가면 파티션2 빔

D프로세스가 나가면 파티션4 빔

FPM VS VPM

• 공통점

하지만 external fragmentation 발생 가능

• 차이점

1. VPM: 프로세스가 들어옴에 따라

파티션 개수 및 크기가 달라짐

1. VPM : 프로세스 크기에 따른 파티션 할당해주기에

internal fragmentation 해결

[VPM 사용 기법 1] placement strategies 배치기법

빈 파티션 크기 N

들어오는 프로세스 크기 S

#N>S인 파티션 찾는 방법

1. first-fit

테이블의 처음부터 sequential 하게 search

1. best-fit

S와 제일 가까운 N찾기

예) S=20이라면 N=30 22중 22택

단점)

• 찾는 시간 오래 걸림
• 크기가 작은 빈공간 많이 발생

∴ external fragmentation 원인이 됨

1. worst-fit

제일 큰 파티션부터 allocation

1. next-fit

직전 search가 끝난 부분부터 sequential search

∴ 앞부분 파티션만 사용하는 게 아니라 전체 파티션 골고루 사용 가능

#최선의 배치기법

빠른 시간 내에 결정하는 게 좋음(오버헤드 작아야함)

따라서 first fit 또는 next fit 기법 사용

[VPM 사용 기법 2] Coalescing holes

인접한 빈 파티션을 합침

예)

파티션 1, 2 합침

파티션 1, 2, 3 합침

[VPM 사용 기법 3] storage compaction

빈 공간을 하나의 큰 파티션으로 통합

대량의 메모리를 다른 위치로 읽어오며 이동해야함

∴ overhead 큰 기법

∴ E “swap out” -> coalescing holes 적용

2.2 Discontiguous Memory Allocation

프로세스 이미지 분할 → 분할한 이미지를 메인 메모리에 비연속적으로 배치

2.2.1 Paging

discontiguous memory allocation 기법 1

특징

• 프로세스의 physical address가 불연속적이어도 됨
• 하드웨어와 OS가 밀접히 연결

예시

Basic Method

• page 분할

logical memory → page 4개로 분할

• page

• page 불연속 배치

logical memory page → physical memory (주기억장치)

• page table

page table ← page frame에서 page 위치 저장

• page frame

• logical address

• address mapping

contiguous allocation address mapping

→ load time binding

코드 수행 전에 모든 주소에 relocation address 더해줌

→ run time binding

logical address + relocation address(reg)

Discontiguous address mapping

load time binding 어렵기에 run time binding 해야함

→ page table 활용

예시

Memory Management Unit(MMU) : address mapping 담당

logical address(p, d)

page table에서 page "p"→ page frame "f"(physical address) 접근

page frame주소 "f" + offset "d" 접근 = physical address

page table 저장

커널의 PCB 내에 저장한다면? → page 접근 시 메모리 접근해야함

따라서

• cpu reg 마련
• TLB Associative Memory 사용

빠른 address mapping 가능케 하는 하드웨어

2.2.2 Segmentation

Basic concept

프로세스 조각 = segmentation

조각들의 크기가 다르다 (paging 차이점)

조각 내는 기준

process = text(code) + data(global variables) + heap + stack + shared memory

각 영역별로 segment 나눔

segmentation 주소

logical address = (s, d)

s : segment #

d : offset

예시

segment table

= segment mapping table

segment# = base(segment 시작 주소) + limit(segment 크기)

예시

address mapping → OS & MMU 담당

address mapping = logical address → physical address

address mapping 과정은 사용자에게 보이지 않는다

• logical address(s, d)

s segmentation # → segmentation table

• segmentation table (b, l)
• l segmentation frame size > d segmentation offset

b segmentation base + d segmentation offset

→ physical address