DEVELOPyo

[3강. 데이터링크 계층 프로토콜의 HDLC 2]

- frame은 헤더의 시퀀스 넘버를 사용하여 순서를 구분

# ACK 와 NAK

ACK : 정상 수신

NAK : 비정상 수신

[ARQ의 종류]

1. Stop N Wait ARQ

프레임을 보내고 ACK/NAK 올때까지 다음 프레임을 보내지 않음

송신측은 time out 이 나면 재전송

(송신측 sliding window 가 1인 Go-Back-N ARQ와 같다)

# piggybacking

ACK와 데이터를 동시에 보냄

2. Go-Back-n ARQ (GBn ARQ)

window 크기 : 2의 (m-1)제곱 만큼 (window 크기만큼 수신측 회신 없이 프레임 전송)

항상 순서대로 ACK 를 받아서 처리

손상 분실된 프레임 이후의 프레임 모두 재전송(효율 낮음)

구조 간단 하고 구현 단순

수신측 데이터 문제있을 경우 NAK 전송 혹은 silence

타이머 만료시 ACK 오지 않은 프레임(sliding window의 첫 프레임)부터 재전송

수신측 sliding window 크기는 1로 받고자 하는 프레임의 번호만 가리키고 있다. 수신된 프레임의 번호가 기다리는 프레임의 번호가 아닌 경우 버리고 간다.(silence)

3. Selective Repeat ARQ (SR ARQ)

Go-Back-n ARQ 비효율 문제 개선한 방식.

손상되거나 분실된 프레임만 재전송(NAK 받은 프레임)

데이터 재정렬이 필요, 별도 버퍼 필요

Timer는 각 프레임에 존재하여 각 타이머 만료시 해당 프레임을 다시 보냄.

ACK3이 오면 프레임 2만 잘 받았다고 판단

[HDLC (High level Data Link Control) 프로토콜]

- ISO에서 개발한 국제 표준 프로토콜.

- 점대점링크(point to point), 멀티포인트 링크에서 사용

- 오류제어를 위해 GBn ARQ, SR ARQ 방식 사용

1. 분류 정의

Data link 프로토콜의 종류 : Asynchronous/Synchronous protocols

Asynchronous protocols의 종류 : XMODEM, YMODEM, ZMODEM, BLAST...

Synchronous protocols의 종류 : Character-oriented protocols, Bit-oriented protocols

Bit-oriented protocols 의 종류 : SDLC, HDLC...

2. HDLC 의 3가지 station types

1) primary station(master): link 컨트롤에 책임을 가짐

2) secondary station(slave): master에 의해 제어당하는 station

3) combined station: primary/secondary 의 조합

3. Unbalanced(1:N Multi-drop(ex:전화선))/Balanced(1:1 peer to peer) 형태의 link 모두 지원

4. half-duplex(반이중: 전송 수신 동시에 불가 (ex: Stop N Wait ARQ))/full-duplex(전이중: 전송 수신 동시 가능 (ex: GBn ARQ)) 모두 지원

5. NRM(normal response mode), ARM(asynchronous response mode), ABM(asynchronous balanced mode) 지원

1) NRM: primary 의 command 에 의해 secondary가 데이터 전송 가능

2) ARM: secondary가 primary에 언제든지 데이터 전송 가능(주종 관계는 NRM과 동일)

3) ABM: primary, secondary 관계가 동등 (주로 쓰임)

6. Frame 형태

1) I-frames(Information frames) : 일반적인 정보가 담긴 데이터(seq 존재)

2) S-frames(Supervisory frames) : ACK, NAK...

3) Unnumbered frames(U-frames) : seq가 없는 데이터(ex: 연결/단절 신호)

7. Frame 형태 - 상세

1) Flag: 1byte

2) Address: 1byte

3) Control field: 1byte

* S-Frame

REJ : GBn ARQ 에서의 NAK (NAK3 : 3이후로 전부 재전송)

SREJ : SR ARQ 에서의 NAK (NAK3 : 3만 재전송)

* U-Frame

4) data: N bytes

5) FCS: 2Bytes (데이터 에러 검출용)

[PPP (Point to Point Protocol구성요소]

1. LCP (Link Control Protocol)

데이터는 없고 링크를 관리하기 위한 프로토콜

2. Authentication protocols

1) PAP : 유저가 id, pw 송신, 시스템은 ACK/NAK 회신 (보안취약)

2) CHAP : 시스템은 challenge value 를 보내고 유저는 pw 에 challenge value를 더한 값을 송신.

시스템은 그 값을 확인하여 인증처리. (pw가 노출되지 않아 보안성 높음)

3. NCP (Network control protocols)

LCP -> PAP/CHAP -> NCP -> 데이터 송신 -> NCP -> LCP 와 같은 순서

※ KOCW 성균관대학교 안성진 교수님의 컴퓨터네트워크 강의 참고

[1강. 링크계층 프로토콜]

1. Data link 계층에서 하는 일

1. Frame synchronization: frame송수신 동기화

2. Flow control: 수신쪽에서 overflow가 일어나지 않도록 흐름제어

3. Error control

4. Physical addressing: 식별

5. Access control: 접근제어 (multiplex 관련)

2. Poll/Select

multidrop/multipoint 방식에서 line cost 를 절감하기 위해 사용하는 방법

* multidrop/multipoint : 여러 터미널이 하나의 선을 공유하는 경우 (ex: 전화선)

1) polling : primary가 secondaries 에 전송할게 있는지 질의 (데이터흐름 secondaries->primary)

2) select : primary 장치가 전송할게 있을때마다 사용 (데이터흐름 primary->secondaries)

3. Framing

data link 계층은 bits를 frames 로 packing. 각각의 frames 은 구분가능.

frame 내에서 single bit error 가 존재할 경우 전체에 대한 재전송이 필요.

1) fixed-size framing : 고정크기

2) variable-size framing : 가변크기

[2강.데이터링크 계층 프로토콜의 HDLC]

1. Frame

1) Character-oriented protocols

Character(2bytes = 8bit) 가 최소단위의 frame으로 사용됨

#byte-stuffing이란

flag bit와 data 의 bit 가 일치하는 경우 프레임 단위 구분이 모호해지는 문제가 있음.

이를 구분하기 위해 byte-stuffing(or character stuffing) 전략을 사용.

이때 삽입되는 byte를 ESC(escape character)라고 칭함

예) ESC 삽입의 예

flag와 일치하는 data bit 가 있을 경우 앞에 ESC 삽입.

ESC와 동일한 bit가 있을 경우 그 앞에도 ESC 삽입.

ESC 뒤의 데이터는 무조건 데이터 bit로 간주.

2) Bit-oriented protocols (주로사용)

01111110 을 주로 flag 로 사용

#Bit stuffing

flag와 data bit을 구분하기 위해 011111 와 같이 1이 연속적으로 5개 있는 경우 그뒤에 0을 삽입하여 flag와 data bit 를 구분

* 수신측은 1 다섯개 뒤에 있는 0은 무조건 제거

2. Flow control

수신측의 속도를 맞춰 송신측의 속도 제어

# Flow control 방법 세가지

1) XON/XOFF : 전송stat/stop

ex: PC->프린터, 프린터 출력속도가 느려 버퍼가 거의 찰 경우 PC에 stop 요청 이후 start 요청

2) Stop-and-wait : frame을 1개씩 보내기 

ex: 프레임 1개 전송 후 잘 받았다는 회신을 받아야 다음 프레임 전송

3) Sliding window  : frame 여러개를 한번에 보내기 

* Window size = outstanding frame의 갯수

                    = unacknowledged frame

                    = ACK를 받지 않은 frame

                    = ACK 없이 보낼 수 있는 최대 frame 수

eg. window size 가 3인 경우, ACK 없이 최대 3개 프레임을 전송 할 수 있음.

eg2. window size가 3일 때, ack 를 첫번째 송신후 받은 경우 두번째 프레임으로 부터 다시 3개까지 ACK 없이 프레임 전송 가능

3. Error Control

Error detection + Error correction

# Error Control 방법

1) Discarding the errors : 에러 무시 (인터넷 전화)

2) Forward Error Correction(FEC) : 수신측에서 에러 수정

3) Automatic repeat request(ARQ) : 재전송

※ KOCW 성균관대학교 안성진 교수님의 컴퓨터네트워크 강의 참고

P2P (Peer to Peer)

- always-on server 가 없다

- end systems 간의 직접 communicate

eg) BitTorrent, VoIP(Skype)

1. 보통의 Server-Client 간 File Distribution Time

1) File F 를 N 번 업로드 하는데 걸리는 서버의 전송 시간 : NF/Us

2) 클라이언트가 파일 F를 다운로드 받는데 걸리는 최대 시간 F/dmin

파일 F를 N개의 클라이언트에 distribute 하는데 걸리는 시간 : max { NF/Us , F/dmin }

    : 서버가 파일을 업로드 하는 시간 or 클라이언트 중 파일을 다운로드하는데 최대로 걸리는 시간 중 최대 시간

    : 유저가 많아질 수록 N 이 증가하므로 속도가 느려짐

2. P2P 에서의 File Distribution Time

1) 서버에서 하나의 카피를 올리는 경우 걸리는 시간 : F/Us

2) 클라이언트가 파일 F를 다운로드 받는데 걸리는 최대 시간 : F/dmin

N명의 클라이언트 모두가 파일을 받을 경우 NF bits

max upload rate : Us + ∑Ui

파일 F를 N개의 클라이언트에 distribute 하는데 걸리는 시간 : max {F/Us, F/dmin, NF/(Us+∑Ui)}

: 유저가 많아질수록 N 과 Ui 모두 증가하므로 속도가 느려지지 않음

Client-Server vs P2P Distribution Time 비교

BitTorrent

- file 을 256Kb chucks로 나눔

- torrent : 파일 chunk를 교환하는 peer 그룹

- tracker : 토렌트에 속하는 peer 가 누구인지 tracking

- churn : peer 가 들어갔다 나갔다 하는 것

- rarest first : chunk를 보유한 peer 가 가장 적은 것 부터 request

- selfish peer : 다운로드만 받고 업로드는 하지 않는 peer

※ tit-for-tat

좋은 partner peer 를 남기고 selfish peer 를 버리기 위한 전략

- 가장 많은 chunk 를 제공하는 peer top 4 에게 chunk 를 보내준다

- 10초마다 top 4를 재평가

- 30초마다 랜덤으로 peer 를 선택하고 chunk를 보낸다. (top 4 가 고정되는 것을 방지하기 위해)

※ 이화여대 이미정 교수님의 네트워크 강의 내용 정리

DNS : Domain Name System

hostname 를 ip 주소로 해석

centralize DNS 사용하지 않는 이유

1) 트래픽 집중

2) 먼 거리에 위치한 국가의 데이터베이스 접근 불리

3) 유지보수

4) 에러를 대비한 클러스터링 없음

DNS 서버의 위계구조 (hierarchial database)

- Root DNS Servers

- Top-level Domain Servers (TLD)

  : .com, .org, .edu, .net 및 .jp .kr 등의 국가 도메인을 담당 eg) 한국인터넷정보센터가 .kr 을 담당하는 TLD

- Authoritative DNS Servers

  : 각 기관이 가지고 있는 DNS 서버

  : 기관내 connected 된 모든 hostname, IP 매핑정보를 가지고 있음

- Local DNS name Server

  : 위계구조에 포함되진 않음, 매핑정보를 caching 하며 proxy server로도 불림

1) client는 root dns server에 com DNS server 질의

2) client는 get amazon.com DNS 서버를 알아내기 위해 .com DNS server에 질의

3) client는 www.amazon.com IP 주소를 알아내기 위해 amazon.com DNS server에 질의

DNS root name servers 는 세계 총 13군데 위치

우리나라는 가장 가까운 일본 DNS 사용

DNS 위계 구조 호출 순서

root > TLD > authoritative 순서로 호출

local DNS server에 캐싱하여 상위 레벨 DNS 서버의 부하방지

Local DNS Server 의 Outdated Domain name 정보의 확인을 위해 TTL(Time-To-Live) 레코드 사용

유효기간(TTL) 이 지난 경우 캐시 삭제됨

DNS records

name, value, type, ttl

레코드 타입별 name/value

A (Host) : name(호스트 서버네임) value(IPv4) eg)authoritative DNS 

AAAA : name(호스트 서버네임) value(IPv6) 

NS (Name Server) : name(도메인네임) value(authoritative 서버네임) eg) TLD DNS

CNAME : name(alias) value(canonical name)

DNS query 순서

1) 

클라이언트(브라우저)에서 /etc/resolv.conf 에 지정되어있는 로컬 NS 서버 (네임서버) 로 www.yahoo.com 에 대한 요청

2)

네임서버는 root DNS 서버 IP 주소를 기록한 hint 파일을 가지고 있으며 이를 참조하여 root DNS 서버에 www.yahoo.com 에 대한 요청 전달.

root DNS 서버는 TDL(최상위네임서버)들의 글루레코드를 가지고 있으며 이를 참조하여 .com 네임서버를 참조하라고 응답.

※ 글루레코드(glue record)란 네임서버명(NS 레코드)과 IP주소(A 레코드)을 의미

3)

.com 네임서버 즉, TDL 서버는 .com 을 TDL (최상위도메인) 로 사용하는 도메인들의 글루레코드를 가지고 있으며 이를 참조하여 www.yahoo.com 의 네임서버를 참조하라고 응답

(authoritative DNS server의 글루레코드(NS + A) 응답)

4) 

yahoo.com의 네임서버는 yahoo.com 도메인에 대한 존(zone)파일을 참조하여 www.yahoo.com의 의 IP주소를 네임서버(로컬 NS)로 돌려준다.

(authoritative DNS server 는 IP주소(A 레코드) 를 클라이언트가 최초 요청을 한 네임 서버(로컬 NS)로 응답)

5) 

최초 요청을 했던 네임 서버(로컬 NS)는 클라이언트에게 IP 주소를 전송

※ 한양대학교 이석복 교수님의 컴퓨터네트워크 강의 내용 정리

※ https://webdir.tistory.com/161

IP와 PORT

IP : 호스트

port : 호스트 내의 프로그램

application layer 는 transport layer에 종속적이며 transport layer에서 application layer에 다음과 같은 것들을 지원해준다.

1) data integrity

2) timing

3) throughput

4) security

HTTP (hypertext transfer protocol)

- WEB's application layer protocol

- TCP 사용

- default 80번 port 사용

- stateless : 클라이언트 요청에 대한 상태저장 없음 (cookie 사용)

* safari, explorer, chrome 은 모두 다른 application 이지만 모두 같은 HTTP (protocol) 을 사용하므로 브라우저와 무관하게 application 사용이 가능하다

HTTP 의 두가지 방식

1. non-persistent HTTP

- TCP 커넥션을 HTTP 사용후 close

- 매 http 마다 TCP 커넥션을 새로 맺음

- 응답시간이 persistent 방식보다 더 많이 걸림

* RTT : round trip time

2. persistent HTTP

- multiple objects can be sent over single TCP connection between client, server

  클라이언트/서버 간 하나의 TCP 커넥션으로 여러개의 HTTP 송수신을 수행

- 현재 사용하는 HTTP 1.1 버전은 persistent 가 default. (지속커넥션 사용)

* 파이프라인 사용

HTTP request message

Cookie 동작 순서

Web caches(Proxy server)

origin server에 HTTP 요청을 하는 서버대신 proxy 서버에 HTTP 요청

- origin server의 부하를 줄이고

- 비용을 줄임

- 속도가 빠름

※ Cache에 저장된 데이터가 최신이 아닐 수 있다.

브라우저로 전달되는 객체들이 최신임을 확인하며 캐싱할 수 있도록 Conditional GET 사용

Conditional GET

- HTTP 요청에 If-Modified-Since 헤더 라인 포함.

- 서버에 있는 객체의 마지막 수정된 날짜와 비교.

수정된 객체라면 객체를 보내줌 (200 OK + data)

최신 상태이면 object를 보내지 않음 (304 Not modified)

SMTP (Simple Mail Transfer Protocol)

- 메일서버에 송신자가 메일을 보낼때, 송신메일서버가 수신메일서버에 메일을 보낼 때 사용되는 프로토콜

- 수신메일서버에서 수신인이 메일을 읽어갈 땐 POP/IMAP/HTTP 등의 프로토콜을 사용

- persistent connection 사용

- default 25번 포트  사용

- handshaking > transfer > closure 순서로 동작

HTTP : 클라이언트 입장에서 데이터를 가져오므로 pull protocol

SMTP : 클라이언트 입장에서 데이터를 보내므로 push protocol

※ 한양대학교 이석복 교수님 컴퓨터네트워크 강의 내용 정리

※ 이화여대 이미정 교수님 컴퓨터네트워크 강의 내용 정리

Network Structure : 네트워크 구성요소

1. network edge :

- applications and hosts

2. network core :

- routers

3. access networks, physical media :

- communication links 라우터들을 연결시켜주는 링크

1. network edge :

1) end systems (hosts) : run application programs

eg) Web, email

2) client/server model : client host requests, receives service from always-on swerver

eg) web browser/server; email client/server

3) peer-peer model : minimal use of dedicated servers

eg) Skype, BitTorrent

데이터 통신방식 

1. connection-oriented service

TCP (Transmission Control Protocol)

- reliable : 신뢰할 수 있음

- flow control : 수신자 능력 고려하여 받을 수 있는 만큼 전송

- congestion control : 네트워크 막힘현상시 속도 낮춰서 전송

사용: HTTP, FTP, Telnet, SMTP(email)

2. connectionless service

UDP (User Datagram Protocol)

- connectionless

- unreliable data transfer

- no flow control

- no congestion control

사용: Streaming media, DNS

2. network core :

라우터간의 연결들의 집합

네트워크를 통한 데이터 전송방식

1. circuit switching :

출발지에서 목적지까지 가는 길을 미리 설정

bandwidth 가 1Mpbs이고 1명의 유저당 active 상태에서 100kb/s 사용시 최대 10명의 유저만 사용가능

2. packet-switching : 

패킷 순서가 정해져있지 않으며 패킷을 요청시 공유한다. (statistical multiplexing )

패킷 딜레이

1) nodal processing

check bit errors : 패키지 검사

2) queueing : 큐 순서 기다리기

※ queue 가 초과하는 경우 packet 이 유실된다. (대부분의 packet 유실은 queue 초과로 일어난다)

3) Transmission delay

R = link bandwidth(bps)

L = packet length (bits)

L/R : time to send bits into lnk

 : 큐 순서 도달 후, 시작 bit 부터 끝 bit 까지 link 를 통해 bit가 나가는데 총 걸리는 시간

4) Propagation delay : 

d = length of physical link

s = propagation speed in medium (광속)

d/s = propagation delay

패킷 딜레이를 줄이려면?

1) processing delay : 라우터 성능 업그레이드

2) queueing delay : 사용자 수에 의해 결정되므로 제어 불가

3) transmission delay : 케이블 업그레이드

4) propagation delay : 광속이므로 제어 불가

※ 한양대학교 이석복 교수님의 컴퓨터네트워크 강의 내용 정리

Allocation of File Data in Disk 

Contiguous Allocation

단점 :

- external fragmentation, hole이 발생

장점 : 

- Fast I/O (헤드가 이동하는 시간이 짧음)

- 한번의 seek/rotation 으로 많은 바이트 transfer

- Realtime file용, process의 swapping 용으로 사용

- Direct access(=random access) 가능

Linked Allocation

장점 :

- external fragmentation 발생 없음

단점 :

- No random access

- Reliability 문제

- 한 sector 가 고장나 pointer 유실시 많은 부분을 잃음

- Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림 (512bytes는 sector로, 4bytes는 pointer로 사용됨)

* FAT(File-allocation table) 파일 시스템 : 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

Indexed Allocation

장점 :

- external fragmentation 발생 없음

- Direct access 가능

단점 :

- Small file의 경우 공간 낭비

- 파일이 너무 큰 경우 하나의 block 으로 index 를 저장 할 수 없음

UNIX 파일시스템 구조

Boot block

- 모든 파일시스템은 boot block 이 제일 위에있음

- 컴퓨터 부팅시 0번블럭(붙 블럭)을 올려서 부팅시킴

Superblock

- 파일시스템에 관한 총체적인 정보를 담고 있다

Inode

- 파일 이름을 제외한 파일의 모든 메타 데이터 저장

Data block

- 파일 실제 내용 보관

FAT 파일 시스템

FAT

메타데이터의 일부를 보관 (위치정보)

FAT 배열의 크기는 data block 의 크기와 동일

FAT 은 복제본을 저장하여 신뢰도를 높임

Free Space Management : 비어있는 블락 관리방법

1. Bit map 

Bit map 을 위한 부가적인 공간을 필요로 함

연속적인 n개의 free block을 찾는데 효과적

2. Linked list 

모든 free block들을 링크로 연결(free list)

연속적인 가용공간을 찾는게 힘듦

공간낭비 없음

3. Grouping

linked list 방법의 변형

첫번째 free block이 n개의 pointer를 가짐

n-1 pointer는 free data block을 가리킴

마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

4. Counting

프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안

Directory Implementation : 디렉토리 저장 방법

1. Linear list

- <filename, file의 메타데이터>의 list

- 구현이 간단함

- 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요(time-consuming)

2. Hash Table

- linear list + hashing

- Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌

- search time을 없앰

- Collision 발생 가능

* F에 Hash 함수 적용시 F는 특정 범위로 한정지어짐.

* Hash 함수를 적용하여 조회

※ 이화여대 반효경 교수님의 운영체제 강의 정리

File

named collection (메모리는 주소를 통한 접근)

비휘발성의 보조기억장치에 저장

운영체제는 다양한 저장 장치를 file 이라는 동일한 논리적 단위로 볼 수 있게 해 줌

Operation 종류 : create, read, write, reposition, delete, open, close

File attribute (metadata)

파일 이름, 유형, 저장위치, 파일사이즈, 접근권한, 시간(생성/변경/사용), 소유자과 같은

파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들

File system

운영체제에서 파일을 관리하는 부분

파일 및 파일의 메타데이터, 디렉토리 정보

파일의 저장 방법 결정

파일 보호

Directory

파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일

그 디렉토리에 속한 파일 이름 및 파일 attribute들

Operation 종류 : search for a file, create a file, delete a file, list a directory, rename a file, traverse the file system

Partition(=Logical Disk)

하나의 물리적 디스크 안에 여러 파티션을 두는게 일반적

여러 개의 물리적인 디스크를 하나의 파티션으로 구성하기도 함

물리적 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 swapping 등 다른 용도로 사용 가능

open()

파일의 메타데이터를 메모리로 올린다.

1) fd = open("/a/b") : 프로그램이 b 메타데이터 정보를 요청

2) 시스템콜을 하여 CPU를 운영체제에 넘긴다.

3) CPU가 root 메타데이터를 먼저 메모리에 올린다(root 메타데이터의 디렉토리는 이미 알고 있음)

4) root 메타데이터를 연다

5) root 메타데이터에 존재하는 a 메타데이터의 파일시스템상 위치정보로 디스크에서 a의 메타데이터를 가져와 메모리에 올린다

6) a의 메타데이터를 연다

7) a의 메타데이터에 존재하는 a content의 파일시스템상 위치정보로 디스크에서 a의 content 안에 존재하는 b의 메타정보를 가져와 메모리에 올린다

8) b의 메타정보를 가리키는 포인터의 인덱스(파일 디스크립터) 값을 리턴

9) read(fd...) : 프로그램이 b content 정보 요청(읽기)

10) 읽은 내용을 사용자 프로그램(Process A)에 직접 주는게 아닌, 커널 메모리 영역(buffer cache)으로 가져온다

11) 사용자 메모리영역(Process A)엔 그 내용을 카피해서 준다.

※ 만약 다른 프로그램(Process B)에서 b의 content 를 요청한다면 운영체제가 buffer cache에서 전달해준다 

※ File System 의 Buffer cache 환경에선 운영체제가 모든 정보를 알고 있으므로(파일 시스템 접근시 시스템 콜을 통해 제어권이 CPU로 넘어오므로) LRU, LFU 알고리즘을 사용할 수 있다. 

※ per-process file descriptor table : 파일 디스크립터 테이블은 프로세스마다 따로 존재

※ system-wide open file table : system wide 로 전체 시스템에 한개로 관리되지만 각각의 프로그램들이 파일의 offset을 프로그램 별로 관리하기 위한 공간(table)은 따로 존재

File Protection

1. Access control matrix : linked list 형태로 권한 관리 (overhead가 큼)

Access control list : 파일별로 누구에게 어떤 접근 권한이 있는지 표시

Capability list: 사용자별 자신이 접근 권한을 가진 파일 및 해당 권한 표시

2. Grouping

전체 user를 owner, group, public의 세그룹으로 구분

각 파일에 대해 세그룹의 접근 권한(rwx)을 3비트씩 표시

UNIX를 포함한 대부분의 OS에서 사용

3. Password

파일마다 password를 두는 방법

rwx 마다 password를 하나씩 부여해야하므로 관리가 어려움

File System의 Mounting

파티션을 통해 여러개의 논리적 디스크로 분리된 하나의 물리적 디스크

각각의 논리적 디스크에 file system 존재

다른 파일시스템에 접근할 경우 mount 사용

disk3의 루트를 disk1의 usr 경로에 연결(mount)하여 타 파일시스템 접근이 가능

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Page Frame의 Allocation(할당)

: 각 Process에 얼마만큼의 Page Frame을 할당할 것인지의 문제

- 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조하므로 명령어 수행을 위해 최소한 할당되어야 하는 frame 의 수가 있다. (page fault 를 줄이기 위해)

Allocation Scheme

Equal allocation : 모든 프로세스에 똑같은 갯수 할당

Proportional allocation : 프로세스 크기에 비례하여 할당

Priority allocation : 프로세스의 priority에 따라 다르게 할당

Global replacement 와 Local replacement 의 차이

Global replacement

Replace시 다른 process에 할당된 page frame을 빼앗아 올 수 있다

FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용하는 경우

Working set, PFF 알고리즘 사용

Local replacement

자신에게 할당된 frame 내에서만 replacement

FIFO, LRU, LFU 등의 알고리즘을 local(process) 별로 운영시

Global replacement 에서의 문제

Thrashing

메모리에 올라와 있는 프로그램이 늘어날 수록 CPU 이용량은 올라가지만, 

메모리에 프로그램이 너무 많이 올라갈 경우 page frame 수 (메모리 할당 용량)가 너무 적어질 경우 page fault 가 매우 빈번하게 발생하게 되어 CPU utilization 은 낮아지고, 프로세스는 page의 페이지를 빼고 넣고를 (swap in/swap out) 반복하게 되어 실제 CPU는 놀게 되는 현상

Thrashing 현상을 방지하기 위한 방법들

1. Working-set Model

- Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page 들의 집합을 Working Set이라고 한다 (프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조, 이 장소들의 집합을 working set이라 함)

- Working set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend) : 묶음으로 넣거나 아예 넣지 않거나

- Thrashing을 방지하고 Muliprogramming degree를 결정한다

Working-set Algorithm

- Process들의 working set size의 합이 page frame의 수보다 큰 경우 일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜준다

- Working set을 다 할당하고도 page frame이 남는 경우 Swap out 되었던 프로세스에게 working set을 할당

Window size 

Working size가 너무 작으면 locality set(필요한 페이지 묶음)을 모두 수용하지 못할 수 있다

Working size 동안 Working set에 속한 page는 메모리에 유지, 속하지 않는 것은 버린다

2. PFF(Page-Fault Frequency) Scheme

Page-fault rate의 상한값과 하한값을 두고, 

Page fault rate 상한값을 넘으면 frame을 더 할당

Page fault rate 하한값 이하면 할당 frame 수를 줄인다

빈 frame이 없으면 일부 프로세스를 swap out

※ Page size의 결정

Page size가 작다면 

필요한 정보만 메모리에 올라와 메모리 이용에 효율적(페이지 단위가 작으므로 작은 크기로 올릴 수 있음)인 장점 등이 있지만, 

Disk seek (디스크 헤드 이동) 시간 증가

Page size를 감소시킬 경우

페이지 수 증가,

페이지 주소를 관리하는 페이지 테이블 크기 증가와 같은 단점이 있다.

위와 같은 이유로 Page 크기를 키우는게 최근 트렌드

※ 이화여대 반효경 교수님의 운영체제 강의 정리

Demand Paging

- 실제로 필요할 때 page를 메모리에 올리는 것

- I/O 양의 감소

- Memory 사용량 감소

- 빠른 응답 시간

- 더 많은 사용자 수용

Valid/Invalid bit 의 사용

- 사용되지 않는 주소영역인 경우, 페이지가 물리적 메모리에 없는 경우 : Invalid

- 처음에는 모든 page entry 가 invalid로 초기화

- address translation 시에 invalid bit이 set 되어 있으면(요청한 주소가 메모리에 올라와 있지 않은 경우) page fault 발생

page fault

: 요청한 주소가 메모리에 올라와 있지 않은 경우 발생

invalid page를 접근하면 MMU가 trap을 발생시킨다 (page fault trap)

Kernel Mode로 들어가서 page fault handler 가 invoke된다

page fault 처리 순서

1. Invalid reference ? ( if bad address, protection violation ) abort process

2. get an empty page frame (없으면 뺏어온다)

3. 해당 페이지를 disk에서 memory 로 읽어옴

  1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당한다(block)

  2) Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"

  3) ready Queue에 process를 insert -> dispatch later

4. 이 프로세스가 CPU를 잡고 다시 running

5. 중단되었던 instruction 재개

Page replacement

- Free Frame(비어있는 frame(physical memory 영역))이 없는 경우 수행됨

- 어떤 frame을 빼앗아올지 결정해야 한다 (곧바로 사용되지 않을 page를 쫓아내는 것이 좋다)

- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음

Page fault를 줄이기 위한 Replacement Algorithm의  종류

page-fault rate을 최소화 하는 것이 목표

알고리즘의 평가기준은 주어진 page reference string에 대해 page fault를 얼마나 내는지

1. Optimal Algorithm (=Min Algorithm)

- 가장 먼 미래에 참조되는 page를 replace (미래를 안다는 가정)

- 다른 알고리즘의 성능을 측정하는 기준점이 됨(실제 사용은 불가한 offline 알고리즘)

- Belady's optimal algoroithm MIN, OPT 등으로 불림

-> 7번째 수행에서 5를 참조 할 때, 미래에서 가장 나중에 참조되는 4(마지막에서 2번째)를 쫓아내고 대신 5를 넣음

2. FIFO Algorithm (first in first out)

먼저 들어온 것을 먼저 내쫓는다

FIFO Anomaly (Belady's Anomaly) : 페이지가 늘어남에도 불구하고 page faults는 증가하는 현상이 발생

3. LRU Algorithm (Least Recently Used)

가장 오래전에 참조된 것을 지운다

4. LFU Algorithm (Least Frequently Used)

참조 횟수(reference count)가 가장 적은 페이지를 지움

* 최저 참조 횟수인 page가 여럿인 경우

- LFU 알고리즘 자체에는 여러 page 중 임의로 선정

- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음

* 장단점

- LRU 처럼 직전 참조 시점만 보는게 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음

- 참조 시점의 최근성을 반영치 못함

- LRU 보다 구현이 복잡함

※ LRU, LFU 의 비교

LRU

위에 있을 수록 오래된 참조

- linked list 형태

- 참조될 때 맨 아래에 link시킴

- 쫓아낼 경우 맨 위의 페이지 쫓아냄

LFU

LRU 처럼 linked list 형태로 관리하기는 비효율적

: 새로 참조될 때마다 어디에 link 시킬지 판별하기 위해 참조횟수를 비교해야함 (시간 복잡도 O(N)))

linked list 형태 대신 heap 으로 구현, 2진트리로 구성

* 쫓아낼 경우 root를 쫓아내고 heap을 재구성

캐싱 기법

- 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스 하는 방식

- paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용

캐시 운영의 시간 제약

- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음

- Buffer caching이나 Web caching의 경우

  : O(1) 에서 O(long n) 정도까지 허용

- Paging system인 경우

  : Page fault인 경우에만 OS가 관여함

  : 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음

  : O(1)인 LRU의 list 조작조차 불가능

* Paging System에서 LRU, LFU는 사용이 불가하다

: page fault 발생시(CPU 제어권이 운영체제로 넘어오면)에만 디스크에서 메모리에 올라온 시간을 알 수 있으며

이미 메모리에 페이지가 있으면 알 수 없음

Clock Algorithm(=Second chance algorithm = NRU(Not Recently Used))

LRU의 근사 알고리즘, LRU/LFU 대신 실제 사용되는 알고리즘

reference bit : 참조여부를 의미(1:최근에 참조된 경우, 0:최근에참조되지 않은 경우)

modified bit(=dirty bit) : write(변경) 여부를 의미(1:write 된 페이지, 0:write 되지 않은 페이지) 

1) 최근에 참조된 경우 Reference bit은 1

2) 1인 경우 Reference bit 을 0으로 바꾸고 다음 페이지를 확인(최근에 참조된 페이지인 경우이므로 다음 페이지 확인)

3) 0인 경우를 발견하면 페이지를 내쫓는다

※ 이화여대 반효경 교수님의 운영체제 강의 정리