Brute force Study

File System Implementation

파일 시스템 구현 (File System Implementation)

• 사용자 관점에서의 파일 시스템 (File system of the user’s viewpoint)
  • 파일 시스템을 사용자에게 어떻게 보여줄 것인가?
  • 파일 시스템 인터페이스
  • 파일, 디렉토리, 속성 및 작업
  • 예: 트리 구조

• 저장 관리 관점에서의 파일 시스템 (File system of the storage management viewpoint)
  • 논리적 파일 시스템을 저장 장치에 어떻게 매핑할 것인가?
  • 파일 시스템 구현
  • 레이아웃, 데이터 구조 및 알고리즘
  • 저장 내부를 이해하는 것이 필요함

• 파일 시스템은 저장 장치를 블록의 시퀀스로 간주
  • 디스크와 메모리 간의 데이터 전송은 블록 단위로 이루어짐.
  • 각 블록에는 일반적으로 512바이트인 하나 이상의 섹터가 있음.

• 파일 시스템 구현 (File system implementation)
  • 각 파일에 대해 속성(attribute)과 파일 데이터(file data)가 저장되어야 함.
  • 속성 - 크기, 권한, 소유자, 시간 등
  • 속성 및 파일 데이터를 저장할 공간을 어떻게 할당할 것인가?

• 파일 시스템 구현 (Unix file system)
  • i-node
    • 파일 데이터에 대한 속성 + 인덱스 (Attribute + indexes for file data)
  •  i-node 영역과 파일 데이터 영역은 분리됨

•  i-node 크기는 같지만, 파일 데이터의 크기는 다름
  • i-number를 통해 i-node에 접근 가능
•  파일 데이터 저장 공간을 어떻게 할당할 것인가?
  • 연속 (contiguous) / 링크 (linked) / 인덱스 (indexed) 할당

Contiguous Allocation

연속 할당 (Contiguous Allocation)

• 각 파일은 디스크의 연속된 블록 집합을 차지함
  • 시작 위치와 길이만 필요함

• 파일에 순차/랜덤 접근이 쉬움
• 새 파일을 위한 공간 찾기가 어려움

Linked Allocation

연결 할당 (Linked Allocation)

• 각 파일은 디스크 블록의 연결 리스트(linked list) 
  • 예: MS-DOS 파일 시스템 (FAT 파일 시스템)
  • 블록이 디스크 어디에나 흩어질 수 있음 → 공간 낭비 없음
  • 순차 접근에만 효과적
  • 포인터가 손실되거나 손상되면?

• MS-DOS의 FAT 파일 시스템 
  
  • 각 디스크 블록에 대한 항목이 하나 있음

참고)

FAT (File Allocation Table)

• 디스크의 각 블록에 대한 정보를 가지고 있습니다. 파일이 어떤 블록에 저장되어 있는지를 추적합니다.

작동 방식

1. 파일 할당
   • 파일이 디스크에 저장될 때, 파일의 데이터는 여러 데이터 블록에 저장됩니다.
   • 예를 들어, 파일의 첫 번째 블록은 217번 블록에 저장되고, FAT의 217번 항목은 다음 블록 번호(618)를 가리킵니다.
2. FAT 테이블의 역할
   • FAT 테이블은 각 데이터 블록의 다음 블록 번호를 가리킵니다.
   • 블록 217의 다음 블록은 618이며, 블록 618의 다음 블록은 339입니다.
   • 블록 339은 파일의 끝을 나타내며(EOF), 더 이상 이어지는 블록이 없음을 표시합니다.
3. 디렉토리 엔트리
   • 디렉토리 파일에는 파일 이름과 함께 파일의 첫 번째 데이터 블록 번호가 저장됩니다.
   • 이 예시에서는 파일 이름과 첫 번째 블록 번호(217)가 저장되어 있습니다.

Indexed Allocation

인덱스 할당 (Indexed Allocation)

• 모든 포인터를 인덱스 블록으로 가져옴
  • 랜덤 접근 가능
  • 연속된 블록을 찾을 필요 없음
  • 파일당 하나의 인덱스 블록 필요
  • 큰 파일을 위한 인덱스 블록의 크기가 여전히 작다면 문제가 발생한다

• 다단계 인덱스 (Multilevel index, 예: UNIX 파일 시스템)
  • UNIX 파일 시스템의 i-node에 15개의 포인터 필드
    • 직접 블록 (direct blocks)을 위한 12개의 포인터 필드
    • 간접 블록 (indirect blocks)을 위한 3개의 포인터 필드
      • 단일, 이중, 삼중

참고)

i-node 구조

i-node는 파일이나 디렉토리에 대한 정보를 가지고 있는 데이터 구조체로, 다음과 같은 필드를 포함합니다:

• mode: 파일의 타입 및 접근 권한
• owners: 파일의 소유자 정보
• timestamps: 파일의 생성, 수정, 접근 시간
• size block: 파일의 크기
• count: 파일을 참조하는 링크 수
• 포인터들:
  • 12개의 직접 블록 포인터 (direct blocks): 파일의 데이터 블록을 직접 가리킵니다.
  • 단일 간접 블록 (single indirect block): 이 포인터는 데이터 블록을 가리키는 또 다른 블록을 가리킵니다.
  • 이중 간접 블록 (double indirect block): 데이터 블록을 가리키는 블록의 포인터를 다시 가리키는 블록을 가리킵니다.
  • 삼중 간접 블록 (triple indirect block): 이중 간접 블록을 가리키는 블록을 가리킵니다.

데이터 블록 접근 방법

1. 직접 블록 (Direct Blocks)
   • i-node의 첫 12개 포인터는 직접 데이터 블록을 가리킵니다.
   • 소형 파일의 경우 대부분의 데이터는 이 포인터들을 통해 직접 접근됩니다.
2. 단일 간접 블록 (Single Indirect Block)
   • i-node의 단일 간접 블록 포인터는 데이터 블록을 가리키는 포인터 블록을 가리킵니다.
   • 이 블록을 통해 더 많은 데이터 블록을 참조할 수 있습니다.
3. 이중 간접 블록 (Double Indirect Block)
   • i-node의 이중 간접 블록 포인터는 단일 간접 블록들을 가리키는 블록을 가리킵니다.
   • 파일이 더 클 경우, 이 구조를 통해 더욱 많은 데이터 블록을 참조할 수 있습니다.
4. 삼중 간접 블록 (Triple Indirect Block)
   • i-node의 삼중 간접 블록 포인터는 이중 간접 블록들을 가리키는 블록을 가리킵니다.
   • 매우 큰 파일을 지원하기 위한 구조입니다.

결론) Indirect Block을 통해서 큰 파일에 접근할 수 있다.

Free Space Management

• 비트맵 (Bit map, bit vector라고도 함)
  • 블록[i]가 할당되면 비트는 1; 그렇지 않으면 비트는 0.

• 연속된 여유 블록을 얻기 쉬움
• 비트맵은 추가 공간을 필요로 함
  • 예: 블록 크기 = 2^12 바이트 (= 4KB)
  • 디스크 크기 = 2^40 바이트 (= 1TB)
  • n = 2^40/2^12 = 2^28 비트 (= 32MB)

• 연결 리스트 (Linked list)
  • 공간 오버헤드 없음
  • 연속된 여유 블록을 쉽게 얻을 수 없음

• 그룹화 (Grouping)
  • 연결 리스트 접근법의 수정
  • 처음 n-1의 여유 블록(free block)은 실제로 여유 상태
  • 마지막 블록은 또 다른 n개의 여유 블록의 주소를 포함함

Directory Implementation

디렉토리 구현 (Directory Implementation)

• 선형 리스트 (Linear list)
  • (파일 이름, 파일에 대한 포인터)
  • 구현이 간단함
  • 파일 검색에 시간이 많이 소요됨
  • B-트리를 사용할 수 있음
• 해시 테이블 (Hash Table)
  • 해시 데이터 구조를 가진 선형 리스트
  • 해시 함수는 "파일 이름"을 "파일의 선형 리스트에 대한 포인터"로 변환
  • 디렉토리 검색 시간을 줄임
  • 충돌을 해결해야 함

Performance and Recovery

성능 및 복구 

• 효율성 (Efficiency)
  • 파일의 데이터 블록을 해당 파일의 i-node 블록 근처에 유지하여 검색 시간을 줄임.
  • i-node의 "마지막 접근 시간" 정보는 블록 읽기와 쓰기를 필요로 함.
  • 데이터 접근에 사용되는 포인터의 크기? 16bit 또는 32bit.
• 성능 (Performance)
  • 버퍼 캐시 (Buffer cache)
    • 자주 사용되는 블록을 위한 메인 메모리의 별도 섹션
  • 읽기 선행 (read-ahead)
    • 순차 접근을 최적화하기 위한 기술

• 버퍼 캐시 (Buffer cache)
  • 파일이 접근될 때마다 파일 데이터는 디스크에서 가져와야 함.
  • 그러나 디스크 접근은 큰 I/O 오버헤드를 발생시킴.
  • 파일 접근 패턴에서 한 번 접근된 데이터는 곧 다시 사용될 것임 (시간적 지역성, temporal locality).
  • 버퍼 캐시는 곧 다시 사용될 블록을 유지하여 디스크 접근을 줄임.

• 불일치가 발생할 수 있음 (Inconsistency can occur)
  • 파일 시스템의 일부가 속도 향상을 위해 메모리에 유지됨.
  • 시스템이 충돌하면? 모든 데이터를 디스크에 저장할 수 없음.
  • 디렉토리 또는 메타데이터(i-node)가 손실되면?
• 일관성을 위한 솔루션 (Solutions for consistency)
  • 일관성 검사기(Consistency checker)
    • e.g. UNIX의 fsck
    • 디스크의 데이터 블록과 디렉토리 구조의 데이터를 비교하고 불일치를 수정하려고 시도.
  • 중요한 메타데이터를 위한 동기식 쓰기 (Synchronous write)
  • 저널링 (Journaling)
• 시스템 프로그램을 사용하여 데이터 백업 (Use system programs to back up data)
  • 디스크에서 다른 저장 장치로
  • 백업 데이터를 복원하여 손실된 파일 또는 디스크 복구

File System

• 파일 시스템
  • File system
  • 저장 장치에 데이터를 조직화하는 소프트웨어.

User's viewpoint (사용자의 관점)

Storage management's viewpoint (저장 관리의 관점)

사용자의 관점에서의 파일 시스템

• File system interface (파일 시스템 인터페이스)
• How to show the file system to user? (사용자에게 파일 시스템을 표시하는 방법)
• 파일, 디렉터리, 속성, 그리고 작업
• 트리 구조

저장 관리 관점에서의 파일 시스템

• File system implementation (파일 시스템 구현)
• How to map the logical file system to the storage device? (논리적 파일 시스템을 저장 장치에 매핑하는 방법)
• 레이아웃, 데이터 구조, 그리고 알고리즘
• 저장 내부 구조를 이해해야 합니다.

파일 시스템의 목표

File Concept

• 파일 (File)
  • A named collection of related information. (관련 정보의 명명된 모음)
  • It is just a sequence of bytes. (바이트의 연속)
  • It is stored on secondary storage. (2차 저장장치에 저장됨)
  • It is divided into data files and program files. (데이터 파일과 프로그램 파일로 나뉨)

• 파일을 유지관리하기 위한 파일 속성 (File attributes for maintaning files) 
  • 이름 (Name)
    • 사람이 읽을 수 있는 형태로 유지되는 유일한 정보.
  • 식별자 (Identifier)
    • 파일 시스템 내에서 파일을 식별하는 고유 태그(번호).
  • 유형 (Type)
    • 정규 파일, 디렉토리, 심볼릭 링크, 명명된 파이프 등.
  • 위치 (Location)
    • 장치 내 파일 위치를 가리키는 포인터.
  • 크기 (Size)
    • 현재 파일 크기.
  • 보호 (Protection)
    • 읽기, 쓰기, 실행.
  • 시간, 날짜 및 사용자 식별 (Time, date, and user identification)

• 파일 작업 (File operations)
  • 만들기 (Create)
  • 삭제 (Delete)
  • 열기 (Open)
  • 닫기 (Close)
  • 읽기 (Read)
  • 쓰기 (Write)
  • 잘라내기 (Truncate)
  • 파일 탐색 내 재배치 (Reposition within file-seek)

• 파일 유형 (File types)
  • Is recognized with file extension. (파일 확장자로 인식됨)
    

    File type	Usual extension	Function
    executable	exe, com, bin, or none	read-to-run machine-language program
    object	obj, o	compiled, machine language, not linked
    source code	c, cc, java, pas, asm, a	source code in various languages
    batch	bat, sh	commands to the command interpreter
    text	txt, doc	textual data, documents
    word processor	wp, tex, rtf, doc	various word-processor formats
    library	lib, a, so, dll	libraries of routines for programmers
    print or view	ps, pdf, jpg	ASCII or binary file in a format for printing or viewing
    archive	arc, zip, tar	related files grouped into one file, sometimes compressed, for archiving or storage
    multimedia	mpeg, mov, rm, mp3, avi	binary file containing audio or A/V information

  • Magic number (in UNIX)
    • 파일 시작 부분에 저장되어 파일 유형을 대략적으로 나타냄.
    • 예: 실행 파일, 배치 파일(또는 셸 스크립트), 포스트스크립트 파일 등.

Access methods

• Sequential access (순차 접근)
  • 파일은 순서대로 접근되며, 한 레코드씩 차례대로 처리.
  • 파일의 다음 부분을 읽거나 쓰며 파일 포인터를 자동으로 이동시킴.
  • 예: 편집기, 컴파일러
• Random access (Direct access) (랜덤 접근)
  • 파일은 무작위 순서로 접근됨.
  • 파일 읽기/쓰기 순서에 제한이 없음.
  • 예: DBMS

Directory

• 디렉토리 (Directory)
  • 파일과 다른 디렉토리 그룹을 포함하는 가상 컨테이너.
  • 예: 트리 구조의 디렉토리

• 유닉스 디렉토리 구조 (Unix's directory structure)
  • 디렉토리 엔트리는 (파일 이름, inode 번호)로 저장됨
  • inode는 (attributes, 파일 데이터 포인터)를 포함한다

• 디렉토리에서 수행되는 작업
  • 파일 검색 (Search for a file)
    • 특정 파일 또는 유사한 이름의 파일 항목 찾기
  • 파일 생성 (Create a file)
    • 새 파일을 생성하고 디렉토리에 추가
  • 파일 삭제 (Delete a file)
    • 디렉토리에서 파일 제거
  • 디렉토리 목록 (List a directory)
    • 디렉토리의 파일 목록 나열
  • 파일 이름 변경 (Rename a file)
    • 파일의 이름 변경
  • 파일 시스템 탐색 (Traverse the file system)
    • 모든 디렉토리 및 디렉토리 구조 내의 모든 파일에 접근

Tree-Structured Directory

• 트리 구조 디렉토리 (Tree-Structured Directory)

Acyclic-Graph Directories

• 비순환 그래프 디렉토리 (Acyclic-Graph Directories)
  • 공유 하위 디렉토리 및 파일 (Shared subdirectories and files)을 가지고 있다.

• 동일한 파일(또는 하위 디렉토리)이 두 개의 다른 디렉토리에 있을 수 있음
  • 탐색 문제와 삭제 문제 (Traverse problem and delete problem) 
    • 시나리오 (A scenario)
      • Kim에게 파일 X가 있음. Lee는 그의 디렉토리 아래에 동일한 X를 가져야 함.
      • UNIX에서는, Lee의 디렉토리에 “링크 (link)”를 생성함.
    • 하드 링크 (Hard link)
      • X의 메타데이터를 Lee의 디렉토리에 복사.
      • X를 삭제하면?
        • 참조 카운트(reference count) 사용
        • (X가 삭제되더라도 다른 링크가 남아 있는 한 데이터는 유지됩니다.)
    • 심볼릭 링크 (Symbolic link)
      • Lee의 디렉토리에 대한 X의 경로명(pathname)을 생성.
      • X를 삭제하면?
        • 덩글링 참조 (dangling reference)
        • (원본 파일이 삭제되면, 남아있는 링크가 가리키는 경로가 유효하지 않게 됩니다.)

File System Mounting

파일 시스템 마운트 (File system mount)

• 파일 시스템 마운트 (File system mount)
  • 운영 체제에 ㅌ파일 시스템이 사용 준비가 되었음을 지시하고 시스템의 파일 시스템 계층 구조에서 특정 지점(mount point)에 연결

• 루트 파일 시스템 (root file system) : 모든 파일에 접근 가능
• 디스크 2 및 디스크 3의 파일에 접근하는 방법?

위 예시는 disk 3에 있는 stdio.h 파일에 접근하는 예시이다

디스크 2와 디스크 3에 있는 파일에 접근하기 위해서는 다음과 같은 단계를 거쳐야 한다.

• 디스크 확인: 시스템에서 사용 가능한 디스크를 확인한다. 디스크 2와 디스크 3가 시스템에 연결되어 있는지 확인해야 한다.
• 파티션 확인: 각 디스크에는 하나 이상의 파티션이 있을 수 있다. 디스크의 파티션 구성을 확인하여 원하는 파티션을 식별한다.
• 파일 시스템 마운트: 선택한 파티션에 포함된 파일 시스템을 마운트한다. 이를 위해 마운트 지점(예: /mnt/disk2, /mnt/disk3)을 생성하고 해당 지점에 파일 시스템을 연결한다.
• 파일 접근: 마운트된 파일 시스템의 마운트 지점을 통해 해당 디스크에 있는 파일에 접근할 수 있다. 마운트 지점을 통해 파일을 읽거나 쓰는 등의 작업을 수행할 수 있다.

참고) https://jinger.tistory.com/entry/OS-13-File-System-Interface

File Protection

파일 보호 (File protection)

• 파일 소유자는 누가 무엇을 할 수 있는지 제어할 수 있어야 함
  • 무엇 (what) - 권한 (읽기, 쓰기, 실행, 추가, 삭제, 목록 등)
  • 누구 (whom) - 사용자 (수퍼유저, foo, kim, park, jane 등)
• 그룹화가 필요함 (Grouping is required)
  • 접근 권한
    • 읽기, 쓰기, 실행
  • 세 가지 사용자 클래스
    • 소유자, 그룹, 기타
• 예시 (Example)
  • drwxrwxr-x 2 foo staff 4096 Oct 30 23:25 examples
  • -rw-rw-r-- 1 foo student 62 Oct 30 23:25 hello.c
    • foo는 R/W 할 수 있고, student 도 R/W 할 수 있다. 나머지는 only read만 가능하다.
  • drwxrwxr-x 2 foo staff 4096 Oct 30 23:24 programming_test
  • -rw-rw-r-- 1 foo student 32 Oct 30 23:25 test.txt

Modern I/O Systems

다양한 종류의 I/O 장치가 있습니다

• CPU는 디바이스 컨트롤러(device controller)와 상호작용합니다.
  • 디바이스 컨트롤러는 읽고 쓸 수 있는 레지스터 세트를 포함합니다.

Programmed I/O

Port I/O

• 특수 프로세서 명령어를 사용하여 데이터를 전송합니다.
  • 예: 인텔 아키텍처의 in/out 명령어
• 각 장치는 다른 I/O 포트를 사용합니다. (포트 번호)

Memory-mapped I/O

• 디바이스 컨트롤러의 레지스터는 물리 주소 공간에 매핑됩니다.
  • 주소는 하드웨어 점퍼(hardware jumper) 또는 부팅 시 프로그래밍으로 설정됩니다.
• I/O는 로드 및 저장 명령어(load and store instructions)를 통해 수행됩니다.
• I/O 주소 공간이 시스템 메모리 주소 공간의 범위를 차지하기 때문에 프로세스에서 사용할 수 없습니다.

Direct Memory Access (DMA)

Direct Memory Access

• 대량의 데이터 이동을 위해 프로그래밍된 I/O를 피하기 위해 사용됩니다.
• DMA 컨트롤러에게 메모리 버스에 대한 접근 권한을 부여합니다.
• CPU를 우회하여 I/O 장치와 메모리 간에 직접 데이터를 전송합니다.
• DMA 전송을 수행하는 6단계 프로세스

• 디바이스 드라이버는 버퍼 주소 X로 디스크 데이터를 전송하라는 명령을 받음
• 디바이스 드라이버는 디스크 컨트롤러에게 디스크에서 버퍼 주소 X로 C 바이트를 전송하라고 명령함
• 디스크 컨트롤러는 DMA 전송을 시작함
• 디스크 컨트롤러는 각 바이트를 DMA 컨트롤러로 보냄
• DMA 컨트롤러는 주소 X의 버퍼로 바이트를 전송하면서 메모리 주소를 증가시키고 C를 0이 될 때까지 감소시킴
• C가 0이 되면 DMA는 전송 완료를 신호하기 위해 CPU를 인터럽트함

Polling vs. Interrupt

• OS는 I/O 장치가 작업을 완료했을 때를 알아야 하기 때문에 Polling과 Interrupt를 사용한다.

Interrupt

• I/O 장치가 서비스가 필요할 때마다 인터럽트를 생성합니다.
• 예측할 수 없는 이벤트를 잘 처리합니다.
• 디바이스 드라이버에서 처리됩니다.

Polling

• I/O 장치는 상태 레지스터(status register)에 완료 정보를 입력합니다.
• OS는 주기적으로 디바이스 전용 상태 레지스터를 확인합니다.
• 드문 또는 예측할 수 없는 I/O 작업의 경우 많은 사이클을 낭비할 수 있습니다.

일부 장치는 Polling과 Interrupt를 결합하여 사용합니다

• 예: 고대역폭 네트워크 장치
  • 첫 번째 패킷 수신에 대해 인터럽트 발생
  • 이후 패킷에 대해 Polling

Standard Interfaces to Devices(표준 인터페이스 장치)

Block Devices(블록 장치)

• 데이터는 블록 단위로 접근됩니다.
• 예: 하드 디스크, 테이프, SSD
• 명령어: read(), write(), seek()
• 파일 시스템 또는 원시 I/O 접근

Character Devices(문자 장치)

• 예: 키보드, 마우스, 프린터
• 한 번에 한 문자씩 처리
• 명령어: get(), put()

Network Devices(네트워크 장치)

• 예: 이더넷, 무선, 블루투스
• 유닉스와 윈도우는 소켓 인터페이스 포함
• 명령어: create(), connect(), listen(), accept(), send(), receive()

Blocking and Non-blocking I/O

Blocking I/O(봉쇄형 I/O) - "Wait"

• I/O가 완료될 때까지 프로세스가 중단됩니다.
• 데이터 요청 시 프로세스가 데이터 준비될 때까지 대기
• 데이터 작성 시 프로세스가 데이터가 작성될 때까지 대기

Non-blocking I/O(비봉쇄형 I/O) - "Don't Wait"

• 요청된 데이터의 바이트 수를 반환하며 빠르게 종료

Kernel I/O Subsystem

I/O subsystem

• 디바이스에 출력을 위한 간단한 예제

• 이 코드는 많은 다른 디바이스에서 작동합니다.
• I/O 서브시스템은 다양한 디바이스에 대한 표준 인터페이스를 제공합니다.
  • create, open, read, write, close, etc.
• I/O 서브시스템은 디바이스 드라이버와 협력할 프레임워크를 제공합니다.

Device Driver

• 디바이스와 직접 상호작용하는 커널의 디바이스 전용 코드

Kernel I/O Subsystem

A kernel I/O structure

• (애플리케이션 레벨에서 커널 레벨로의 I/O 요청 흐름)
• (하드웨어 장치 드라이버와의 상호작용)

Kernel I/O Subsystem

I/O Scheduling

• I/O 성능 향상을 위해 I/O 요청을 재정렬합니다.
• 예: 디스크 I/O 스케줄링 - SSTF, SCAN, C-SCAN 등

Buffering

• 장치 간 데이터 전송 시 메모리에 데이터를 저장
  • 장치 속도 불일치 문제를 해결
  • 장치 전송 크기 불일치 문제를 해결

Caching

• I/O 성능 향상을 위해 빠른 메모리(fast memory)에 데이터 복사본을 저장

Spooling(Simultaneous Peripheral Operations On-Line)

• 인터리브된 데이터 스트림을 수용할 수 없는 장치를 위해 출력을 보관합니다.
• 데이터를 병렬적으로 처리할 수 없는 장치를 위해 출력을 보류하는 기능을 말함
• 예: 프린터

Kernel I/O Subsystem

A blocking read request example

(1) 사용자 프로세스: 시스템 호출로 I/O 요청

(2) 커널 I/O 서브시스템:

• (2-1) 요청을 이미 충족할 수 있는지 확인, 충족할 수 있으면 데이터 전송 후 완료 상태 또는 오류 코드를 반환하고 (9)으로 이동
• (2-2) 충족할 수 없으면 디바이스 드라이버에게 요청을 전송하고, 적절한 경우 프로세스를 블록 (3)

(3) 커널 I/O 서브시스템: 디바이스 드라이버에게 요청을 전송하고, 적절한 경우 프로세스를 블록

(4) 디바이스 드라이버: 요청을 처리하고, 컨트롤러에게 명령을 전송, 인터럽트가 발생할 때까지 블록하도록 컨트롤러를 구성

(5) 디바이스 컨트롤러: 장치를 모니터링하고, I/O가 완료되면 인터럽트 발생

(6) 디바이스 컨트롤러: I/O 완료 시 인터럽트 생성

(7) 인터럽트 핸들러: 인터럽트를 수신하고, 데이터가 입력된 경우 디바이스 드라이버 버퍼에 데이터를 저장, 디바이스 드라이버를 언블록하도록 신호

(8) 디바이스 드라이버: 완료된 I/O를 확인하고, 상태 변경을 I/O 서브시스템에 표시

(9) 커널 I/O 서브시스템: (적절한 경우) 데이터를 프로세스에 전송하고, 완료 상태 또는 오류 코드를 반환

(10) 사용자 프로세스: 시스템 호출로부터 반환, I/O 완료, 입력 데이터 이용 가능 또는 출력 완료

Hard Disk Internals

Moving head disk mechanism

• 아래 내용은 참고 
  • 트랙(track): 디스크 표면에서의 원형 경로
  • 스핀들(spindle): 디스크를 회전시키는 중심축
  • 섹터(sector): 트랙을 나눈 작은 저장 단위
  • 실린더(cylinder): 동일한 위치의 모든 트랙
  • 표면(surface): 플래터의 저장 공간
  • 플래터(platter): 회전하는 디스크
  • 헤드(head): 데이터를 읽고 쓰는 장치
  • 회전(rotation): 디스크의 회전 운동

• Disk I/O service time
  • 디스크 I/O 서비스 시간: 탐색 시간 + 회전 지연 + 데이터 전송 시간
    • 탐색 시간(Seek time): 디스크 헤드를 원하는 트랙으로 이동하는 시간(위 아래 수직이동)
      • 탐색 시간 ≈ 탐색 거리
    • 회전 지연(Rotational delay): 원하는 섹터가 디스크 헤드 아래에 올 때까지의 회전 시간(수평 이동)
      • 최적의 경우 = 0
      • 최악의 경우 = 한 번의 회전 시간
    • 데이터 전송 시간(Data transfer time): 디스크 매체에서 디스크 버퍼로 데이터 전송 시간
    • 탐색 시간 또는 회전 지연 >> 데이터 전송 시간

Hard Disks

• 플래터 크기
  • 역사적으로 0.85인치에서 14인치까지 다양
  • 일반적으로 3.5인치, 2.5인치, 1.8인치
• 용량
  • 30GB에서 3TB까지 다양
• 성능
  • 전송 속도: 이론적 – 6Gb/sec, 실제 – 1Gb/sec
  • 탐색 시간: 3ms에서 12ms, 데스크탑 드라이브는 평균 9ms
  • 평균 탐색 시간: 트랙의 1/3 기반으로 측정 또는 계산
  • 스핀들 속도 기반 지연 시간: 1/(RPM/60) = 60/RPM
  • 평균 지연 시간 = ½ 지연 시간

Solid-State Disks(SSD)

• 비휘발성 메모리
  • 하드 드라이브처럼 사용되며 다양한 기술 변형이 있음
• 장점
  • 하드 디스크 드라이브(HDD)보다 신뢰성이 높을 수 있음
  • 훨씬 빠름
• 단점
  • 메가바이트(MB)당 가격이 더 비쌈
  • 수명이 더 짧을 수 있음
  • 용량이 적음
• 추가 정보
  • 버스 속도가 너무 느릴 수 있어 PCI에 직접 연결
  • 이동이 필요한 부품이 없어서 탐색 시간이나 회전 지연이 없음

Magnetic Tape

• 초기 2차 저장 매체
  • 오픈 스풀에서 카트리지로 진화
• 특징
  • 비교적 영구적이며 대량의 데이터를 저장
  • 접근 시간 느림
  • 랜덤 액세스는 디스크보다 약 1000배 느림
• 주 용도
  • 백업, 잘 사용되지 않는 데이터 저장, 시스템 간 데이터 전송 매체
• 보관 방식
  • 스풀에 보관되며, 읽기-쓰기 헤드를 지나 감거나 다시 감음
• 전송 속도
  • 헤드 아래에 데이터가 있을 때 디스크와 유사한 속도
  • 140MB/sec 이상
• 일반 저장 용량
  • 200GB에서 1.5TB

NAS(Network-Attached Storage)

• 정의
  • 네트워크를 통해 로컬 연결(버스 등) 대신 사용 가능한 저장소
    • 파일 시스템 원격 연결
• 공통 프로토콜
  • NFS, CIFS
• 구현
  • 원격 프로시저 호출(RPC)로 호스트와 저장소 간 데이터 전송
  • 일반적으로 TCP 또는 UDP를 사용하는 IP 네트워크에서 실행
• iSCSI 프로토콜
  • IP 네트워크를 사용해 SCSI 프로토콜 전송
    • 장치 원격 연결(블록 단위)

Disk Scheduling Algorithms

• Disk I/O scheduler
  • 일반적으로 새로운 서비스 요청은 요청 대기열(request queue)에 배치됨
    • 요청(Request): 디스크 I/O 스케줄러의 스케줄링 단위
      • R/W 유형, 디스크 주소, 섹터 수
  • 요청 완료 시 디스크 I/O 스케줄러는 다음 요청을 선택
  • 평균 디스크 I/O 서비스 시간은 디스크 I/O 스케줄링 알고리즘에 따라 다름

Disk Scheduling Algorithms

• 목표
  • 탐색 시간과 회전 지연 최소화
  • 디스크 컨트롤러에서 실린더 기반 매핑

• 문제점
  • 운영 체제는 회전 지연을 추정할 수 없음
  • 디스크의 회전 속도와 트랙당 섹터 수가 다름
• 평가
  • 요청 대기열(request queue) 상태와 현재 디스크 헤드 위치 제공
  • --> 각 디스크 스케줄링 알고리즘마다 총 헤드 이동을 계산

FCFS (First Come First Served)

• 정의
  • 도착 순서대로 요청 처리
• 예시
  • 요청 상태: R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
  • 디스크 헤드 위치: 22

• 단점
  • 탐색 거리(seek distance)가 너무 김

SSTF (Shortest Seek Time First)

• 정의
  • 현재 헤드 위치에서 최소 탐색 시간으로 요청 처리
• 예시
  • 요청 상태: R1(25), R2(92), R3(56), R4(4), R5(17), R6(52), R7(10), R8(32)
  • 디스크 헤드 위치: 22

만약 처리 순서를 구하라고 하면, 수직선에 각 request 헤드 위치를 표시한 후, 문제에서 주어진 디스크 헤드 위치부터 그리디 알고리즘으로 풀면 된다.

• 특징
  • 그리디 알고리즘
  • 일부 요청이 굶주림(starvation)에 빠질 수 있음

SCAN

• 디스크 헤드가 디스크 한쪽 끝에서 시작하여 반대쪽 끝으로 이동하면서 요청을 서비스함. 끝에 도달하면 방향을 바꿔 계속 서비스함.
• 엘리베이터 알고리즘(elevator algorithm)이라고도 함.
• 예:
  • Queue state => R₁(25), R₂(92), R₃(56), R₄(4), R₅(17), R₆(52), R₇(10), R₈(32)
  • Position of disk head => 22

C-SCAN

• SCAN의 변형임.
• SCAN보다 더 균일한 대기 시간을 제공함.
• 다른 끝에 도달하면 반환 경로에서 아무 요청도 서비스하지 않고 즉시 디스크 시작점으로 돌아옴.
  • cf)SCAN : 다른 끝에 도달하면 방향을 바꿔서 서비스
• 예:
  • Queue state => R₁(25), R₂(92), R₃(56), R₄(4), R₅(17), R₆(52), R₇(10), R₈(32)
  • Position of disk head => 22

C-LOOK

• C-SCAN의 실질적 구현임.
• 디스크 헤드는 각 방향에서 최종 요청까지만 이동한 후, 디스크 끝까지 가지 않고 즉시 방향을 바꿈.
• 예:
  • Queue state => R₁(25), R₂(92), R₃(56), R₄(4), R₅(17), R₆(52), R₇(10), R₈(32)
  • Position of disk head => 22

Disk Formatting

Physical formatting (low-level formatting)

• 물리적 포맷팅 (저수준 포맷팅)
  • 디스크를 사용하기 전에, 디스크 컨트롤러가 읽고 쓸 수 있는 섹터로 나누어야 함.
  • 대부분의 하드 디스크는 제조 과정에서 물리적으로 포맷됨.
  • 이 과정에서 각 섹터에 대한 특수 데이터 구조가 추가됨.
  • 헤더와 트레일러는 디스크 컨트롤러가 사용하는 정보를 포함함.
    • 예: 섹터 번호, 오류 수정 코드 (ECC)

Partition

• 파티션
  • 디스크는 여러 논리 디스크로 나눌 수 있음.
  • 운영체제는 각 파티션을 별도의 디스크처럼 취급할 수 있음.

Logical formatting

• 논리적 포맷팅
  • 운영체제는 초기 파일 시스템 data structures를 저장함.
    • 예: 슈퍼블록, 여유 공간 비트맵 등.

Swap Space Management

Swap space

• 스왑 공간
  • 가상 메모리는 디스크 공간을 주 메모리의 확장으로 사용함.
  • 두 가지 형태로 구현될 수 있음.
    • 파일 시스템 내의 일반 파일 - 예: Windows
    • 별도의 디스크 파티션 - 예: UNIX

Virtual Memory Concepts

Restricted physical memory size

• 물리적 메모리 크기의 제한
  • 물리적 메모리 공간보다 큰 프로그램은 실행될 수 없음.

General program execution pattern

• 일반적인 프로그램 실행 패턴
  • 프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않음.
    • 오류 코드 및 예외 코드
    • 100x100 배열 중 10x10 요소만 사용됨.
    • 프로그램의 특정 옵션 및 기능이 드물게 사용됨.
  • 전체 프로그램이 필요할 때조차도 모든 부분이 동시에 필요하지 않을 수 있음.

Virtual memory

• 가상 메모리
  • 메모리에 완전히 들어가지 않은 프로세스의 실행을 허용.
  • 프로그램의 일부만 메모리에 있어도 실행 가능.
  • 논리적 메모리 주소 공간과 물리적 메모리 주소 공간의 분리.
  • 논리적 메모리 주소 공간이 물리적 메모리 주소 공간보다 클 수 있음.

Virtual Address Space

• 가상 주소 공간
  • (프로그램의 코드, 데이터, 힙, 스택이 각각의 세그먼트로 나뉘어 가상 메모리 공간에 배치됨.)
  • (힙과 스택은 서로 반대 방향으로 성장함.)

Demand Paging

Virtual memory can be implemented via demand paging.

• 가상 메모리는 요청 페이징(demand paging)을 통해 구현될 수 있음.
  • 페이지가 필요할 때만 메모리에 가져옴.
    • I/O가 적게 필요함.
    • 메모리가 적게 필요함.
  • 페이지가 교체(swapped in and out)될 수 있어야 함.

When a page is referenced,

• 페이지가 참조될 때,
  • 유효한 참조면 참조.
  • 유효하지 않은 참조면 메모리에 가져옴.

• 유효-무효 비트(valid-invalid bit)가 각 페이지 테이블 항목과 연관됨. 
  • v(valid) = 메모리에 있음.
  • i = 메모리에 없거나 합법적이지 않음.(bad address, protection violation)
  • 주소 변환 중, 유효-무효 비트가 i면 페이지 폴트(page fault).

Page table when some pages are not in main memory.

• 일부 페이지가 메인 메모리에 없는 경우의 페이지 테이블.
  • (논리적 메모리에서 페이지가 물리적 메모리와 매핑됨. 유효-무효 비트를 통해 페이지의 존재 여부를 확인.) 

Access to invalid page causes page fault.

• 유효하지 않은 페이지 접근은 페이지 폴트를 일으킴.
  • 운영 체제 내의 페이지 폴트 핸들러가 호출됨.

Page fault handler deals with the page fault as follows.

• 페이지 폴트 핸들러가 다음과 같이 페이지 폴트를 처리함.
  1. 유효하지 않은(invalid) 참조인가?
  • 만약 주소 오류나 보호 위반이면 프로세스 중단.
  • 만약 메모리에 없으면 계속 진행.
  1. 빈 페이지 프레임 가져오기.
  • 빈 페이지 프레임이 없으면 일부 페이지 프레임 교체.
  1. 페이지를 페이지 프레임에 읽어오기.
  • 디스크 I/O가 완료될 때까지 프로세스가 차단됨.
  • 디스크 I/O 완료 시 페이지 테이블 항목을 유효(valid)로 설정.
  • 프로세스를 준비 큐(ready quie)에 다시 삽입하고 나중에 dispatch.
  1. 페이지 폴트를 유발한 명령어 재시작.

Demand Paging

Page fault handling

• 페이지 폴트 처리
  • (페이지 폴트 핸들러가 운영 체제에서 참조를 처리함.)
  • (페이지가 디스크에서 메모리로 가져와짐.)
  • (페이지 테이블이 리셋되고 명령어가 재시작됨.)

Page Fault Rate 0 ≤ p ≤ 1.0

• 페이지 폴트 비율 0 ≤ p ≤ 1.0
  • p = 0이면 페이지 폴트 없음.
  • p = 1이면 모든 참조가 폴트.

Effective Access Time (EAT)

• 유효 접근 시간 (EAT)
  • EAT = (1 - p) * 메모리 접근 시간 + p * 페이지 폴트 서비스 시간
  • 예:
    • 메모리 접근 시간 = 200 ns
    • 평균 페이지 폴트 서비스 시간 = 8 ms (8,000,000ns)
    • EAT = (1 - p) * 200 + p * 8,000,000
    • 1,000번 접근 중 1번이 페이지 폴트를 일으키면
      • EAT = 8,200 ns
      • 40배 느려짐.

It is important to keep the page fault rate low.

• 페이지 폴트 비율을 낮게 유지하는 것이 중요함.
  • 좋은 페이지 교체 정책(good page replacement policy) 필요.

Page Replacement

Page replacement

• 페이지 교체
  • 실제로 사용되지 않는 페이지를 찾아 교체.
  • 좋은 페이지 교체 알고리즘은 최소한의 페이지 폴트를 발생시킴.

Locality of reference

• 참조의 지역성
  • 동일한 페이지가 여러 번 메모리에 불러들여질 수 있음.
  • 실제 대부분의 프로그램에서 관찰되는 현상.
  • 일정 시간에 일부 페이지만 집중적으로 참조하는 프로그램 동작.
    • 루프
  • 페이징 시스템의 성능을 좋게 하는 근거.

페이지 폴트 핸들러(page fault handler)에는 페이지 교체가 포함됩니다.

1. 디스크에서 원하는 페이지의 위치를 찾습니다.
2. 여유 프레임(free frame)을 찾습니다.
   • 여유 프레임이 있으면 사용합니다.
   • 여유 프레임이 없으면, 페이지 교체 알고리즘(page replacement algorithm)을 사용하여 희생자(victim)를 선택합니다.
3. 원하는 페이지를 (새로) 여유 프레임에 가져옵니다; 페이지 테이블을 업데이트합니다.
4. 프로세스를 다시 시작합니다.

Page Replacement Diagram

참고)

• 1. 희생 페이지(victim page)를 스왑 아웃합니다.
  2. 페이지 테이블의 유효-무효(valid-invalid) 비트를 무효로 변경합니다.
  3. 원하는 페이지를 스왑 인합니다.
  4. 새로운 페이지에 대해 페이지 테이블을 리셋합니다.

Evaluating Page Replacement Algorithms

• 이상적인 알고리즘(Ideal Algorithm)
  • 가장 낮은 페이지 폴트(page-fault) 비율을 얻습니다.
• 알고리즘 평가 방법
  • 특정 메모리 참조 문자열(reference string)에서 실행하고,
  • 해당 문자열에서 페이지 폴트 수를 계산합니다.
• 예시
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Page Faults vs. Frames

• 페이지 폴트 수 대 프레임 수
  • (페이지 폴트 수와 프레임 수 간의 관계를 나타내는 그래프를 보여줍니다.)

FIFO Page Replacement

• FIFO(First In First Out) 순서로 교체합니다.
• 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• 페이지 폴트 수: 15

FIFO Page Replacement Example

• FIFO 페이지 교체 예시(FIFO Page Replacement Example)
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 3 프레임: 9 페이지 폴트
  • 4 프레임: 10 페이지 폴트
  • 벨라디의 역설(Belady's Anomaly)
    • 더 많은 프레임이 더 많은 페이지 폴트를 초래합니다.

FIFO Illustrating Belady’s Anomaly

• 벨라디의 역설을 보여주는 FIFO
  • (프레임 수와 페이지 폴트 수의 관계를 보여주는 그래프입니다.)

Optimal Page Replacement

• 최적 페이지 교체(Optimal Page Replacement)
  • 가장 오랜 기간 사용되지 않을 페이지를 교체합니다.
  • (LRU랑 헷갈리지 말자. 미래의 페이지 참조를 미리 알고 있다고 가정하고, 가장 나중에 참조되는 페이지를 교체하는 방식임! 미래를 봐야해!)
  • 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Optimal Page Replacement Example

• 최적 페이지 교체 예시(Optimal Page Replacement Example) 
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 페이지 폴트 수: 6
  • 알고리즘 성능 평가에 사용됩니다.
    • 최적 알고리즘은 페이지 폴트 비율의 하한을 제시합니다.

Least Recently Used (LRU)

• LRU (Least Recently Used)
  • 가장 최근에 사용되지 않은 페이지를 교체합니다.
  • 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

• LRU (Least Recently Used)
  • 참조 문자열(Reference string): 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 8 페이지 폴트(page faults)

• 구현 방법? (How to implement it?)
  • 각 페이지에 대한 참조 시간을 기록해야 합니다.
  • 가장 오래된 참조 시간을 가진 페이지를 찾아야 합니다.
  • 너무 큰 공간과 시간 오버헤드 (Too large space and time overhead)
    • 많은 근사 알고리즘이 제안되었습니다.

• 카운터 구현 (Counter implementation)
  • 모든 페이지 엔트리는 카운터를 가집니다.
  • 페이지가 참조될 때마다 시계(clock)가 증가합니다.
  • 페이지 A가 참조될 때, 클럭을 A의 카운터에 복사합니다.
  • 가장 작은 카운터 값을 가진 페이지를 교체합니다.
• 스택 구현 (Stack implementation)
  • 페이지의 스택을 유지합니다.
  • 페이지가 참조될 때, 그것을 최상위로 이동합니다.
  • 교체를 위한 검색이 필요 없습니다.

• 스택 구현 (Stack implementation)
  • 참조 문자열 (reference string): 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 7, 1, 2
  • 스택 변경 전 (stack before a): [2, 1, 0, 7, 4]
  • 스택 변경 후 (stack before b): [7, 2, 1, 0, 4]

LRU Approximation Algorithms

• LRU 근사 알고리즘 (LRU Approximation Algorithms)
  • LRU 페이지 교체를 위해, 많은 시스템들이 하드웨어 지원을 제공합니다.
•  참조 비트 (Reference bit)
  • 각 페이지에 대한 비트가 있고, 초기값은 0입니다.
  • 페이지가 참조될 때 1로 설정됩니다.
  • 0인 페이지를 교체합니다 (존재하는 경우).
  • 그러나 참조 순서를 알 수 없습니다.

• 세컨드 찬스 페이지 교체 알고리즘 (Second chance page replacement algorithm) 
  • 시계 알고리즘 (clock algorithm)
    • 교체할 페이지가 참조 비트 1을 가지면,
      • 페이지를 메모리에 남겨 둡니다.
      • 참조 비트를 0으로 설정합니다.
      • 다음 희생자를 찾기 위해 포인터를 이동합니다.

Counting Algorithms

• 카운팅 알고리즘 (Counting Algorithms)
  • LFU (Least Frequently Used) 알고리즘
    • 참조된 횟수를 기록합니다.
    • 가장 적은 횟수를 가진 페이지를 교체합니다.

Allocation

• 할당 (Allocation)
  • 이전 교체 알고리즘
    • 페이지 폴트가 발생하면 희생자를 선택합니다.
      • 고정 할당(fixed allocation)을 가정했으며, 가변 할당(variable allocation)은 아닙니다.
    • 페이지 폴트 시 한 페이지 프레임을 더 할당하는 것을 고려하지 않았습니다.
  • 할당 문제 (Allocation problem)
    • 페이지 폴트 시 할당 크기를 결정합니다.
      • 고정 할당 (fixed allocation)
      • 우선순위 할당 (priority allocation)

Fixed Allocation

• 고정 할당 (Fixed Allocation)
  • 균등 할당 (Equal allocation)
    • 100개의 프레임과 5개의 프로세스가 있다면, 각 프로세스에 20개의 프레임을 할당합니다.
  • 비례 할당 (Proportional allocation)
    • 프로세스 크기에 따라 할당합니다.

Priority Allocation

• 우선순위 할당 (Priority Allocation)
  • 크기보다 우선순위를 사용하는 비례 할당 방식 사용.
  • 더 높은 우선순위를 가진 프로세스에 더 많은 메모리를 할당합니다.

Global vs. Local Allocation

• 전역 교체 (Global replacement)
  • 프로세스가 모든 프레임 집합에서 교체 프레임을 선택합니다.
  • 하나의 프로세스가 다른 프로세스에서 프레임을 가져갈 수 있습니다.
• 지역 교체 (Local replacement)
  • 각 프로세스가 할당된 프레임 집합에서만 선택합니다.

Thrashing(스레싱)

• Thrashing : 프로세스가 "충분한" 페이지를 가지고 있지 않다면, 페이지 폴트 비율이 매우 높아지는 현상
• 이로 인해 
  • 낮은 CPU 사용률 (low CPU utilization)
  • 운영체제는 멀티프로그래밍의 정도를 증가시켜야 한다고 생각합니다.
  • 또 다른 프로세스가 시스템에 추가됩니다.
• 스레싱 (Thrashing)
  • 프로세스가 페이지를 교환하는데 바쁩니다.

Why does thrashing occur?

• 왜 스레싱이 발생하는가? (Why does thrashing occur?)
  • 지역성 크기의 합이 총 메모리 크기를 초과합니다 (∑ size of locality > total memory size).

Working-set Model

• 작업 집합 모델 (Working-set Model)
  • 메모리 참조 패턴의 지역성 (Locality in a memory-reference pattern) 을 나타낸다
    • 시간적 지역성 (Temporal locality): 상대적으로 짧은 시간 동안 특정 데이터 및/또는 자원의 재사용.
    • 공간적 지역성 (Spatial locality): 상대적으로 가까운 저장 위치 내에서 데이터 요소의 사용.

• 작업 집합 모델 (Working set model)
  • 지역성(locality) 가정에 기반합니다.
  • Δ는 작업 집합 윈도우 (working-set window)로, 고정된 페이지 참조 수를 의미합니다.
• WSS_i (프로세스 P_i의 작업 집합)
  • 가장 최근의 Δ에서 참조된 페이지의 총 수
    • Δ가 너무 작으면 전체 지역성을 포괄하지 못합니다.
    • Δ가 너무 크면 여러 지역성을 포함하게 됩니다.
      • Δ가 무한대이면 전체 프로그램을 포괄하게 됩니다.
• D = ∑ WSS_i = 총 요구 프레임 수 (total demand frames)
  • 만약 D > m 이면, 스레싱이 발생합니다.
  •  --> 프로세스 중 하나를 중단합니다 (suspend).

• 위는 작업 집합 예시 (Working set example)

Page-Fault Frequency Scheme

• 페이지 폴트 빈도 방식 (Page-Fault Frequency Scheme)
  • "허용 가능한" 페이지 폴트 비율을 설정합니다.
    • 실제 비율이 너무 낮으면, 프로세스는 프레임을 잃습니다.
    • 실제 비율이 너무 높으면, 프로세스는 프레임을 얻습니다.

Multistep Processing of a User Program

1. source program(test.c)가 compiler나 assembler에 의해 object module(test.o) 파일로 컴파일 됨(컴파일 시간)
2. linker가 다른 object module과 linking 해줌
3. loader가 모듈과 system library를 load함 (2, 3 과정을 load time이라고 함)
4. loader에 의해 메모리에 올라온 프로세스가(실행시간에) dynamically loaded system library에서 불러온다.

(Windows의 경우 프로세스에서 DLL 파일을 실행시킨 후 프로세스로 복귀함)

Address binding

• 프로그램 명령어와 데이터를 물리 메모리 주소에 연결하는 과정
  • 명령어나 데이터에 접근할 때 주소를 이용하기 때문

• Address binding은 다음 3가지 단계에서 발생할 수 있음
  • Compile time binding
  • Load time binding
  • Execution time binding

Compile time binding

• 만약 프로그램이 메모리에 적재되는 위치를 컴파일 시간에 알고 있다면, absolute address(절대 주소)를 가진 absolute code(절대 코드)가 생성된다

• 만약 시작 주소가 변경된다면(프로그램이 적재되는 메모리 상의 위치가 변경된다면), 반드시 코드 recompile 해야 함

Load time binding

• 만약 프로그램이 메모리에 적재되는 위치를 컴파일 시간에 알지 못한다면, relative address(상대 주소)를 가진 relocatable code(재배치 가능한 코드)가 생성된다

• 프로그램이 메모리에 적재될 때, binding이 일어남
• 프로그램의 start location(적재 위치)가 바뀌더라도, recompile 할 필요가 없다.

Execution time binding

• runtime까지 binding이 지연됨
• CPU가 주소를 생성하면(명령어나 데이터를 참조하기 위해 주소를 요청하는 경우), binding이 일어남

• 컴파일 할 때 상대주소로 변환되고, 메모리에 적재 될 때도 절대주소가 아닌 상대 주소로 적재가 됨
• CPU가 요청한 주소로 접근하기 위해서는 MMU라는 하드웨어의 도움을 통해 address mapping이 일어남
• 대부분 OS가 이 방법을 사용함

정리하자면 절대주소(컴파일 시간, disk에 절대 주소가 저장됨), 상대주소(load time), Runtime Binding(메모리에도 상대주소 상태로 적재)

그리고 아래에 논리 주소가 있음

Memory Management Unit

• Logical address(논리 주소)
  • CPU에 의해 생성되는 주소
  • virtual address(가상 주소)라고도 함
• Physical address(물리 주소)
  
  • 메모리 유닛에 의해 보여지는 주소

• MMU
  • 논리 주소를 물리 주소로 매핑해주는 하드웨어
• Simple MMU scheme
  • relocation register(재배치 레지스터)에 있는 값이 CPU에 의해 생성된 모든 주소에 더해짐

• Program과 CPU
  • 논리 주소만을 다루고, 물리 주소를 절대 알지 못함

Dynamic Loading

• Routine(루틴, 프로시저나 함수로 이해하자)이 호출될 때 까지 load X
• 메모리 주소공간 활용을 효율적으로 할 수 있음
  • 사용되지 않는 루틴은 절대 load X
• 많은 양의 error handling code가 필요할 때 유용하다
  • Error는 자주 발생하지 않기 때문

• Load 할 때 마다 매번 동일한 address가 비어있지 않는다
  • 어디든지 load 될 수 있기 때문에 dynamic linking이 필요하다

Dynamic Linking

Dynamic linking

• Linking이 execution time까지 연기된다

Shared library

• library를 필요로 하는 모든 프로세스에 대해 메모리에 하나의 복사본만 있어도 충분하다

Swapping

Swapping

• 프로세스는 일시적으로 메모리에서 백업 저장소로 스왑된 다음, 나중에 메모리로 가져올 수 있다

Backing store

• 모든 이미지를 수용할 만큼 빠르고 크다
• ex) disks

Contiguous Allocation

• 메인 메모리는 보통 두 파티션으로 나눠진다
  • 하나는 OS로
  • 나머지 하나는 user process로
• 메모리 매핑과 보호
  • 재배치 레지스터(Relocation registers)는 user process를 보호하기 위해 사용됨
  • Limit register는 논리 주소의 범위를 가지고 있음
    • 각 논리 주소는 limit register 보다 작아야 함
    • (Relocation register + logical address) < (Relocation register + limit register : user process 범위)이므로, 파티션을 넘어서 접근하지 못한다
  • MMU는 동적으로 논리주소를 매핑함
    • 재배치 레지스터의 값을 더함으로써 매핑
• Hardware는 연속적인 메모리 할당을 지원함

Memory allocation

메모리 공간은 크게 운영체제를 위한 공간과 프로세스를 위한 공간으로 나눌 수 있습니다.

운영체제는 시스템의 전원이 꺼질 때까지 메모리의 일정 부분을 계속 차지하게 되지만, 프로세스들은 생성과 종료에 따라 메모리 공간을 차지하기도 하고 반납하기도 합니다.

그림 (a)와 같이, 메모리의 윗부분에 운영체제가 있고, 그 아래에 프로세스 1, 프로세스 2, 프로세스 3가 있다고 가정하겠습니다.

프로세스 2가 종료되면 사용중인 메모리 공간을 반납하게 되어 그림 (b)처럼 바뀝니다.

그런 다음, 프로세스 4가 생성되면 그림 (c)와 같은 모양이 되고, 여기에서 프로세스 1이 종료되면 그림 (d)처럼 됩니다.

즉, 프로세스의 생성과 종료에 따라 다양한 크기의 홀(hole)이 메모리 곳곳에 생기는데요.

프로그램은 메모리에 적재될 때 전체 이미지를 수용할 수 있는 홀을 찾아 메모리 공간을 할당해야 할 것입니다.

따라서, 운영체제는 메모리의 어떤 공간을 할당하였는지, 또 어떤 공간이 사용되지 않는지를 지속적으로 관리해야 합니다.

• Hole (가용할 수 있는 큰 블록 메모리)
  • 메모리 상에 다양한 크기의 hole이 흩어져서 존재한다
• process가 생성되면
  • 수용할 수 있을만큼 충분히 큰 hole에 메모리가 할당된다
• OS는 다음과 관련된 정보를 가지고 있음
  • allocated partitions
  • free partitions(hole)

Dynamic Storage-Allocation Problem

프로그램을 메모리로 적재할 때, 다양한 홀 중 어디에 할당하는 것이 좋을까?

P2 / P5 / P7 프로세스에 대한 공간이 할당되어 있고, 나머지 공간은 반납되었거나 한 번도 사용하지 않은 공간. 즉 가용 공간임

운영체제는 가용 공간을 관리 하기 위한 정보를 유지하는데요.

이 예제에서는 100번지부터 140번지까지, 160번지부터 190번지까지, 230번지부터 250번지까지, 그리고 320번부터 400번까지가 가용 공간입니다.

이러한 상황에서 프로세스 8을 생성하여 프로그램을 적재하기 위해 25만큼의 메모리 공간이 필요하다고 가정해 보겠습니다.

이를 수용할 수 있는 가용 공간이 여러 개가 있는데요.

먼저, 최초 적합(first fit) 기법은 프로그램 이미지를 수용할 수 있는 가용 공간 중 첫 번째에 할당하는 방법입니다.

이 예제에서는 100번지부터 시작하는 가용 공간의 크기가 40이므로 이 프로그램을 수용할 수 있고, 따라서 최초 적합 기법에 따르면 이 공간을 할당해 줍니다.

두 번째는 최적 적합(best fit) 기법으로, 프로그램 이미지를 수용할 수 있는 가용 공간 중 가장 작은 것을 할당하는 방법입니다.

이 예제에서는 160번지부터 시작하는 가용 공간이, 수용 가능한 것 중에서 가장 작기 때문에 여기에 할당합니다.

세 번째는 최악 적합(worst fit)으로, 가장 큰 가용 공간을 할당해 주는 기법입니다.

여기에서는 320번지부터 시작하는 가용 공간의 크기가 가장 크므로 여기에 할당하게 되겠지요.

External Fragmentation(외부 단편화)

• 요청을 만족하기 위한 가용 공간이 존재하지만, 연속적이지 않음
• compactation(압축)으로 줄일 수 있음
  • 모든 가용 공간을 하나의 큰 block에 모은다

Internal Fragmentation(내부 단편화)

외부 단편화 문제를 완화하기 위해 메모리를 고정된 크기로 분할하여 프로그램을 적재하는 방법

• 할당된 메모리가 요청된 메모리보다 약간 클 수 있다
• 크기 차이로 인해 파티션 내부에 남는 공간이 생길 수 있지만, 사용되지 않는다

Paging

프로그램 이미지를 통째로 메모리에 적재하는 것은 외부 단편화를 발생시키는 등 메모리 공간을 관리하기 어렵게 만드는데요.

그러한 이유로, 최근의 많은 운영체제는 페이징 기법을 사용하고 있습니다.

페이징 기법은 말 그대로 메모리를 페이지 단위로 관리하겠다는 것인데요.

먼저 메모리를 페이지 프레임이라는 고정된 크기로 나누고, 프로그램 이미지 또한 페이지라는 고정된 크기로 나눕니다.

마치 사진을 액자에 끼우듯 페이지를 페이지 프레임으로 적재하는 방식이지요.

따라서 페이지와 페이지 프레임 크기는 같아야 하고, 일반적으로 512바이트에서 8킬로바이트 사이입니다.

페이징 기법에서는 프로그램 이미지를 한꺼번에 통째로 메모리로 적재하지 않습니다.

프로그램 이미지는 그대로 디스크에 있고, 프로그램이 시작할 때 첫 번째 페이지만 메모리로 적재합니다.

나머지 페이지들은 필요할 때 그때그때 올리면 그만입니다.

따라서 프로그램의 페이지들은 각자 메모리에 있을 수도 있고, 디스크에 있을 수도 있습니다.

또한 페이지들은 연속적으로 적재될 필요없이 메모리의 아무 위치에나 적재될 수 있는데요.

이는 MMU의 일을 더 어렵게 만듭니다. 

즉, 논리 주소를 물리 주소로 바꾸기 위해서는 각 페이지가 어느 페이지 프레임에 적재되어 있는지를 알아야 하는데요.

이러한 정보는 페이지 테이블에 기록됩니다.

• 메모리와 (프로그램)이미지를 고정된 사이즈로 각각 나누는 것
  • page frame과 page
  • 사이즈는 2의 거듭제곱으로, 512B와 8KB 사이
• 전체 프로그램 이미지는 디스크에 있다
• 프로그램이 시작할 때, 첫 번째 페이지 메모리에 적재된다
• 나머지 페이지들은 필요할 때 메모리에 적재된다
• 프로그램의 특정 페이지 X는
  • 이미 메모리에 있는 page frame Y에 적재되었거나
  • 적재되기 전이라, 디스크에 있다
• 페이지는 메모리의 아무 위치에나 적재될 수 있다
• CPU가 주소를 제공할 때 마다 MMU는 page table을 찾는다
  • 논리 주소를 물리 주소로 변한하기 위해

주소 변환

• CPU에 의해 생성된 논리 주소는 두가지 부분으로 나눠진다
• 예를 들어 주소의 길이가 32이고, 페이지의 크기가 4KB라고 해보자

• Page number(p)
  • 페이지 테이블에서 index로 사용된다
  • 인덱스가 가리키는 엔트리에는 해당 페이지가 물리적 메모리에 적재되어 있는 페이지 프레임의 시작주소(base address)가 들어 있다.
• Page offset(d)
  • 물리적 메모리 주소를 정의하기 위해 시작주소와 결합한다
  • 위 예시에서는 하위 12비트의 페이지 오프셋을 더해서 물리 메모리 주소를 얻어냅니다.
  • 페이지 단위로 메모리에 적재하기 때문에 논리주소를 물리주소로 변환하더라도 페이지 내의 오프셋은 변하지 않음

Page number를 페이지 테이블과 비교해서 시작 주소를 얻고, Page offset과 시작 주소를 더해서 물리 주소를 얻는다

Shared pages

페이징 기법의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점입니다.

예를 들어 세 개의 문서 편집기를 실행하여 각각 다른 파일들을 작성한다고 가정해 보겠습니다.

개념적으로는 문서 편집기의 코드를 메모리에 세 카피 두어야겠지만, 메모리에 한 카피만 두고 세 프로세스가 공유하는 것이 효율적일 것입니다.

그림처럼 세 개의 프로세스들은 페이지 테이블을 통해 코드를 쉽게 공유할 수 있습니다.

각 프로세스들은 데이터 페이지만 각각 다른 메모리 공간에 적재해 두고, 코드 페이지들은 서로 공유하고 있는데요.

즉, 세 개의 코드 페이지들이 페이지 프레임 번호 3, 4, 6에 각각 적재되어 있고, 각 프로세스들은 페이지 테이블을 통해 이들을 접근하고 있음을 알 수 있습니다.

Memory protection is implemented

• 각 프레임에 protection bits를 연결
• Read-only, read-write, execute-only bit
• Valid-invalid bit

페이징 장점

• 물리적 메모리보다 큰 메모리 공간을 제공합니다.
  • 32비트 프로세서라면 4GB의 논리 주소 공간이 가능하다.
• 요구 페이징(demand paging) 지원
• 메모리 배치 정책이 필요하지 않습니다.
• 페이지 공유 제공
• 메모리 공간을 서로 보호합니다.

페이징 단점

• 시간적인 오버헤드
  • 페이지 테이블 또한 메모리로 적재되어야 하므로, 메모리에 적재된 코드나 데이터를 접근하기 위해 페이지 테이블을 추가로 접근해야 하는 시간적인 오버헤드가 존재합니다.
  • TLB(Translation Look-aside Buffer) 로 완화
• 공간적인 오버헤드
  • 페이지 테이블을 저장하기 위한 공간이 커질 수 있다는 점
  • Multi-level page table, hashed page table, inverted page table

페이지 테이블의 구현

• 페이지 테이블은 메인 메모리에 보관됩니다.
  • 페이지 테이블 기본 레지스터(Page-Table Base Register, PTBR)는 페이지 테이블을 가리킵니다.
• 모든 데이터/명령어 액세스에는 두 번의 메모리 액세스가 필요합니다.
  • 하나는 페이지 테이블용이고 다른 하나는 데이터/명령어용입니다.
• 두 번의 메모리 접근 문제는 해결될 수 있습니다
  • TLB(Translation Look-aside Buffer)를 사용합니다.

TLB를 사용한 paging

그림은 TLB가 사용된 페이징 기법의 구조를 보여줍니다.

CPU가 요청한 논리 주소를 페이지 테이블을 통해 바로 물리 주소로 변환하지 않고, 먼저 TLB에 저장된 정보를 살펴봅니다.

TLB는 Translation Lookaside Buffer (트렌스레이션 룩어사이드 버퍼)의 약자로, 자주 변환되는 주소 정보를 담고 있는 특수한 하드웨어 캐쉬입니다.

즉, CPU가 요청한 논리 주소에 대한 변환 정보가 TLB내에 있는지 먼저 살펴보고,

변환 정보가 있으면 페이지 테이블을 참조할 필요없이 바로 물리 주소로 변환하고,

변환 정보가 없으면 페이지 테이블을 참조하여 물리 주소로 변환합니다.

하지만 TLB에는 모든 페이지 번호에 대한 정보를 가지고 있는 것이 아니므로, CPU가 요청한 페이지 번호를 찾기 위해 TLB의 모든 엔트리를 탐색해야 합니다.

이는 동시에 모든 엔트리들을 탐색할 수 있는 하드웨어의 도움을 통해 일반적으로 해결합니다.

유효 접근 시간(Effective Access Time)

• TLB lookup time: ε
• Memory access time: 1 
• Hit ratio: α
  • Percentage that is found in TLB.
• Effective Access Time = (1 + ε) α + (2 + ε)(1 – α)= 2 + ε– α

페이지 테이블을 저장하려면 추가 메모리 공간이 필요합니다.

프로그램이 큰 주소 공간을 가지고 있다.

• 32비트 주소를 사용한다면,
  • 4GB 크기의 프로그램을 처리할 수 있습니다.
  • 100만 개의 페이지 테이블 항목 (페이지 크기가 4KB인 경우)
  • 4MB 페이지 테이블 필요 (entry 크기가 4B인 경우, 일반적으로 4바이트임)

페이지 테이블은 프로세스별 자료 구조입니다.

• 페이지 테이블을 저장하려면 4MB *  N(프로세스 수)이 필요합니다.

Page Table의 구조

• Hierarchical Page Table
  • Two level page table scheme(2단계 페이지 테이블)
  • Three level page table scheme(3단계 페이지 테이블)
• Hashed Page Table
• Inverted Page Table

2단계 페이지 테이블

• 페이지 테이블 자체로 페이징된다
  • 모든 페이지 테이블을 디스크에 저장한다
  • 필요할 때 페이지 테이블의 페이지를 적재한다

페이지 테이블 공간 문제를 해결하기 위해 다양한 방법들이 제안되었습니다만, 가장 많이 사용되는 것이 다단계 페이징 기법입니다.

여기에서는 2단계 페이지 테이블 구조를 설명드리겠습니다.

그림의 가장 오른쪽에 메모리가 있고, 가운데에 페이지 테이블이 존재합니다.

이 기법의 핵심은, 페이지 테이블도 메모리에 적재되므로 페이지 테이블 자체를 페이징한다는 것입니다.

즉, 페이지 테이블 전체는 디스크에 저장해두고, 필요할 경우 하나씩 적재하는 방법이지요.

따라서, 페이지 테이블을 구성하는 각 페이지가 디스크 혹은 메모리에 있을 수 있으므로, 이러한 정보를 담고 있는 상위 레벨의 페이지 테이블이 하나 더 필요합니다.

물론 상위 레벨의 페이지 테이블은 항상 메모리에 있어야겠지요.

여기에서는 각각을 구분하기 위해 기존의 페이지 테이블을 내부 페이지 테이블(inner page table), 상위 레벨의 페이지 테이블을 외부 페이지 테이블(outer page table)이라 부르겠습니다.

2단계 페이지 테이블 체계를 사용한 주소 변환

• 논리 주소(4K 페이지 크기의 32비트 주소)가 분할됩니다.
  •  20비트 페이지 번호입니다.
  •  12비트 페이지 오프셋입니다.
•  페이지 테이블 자체가 호출되기 때문에 페이지 번호가 더 분할됩니다.
  • 외부 페이지 테이블의 인덱스는 10비트입니다.
  • 내부 페이지 테이블의 인덱스는 10비트입니다.

3단계 페이지 테이블

64비트 프로세서의 3단계 페이징

Hashed Page Table

• 논리 페이지 번호(logical page number)가 테이블에 해시된다
  • 즉, Hash Table을 사용하여 논리 페이지 번호를 해싱한다.
• 해시 테이블은 동일한 위치에 해시된 요소들의 체인을 포함한다
• 논리 페이지 번호는 체인 내 항목(엔트리)들의 첫 번째 필드와 일치하는지 비교한다
• 만약 일치하는 항목이 발견된다면, 해당 물리 프레임 번호(physical frame number)를 얻는다

(논리 번호를 해시함수에 넣어 얻는 해시 값을 인덱스로 하여 일치하는 페이지 테이블 엔트리를 찾는다)

Inverted Page Table(역 페이지 테이블)

페이지 테이블의 공간 오버헤드

• 페이지 테이블 크기는 프로그램 크기에 비례합니다.
  • 각 페이지(4KB)마다 하나의 페이지 테이블 엔트리(4B)가 필요합니다.
•  실제로는 한 번에 일부 페이지만 필요합니다.

역 페이지 테이블 (Inverted Page Table)

앞에서 봤던 페이징 구조에서는, 논리 주소를 물리 주소에 매핑하는 정보를 담는 페이지 테이블을 이용했다. 이 페이지 테이블은 현재 페이지(page number)가 어떤 프레임(base address)에 저장되있는지를 나타내고 있었다. 즉 page number를 base address로.

하지만 Inverted Page Table에서는 페이지 프레임을 기준으로 매핑 정보를 페이지 테이블에 저장한다. 각각의 프레임들이 어떤 프로세스의 어떤 페이지에 할당되어 있는가를 나타낸다. 따라서 프레임의 수와 페이지 테이블의 엔트리 수가 같다. 페이지 테이블의 i번째 엔트리는 physical memory의 i번째 프레임에 해당한다.

CPU가 pid와 page number를 알려주면, 몇 번째 프레임에 해당하는 지 알려주는 구조이다.

• 각 페이지 프레임마다 하나의 페이지 테이블 엔트리.
  • 각 페이지 테이블 엔트리는 프로세스 ID를 포함해야 합니다.
• 시스템에는 하나의 페이지 테이블만 있으면 충분합니다.
  • 엔트리는 페이지 프레임의 수만큼 필요합니다.
• 이는 연관 검색(associative search)이며, 전체 테이블을 검색해야 합니다.
  • 페이지 테이블을 저장하는 데 필요한 메모리를 줄이지만, 테이블 검색에 필요한 시간이 증가합니다.
  • 따라서 해시 테이블이나 연관 레지스터를 사용해야 합니다.

Inverted Page Table Diagram

역 페이지 테이블 구조도

(참고)

• CPU에서 논리 주소(logical address)를 생성합니다.
  • 논리 주소는 PID, 페이지 번호(p), 변위(d)로 구성됩니다.
• 페이지 테이블을 검색하여 일치하는 항목을 찾습니다.
  • 페이지 테이블 항목은 프로세스 ID(pid)와 페이지 번호(p)를 포함합니다.
• 물리적 주소(physical address)는 프레임 번호(i)와 변위(d)로 구성됩니다.
• 물리적 주소를 사용하여 실제 메모리에 접근합니다.

Segmentation

페이징 기법에서는 프로그램 이미지를 무조건 페이지라고 하는 고정된 크기로 잘라 메모리에 적재하였습니다.

이와는 달리, 프로그램 이미지를 세그먼트 단위로 적재하는 기법이 있는데, 이를 세그먼테이션이라고 합니다.

여기서 세그먼트란 프로그램 이미지를 구성하는 코드, 데이터, 스택, 힙, 심볼 테이블 등을 의미합니다.

즉, 프로그램을 단순히 바이트들의 배열로 보는 것이 아니라, 세그먼트들의 집합으로 이해하고, 이러한 단위로 메모리를 관리하자는 개념입니다.

세그멘테이션 (Segmentation)

• 프로그램은 여러 세그먼트의 집합입니다.
  • (데이터, 힙, 스택, 코드 등 다양한 세그먼트로 구성됩니다.)
  • (각 세그먼트는 물리 메모리에 개별적으로 배치됩니다.)

Segment Table

세그먼트 테이블

• 세그먼트 테이블은 프로그램 이미지 내에서 각 세그먼트의 위치를 나타냅니다.
  • 예: 세그먼트 0, 세그먼트 1, 세그먼트 2, 세그먼트 3, 세그먼트 4.

논리 주소 구성 (Logical address consists of)

• 논리 주소는 <세그먼트 번호, 오프셋>으로 구성됩니다.

세그먼트 테이블

• 각 테이블 엔트리는 다음을 포함합니다.
  • base: 세그먼트가 메모리에 위치한 시작 물리 주소.
  • limit: 세그먼트의 길이.

세그먼트 테이블 베이스 레지스터 (Segment-table base register, STBR)

• 메모리 내 세그먼트 테이블의 위치를 가리킵니다.

세그먼트 테이블 길이 레지스터 (Segment-table length register, STLR)

• 프로그램에서 사용되는 세그먼트의 수를 나타냅니다.
  • 세그먼트 번호 s는 s < STLR일 때 합법적입니다.

Address Translation with Segmentation Architecture

세그먼테이션 아키텍처를 사용한 주소 변환

세그먼트 테이블을 이용한 주소 변환 과정을 그림을 통해 설명드리겠습니다.

CPU가 요청한 논리주소 중 s로 표시된 상위 비트들은 세그먼트 테이블에서 인덱스로 사용되어, base 값을 통해 해당 세그먼트가 적재된 메모리의 시작주소를 알아냅니다.

논리주소 중 d로 표시된 하위 비트들은 limit 값을 통해 요청 주소가 해당 세그먼트의 범위를 넘지 않았는지 확인하고, 넘지 않았을 경우에는 base 값에 더해져서 물리주소로 변환됩니다. (위에서 봤던 limit register가 하는 역할과 비슷)

참고) 그림 설명

• CPU는 논리 주소를 생성합니다.
  • 논리 주소는 세그먼트 번호(s)와 변위(오프셋)(d)로 구성됩니다.
• 세그먼트 테이블에서 세그먼트 번호(s)를 사용하여 베이스(base)와 리미트(limit)를 검색합니다.
• 변위(d)가 리미트(limit)보다 작으면 물리 주소가 계산됩니다.
  • 베이스(base)와 변위(d)를 더하여 물리 주소를 생성합니다.
• 변위(d)가 리미트(limit)를 초과하면 주소 오류가 발생합니다.

Segmentation

보호 (Protection)

• 보호 비트(Protection bits)는 세그먼트와 연관됩니다.
  • 유효성 비트(validation bit).
  • 읽기/쓰기/실행 권한.

코드 공유 (Code sharing)

• 코드 공유는 세그먼트 단위에서 발생합니다.

세그먼트 길이가 다양하므로

• 동적 저장 할당 문제(dynamic storage-allocation problem)가 존재합니다.
  • 첫 맞춤(first-fit), 최적 맞춤(best-fit), 최악 맞춤(worst-fit)을 기억하시나요?

Segmentation에서 "보호 비트를 사용할 수 있고, 코드 공유를 할 수 있고, 동적 저장 할당 문제가 존재한다" 정도 알고 넘어가자