개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

쓰레싱(Fhrashing)

page fault가 너무 자주일어나는 것을 쓰레싱이라고 한다.

• cpu utilization vs Degree of multiprogramming(cpu이용률 vs 메인메모리에 올라온 프로세스의 수)
  • 프로세스 개수 증가 > cpu 이용률 증가
  • 일정 범위를 넘어서면 cpu 이용률 감소
  • 이유: 빈번한 page in/out
  • Thrashing: i/o 시간 증가 때문

• 쓰레싱 극복
  • Global replacement 보다는 local replacement
  • 프로세스당 충분한/적절한 수의 메모리(프레임) 할당

프레임 할당(Allocation of Frames)

어떤 프로세스에게 얼마만큼의 프레임을 할당해줄 것인가를 결정

• 정적할당(static allocation): 프로세스를 실행해보지않고 프로세스 사이즈만 보고 결정
  • 균등할당(Equal allocation): 모든 프로세스에게 동일한 비율로 할당
  • 비례할당(Proportional allocation): 용량이 클수록 비례하게 할당
• 동적할당(dynamic allocation): 실제 실행을 해보고 결정
  • Working set model
  • Page fault frequency
  • etc

Working set model

• Locality vs working set
  • Locality: 페이지들이 모여있는 것 (cpu가 내는 주소는 모여져있다.)
  • working set: 과거 일정 시간대에 사용된 페이지
• Working set window(=Δ): 현 시점을 기준으로 얼마를 과거로 보는지에 대한 시간
• Working set 크기 만큼의 프레임 할당

Locality만큼 프레임을 할당해주면 좋겠지만, 미래의 Locality를 알수가 없기때문에 과거에 참조했던 페이지,
즉 과거는 얼마만큼 과거나면 working set window seconds 이는 os를 만든사람이 결정한다.

과거 사용된 페이지(working set)만큼을 할당해준다. 그렇게 되면 쓰레싱이 발생하지도 않으면서 메모리를 너무 낭비하지도 않을 것이다.

Page-Fault Frequency(PFF)

• Page fault 발생 비율의 상한/하한선
• 상한선 초과 프로세스에 더 많은 프레임 할당
• 하한선 이하 프로세스의 프레임은 회수

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

페이지 교체 알고리즘(Page Replacement Algorithms)

• FIFO(First-In First-Out)
• OPT(Optimal)
• LRU(Least-Recently-Used)

FIFO(First-In First-Out)

메인메모리에 제일 먼저 올라온 애를 victim으로 선택

• Simplest idea: 초기화 코드는 더 이상 사용되지 않을 것
• 예제
  • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

  • of frames = 3 # 남아있는 프레임의 수

  • 15 page fault

• Belady’s Anomaly
  • page fault는 같은 프로그램 안에서 메모리가 작을 수록 자주일어나는데 프레임 수가 늘어남에도(=메모리 용량이 늘어난다) page fault가 늘어나는 현상

  • 언제나 일어나는 것은 아니고 페이지 참조열이 특정한 상황에서 일어난다.

  • 프레임 수(=메모리 용량) 증가에 PF 회수 증가?

OPT(Optimal)

앞으로 가장 사용되지 않을 것을 victim으로 선택
Rule: Replace the page that will not be used for the longest period of time

• 예제
  • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

  • of frames = 3

  • 9 page fault

• Unrealistic: 미래는 알 수 없다.
  • cf. SJF CPU scheduling algorithms

LRU(Least-Recently-Used)

최근에 가장 적게 사용된 것은 victim으로 선택
Rule: Replace the page that has not been used for the longest period of time
-> 최근에 사용되지 않으면 나중에도 사용되지 않을 것

• 예제
  • 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

  • of frames = 3

  • 12 page fault

OPT보다는 자주일어나고 FIFO보다는 적에 일어난다. 그래서 대부분의 컴퓨터는 LRU를 사용한다.

Global vs Local Replacement

• Global replacement: 메모리 상의 모든 프로세스 페이지에 대해 교체
• Local replacement: 메모리 상의 자기 프로세스 페이지에 대해 교체
• 성능 비교: Global replacement가 더 효율적 일 수 있다.

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

페이지 교체(Page Replacement)

메모리가 가득차게되면 페이지를 교체해줘야 한다.

• Demand Paging: 요구되어지는 페이지만 backing store에서 가져온다.
  • 프로그램 실행 계속에 따라 오구페이지가 늘어나고, 언젠가는 메모리가 가득차게 된다.
• Memory full > victim page
  • page-out: 메모리가 가득하면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아낸다.
  • page-in: 그 빈 공간으로 페이지를 가져온다.

Victim Page, 어느 페이지를 몰아낼 것인가?

• I/O 시간 절약을 위해
• 기왕이면 modify 되지 않은 페이지 를 victim으로 선택: modified bit(= dirty bit)

modified bit인 여러 페이지 중에서도 무엇을 victim으로 할 것인가?

• Random
• First-In / First-Out(FIFO)
• 그외
• page replacement algorithms

페이지 참조 열(Page reference string)

페이지 번호중에서 바로 이어지는 숫자는 스킵하고 넘어가는 것

• cpu가 내는 주소: 100 101 102 432 612 103 104 611 612
• page size = 100바이트라면
• 페이지 번호 = 1 1 1 4 6 1 1 6 6
• page reference string = 1 4 6 1 6

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

가상메모리(Virtual Memory)

물리 메모리 크기 한계 극복하기 위해 생겨남

물리 메모리보다 큰 프로세스를 실행? e.g) 100MB 메인 메모리에서 200MB 크기의 프로세스 실행

어떻게 해결할까?

프로세스 이미지를 모두 메모리에 올릴 필요는 없다. 즉, 현재 실행에 필요한 부분만 메모리에 올린다.
오류 처리 제외, 배열 일부 제외, 워드프로세스에서 정렬, 표 기능 제외 -> 동적 적재(dynamic loading)과 비슷한 개념

즉, 일반적으로 프로세스를 메모리에 올린다고하면 code, data, stack을 한번에 다 올려야 한다고 생각하지만, 실제로 그럴필요가 없다.

좀 더 현실적으로 프로세스가 여러개가 있고 이를 메모리에 올리려고 한다면, 각 프로세스를 페이지별로 쪼개고(일정 크기로) 각각 필요한 페이지만을 메모리에 올린다. 크기가 큰 프로세스 전체는 메모리에 다 올릴 수가 없지만, 지금 이 순간에 필요한 애들만(쪼개져 있는 애들 중) 올리면 충분히 메모리에 올릴 수가 있게된다. 이렇게 프로세스를 자르되, 요구되는 페이지만 메모리에 올리는 것을 요구페이지 라고 한다.

요구 페이지(Demand Paging)

프로세스를 페이지 단위로 잘라서 메모리에 올리는데 요구되는 페이지만 메모리에 올리고 필요하지 않은 페이지들은 backing store(하드디스크)에 저장해주는 것
페이지가 요구되어지면 그때 그때 들고 올라온다 > 요구페이지

• 프로세스 이미지는 backing store에 저장
• 프로세스는 페이지의 집합
• 지금 필요한 페이지만 메모리에 올린다(load) -> 요구되는(demand)페이지만 메모리에 올린다

요구페이지를 만들기 위해서는 어떤 하드웨어가 필요할까?

1. valid bit 추가된 페이지 테이블
2. backing store(=swap device)

페이지 결함(Page fault) = 페이지 부재

접근하려는 페이지가 메모리에 없다(Invalid)

페이지 결함이 일어났다는 것은 cpu 어떤 주소를 냈는데, 그에 해당하는 페이지 엔트리 내용이 0으로 나타났다는 것
이때 페이지 테이블에서 cpu로 전기신호(인터럽트)를 보내게 되고 이를 감지한 cpu는 os에게 routine을 통해 (page fault routine)을 실행하게 된다.

Steps in handling a page fault
Backing store에서 해당 페이지를 가져온다.
cpu가 어떤 주소를 냈고 해당 주소에 대해 invalid를 보게되면 page table에서 cpu에 interrupt를 걸어
os루틴안에서 해당 페이지를 읽어서 메모리로 가져오고 가져온 프레임 번호를 테이블에 기록하고 해당 비트를 valid로 하면 원하는 페이지를 열 수 있다.

용어: pure demand paging vs prepaging

순수 요구페이징(pure demand paging) : 진짜 필요한 애들만 가져오는 것
프로그램이 처음 시작할 적에 지금 필요한게 아니면 아무것도 들고오지 않기 때문에 처음 시작할 때부터 page fault가 일어난다.

그래서 속도는 느리지만, 메모리가 절약된다.

미리페이징(prepaging) : 지금 필요하지 않아도 미리 몇페이지를 가져오는 것

속도는 빠르지만(page fault가 적게 일어남) 메모리 낭비가 있다.

비교: swapping vs demand paging

• Swapping: 메모리와 backing store를 움직이는 단위가 프로세스 단위로 움직임
• Demand Paging: 갖고오는단뒤가 페이지 단위임

유효 접근 시간

cpu가 주소를 낼때 빠르게 읽히는게 있고, 느리게 읽히는 게 있는데 이때 평균적인 속도는 얼마정도일까를 유효접근시간이라고 한다.
메모리의 어떤 영역은 빠르게 읽히고, 느리게 읽힐텐데 이에 대한 평균 시간(확률)

• Effective Access Time
  • probability of a page fault = page fault rate
  • T = (1-p)T + pT
  • 유효접근시간 = (1-page fault가 일어날 확률) * 메모리 읽는 데 걸리는 시간 + page fault가 일어나면 걸리는 시간

이 확률이 낮을 수록 좋은 건데 현실적으로는 어떨까?

지역성의 원리(Locality of reference): cpu가 참조하는 주소가 지역에 모아져있다

메모리 접근은 시간적, 공간적 지역성을 가진다. 실제 페이지 부재 확률은 매우 낮다.

• 시간적 지역성: cpu가 읽은곳을 나중에도 읽을 수가 있다. 코드에는 반복문이 많고, 한번 읽은 애를 또 읽을 확률이 높다.
• 공간적지역성: 지금 1000번지를 읽으면 나중에도 1000번지에 인접한 구역을 읽는다. 주소만 들고오는게 아니라 블락 단위로 가져온다.

다른방법

HDD는 접근 시간이 너무 길다 > swap device로 부적합
SSD 또는 느린 저가 DRAM 사용한다!

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

세그멘테이션(Segmentation)

프로세스를 논리적 내용(=세그먼트)으로 잘라서 메모리에 배치하는 것

• 프로세스는 세그먼트(segment)의 집합: 하나의 프로세스는 최소 3개 이상의 세그먼트로 구성
  • 프로세스는 기본적으로 code + data + stack으로 구성되어있다. 하나의 프로그램이 돌기 위해서는 이 3개로 구성된 뭉치가 있어야한다.
• 세그먼트의 크기는 일반적으로 같지 않다: 코드길이, 데이터길이, 스택길이가 다르고 각자의 길이 모두가 다르기 때문

세그먼트를 메모리에 할당!

MMU내의 재배치 레지스터 값을 바꿈으로써 CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각한다.
MMU는 세그먼트 테이블(segment table)이 된다.

주소 변환(Address Translation)

• 논리주소(Logical address): cpu가 내는 주소는 segment 번호(s) + 변위(d)
• 주소변환: 논리주소 -> 물리주소(Physical address)
  • 세그먼트 테이블 내용: base + limit
  • 세그먼트 번호(s)는 세그먼트 테이블 인덱스 값
  • s에 해당되는 테이블 내용으로 시작 위치 및 한계값 파악
  • 한계(limit)를 넘어서면 segment violation 예외 상황 처리
  • 물리주소 = base[s] + d

segment table은 base(시작번지)와 limit(한계값)으로 이루어져있고, page table은 1차원 배열로 이루어진 반면 segment table은 2차원으로 이루어져있다.

• 예제
  • 논리주소 (2,100)은 물리주소 무엇인가? 4400
  • 논리주소 (1,500)은 물리주소 무엇인가? 6800(x) 해당주소 없음(limit를 넘어감)

보호와 공유

보호(Protection): 해킹 등 방지
모든 주소는 세그먼트 테이블을 경유하므로, 세그먼트 테이블 엔트리마다 r,w,x 비트를 부여한다.
해당 세그먼트에 대한 접근 제어가 가능하고 이는 페이징보다 우월하다.

그 이유는 프로세스를 자를 때 페이징은 일정크기로 자르는데, 그렇게 되면 각 페이지에는 code, data, stack이 구분없이 자려져 있어 섞일 수 있다.
그러나 세그먼트는 부위별로 자르기에 섞이지가 않다. code끼리, data끼리, stack끼리..

즉, 페이징은 한 페이지 안의 r,w,x를 구분짓기가 어려워진다는 의미

공유(Sharing): 메모리 낭비 방지
같은 프로그램을 쓰는 복수개의 프로세스가 있다면, Code + data + stack에서 code는 공유가 가능하다.
(단, non-self-modifying code = reentrant code = pure code인 경우)
프로세스의 세그먼트 테이블 코드 영역이 같은 곳을 가리키게 하고 이는 페이징보다 우월하다.

그러나 대부분의 os는 페이징을 사용한다.

Segmentation의 단점: 외부단편화(External Fragmentation)

세그먼트 크기는 고정이 아니라 가변적이다. 그렇기 때문에 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리를 할당 해야한다.
first, best, worst-fit, compaction등 문제

프로세스를 잘라서 메모리에 올리는 이유는 외부단편화를 없애기 위해서인데, 이를 해결해주지 못한다. -> 치명적인 문제

Segmentation + Paging

세그멘테이션은 보호와 공유면에서 효과적이고 페이징은 외부 단편화 문제를 해결해준다.
따라서 세그먼트를 페이징한다! = Paged segmentation, ex) Intel 80x86

1. 프로세스를 처음에는 세그먼트로 자른다. (code + data + stack)
2. 각 세그먼트를 페이지로 자른다.

이 또한 그러나 MMU를 두개를 거치게 됨으로 속도면에서는 조금 떨어진다는 단점이 존재한다. = trade off