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

디스크 스케줄링(Disk Scheduling)

• 디스크 접근시간
  • Seek time + retotatinal delay(track이 도는시간) + transfer time
  • 탐색시간(seek time)이 가장 크다 = header를 움직이는 시간
• 다중 프로그래밍 환경(지금 우리의 프로그래밍 환경)
  • 디스크 큐(disk queue)에는 많은 요청(request)들이 쌓여있다.
  • 요청들을 어떻게 처리하면 탐색시간을 줄일 수 있을까? = 디스크 스케줄링 알고리즘

디스크 스케줄링 알고리즘

• FCFS(First Come First Served)
• Shortest-Seek-Time-First
• Scan Scheduling
• Elevator Algorithm

FCFS(First Come First Served)

가장 먼저온 것을 가장 먼저 실행 -> Simple and fair

• 예제
  • 200cylinder disk, 0 .. 199
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently ay cylinder 53
  • Total head movement = 640 cylinders
  • Is FCFS efficient?

Shortest-Seek-Time-First

Select the request with the minimum seek time from the current head position
-> seek time(disk head가 움직이는 시간)이 최소화 되는 것을 가장 먼저 해라

• 예제
  • 200cylinder disk, 0 .. 199
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently ay cylinder 53
  • Total head movement = 236 cylinders

• 문제점
  • Starvation
  • Is SSTF optimal? No!

Scan Scheduling

Scan disk: The head continuously scans back and forth across the disk
disk head가 디스크 전체에 걸쳐서 스캔하는것(들어갔다 나갔다가..)

• 예제
  • 200cylinder disk, 0 .. 199
  • Disk queue: 98 183 37 122 14 124 65 67
  • Head is currently ay cylinder 53 (moving toward 0)
  • Total head movement = 53 + 183 cylinder(less time)

• 토론
  • Assume a uniform distribution of requests for cylinder: request들이 고르게 분포되어있다.
  • Circular SCAN is neccessary?
    • 일반적으로 request는 하드디스크에 골고루 분포되어있다.

SCAN 알고리즘의 변종

• C-SCAN
• LOOK
• C-LOOK

C-SCAN

Treats the cylinders as a circular list htat wraps around from the final cylinder to the first one

마지막 부분이 첫번째 부분과 연결되어있는 것처럼 생긴 것. 원형모양처럼!
움직인 거리는 더 많을 수 있어도 시간은 훨씬 단축된다!

LOOK

The head goes only as far as the final request in each direction
Look for a request before continuing to meve in a given direction

0을 거치지 않고 바로 turn! 즉 head는 final request까지만 간다!
해당되는 방향으로 계속 갈 것인가를 결정하기 전에 그 이후의 큐가 있는지를 확인하고 움직인다.

C-LOOK

LOOK version of C-SCAN

request의 끝까지만 가는것. 199까지 가는게 아니라 183까지만 간다!

Elevator Algorithm

SCAN알고리즘을 부르는 또다른 호칭

SCAN and variants

• SCAN & C-SCAN
• LOOK & C-LOOK

The head behaves just like an elevator in a building. first servicing all the requests going up, and then reversing to service requests the other way

올리가는 것 쭈욱 서비스하고 내려오면서 또 해결

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

• 컴퓨터 시스템 자원 관리 CPU: 프로세스 관리(CPU 스케줄링, 프로세스 동기화)
  • 주기억장치: 메인 메모리 관리(페이징, 가상 메모리)
  • 보조기억장치: 파일시스템
• 보조기억장치(하드 디스크)
  • 하드디스크: track(cylinder), sector
  • Sector size = 512 bytes, cf. Block size: sector를 모아둔 것->block
  • 디스크는 블록 단위의 읽기/쓰기(block device)함 <-> character device
  • 디스크 = pool of free blocks, free blocks들의 모음
  • 각각의 파일에 대해 free block을 어떻게 할당해줄까?

파일할당

• 연속 할당(Contiguous Allocation)
• 연결 할당(Linked Allocation)
• 색인 할당(Indexed Allocation)

연속 할당(Contiguous Allocation)

각 파일에 대해 디스크 상의 연속된 블록을 할당(배열)

장점 : 디스크 헤더의 이동 최고화 = 빠른 I/O 성능
단점 : 외부 단편화로 인한 디스크 공간의 낭비 발생

옛날 IBM VM/CMS 에서 사용했으며 동영상, 음악, VOD 등에 적합하다.
파일의 크기가 큰 애들이 흩어져있다면 가져오는데 시간이 오래걸리지만 모여있으면 가져오는데에 시간이 적게걸린다.

• sequential access(순차접근): 순서적으로 읽기 가능
• direct access(직접접근): 특정 부분을 바로 읽기 가능
  • directory: 파일들의 정보를 모아둔 테이블

연속 할당의 단점

파일이 삭제되면 hole이 생성되는데, 이렇듯 파일의 생성/삭제가 반복되면 곳곳에 hole들이 흩어져있게 된다. 그렇다면 새로운 파일을 어느 hole에 둘 것인가에 대한 고민이 생기고 이때 외부단편화 문제가 발생하게 된다

• 디스크의 compaction은 가능하지만 시간이 굉장히 오래 걸린다.

즉, 외부 단편화로 인한 디스크 공간의 낭비 발생한다.

더 나아가, 사실 파일 생성 당시 파일의 크기를 알 수 없다. 즉, 파일을 어느 hole에 넣어야 할 지 알 수가 없다.
더 나아가 파일의 크기가 계속 증가할 수 있다(log file) -> 기존의 hole 배치로는 불가!

연결 할당(Linked Allocation)

파일을 연속적으로 나누는게 아니고, 자료구조의 linked list로 바라봄으로써 아무데나 들어갈 수 있다.

file = linked list of data blocks

파일 디렉토리(directory)는 제일 처음 블록을 가리킨다.
각 블록은 포인터 저장(다음 블록은 어디있는지)을 위한 4바이트 또는 이상을 소모한다.

새로운 파일 만들기

1. 비어있는 임의의 블록을 첫 블록으로
2. 파일이 커지면 다른 블록을 할당 받고 연결 -> 장점 :외부 단편화 발생하지 않음

연결 할당의 단점

순서대로 읽기(sequential access)만 가능하며, direct access(중간부터 읽기) 불가하며 포인터 저장 위해 4바이트 이상 손실한다.

• 낮은 신뢰성: 포인터 끊어지면 이하 접근 불가하다
• 느린 속도: 헤더의 움직임

연결 할당의 개선점: FAT 파일 시스템

File Allocation Table 파일 시스템으로 MS-DOS, OS/2, Windows등에서 사용한다.

연결할당의 변종으로 포인터들만 모은 테이블(FAT)을 별도 블록에 저장하고 FAT 손실 시 복구를 위해 이중 저장하는 시스템을 갖는다. 이는 direct access도 가능하며(FAT내용을 가져와 헤더를 움직임) FAT는 일반적으로 메모리 캐싱을 한다.

색인 할당(Indexed Allocation)

연결할당과 같이 아무데에나 파일을 할당할 수 있고, 그 정보를 저장하는 블락을 할당

데이터 블럭 외에 각 파일 당 한 개의 인덱스 블록이 존재한다.
인덱스 블록은 포인터의 모음이며 디렉토리는 인덱스 블록을 가리킨다. Unix/Linux 등에서 사용한다.

장점 : direct access 가능, 외부 단편화 없음
단점 : 인덱스 블록 할당에 따른 저장공간 손실
-> 예: 1바이트 파일 위에 데이터 1블록 + 인덱스 1블록

파일의 최대 크기

• 예제: 1블록 = 512 bytes = 4bytes x 128개의 인덱스 = 128*512bytes = 64KB
• 예제: 1블록 = 1KB = 4bytes x 256개의 인덱스 = 256*1KB = 256KB
• 해결방법: Linked, Multilevel index, Combined 등
  • Linked: 인덱스블락이 다른 인덱스 블락을 가리키도록 함
  • Multilevel index: 블락을 여러개를 둠
  • Combined: Linked와 Multilevel index를 합친 것

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

요구페이지 혹은 페이징을 할때 프로세스를 일정크기만큼 자른다고 했는데, 자른 하나하나를 페이지라고 한다.
그럼 이럴때 한 페이지의 사이즈는 어떻게 될까? 큰게 좋을까, 작은게 좋을까?

페이지 크기(Page size)

• 일반적인 크기: 4KB -> 4MB
• 점차 커지는 경향: 하나의 프로세스 크기들이 커지고 있기 때문

페이지 크기 영향

• 내부 단편화: 페이지 크기가 작을수록 좋다.
• Page-in, Page-out 시간: 페이지 크기가 클수록 좋다.
• 페이지 테이블 크기: 페이지 크기가 클수록 좋다.
• Memory resolution: 해상도. 페이지 크기가 작을수록 좋다.
• Page fault 발생확률: 페이지 크기가 클수록 좋다.

메모리도 커지고, 프로세스도 커져가는 상황에서 그에 따라 페이지 사이즈도 점차 커지는 경향이 있다.

기술 동향: 페이지 테이블

원래는 별도의 chip(TLB 캐시로 만들지만, 기술 발달에 따라 캐시 메모리는 on-chip형태로 TLB 역시 on-chip 내장(cpu안에 들어감)

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

쓰레싱(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가 더 효율적 일 수 있다.