[CS면접 Handbook] 2편 System Programming

이전에는 일반적인 OS의 여러 기능들을 추상적으로 살펴보았는데요, File System과 network에 대해서는 설명하지 않았습니다. SP에서는 Linux의 FS, network Implementation을 중점적으로 설명합니다. 일반적으로 면접에서 나올만한 질문들은 아닐 것 같습니다. 

• File: variable length, persistnet, 연속적임
• Address Space: fixed length, volatile, 비연속적 (text data stack)
• File System의 목적은 data를 읽고 저장하고 쓰는 최소한의 기능 제공을 목표로 한다. 하지만 DB system은 consistency를 보장하는 것이 주된 목적이다. FS에서는 failure semantics가 보장되지 않는다. Persistent yet consistent. 운영체제의 일부인 FS는 fundamental만을 제공하고자 한다. 
• File system: file과 disk간 mapping제공. 사용자는 file 접근을 위해서 물리적으로 저장된 위치를 알 필요가 없다. 
• metadata - File Attribute: name(파일명), type(운영체제에서 지원하기 위한 정보로 주로 확장자에 해당함. executable, mp4, etc), location: 저장장치에 기록되어 있는 블록 위치, size(파일 크기), protection: 파일 read,write, execution권한, time, .. directory, inode(disk속 물리적 위치) 등등
• Metadata는 원래는 disk에 존재하나 자주 caching된다. Caching한다면 언제나 inconsistency를 걱정해야 한다. File의 inconsistency를 처리하기 위해서 failure semantics를 정의하는데 그것이 바로 journaling file system이다. Journal에 file의 change를 임시저장한다. 이러한 journal은 NVRAM(non-volatile ram)에 기록된다. Metadata caching은 디지털 포렌식이 가능한 이유와도 관련성이 깊은데, file delete시에는 metadata만 사라지기 때문에, disk속에는 자료가 남아있는 것이다. 과거 부팅이 오래걸렸던 이유는 meta data와 관련이 깊은데, storage가 크면 클수록 부팅이 오래걸렸다. storage전체에 있는 file들의 metat data를 가져와야 했기 때문이다. 
• File operation: create, write, read, fileseek(current-file position 포인터를 특정 위치로 옮긴다.), delete, open(meta data 캐싱), close(meta data를 디스크로 저장)
• current file position 포인터란 파일을 읽거나 쓸 때마다 자동으로 업데이트 되는 포인터로 파일에 대해 프로세스가 어디까지 작업을 했는지를 기록하는 포인터. (pagination을 위해 사용하는 index를 떠올리면 좋을 듯하다)
• file의 사용순서는 언제나 다음과 같다. open(2) - read -close(2)
• 여러 프로세스가 파일을 어떻게 공유할까? per process table, system-wide-table이 존재한다. per process table의 경우에는 file pointer들을 가지고 있는다. process마다 fp가 필요하다. 여러개의 프로세스가 하나의 file을 모두 read할 수 있기 때문에. System-wide table에서는 access date, file location, open count를 기록한다. open(2) 은 open count를 증가시키고, close(2)는 감소시킨다. delete는 system-wide table에서 open count를 확인한 후에 지워지도록 한다. 
• soft link(삭제시 link만 삭제), hard link(삭제시 원본까지 삭제). hard link의 경우 원본 파일의  inode를 가르키고, soft link는 원본 파일의 inode를 가르킨다.
• 일반적으로는 directory와 device는 분리되어 있다. 다만 windows는 C: 로 device를 정해두었다. 
• Mount: 비어있는 디렉토리에 임의의 device를 붙이는 개념이다. 

시스템프로그래밍-2021-2-유혁

• Namespace : a set of symbols. (도커 컨테이너는 서로 다른 namespace) mount된 뒤에는 모두 같은 namespace를 가진다.
• FS가 달라도, remote storage여도 mount가 가능하다(NFS). 
• access types in protection: read,write, execute 3개가 존재한다. 1 1 1 => 7, 1 1 0 => 6 , 0 0 1 =>1
• group의 경우 etc/group에서 정의, access 변경은 chmod(1) 사용, onwer나 group으로의 변경은 chown(1), chgrp(1) * 소괄호 속 숫자가 1이면 command line, 2이면 system call이다. 
• Storage내 data block이 저장되는 방식은 다음이 대표적이다. 
• contiguous allocation: 물리적으로 연속된 공간에 있으므로, 전체 파일을 읽어들일 경우 성능이 매우 뛰어나다. 하지만 파일은 반드시 한번에 끝까지 기록되어야 하며, 확장을 위해 끝에 예비용 block을 남겨둘 경우 disk공간 낭비가 발생한다. Netflix streaming처럼 read작업이 많은 경우 효율적임. 

• Linked List Allocation: 공간낭비가 없다. 하지만, random access가 불가능하다. file의 특정 위치가 알고 싶으면 file의 시작노드부터 찾아야 한다. 또한 다음번 block을 지시하는 pointer를 둘 수 있다. 
• Linked List using index

• Inode(실제 사용되고 있다)
• file에 대한 data block index를 계층으로 관리한다. 이전의 경우 1 level paing보다 multi-level paging이 유리한 것과 비슷하다. 

• block size 4KB, pointersize=4B 를 기준으로, direct block= 4KB *12, single Indirect= 4KB*1024 = 48KB, doulbe indirect= 4KB*1024*1024 = 4MB, 1024= 4KB/ 4B
• Ms-DOS에서의 directory표현은 꽤나 복잡하다. MS는 Linked List Allocation을 채택하고 있음. 
• Linux에서의 directory 표현은 꽤나 간편하다. Linux는 i-node이기에 i-node number+ file name에 불과하다. 

• 주요한 directory inode의 경우는 cache해둔다. 
• File System 계층화: 파일 시스템 역시도 여러 개의 계층으로 나뉘어져있다. 코드  중복 방지를 위해서.

• Logical File System: 파일 시스템 메타 데이터 관리
• File-organization module: 파일의 논리 블록 주소를 물리 블록 주소로 변환, 각 파일의 논리 블록은 0부터 N까지 번호가 주어지며, 데이터를 실제 저장하는 물리 블록은 저장장치 주소임. 
• Basic File System: 장치 드라이버에게 저장장치의 물리 블록을 읽고 쓰도록 명령을 내림. 
• I/O control: 장치 드라이버가 저장장치 하드웨어에 명령어 전달. Device Driver는 device specific 하다. 
• VFS(virtual file system): 다양한 FS를 abstract한다. Disk용, flash, USB, CD-ROM, 등 다양한 FS를 편리하게 사용한다. VFS의 구현을 위해 overloading 개념을 활용함. (c언어라 function pointer로 활용함) (오버로딩이란? 메서드 명이 중복될 때 parameter를 비교함으로써 implicit하게 적합한 메서드로 매핑되는 것)
• Inode는 file의 자료구조이다. 그렇다면 FS의 자료구조는 어떻게 구성되어 있을까?

• Boot Block은 디스크의 첫번째 블록으로 운영체제가 시작하기 위해서 필요한 정보를 가지고 있는 block이다. 
• Super Block: 현재 마운트된 FS당 하나씩 주어진다. Inode table의 위치를 저장하고 있다. superblock의 경우 inode자료구조로 구현되어있으며 memory에 주로 cache된다. 
• 한편 여태까지는 on-disk 자료구조들을 살펴보았는데  in-memory structure도 존재한다. 
• System-wide open file table, per process open-file table, 이전의 file open, delete를 관리하기 위한 테이블이다. 
• FD(file descriptor): per process file table에서의 index로, 각 process에서 파일에 부여하는 index이다. 
• Dentry: 디렉토리 접근과 관련된 내용에 대한 cache
• Buffer cache: process에서 작성한 내용을 write back하기 전까지는 메모리에 write한다. 우리가 저장버튼 안누르고 무언가 작성하는 경우를 생각하면 좋다. Buffer Cache Policy: physical memory의 1~10%가 할당되어야 한다. LRU가 제일 일반적이다. 
  • 단, DBMS는 failure semantics issue 때문에 buffer cache를 사용불가능하다. multimedia application 의 경우에도 LRU에서 이득을 볼 수 없어서 buffer cache를 사용하지 않는다. 노래를 듣거나, 동영상을 보는 경우, 글을 작성중인 경우를 생각해보자.  글을 작성하는 경우에는 앞선 내용을 수정하는 일이 발생할 수 있다. cache가 이득일 수 있다. 하지만 나머지들은 그럴 일이 없기에 cache하는것이 큰 의미가 없을 수 있다. 
  • write과정에서 만약 write한 대상이 in-memory cache라면 dirty bit=1로 설정하고, kernel daemon이 이러한 내용을 DB에 수정하도록 한다 (커널에는 이러한 역할을 수행하는 kernel thread가 존재한다. data:30초, metadata:5초 마다 동작한다. 한편 fsync(2) syscalo을 통해서 강제적으로 반영시키는 것도 가능하다. 
• Memory-Mapped File System: file을 address space의 일부에 mapping시킨다. mem read, memwrite instruction만으로 file에 대해서 read write를 수행할 수 있는 장점이 존재한다. 
• UFS: unix file system에선 블록 사이즈가 작아서 throuput이 작았다. datablock의 위치도 임의적으로 되어있어서 inode와 data block간 거리가 멀었다.이를 해결하기 위해서 FFS(fast file system)에서는 블록 사이즈를 넓혔다(4KB). 또한, fragmentation을 활용하였다. (internal fragmentation). 또한 cylinder group을 정의해서 한 그룹 내에 superblock, inode, file을 배치했다. 같은 디렉토리에 속한다면 같은 cylinder group내에서만 이동하면 되도록.
• 디스크 접근시간: accesstime= seektime(arm의 이동시간)+rotationdelay(spin시간)+transferdelay
• Process Scheduling과 마찬가지로 disk Scheduling역시 다양한 방법이 존재한다. (1) FCFS , (2)SSTF(shortest seek time first 가장근처), (3) SCAN(쭉 갔다가 돌아옴. 다만 variance가 높음) (4)C-SCAN(끝까지 한방향으로만) (5)C-Look(끝까지는 안가고 마지막 스케줄까지만)
• 이러한 disk scheduling은 file allocation 방법에 영향을 받게 된다. contiguous allocation의 경우 linked 혹은 indexed allocation방법보다 유리할 것이다. (만약 contiguous하게 allocate되어있는 경우 SCAN과 비슷한 형태가 유리하긴 할 것이다. 영상이 연속적이므로)
• NAND flash: 유한한 delete lifetime을 가지고 있다. SSD의 경우 7~80%가 점유되면 성능이 확 떨어진다. erase가 부담스러워지기 때문이다. 이러한 SSD를 활용하기 위해서는 ext4+ftl(flash translation layer)를 활용하나, F2FS를 활용하기도 한다. 
• Flash friendly fs의 대표주자 LFS(log-stuctured file system) wear leveling을 고려해서 균등하게 write가 이뤄지도록 해야 한다. LFS를 활용하게 되면 crash recory 상황에서 가장 마지막 작성한 부분만을 확인하면 되는 장점이 있다. 기존의 FS에서는 disk전체를 비교해야 한다. 

sequential write

• 모든 update내역이 남아버리기 때문에 append가 되면 디스크 공간이 사라진다. 또한 read시 indexing이 어렵다. 
• Linux. FS에선 superblock으로부터 차례차례 모든 data block에 접근하는게 가능했는데 지금은? 이를 해결하기 위해서 inode map을 도입한다. Inode map은 각 inode의 현재 위치를 기록하고 있다. (결국 superblock이랑 비슷한 기능이네. 역시 memory에 cache된다).  만약 write중인데 지우면 안되는 data가 있다면? live data는 다른 segment로 복사해서 모아준다. 아니면 해당 블록은 건너뛰어서 write한다.

결국 fraction alive를 보게되면 50%이하일때는 log-structured가 FFS보다도 유의미하게 좋다. (하지만 FLASH에선 선택권이 없다. LFS써야 SSD오래쓸 수 있다)

• Container: 컨테이너느 cgroup 메커니즘을 활용해서 컨테이너 활용할 수 있는 CPU와 memory 점유율을 제한할 수 있다. 또한 각자의 namespace를 가짐으로서 pid\, mountpoint, network에 대해 독자적인  symbol table을 가질 수 있다.
• 컨테이너 file system은 union file system이다. overlay FS or layered or auFS 라고 불린다. 겹치는 파일/디렉토리가 있으면 나중 layer가 우선된다. => single coherence 보장
• DKI: drive kerenel interface. 커널의 file system은 uniform하지만 device driver은 hw dependent 하다. 이를 위해서 DKI를 둔다. OS마다 DKI가 다르기에, 하드웨어 제조사에서는 OS마다 devcie drvier를 다르게 작성한다.  Windows는 HAL, linux는 loadable module로 이를 해결하고자 노력한다.
• Device is a file for kernel. /dev/tty0에 존재함. 대부분읜 device는 FS의 지원을 받아야 IO가 가능하지만 character device의 경우, fs의 지원없이 IO가능.
• sysfs: pseudo file sysem. device information을 kernel 에서 user space로 가져온다. /proc fs를 보충한다. 
• RAID: (redundany arrays of independent disks): 디스크 가격이 저렴해짐에 따라 디스크를 많이 사용함으로써 reliability와 performance 이점을 얻어보자. 단, performance향상을 위해선 PCI bus가 충분해야 함.

• RAId0: 하나의 disk fail시 전체가 무의미해짐. RAID1: reliability가 높아지지만 어떤 것이 옳은 내용인지 검증불가
• RAID2: bit level strip으로써, code parity를 제공한다. 4bit에 필요한 code parity bit은 3개, RAID3: parity가 fail시 복구할 수 없으며, parity 디스크 접근에 병목 발생; Disk3= disk0^(disk1^disk2) 
• RAID4: block level strip, parity disk접근에 병목 발생, RAID5: RAID0보다 낮은 읽기 성능, parity필요에 따른 RAID1보다 낮은 쓰기 성능. 왜냐하면 parity는 write가 완료된 이후에나 적힐 수 있으며, 또한 read 시에도 반드시 parity를 통한 검산작업이 필요해지기 때문에 성능이 떨어지게 된다.
• Network-attached Storaged: NAS: 저장장치가 네트워크상 존재한다. file sharing protocol이 필요해진다. 내 컴퓨터의 namespace에 없기 때문이다. NFSP(network file sharing protocol)이 각 OS마다 존재한다. linux:NFS, ms:SMB/CIFS, apple: AFP
• NFS의 인증: 초기에는 IP로 인증을 해줬다. 하지만 server user의 UID와 client user UID가 같다면 문제가 발생한다. server에서 모든 권한을 얻어버릴 수도 있다. NFSv4 부턴 kerberos를 사용한 인증
• NFS: unix like system끼리 연결에 최적화. SMB: windows환경 내 연결에 최적화, NFS에 비해 성능이 좋지X

NFS개요

• RPC의 stub: marshaling을 담당한다. endian을 맞추고, pointer를 없앤다. function call을 할 때 우리는 pointer를 자주 사용하는데 pointer를 remote에게 넘기는건 엉뚱한 주소를 넘기는 행동이다. 당연히 array라면 int * 가 아닌 복제된 전체 값을 넘겨야 한다. 즉, scala값 만을 주고받아야 한다. NFS에서 rpc를 활용한다. 이때 주고받는 패킷의 형식은 XDR. RPC를 활용한다면 자율주행차의 경우 외부 서버에 연산을 위임하는것이 가능하다. RPC는 NFS, VDI에 적용된다.

RPC 개요

• REST: 한편 웹 쪽에서 rest 라는 패러다임이 등장한다. URL기반의 리소스. REST에서는 함수의 동작은 모르지만 내가 보고 시픙ㄴ data, file을 url을 통해서 볼 수 있음. 나머지 function은 underline에서 처리하는 것임. RPC는 function oriented, REST는 data oriented라는 본질적 차이가 있음. REST에서의 data 교환은 json이나 xml기반의 text기반이다. 
• gRPC: http/2 기반의 RPC. Protocol buffer가 존재해서, payload data를 serialize한다.
• Kerbreos: 3rd party ticket management 가 필요하다. symmetric key protocol기반이다. UDP port 88사용
• 가정: AS는 tgs secrey key를 가지고 있음. TGS는 SS의 secret key를 가지고 있음. 
• Client는 AS에 id를 보낸다. 그러면 AS는 password를 이용해서 secret key를 만든다. 이후, secret Key ENCRYPTS(TGS session key) 그리고 TGS secret key ENCRYPTS(clientid, valide period, TGS session key)client에 보낸다. client는 앞선 메세지는 복호화해서 TGS session key를 가진다. client이제 TGS session key ENCRYPTS( id, timestamp)를 보낸다. TGS입장에선 모두 복호화한다. TGS 입장에서 id, session key가 match되면,SS secret key ENCRTPYS (ticket, client session key), TGSsession key encrypts (clinet session key)를 client에게 보냄. client는 client session key를 얻고, client session key ENCRYPS (id, timestamp)를 SS에 보낸다. SS는 ticket도, client session의 일치도 확인한다. 맞다면 정보를 client session key로 암호화해서 보낸다. 유저는 timestamp를 보고 신뢰할지 말지 여부를 선택한다.  이 과정에 중간에 누구도 개입하지 못하며, 클라이언트, 서버 모두 서로의 신뢰가 확보된다. 
• HDFS: 패스
• Network
• (1)physical layer-(2)data link layer-(3)network layer(ip layer, one global virtual network임. 예를 들어 건물에 층마다의 ethernet이 다르다고 하자. Network layer은 이러한 층마다 다른 ethernet을 하나로 간주하게 해준다)- (4)transport layer(flow control, packet ordering)-(5)session layer(opening, closing of session)- (6)presentation layer- (7) application layer

• transport, network, data link가 kernel code 분석 대상이다. network layer를