[CS 기초 스터디] 4주차 회의록

정규 회의록

일시 : 2022.11.08 18:30

범위 : 운영체제 10~13강

강의 : 반효경 교수님 운영체제 강의

활동 : github에 올린 내용 정리본 읽고 공부한 내용에 대해 발표 및 질의응답

정리 : https://github.com/GDSC-Ewha-4th/Study-CS.git

---

File

• 메모리는 주소를 통해 접근, 파일은 이름을 통해 접근하는 단위
• File: "a named collection of related information"
• 비휘발성의 보조기억장치(하드디스크)에 저장
• OS는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 관리
• 연산
  • create, read, write, reposition(lseek), delete, open, close
  • open -> file의 metadata를 메모리로 올리기
  • metadata: 파일 이름, 유형, 저장된 위치, 사이즈, 접근 권한(읽기/쓰기/실행), 시간(생성/변경/사용), 소유자,..

File System

• OS에서 파일을 관리하는 부분
• 파일, 메타데이터, 디렉토리 정보 등을 관리
• 파일의 저장 방법 결저
• 파일 보호

Directory

• 디렉토리도 하나의 파일
• 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일
• 디렉토리에 속한 파일 이름 및 파일 metadata
• 연산
  • search file, create file, delete file
  • list a directory, rename a file, traverse the file system

Partition(=Logical Disk)

• 운영체제가 보는 디스크
• 하나의 물리적 디스크 안에 여러 파티션을 둠
• 각 파티션에 file system을 깔거나 swapping 등의 용도로 사용

Open("/a/c")

• 메타데이터에는 file이 저장된 위치를 가리키는 포인터도 포함
• 디스크로부터 파일 b의 메타데이터를 메모리로 가져옴
• c라는 파일의 메타데이터의 위치를 찾아야 함
  • 루트 디렉토리로부터 경로를 따라감 (root의 metadata는 미리 알려져있음)

• open도 시스템콜 -> CPU제어권이 운영체제로 넘어감
• per-process file descriptor table, system-wide open file table
• 루트의 메타데이터(미리 알고있음)가 메모리로 올라감
• 루트의 파일 내용을 열기

• 루트의 하위 파일인 a(디렉토리)의 메타데이터가 있음
• a의 메타데이터를 메모리에 올리기
• a 파일의 하위 파일인 b(디렉토리)의 메타데이터가 있음
• b의 메타데이터를 메모리에 올리기
• PCB의 per-process file descriptor table에 b 메타데이터 위치를 가리키는 fd를 가지고 있음
• fd를 사용자 프로세스의 open의 리턴값으로 반환

이 때, 파일의 메타데이터는 메모리의 system-wide open file table에 올라감

read()

• b를 read하고 싶으면 fd
• b의 메타데이터 위치
• b의 content로 이동
• 사용자 프로세스에게 주기 전에 운영체제가 읽어둠 (buffer cache)
• 다음에 b를 또 read 하면 디스크까지 가지 않아도 운영체제가 그 내용을 줄 수 있음
• 주소 바인딩할 때는 TLB같은 캐시를 사용, 파일시스템에서는 버퍼 캐시
• 파일의 어느 부분을 접근하고 있는지 오프셋이 필요 -> 프로세스마다 필요

File Protection

• 각 파일에 대해서 누구에게 어떤 유형의 접근(read/write/execution)을 허락?
  • 메모리에 대한 protection -> 접근 권한 (read 혹은 write까지 가능)로만 나뉨

Access control Matrix

• access control list: 파일별로 누구에게 어떤 권한이 있는지 표시
• capability: 사용자별로 자신이 접근 권한을 가진 파일 및 권한 표시

Grouping

• 전체 user을 owner, group, public으로 구분
• 각 파일에 대한 권한(rwx)를 3비트씩 표시
  • rwxr--r-- (owner, group, public)

Password

• 파일마다 password를 두는 방법 -> 암기, 관리 어려움

File System의 Mounting

• 한 디스크를 파티션을 통해 여러 논리적 디스크로 나누고, 각 논리적 디스크에 파일 시스템을 설치
• 다른 파티션의 파일 시스템에 접근하고 싶을 때는? -> Mounting
  

파일에 접근하는 방법

• 순차 접근 (sequential access)
  • 카세트 테이프처럼 (테잎을 되감아서 접근)
  • 읽거나 쓰면 offset은 자동 증가
• 직접 접근 (direct access, random access)
  • LP 레코드판 처럼.. -> 임의 접근

Allocation of File Data in Disk - 디스크에 파일 할당

• Contiguous Allocation (연속 할당)
  • 

directory에는 하위 파일의 메타데이터를 가지고 있음 (파일이 할당된 위치 저장: start, length)

• • 단점
  • 크기가 균일 X -> 외부 조각 (external fragmentation)
  • file grow가 어려움 (파일을 수정하면서 크기가 커질 수 있음)
    • 뒤에 빈 block의 한계 -> 제약
    • 미리 큰 hole을 할당: grow 가능 vs 낭비 (internal fragmentation)장점
  • 빠른 I/O가 가능 (대부분의 시간: 헤드의 이동 시간 seek/rotation)
    • start 위치까지만 가면 많은 양의 데이터를 한번에 가져갈 수 있음
    • -> 프로세스의 swapping 용도 (물리적 메모리에서 쫓겨나는 공간)
    • -> realtime 용도
  • 직접 접근이 가능
    • 23위치의 블록이 보고 싶으면 19(start)에서 20, 21,22를 다 볼 필요 없이 한번에 19+4으로 접근 가능
• Linked Allocation (연결 할당)
  • 

파일의 시작, 끝 위치만 적어두고 그 다음 블록의 위치는 그 전 블록에 존재

• • 장점
  • External fragmentation X
  • 단점
  • 직접 접근 X

3번째 블록이 궁금하면? 1-2 블록을 거쳐야 함

• • • 모든 블록에 대해서 헤드 이동 시간(seek/rotation)이 필요
  • reality 문제: 하나의 sector가 고장나면 다음 블록에 대한 포인터가 유실
  • 공간 효율성 문제: 포인터를 위한 공간이 블록의 일부가 되면서 공간 효율성 낮음
  • 변형: FAT(file allocation table) -> pointer을 별도의 공간에 보관
    • -> reality문제와 공간 효율성 문제 해결
• Indexed Allocation (인덱스를 설정한 할당)
  • 

디렉토리에 저장한 파일의 메타데이터에 인덱스 블록의 위치를 저장 &
인덱스 블록에 블록의 위치를 저장해둠

• • 장점
  • 직접 접근 O: 3번째 블록에 접근? 인덱스 블록 -> 3번째 블록
  • External fragmentation X
  • 단점
  • 작은 파일의 경우 공간 낭비
  • 굉장히 큰 파일 -> 하나의 인덱스 블록에 모든 위치를 담지 못함
    • 해결 -> linked schme(인덱스 블록의 마지막: 또다른 인덱스 블록), multi-level index

UNIX의 파일 시스템 구조

• Boot block: 부팅에 필요한 정보 (bootstrap loader)
  • 파일 시스템 종류와 상관없이 디스크의 맨 처음 블록은 부트 블록
• Super block: 파일 시스템의 총체적 정보 관리
  • 어디가 빈 블록이고, 어디가 사용중인 블록인지 관리
  • 어디까지가 Inode list, 어디부터 Data block인지 관리
  • 블록의 크기, inode의 수, data block의 수, free block list의 head
• Inode list: 파일의 메타데이터를 가지고 있음
  • 파일 이름(디렉토리에 위치) 외 나머지 메타데이터
  • : 위치정보, owner, timestamp, size block, count, ..
• Data block: 파일의 실제 내용 보관
  • 디렉토리에는 파일의 이름과 Inode의 번호(Index block)

Unix에서는 Indexed allocation를 사용 (Inode list에 있음(=위치정보))

• 파일이 작으면 direct blocks로 파일의 위치를 가리킴
• 큰 파일 -> single indirect, double indirect, triple indirect, ...? (multi-level index)

FAT 파일 시스템 구조

• Boot block: 부팅에 필요한 정보 (bootstrap loader)
• FAT: 메타데이터 중 일부(=위치 정보)를 FAT에 보관
  • 나머지는 디렉토리 - 파일의 시작 위치, 파일 이름, ...
  • 다음 위치를 데이터 블록이 아닌 FAT에 보관
  • 217(시작 위치는 디렉토리에) -> FAT의 217:618 -> 618 -> FAT의 618:339 -> 339 -> FAT의 339: EOF 끝
  • Linked Allocation: disk 헤드가 블록을 따라 이동해야 함 (순차 접근만 가능)
    • FAT에서 n번째 블록의 위치를 알게 된 후에는 직접 접근 가능
      • FAT에서는 이동해야 하는 것은 맞지만, FAT 배열을 메모리에 올려둔 후에는 메모리 상에서만 이동하면 됨 (디스크 헤드 이동 필요 X -> 훨씬 빨라짐)
    • FAT에 포인터 존재, FAT을 2개 이상 카피 -> reliablity 문제 해결
• Root directory: 루트 디렉토리
• Data block: 파일의 실제 내용 보관

Free-Space Management

• Bit map or Bit vector
  • 각 블록이 사용중인지 여부를 디스크 블록만큼의 bit map에 관리
  • bit[i] = { 0: free, 1: occupied }
  • 부가적인 공간 필요
  • 연속된 n개의 free block을 찾는데에 효과적
  • UNIX 파일 시스템 - Super block에 위치 (파일 시스템의 총체적 정보)
• Linked list
  • 모든 free block을 링크로 연결 (=> free list)
  • 어차피 비어있으니깐 블록에 포인터로 서로를 연결시켜둠

첫 위치인 free space list head로 보관하면 됨 = 공간 낭비 X

• • 연속된 free block을 찾기 어려움
• Grouping
  • linked list의 변형
  • 첫번째 free block이 n개의 포인터를 가짐
  • n-1번째 포인터는 free data block을 가리킴
  • 마지막 포인터가 가리키는 block은 또다시 n개의 포인터를 가짐
  • 
• Counting
  • (first free block 위치, # of contiguous free block)
  • 프로그램이 반납할 때 한번에 여러개를 반납한다는 성질 이용

Directory 구현

디렉토리 -> 하위의 파일의 메타데이터를 관리

• Linear list
  • <file name, file의 메타데이터>의 리스트
  • 구현하기에 간단함
  • 디렉토리 내에 파일을 찾기 위해서는 순차적 linear search 필요 (시간 오래걸림)
  • 고정된 크기의 entry -> file name이 고정 크기를 넘을 경우도 지원
  • 
• Hash Table
  • linear list + hashing
  • file name을 hash function에 넣어서 계산 후 결과값 F에 넣음
  • <F(file name), file의 메타데이터>
  • hashing -> search time을 없앰, collision 발생 가능성
  • 

File의 메타데이터 보관 위치

• 일부는 디렉토리 내에
• 디렉토리에는 포인터를 두고 나머지는 다른 곳에 보관 (UNIX: inode, FAT 등)

Long file name의 지원

• <file name, file의 메타데이터>의 list에서 각 entry는 고정 크기
• 고정 길이를 넘어가는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 보관
• => 포인터가 가리키는 곳에 이름의 나머지 부분이 존재

VFS와 NFS

• VFS (Virtual File System)
  • 다양한 file system에 대해 동일한 시스템콜 인터페이스(API) 를 통해 접근할 수 있도록 하는 OS의 계층
• NFS (Network File System)
  • 분산 시스템에서는 네트워크를 통해 원격 파일이 공유
  • 서버쪽 클라이언트쪽 각각의 NFS 모듈이 존재
  • NFS는 분산 환경에서 대표적인 파일 공유 방법

Page Cache and Buffer Cache

• Page Cache
  • virtual memory의 paging 시스템에서 사용하는 page frame을 caching의 관점에서 설명
  • page: 블록 여러개
  • 느린곳: 디스크(swap area), 빠른곳: 메모리의 페이지 프레임
  • CPU가 필요한 페이지를 참조할 때, 디스크까지 안 가고 메모리에서 사용 - 캐슁
• Memory-Mapped I/O
  • 원래는 파일 시스템에 접근하기 위해 read, open 시스템콜이 필요
  • 하지만, 파일의 일부를 virtual memory에 mapping 시킴
  • 파일을 I/O가 아닌 메모리 접근 연산으로 I/O 가능
• Buffer Cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 OS 영역의 Buffer cache 사용
  • 디스크를 읽어야 할 때, 시스템콜(IO)
    • OS는 읽은 파일의 내용(블록)을 먼저 읽어서 buffer cache에 보관해두고, 사용자 프로세스에 줌
  • file 사용의 locality 활용
    • 한 번 읽어온 block에 대한 후속 요청: buffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacement 알고리즘 필요 (LRU, LFU)
  • 느린곳: 디스크(file system), 빠른곳: 메모리의 OS영역
• Unified buffer cache
  • 최근 OS에서는 기존의 buffer cache + page cache 통합
  • page: 4K byte, block: 512byte -> 4Kbyte로 통합

• page cache와 buffer cache 통합

프로그램의 실행

디스크의 파일시스템에 있는 프로그램 실행

-> virtual memory의 독자적 address space

-> 당장 사용하면 physical memory & 당장 사용 X 디스크의 swap area

프로세스의 주소 공간 중 code segment

• 코드 자체가 파일 시스템의 실행파일에 존재 (read only 형태로)
• 당장 사용하지 않으면 swap out 대신 지워버려도 됨 (파일 시스템에 존재하니깐..)
  • 필요하면 파일 시스템에서 가져오면 됨
• = memory mapped I/O 활용되는 예
• = 프로그램을 실행시키는 로더가 하는 일
  • 소스 코드 -> 컴파일러: 컴파일 -> 실행파일 -> 로더: 로드 -> 실행

데이터 파일의 사용

• memory mapped I/O 방식
  • 프로세스의 일부(data segment) 메모리에 데이터 파일을 매핑
  • -> 파일을 IO 하는 대신 메모리를 읽으면 됨
  • page fault 발생 -> swap area가 아닌 파일시스템을 찾음
  • 장점: 한 번 매핑 이후에는 시스템콜 X, 직접 메모리 읽기 쓰기 가능
  • 문제: 한 파일을 여러 프로세스가 매핑했을 경우 write로 변경한 것이 모두에게 바로 반영 X
• read write 시스템콜 방식
  • 시스템 콜로 read -> OS가 데이터를 읽어서 프로세스의 data segment에 카피
  • 원본을 운영체제(시스템콜 이용)가 관리하기 때문에 바로 반영

---

Disk 구조

logical block

• 디스크와 외부에서 보는 디스크의 단위 저장 공간
• 디스크 외부(컴퓨터 내부, 호스트)에서 디스크로 요청할 때는 논리적 블록으로 요청

주소를 가진 1차원 배열처럼 취급

• 정보를 전송하는 최소 단위

sector

• 디스크 내부의 저장 위치 (track, sector 번호)
• 디스크 컨트롤러가 처리
  • 논리적 블록과 1:1 매칭
• Sector 0은 최외곽 cylinder의 첫 트랙의 첫 섹터
  • 모든 파일시스템의 디스크의 0번 블럭은 boot block

Disk Management

Physical formatting (low-level formatting)

• 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
• sector = header + 실제 data(512byte) + trailer
• header와 trailer에는 sector number, ECC(error correcting code) 등의 정보, controller가 직접 접근 및 운영

Partitioning

• 디스크를 하나 이상의 cylinder 그룹으로 나누는 것 -> Logical Disk
• OS 입장에서는 partitioning된 logical disk를 독립된 disk로 봄
  • 서로 다른 파일 시스템 설치하는 것도 가능.. 독립된 디스크니깐..

Logical formatting

• 파일 시스템을 만드는 것
• FAT, inode(UNIX), free space 등의 구조

Booting

• ROM에 있는 "small bootstrap loader"
  • DRAM 옆에 있는 비휘발성 메모리 (Read Only Memory)
• Sector 0의 boot block을 load하여 실행
• Sector 0은 "full Bootstrap loader program"
  • OS를 디스크에서 load하여 실행

Disk Scheduling

Access time

= Seek time + Rotational latency + Transfer time

• Seek time
  • 헤드를 원하는 실린더로 움직이는 시간 (가장 큰 시간)
  • Disk Scheduling => Seek time을 최소화
• Rotational latency
  • 헤드가 원하는 섹터로 도달하는데 걸리는 시간 (platter 회전 시간)
• Transfer time
  • 실제 데이터의 전송 시간

Disk bandwidth (대역폭)

• 단위 시간 당 전송된 바이트 수

Disk Scheduling 알고리즘

• FCFS (First Come First Served)
• SSTF (Shortest Seek Time First)
  • 현재 위치에서의 Seek time이 짧은 위치의 요청을 먼저 service
  • -> starvation 문제
• SCAN
  • disk arm(head)는 줏대있게 A(한쪽 끝)에서 B(다른쪽 끝)으로 왕복하면서 길목에 있는 요청을 처리
  • 단점: 실린더 위치에 따라 대기 시간이 다름 (방금 지나간 위치에 요청이 오면 꽤나 오래 기다려야 함)
• C-SCAN
  • 헤드가 A(한쪽 끝)에서 B(다른쪽 끝)으로 이동 후, 다시 A로 돌아감
  • B에서 A로 돌아가는 과정에서는 서비스 X
  • 다시 A에 도착하면 B로 이동하면서 job 처리
  • 대기 시간이 균일해짐, 대신 대기 시간이 길어질 수는 있음
• N-SCAN
  • 헤드가 움직이기 시작하면, 그 시점이후에 온 요청은 되돌아올 때 서비스
    • 출발한 시점 이전의 요청까지만 처리
• LOOK
  • 헤드가 진행중이다가 그 방향에 더이상 요청이 없으면 더이상 안 가고 되돌아 감
• C-LOOK
  • 헤드가 진행중이다가 그 방향에 더이상 요청이 없으면 더이상 안 가고 되돌아 감
  • +) A-->B 후에 B에서 A로 돌아가는 과정에서는 서비스 X

디스크 스케줄링 알고리즘은 다른 알고리즘으로 쉽게 변경할 수 있도록 OS와 별도의 모듈로 작성!

Swap-Space Management

디스크 Partitioning => file system(logical disk 1) + swap area(logical disk 2)

• file system -> memory의 volatile한 특성 해결
  • 512byte 단위의 섹터(논리적 블록) 단위로 관리
  • 요즘은 호스트 컴퓨터와 디스크가 데이터를 주고 받는 단위인 4Kbyte로 관리
  • 전원이 나가도 유지 -> 공간효율성 필요
• swap area -> 프로그램 실행을 위한 memory 공간의 부족 해결
  • 프로세스가 살아있는 동안에만 필요 (전원이 꺼지면 필요 없어질 데이터)
    • -> 공간 효율성 X, 속도 효율성 O
    • 프로세스가 돌아가면서 메모리 <-> Swap area 이동을 빠르게 해야함
      • 헤드 이동을 줄이기 위해 대용량의 데이터 단위로 관리

RAID

Redundant Array of Independent Disks

= 여러 개의 디스크를 묶어서 사용

• 디스크 처리 속도 향상
  • 여러 디스크에 block의 내용을 분산 저장 (중복 저장)
  • 병렬적으로 읽어옴 (interleaving, striping) -> 더 빠르게 읽을 수 있음
• 신뢰성 (reliability) 향상
  • 동일 정보를 여러 디스크에 중복 저장
  • 하나의 디스크가 고장나도 다른 디스크에서 읽어오면 됨 (Mirroring, Shadowing)
  • 완벽 중복 저장이 대신 일부 디스크에 parity를 저장하여 공간 효율성을 높일 수 있음
    • 디스크가 고장나더라도 다른 디스크의 parity를 활용해서 복원하거나 고장난 사실을 알아챌 수 있음