Vamos ser Programador com Devfon

Network Layer (1)

Network Layer

• 송신자로부터 수신자로 segment를 전송
• 송신자 측에서는 segment를 datagram으로 캡슐화
• 수신자 측에서는 segment를 transport layer로 전송
• router는 header field의 모든 IP datagram을 검사하여 넘김

Two key network-layer function

• forwarding
  • router의 input에서 적절한 output의 router로 패킷을 전송
• routing
  • 소스로부터 목적지까지 패킷이 전송되어야 할 경로 결정
  • Routing algorithm

Connection setup

• datagrams flow 이전에 두 종단 시스템과 router는 가상의 연결을 맺어야 함
• network: 두 호스트 간의 연결
• transport: 두 프로세스 간의 연결

Connection, connection-less service

• datagram 네트워크는 네트워크 계층의 connection-less service 제공
• virtual-circuit 네트워크는 네트워크 게층의 connection service 제공
• TCP/UDP의 connection-oriented/connectionless와 같음
  • 그러나 host 간 제공되는 서비스이며,
  • 네트워크가 제공하는 circuit 외에는 선택지가 없으며,
  • 네트워크 코어 간 수행된다는 차이 존재

Virtual circuits

• "source-to-dest path behaves much like telephone circuit"
  • performance-wise
  • src-to-dest path와 함께 네트워크적 action이 취해짐
• 각각의 패킷은 Virtual circuit Identifer를 지님(dest host의 주소가 아님)

• VC consists of
  • path from src to dest
  • VC numbers
    • link에 따라 변경될 수 있음
  • entries in forwarding tables
• VC는 현대 인터넷에 사용되지 않음

Datagram networks

• router는 종단 간 연결에 대한 상태를 지니지 않음
• Packet는 단순히 dest host address를 참조해 전송됨

Longest prefix matching

• forwarding table을 참조할 때, 가장 긴 접두부를 공유하는 범위의 Link inferface를 참조하게 되는 것

Router architecture overview

• Input ports
  • datagram의 dest를 보고, forwarding table을 참조하여 output port를 검색
  • forwarding 속도보다 datagram이 빨리 들어올 수 있기 때문에 Queue를 사용하여 Queueing
• Output ports
  • 배출 속도보다 빠른 도착 속도를 고려해 buffer를 두어 buffering
  • datagram Scheduling

Switching fabrics

• 3 types of switching fabrics

Switching via memory

• 1세대 Router
• CPU에 의해 직접적으로 switching
• memory의 bandwidth에 switching 속도 제한됨

Switching via a bus

• 공용 bus를 통해 input port memory에서 output port memory로 datagram switching
• bus의 bandwidth에 의해 switching 속도 제한

Switching via interconnection network

• bus bandwidth의 한계 극복
• 멀티프로세서에 여러 개의 프로세서 연결하기 위해 고안됨
• 이제는 보다 더 발전되어 datagram을 일정 길이로 쪼갠 후, 해당 cell들을 fabric을 통해 switching

The Internet network layer

• IP datagram format

IP fragmentation, reassembly

• network link에는 MTU(max transfer size) 존재
• 때문에 큰 크기의 IP datagram은 분할되어 전송
• 최종 목적지에서 재조립됨

IP addressing

• IP 주소: host와 router interface를 위한 32bit의 식별자
• interface: host/router와 physical link 간 연결 장치
• subnet: router의 간섭 없이 물리적으로 접근 가능한 장치들의 집합(위 그림에는 3개의 subnet 존재)
  • subnetmask가 해당 subnet을 구성할 수 있는 host들의 수 정의

CIDR(Classless Inter-Domain Routing)

• 최신의 IP 주소 할당 방법
• 네트워크 클래스를 대체하고, 기존 방식에 비해 유연성을 더해줌
• 급격히 부족해지는 IPv4 주소를 보다 효율적으로 사용하게 해줌

DHCP(Dynamic Host Configuration Protocol)

• 서버로부터 동적으로 IP 주소를 얻음
• 임대하여 사용 중인 주소 갱신 가능
• 서버와 연결되었을 때만 사용하므로, 해당 주소 재사용 가능

NAT: Network Address Translation

• local network를 하나의 IP로 구성 가능
• local 내의 장치들은 보안성도 얻을 수 있음
  • 외부 세계에 의해 addressable, visible 하지 않기 때문
• NAT router가 알아야 할 것
  • outgoing datagram: 어느 장치에서 출발했는지
  • incoming datagram: 어느 장치로 보내야 할 지
  • NAT translation table
• NAT는 router의 기능을 초과하여 end-to-end system에 간섭하게 되는 단점 존재
  • IPv6를 통해 더 많은 주소 사용 가능해질 것

NAT traversal problem

• client는 10.0.0.1의 특정 server와 연결하고 싶음
• 그러나 공개된 외부 IP 주소는 단 하나이기 때문에 direct 연결이 불가
• solution 1
  • 외부 IP의 특정 port로 접근 요청 시, 바로 10.0.0.1로 forwarding 하게 설정
  • e.g., (123.76.29.7, port 2500) always forwarded to 10.0.0.1 port 25000

• solution 2
  • 10.0.0.1의 host에게 공개 IP 주소를 알림
  • 직접 Port 번호와 Mapping(지정 시간을 두고)

• solution 3
  • relay 서버를 활용
  • relay 서버가 client와 NATed client의 패킷 교환을 중개

ICMP: Internet Control Message Protocol

• host와 router들이 network level의 정보를 교환하기 위해 사용
  • error reporting
  • echo request/reply
• ICMP message는 IP datagram에 들어감

Transition from IPv4 to IPv6

• 모든 router들이 동시에 업그레이드될 수는 없음
• 어떻게 network는 IPv4와 IPv6 router를 혼합해서 사용할 수 있을 것인가?

• Tunneling
  • IPv6 datagram이 IPv4의 payload로 실려다님

Transport Layer

Transport services and protocols

• 다른 호스트에서 동작 중인 어플리케이션 프로세스 간 logical communication을 제공
• Transport protocol은 종단 시스템에서 작동
  • send side: app message를 segment로 쪼개어 network layer로 전달
  • rcv side: segment를 재조립하여 message로 만들어 app layer로 전달
• 1가지 이상의 transport 프로토콜 사용 가능
  • TCP and UDP

Transport vs. network layer

• network layer: logical communication between hosts
• transport layer: logical communication between processes

Internet transport-layer protocols

• 순서가 있는 신뢰성 전달: TCP
  • congestion control
  • flow control
  • connection setup
• 순서가 없는 비신뢰성 전달: UDP

Multiplexing/demultiplexing

• multiplexing at sender:
  • 여러 socket으로 부터 온 data를 transport header에 추가(이후 demultiplexing에 이용됨)
• demultiplexing at receiver:
  • header 정보를 이용하여 요청에 맞는 socket에 전달 받은 segment 전송

How demultiplexing works

• host가 IP datagram을 전송 받음
• 각각의 datagram은 source IP와 destination IP를 지님
• 각각의 transport segment는 source port와 destination port를 지님
• host는 IP 주소와 Port 번호를 이용하여 적합한 socket에 해당 segment 전송!

UDP(User Datagram Protocol)

• 'best effort' service UDP
  • 데이터 유실 있을 수 있음
  • 데이터 순서가 섞일 수 있음
• connectionless: UDP Sender와 Receiver 간 handshaking 하지 않음
• 신뢰성 있는 전송을 위해서는 Application 계층에서 신뢰성을 추가해주어야 함
• 장점
  • connection이 필요 없음(Overhead x)
  • 간단하게 구성 가능
  • header size가 작음

UDP checksum

• Sender
  • 1의 보수로 구성된 checksum을 header의 checksum field에 더함
• Receiver
  • 전송 받은 segment의 checksum을 연산
  • 연산된 checksum이 field 값과 같은지 비교하여 오류 여부 판단

Reliable Data Transfer(RDT)

rdt 1.0: reliable transfer over a reliable channel

• 신뢰성 있는 채널 하에서의 데이터 전송을 가정
  • no bit errors
  • no loss of packets
• 송신자는 채널을 통해 데이터 전송
• 수신자는 채널을 통해 데이터 수신

rdt 2.0: channel with bit errors

• 비트 에러가 존재할 수 있음을 가정
• 에러를 어떻게 복구할 것인가? 'Stop and Wait'
  • ACK: 송신자 -> 수신자. 패킷 잘 받았음!
  • NAK: 송신자 -> 수신자. 패킷 못 받았음!
• 그러나 만약, ACK/NAK에 오류가 생긴다면?
  • 송신자는 수신자의 상황을 알 수가 없음!
  • 중복의 문제로 인해 재전송을 하기도 애매함

rdt 2.1

• 송신자는 ACK/NAK에 오류가 생기면 현재 패킷을 재전송
  • 각각의 패킷에 'Sequence Number 부여'
  • 수신자는 'Sequence number' 확인하여 중복된 데이터 폐기
• 0과 1의 두 가지 sequnce num이면 충분
• 수신자는 기대한 Sequnce number와 전송 받은 번호를 비교하여 중복 데이터 폐기 가능
• 수신자는 자신이 보낸 ACK/NAK가 송신자에게 제대로 전송되었는지 알 수 없음

rdt 2.2 NAK-free protocol

• ACK에 Sequence number를 추가함으로써 잘못된 데이터를 받은 것을 다시 송신할 수 있게 하는 프로토콜

rdt 3.0 channels with errors and loss

• channel에서 패킷도 유실될 수 있음을 가정
• 송신자가 ACK를 기다리는 '적당한' 시간 간격을 둠
  • 이 시간 안에 ACK가 도착하지 않으면 패킷 재전송
  • 만약 패킷이 유실된 것이 아니라 단순 지연으로 인해 늦어진 것이었다면
    • sequnce number가 중복 데이터 처리

Pipelined protocols

Go-Back-N

• 송신자는 N개 만큼의 unacked packet을 파이프라인 통해 전송
• 수신자는 점증적 ACK만을 보냄
• 송신자는 가장 오래된 unacked packet에 timer 부착
  • timer 만료되면, unacked된 모든 패킷을 재전송

Selective Repeat

• 송신자는 N개 만큼의 unacked packet을 파이프라인 통해 전송
• 수신자는 각각의 패킷에 대한 individual ack를 송신자에게 전송
• 송신자는 각각의 unacked packet에 대한 timer 유지
  • timer 만료되면, 해당 unacked packet만 재전송

TCP

• 신뢰성 있는, 순서를 보장하는 전송
• Pipelined
  • congestion, flow control이 window 크기 결정
• connection-oriented by handshaking
• TCP의 Sequence number와 ACK

• TCP의 timeout 설정 기준
  • RTT 보다 길게!
  • 너무 짧으면, 불필요한 재전송하게 됨
  • 너무 길면, segment loss에 느린 대처하게 됨

TCP retransmission scenarios

TCP fast retransmit

• timeout 시간이 상대적으로 긴 경우가 있을 수 있음
  • packet loss 이후에 재전송에 긴 지연이 생김
• 중복된 ACK를 통해 packet loss를 감지 가능
• 만약 송신자가 같은 데이터에 대한 ACK를 3번 받게 되면,
  • 가장 작은 번호의 unacked packet부터 재전송

TCP flow control

• 수신자가 송신자를 제어하여, 수신자의 buffer가 overflow되지 않도록 하는 것
• 수신자는 TCP 헤더의 rwnd라는 값에 여유 버퍼 공간을 알려, 송신자가 너무 많은 데이터를 보내지 못하도록 함

Handshake

• 2-way handshake의 실패 사례

• 3-way handshake

TCP: closing a connection

혼잡 제어의 원리

• "too many sources sending too much data too fast for network to handle"
• lost packets과 long delay를 초래
• 1번 시나리오

• 2번 시나리오

• 2번 시나리오의 이상적 해결안
  • Perfect knowledge: 송신자는 router의 buffer에 공간이 있을 때만 패킷 전송
  • Known loss: packet loss를 인지했을 때만 데이터 재전송
• 현실적 해결안
  • duplicates: 송신자는 패킷의 loss와 drop을 고려하여, 2개의 복사본을 보냄
• 3번 시나리오

혼잡 제어의 2가지 접근법

• 호스트 간의 혼잡 제어
  • 네트워크로부터 피드백 존재하지 않음
  • 종단 시스템에서 loss와 delay의 발생을 보고 혼잡 발생 추론
  • TCP와 같은 접근 취함
• 네트워크 지원 하의 혼잡 제어
  • 라우터가 종단 시스템에게 피드백 제공
  • 송신자의 송신 속도 제어

TCP congestion control

• 송신자는 전송 속도를 서서히 증가시킴
  • loss 발생할 때 까지 증가시키며, 적정 bandwidth를 검증
• additive increase: loss 감지될 때 까지 매 RTT마다 전송 속도 증가
• multiplicative decrease: loss 발생 이후에 전송 속도 반으로 절감
  • TCP Reno: loss 발생 이후, 전송 속도를 반으로 줄임
  • TCP Tahoe: loss 발생 이후, 전송 속도를 1로 줄임

Overview

OSI 7계층 탄생 배경

• 여러 정보 통신 업체 장비들은 타사의 장비와 연결이 되지 않는 등 호환성 문제가 존재
• ISO 단체에서 1984년 OSI 참조모델 발표
• OSI란 네트워크 통신의 개방 시스템 상호 연결 모델(Open Systems Interconnection)
• 모든 시스템들들의 상호 연결을 가능케 하는 표준으로 7개 계층으로 구분

각 계층의 캡슐화와 디캡슐화

• 데이터를 전송할 때 각각의 층마다 인식할 수 있어야 하는 헤더를 붙이게 되는데 이러한 과정이 캡슐화
• 데이터가 전송매체를 통해 전송된 후 1계층 부터 7계층으로 올라가며 헤더가 벗겨지는데 이러한 과정이 디캡슐화

OSI 7계층의 계층별 프로토콜과 기능

• PDU(Process Data Unit)이란 각 계층에서의 전송 단위
• 1계층에서는 PDU이 bit라고 생각하기 쉽지만, 단지 신호의 흐름일 뿐
• 2계층(Frame), 3계층(Packet), 4계층(Segment), 그 이상 계층(Data)

각 계층별 대표적 프로토콜

Application Layer

• 사용자와 가장 밀접한 계층이며, 인터페이스 역할 수행
• 기능: 응용 프로세스 간 정보 교환
• ex) email, internet, media player 등의 application

Presentation Layer

• 기능: 데이터 표현에 차이가 있는 응용처리에서의 제어 구조 제공
  • 데이터 표헌 차이: ASCII, JPEG, MPEG 등의 translation
• 전송하는 데이터의 인코딩, 디코딩, 암호화, 코드 변환 등 수행

Session Layer

• 기능: 통신장치 간 상호작용 및 동기화 제공
• 연결 세션에서 데이터 교환과 에러 발생시 복구 관리
  • 즉, 논리적 연결 담당
• ex) SSH

Transport Layer

• 기능: 종단 간에 신뢰성 있고 정확한 데이터 전송 담당
• 4계층 전송 단위는 Segment이며, 종단 간 에러복구와 흐름 제어 담당
• ex) TCP(Transmission Control Protocol), UDP(User Datagram Protocol)

Network Layer

• 기능: 중계 노드 통하여 전송하는 경우, 어떻게 중계할 것인가를 규정
• 3계층 전송 단위는 Packet이며, Packet을 목적지까지 경로 설정을 함
• 데이터를 목적지까지 가장 안전하고 빠르게 전달하도록 하며, 이를 라우팅이라 함
• ex) IP(Addressing, Fragmentation, Routing)
• 3계층 장비: 라우터, L3 스위치

Data Link Layer

• 기능: 물리적 연결을 통하여 인접한 두 장치 간 신뢰성 있는 정보 전송 담당
• 2계층 전송 단위는 Frame이며, 주소와 제어정보 가짐
• 정보의 오류와 흐름을 관리하여 안정된 정보 전달
• ex) IEEE802.2(LLC), IEEE802.3(CSMA/CD), IEEE802.5(Token Ring)
• 2계층 장비: 브릿지, 스위치

Physical Layer

• 기능: 전기적, 기계적 특성 이용하여 통신 케이블로 전기적 신호 전송
• 인코딩 전압 및 케이블 사양 핀의 수 등을 정의한 계층
• 단지, 데이터 전달의 역할만 수행
• 1계층 장비: 케이블, 리피터, 허브

Application Layer

Application architectures

• Client-Server
• Peer-to-Peer(P2P)

Client-Server architecture

• Server
  • always-on host
  • 영구 IP 주소
  • 규모에 따라 데이터 센터일 수도 있음
• Clients
  • Server와 커뮤니케이션
  • 클라이언트 간 직접 커뮤니케이션 하지 못함
  • 간헐적으로 연결
  • 동적 IP 주소를 가질 수 있음

P2P architecture

• no always-on server
• host들이 자발적으로 직접 커뮤니케이션 -> Self scalability
• peer는 다른 peer에게 서비스를 요청하고, 또 다른 peer에게 서비스를 제공할 수 있음
• peer들은 간헐적으로 연결되며, IP 주소를 바꿈
  • 관리의 어려움

Process communicating

• process: host 내에서 실행 중인 프로그램
• 서로 다른 프로세스가 같은 host에서 실행 중이라면, IPC(Inter Process Communication)을 이용하여 통신
• 서로 다른 프로세스가 다른 host에서 실행 중이라면, Messages를 교환하며 통신
• Client process: 통신을 시작하는 프로세스
• Server process: 다른 프로세스의 연결을 기다리는 프로세스

Sockets

• 프로세스는 메시지를 socket으로부터 받거나, socket으로 전송

Addressing processes

• message를 전달받기 위해서 프로세스는 반드시 identifier를 지녀야 함
• identifer는 IP 주소와 포트 번호를 포함
• ex) HTTP Server은 80번 포트 번호 사용, mail server는 25번 포트 번호 사용

App-layer protocol defines

• message type
  • ex) request, response
• message syntax
  • 어떤 필드값이 있어야 하며, 필드 값들이 어떻게 채워져야 하는지
• message semantics
  • 필드 값들의 의미
• 언제 그리고 어떻게 프로세스들이 메시지를 전송하고, 응답하는지에 대한 rules

Application에 필요한 전송 서비스

• Data integrity
  • 어떤 app들은 100% 신뢰 가능한 데이터 전송을 요구(ex: file transfer)
  • 반면, 어떤 app들은 약간의 손실을 허용(ex: audio)
• timing
  • 어떤 app들은 낮은 지연율을 요함(ex: interactive games)
• throughput
• security
  • 암호화, 데이터 무결성...

Internet transport protocols services

• TCP service
  • 신뢰성 있는 전송
  • flow control
  • congestion control
  • connection-oriented
  • does not provide: timing, minimum throughput guarantee, security
• UDP service
  • 비신뢰성 전송
  • does not provide: reliability, flow control, congestion control, timing, throughput guarantee, security, connection set-up

SSL

• 암호화된 TCP 연결을 제공
• data integrity
• end-point authentication
• SSL is at app layer
  • app들은 TCP와 대화하는 SSL 라이브러리를 사용

Web and HTTP

• Web page는 object들로 구성되어 있음
  • object는 HTML file, Image, Audio 등
• Web page는 여러 참조된 object들을 포함하는 HTML file로 구성
• 각각의 object는 URL을 통해 접근 가능
• ex) www.someschool.edu/someDept/pic.gif

HTTP overview

• HTTP: HyperText Transfer Protocol
• Web의 application layer protocol
• Client-Server 모델
  • Client: Web object들을 요청하고, 받고 화면에 보여주는 browser
  • Server: 요청에 대한 응답으로 object를 보내는 Web server
• uses TCP
  • 클라이언트가 80번 포트 번호를 이용하여 서버에 TCP 연결 시작
  • 서버는 클라이언트의 TCP 연결 승인
  • HTTP messages들이 browser와 Web server 간 교환
  • TCP 연결 종료
• HTTP is "stateless(무상태)"
  • 서버는 이전 클라이언트 요청에 대한 어떠한 정보도 저장하지 않음

HTTP connections

• non-persistent HTTP
  • 최대 하나의 object가 TCP 연결 통해 전송 가능
  • 여러 개의 object를 download하기 위해선 여러 번의 연결이 필요
• persistent HTTP
  • 여러 개의 object가 하나의 TCP 연결을 통해 전송 가능

Response Time

• RTT: time for a small packet to travel from client to server and back
• Non-persistent HTTP
  • TCP 연결 시작하기 위한 RTT +
  • HTTP request 위한 RTT +
  • file transmission time =
  • 2 RTT + file transmission time
• Persistent HTTP
  • 서버는 연결을 open 상태로 둠
  • 모든 object를 받기 위해 하나의 RTT만 필요

HTTP request message

• 2개의 HTTP 메시지 타입: request, response

Uploading form input

• POST method
  • Web page는 종종 input form을 포함
  • input이 server에 업로드 됨
• URL method
  • GET method 사용
  • input이 URL의 request line을 통해 업로드
  • ex) www.somesite.com/animalsearch?monkeys&banana

Method types

• HTTP/1.0:
  • GET
  • POST
  • HEAD
• HTTP/1.1:
  • GET, POST, HEAD
  • PUT: URL 필드에 지정된 경로에 파일 업로드
  • DELETE: 특정 URL 필드에 명시된 파일을 삭제

HTTP response message

• status code
  • 200 OK: request 성공, 요청된 object가 이후에 이 msg에 포함될 것
  • 301 Moved Permanently: 요청된 object가 이동함, 이후에 새로운 주소가 이 msg에 명시될 것
  • 400 Bad Request: 서버가 요청 메시지를 처리하지 못함
  • 404 Not Found: 요청된 문서가 이 서버에 존재하지 않음
  • 505 HTTP Version Not Supported

User-Server state: cookies

• 많은 웹 사이트들이 쿠키를 사용
• four components
  • cookie header line of HTTP response msg
  • cookie header line in next HTTP request msg
  • cookie file kept on user's host, managed by user's browser
  • back-end database at Web site

Web caches (proxy server)

• Origin server를 거치지 않고 클라이언트의 요청을 만족하기 위해 사용
• browser가 모든 HTTP request를 cache로 보냄
  • object가 cache에 있다면: cache returns object
  • object가 cache에 없다면: cache가 origin server에 object request 후, client에게 return

Conditional GET

• 목표
  • 만약 cache가 최신의 cached version을 가지고 있으면 object를 전송하지 않음
  • no object transmission delay
  • lower link utilization
• cache: HTTP request에 cached copy의 날짜를 명시
• server: 만약 cached copy가 최신의 것이면 response는 object를 포함시키지 않음

FTP(File Transfer Protocol)

• file을 remote host로/로부터 transfer
• Client-Server model
  • client: side that initiates transfer
  • server: remote host
• 하나의 file 전송 이후에 서버는 data connection 종료
• 서버는 다른 file의 전송을 위해서 다른 TCP data connection을 open
• FTP Server는 'state'를 유지
  • current directory, earlier authentication

E-mail

• Three major components
  • user agents
  • mail servers
  • SMTP(Simple Mail Transfer Protocol)
• User Agent(mail reader)
  • composing, editing, reading mail messages
  • outgoing, incoming messages stored on server
• Mail Servers
  • mailbox는 user에게 온 messages들을 저장
  • message queue는 전송되야 할 mail messages들 담음
  • email messages의 전송을 위한 mail servers들간의 SMTP

SMTP

• reliable transfer를 위해 TCP 사용(25번 포트 번호)
• direct transfer: sending server to receiving server
• Three phases of transfer
  • handshaking
  • transfer of messages
  • closure
• persistent한 연결 사용
• message가 7-bit ASCII로 작성되어야 함

POP3 Protocol

• authorization phase
  • client commands:
    • user: declare username
    • pass: password
  • server responses:
    • +OK
    • -ERR
• transaction phase
  • list: list message numbers
  • retr: retrieve message by number
  • dele: delete
  • quit
• POP3 is stateless across sessions

DNS(Domain Name System)

• IP 주소 대신 'name'을 사용하여 주소에 접근이 가능하게 함
• 분산된 database가 많은 name server들의 계층을 구현
• DNS services
  • hostname to IP addr translation
  • host aliasing
  • mail server aliasing
  • load distribution: 하나의 이름에 많은 IP 주소 설정 가능
• Why not centralize DNS?
  • traffic volume
  • distant centralized database
  • maintenance

DNS: root name servers

• local name server가 name을 처리하지 못할 때 접근하는 서버
• name과 주소의 mapping을 TLD로부터 얻어와 local name server에 return
• 전 세계적으로 13개의 root name server 존재

TLD, authoritative servers

• Top-Level Domain servers:
  • com, org, net, eud, areo, jobs, museums 등과 모든 국가 도메인들을 관리(ex: uk, kr, ca)
• authoritative DNS servers:
  • 기관의 name host들에게 authoritative hostname to IP mapping을 제공하는 기관 소유의 DNS Server
  • 기관 혹은 서비스 제공자에 의해 maintain

Local DNS name server

• 각각의 ISP는 'default name server'라고 불리는 local DNS server 지님
• host가 DNS query를 발생시키면, query는 local DNS server로 전송됨
  • 최근 name-to-address translation 쌍을 local cache에 가지고 있음
  • proxy와 같이 작동하여, query를 계층 구조로 이동시킴
• iterated query

• recursive query

DNS: caching, updating records

• name server가 mapping을 하면, 해당 mapping을 caching
  • cache entry는 TTL 이후에 timeout
  • TLD 서버는 기본적으로 local name server에 cache 되어 있음
    • 그러므로 root name server는 많이 방문되지 않음
• cached entry들은 out-of-date인 것일 수 있음 만약 name host가 IP 주소를 바꿔도, 모든 TTL이 만료될 때 까지 다른 Server들은 해당 변경을 알 수 없음

Attacking DNS

• DDos attacks
  • root server의 traffic을 폭주 시킴
    • traffic filtering을 통해 예방 가능
  • TLD server의 traffic 폭주시키는 것이 더 위험
• Redirect attcks
  • Man-in-middle: query 가로채기
  • DNS poisoning: DNS 서버에 위조 정보 전송

File Systems

File and File System

• File
  • A named collection of related information
  • 일반적으로 비휘발성의 보조기억장치에 저장
  • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 보여줌
  • Operation
    • create, read, write, delete, open, close 등
• Metadata
  • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보
  • ex) 파일 이름, 유형, 저장 위치, 파일 크기
  • ex) 접근 권한, 시간(생성/변경/사용), 소유자 등
• File System
  • 운영체제에서 파일을 관리하는 부분
  • 파일 및 파일의 Metadata, 디렉토리 정보 등 관리
  • 파일의 저장 방법 결정
  • 파일 보호 등

Directory and Logical Disk

• Directory
  • 파일의 Metadata 중 일부를 보관하고 있는 특별한 파일
  • 디렉토리에 속한 파일 이름 및 파일의 metadata 등 보관
  • Operation
    • search for a file, create a file, delete a file
    • list a directory, rename a file, traverse the file system
• Partition(=Logical Disk)
  • 하나의 디스크 안에 여러 Partition을 두는게 일반적
  • 여러 개의 물리적 디스크를 하나의 Partition으로 구성하기도 함
  • 디스크를 Partition으로 구성한 뒤 각각의 Partition에 file system을 깔거다 swapping 등 다른 용도로 사용 가능

open()

• File의 Metadata를 메인 메모리에 올리는 행위
• Directory path search 하는 데 너무 많은 시간 소요
  • read/write와 open을 따로 두는 이유!

• 운영체제에서 파일을 복사한 후, 전달하는 것이 Buffer Cache
  • 운영체제가 cache한 정보를 다 가지고 있으므로 LRU, LFU 등의 알고리즘 사용 가능

File Protection

• 각 파일에 대해 누구에게 어떤 유형의 접근을 허락할 것인가?
• Access Control 방법

• Access control Matrix는 모든 사용자에 대한 접근 권한 항목을 만들어야 하기 때문에 메모리 낭비가 큼
  • 주체에 따라 Linked List를 이용해 만드는 방법을 생각해볼 수 있음
  • 그러나, 이 역시 Overhead가 큼
• 일반적으로 Grouping 기법 사용

File System의 Mounting

Access Methods

• 순차 접근(sequential access)
  • 카세트 테이프를 사용하는 방식처럼 접근
  • 읽거나 쓰면 offset은 자동으로 증가
• 직접 접근(direct access, random access)
  • LP 레코드 판과 같이 접근
  • 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있음

Allocation of File Data in Disk

Contiguous Allocation

• 하나의 파일이 Disk 상에 연속해서 저장되도록 하는 것
• 장점
  • Fast I/O
    • 한 번의 seek / roation으로 많은 Byte transfer
    • Realtime file용으로, 또는 이미 run 중이던 프로세스의 swapping용
  • Direct access(=random access) 가능
• 단점
  • External Fragmentation
  • File grow가 어려움
    • File 생성 시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능케 넉넉히 배당할 수도 있지만, grow 하지 않는다면 그 공간은 낭비(Internal Fragmentation)

Linked Allocation

• 장점
  • External Fragmentation 발생 안 함
• 단점
  • No random access
  • Reliability 문제
    • 한 sector가 고장나 Pointer가 유실되면 많은 부분을 잃게 됨
  • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
• 변형
  • File-Allocation Table(FAT) 파일 시스템
  • 포인터를 별도의 위치에 보관하고 reliability와 공간 효율성 문제 해결

Indexed Allocation

• Indexed 블럭에 파일의 위치를 저장하여 보여줌
• 장점
  • External Fragmentation 발생하지 않음
  • Direct access 가능
• 단점
  • Small file의 경우 공간 낭비
    • 실제로 많은 파일들이 small
  • Large File의 경우 하나의 block으로 index를 저장하기에 부족
    • 해결 방안
    • Linked Scheme: 또 다른 indexed block을 찾아가게 함
    • Multi-level index: like Two-level page

UNIX File System의 구조

• Boot block
  • 부팅에 필요한 정보 저장(Bootstrap Loader)
• Super block
  • 파일 시스템에 관한 총체적 정보를 담고 있음
• Inode list
  • 파일 이름을 제외한 파일의 모든 Metadata 저장
  • 디렉토리는 특정 파일의 Metadata만 가지고 있지만, Inode list는 모든 파일의 Metadata를 가지고 있음
• Data block
  • 파일의 실제 내용 보관
• Indexed allocation을 사용하는 UNIX File System
  • 파일 크기에 따라 direct blocks만 사용할지,
  • single, double, triple indirect를 사용할지 결정
  • 한정된 크기의 inode로 모든 크기의 파일 관리 가능

FAT File System

• 파일의 Metadata 중 일부(ex.위치 정보)를 FAT에 저장
  • 블럭의 다음 블럭을 저장하는 형식
  • 이미 Memory에 올라와 있는 FAT만 보면 되기 때문에, Direct access 가능해짐
  • 포인터 하나가 유실되더라도 FAT에 정보가 있기 때문에 Reliability 문제 해결
• 나머지 Metadata는 Data block이 가지고 있음
• FAT은 중요한 정보이기 때문에 보통 Disk에 2 copy 이상 저장

Free-Space Management

Bit map or bit vector

• Bit map은 부가적 공간을 필요로 함
• 연속적인 n개의 free block을 찾는데 효과적
  • bit map scan을 통해

Linked List

• 모든 Free block들을 링크로 연결
• 부가적 공간 낭비가 없음
• 연속적 가용공간을 찾는 것이 쉽지 않음

Grouping

• Linked list 방법의 변형
• 첫 번째 Free block이 n개의 pointer를 가짐
  • n-1 Pointer는 free data block을 가리킴
  • 마지막 Pointer가 가리키는 block은 또 다시 n pointer를 가짐

Counting

• 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에서 착안
• (First free block, num of contiguous free block)을 유지

Directory Implementation

• Linear List
  • <file name, file의 metadata>의 list
  • 구현이 간단
  • 디렉토리 내에 파일이 있는지 찾기 위해서는 Linear search가 필요
• Hash Table
  • Linear list + hashing
  • Hash Table은 File name을 이 파일의 linear list의 위치로 바꾸어줌
  • Search time을 없애나, Collision 발생 가능
• File metadata의 보관 위치
  • 디렉토리 내에 직접 보관하거나,
  • 디렉토리에는 포인터를 두고 다른 곳(ex. FAT, inode)에 보관

• Long file name의 지원
  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정 크기
  • file name이 고정 크기의 entry 길이보다 길어지는 경우, entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
  • 이름의 나머지 부분은 동일한 directory file의 일부에 존재

VFS and NFS

• Virtual File System(VFS)
  • 서로 다른 다양한 file system에 대해 동일한 System call interface(API)를 통해 접근할 수 있게 해주는 운영체제의 layer
• Network File System(NFS)
  • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • NFS는 분산 환경에서의 대표적 파일 공유 방법

Page Cache and Buffer Cache

• Page Cache
  • Virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
  • Memory-Mapped I/O를 쓰는 경우 File의 I/O에서도 page cache 사용
• Memory-Mapped I/O
  • File의 일부를 Virtual Memory에 Mapping 시킴
  • Mapping 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
  • 이미 메모리에 올라온 File은 마치 내 File 처럼 사용할 수 있는 장점!

• Buffer Cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 Buffer cache 사용
  • File 사용의 locality 활용
    • 한 번 읽어온 block에 대한 후속 요청 시, buffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacement Algorithm 필요

• Unified Buffer Cache
  • 최근 운영체제에서는 기존의 Buffer cache가 Page cache에 통합
  • 따라서 File block들도 Page 크기 단위(4KB)로 읽어옴

Virtual Memory

Demand Paging

• 실제로 필요할 때 Page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • Page가 물리적 메모리에 없는 경우
  • 처음에는 모든 Page entry가 invalid로 초기화
  • address translation시에 invalid bit이 set 되어 있으면, Page fault

Page Fault

• invalid page를 접근하면 MMU가 Page Fault Trap을 발생시킴
• Kernel mode로 들어가 Page fault handler를 invoke
• 다음 순서로 Page Fault 처리
  • Invalid reference? -> abort process
  • Get an empty page frame (없으면 replace)
  • 해당 Page를 disk에서 memory로 읽어옴
    • disk I/O가 끝나기까지 이 프로세스는 block
    • Disk read가 끝나면 Page table entry 기록 후, valid bit set
    • Ready queue에 process 삽입
  • 이 프로세스가 CPU 잡고 다시 running
  • 아까 중단되었던 intruction 재개

free frame이 없는 경우

• Page replacement
  • 어떤 frame을 뺴앗아올지 결정해야 함
  • 곧바로 사용되지 않을 Page 쫓아내는 것이 좋음
  • 동일 Page가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
• Replacement Algorithm
  • Page-fault rate을 최소화하는 것이 목표
  • 주어진 Page reference string에 대해 Page fault를 얼마나 내는지 조사하여 평가 가능

Optimal Algorithm

• 가장 먼 미래에 참조되는 Page를 replace
• 현실적으로 불가능하기 때문에 다른 알고리즘의 성능에 대한 Upper bound 제공

FIFO Algorithm

• FIFO Anomaly: frame 수를 올렸음에도, Page fault의 수가 늘어날 수 있음

LRU Algorithm

• 가장 오래 전에 참조된 Page를 replace

LFU Algorithm

• 최저 참조 횟수의 Page를 replace
• 최저 참조 횟수 page가 여러 개인 경우?
  • 여러 Page 중 임의로 선정하거나,
  • 성능 향상을 위해 가장 오래 전에 참조된 Page를 replace
• 장단점
  • LRU처럼 직접 참조 시점만 보는 것이 아리나 장기적 시간 규모를 보기 때문에 Page의 인기도를 더 정확히 반영할 수 있음
  • 참조 시점의 최근성을 반영하지 못함
  • LRU 보다 구현이 복잡함
• LRU vs. LFU

LRU와 LFU 알고리즘의 구현

다양한 캐싱 환경

• 캐싱 기법
  • 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
  • Paging System 외에도 Cache memory, buffer caching, web caching 등 다양한 분야에서 사용
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  • Buffer caching이나 Web caching의 경우
    • O(1)에서 O(log N) 정도까지 허용
  • Paging System의 경우
    • Page fault의 경우에만 운영체제가 관여
      • Page가 이미 메모리에 존재하는 경우 참조 시간 등의 정보를 운영체제가 알 수 없음
      • LRU의 list 조작 조차 불가능

Clock Algorithm

• LRU의 근사 알고리즘
• a.k.a Second chance algorithm, NRU(Not Recently Used)
• Referece bit를 사용해서 교체 대상 페이지 선정
  • Reference bit가 0인 것을 찾을 때 까지 포인터를 하나씩 앞으로 이동
• 포인터가 이동하는 중에 Reference bit 1은 모두 0으로 set
• Reference bit이 0인 것을 찾으면 해당 Page 교체
• 한 바퀴 되돌아와서도(=Second chance) 0이면 그 때 replace
  • 자주 사용되는 Page라면 Second chance 올 때 1
• Clock Algorithm의 개선
  • reference bit와 modified bit를 함께 사용
  • reference bit = 1; 최근에 참조된 Page
  • modified bit = 1; 최근에 변경된 Page(I/O 동반하는 page)
  • 가능한 modified bit이 0인 Page를 쫓아내서 시간 단축할 수 있을 것

Page Frame의 Allocation

• Allocation problem: 각 프로세스에 얼마만큼의 Page frame을 할당할 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 Page 동시 참조
    • 명령어 수행을 위해 최소 할당되어야 하는 frame 수가 존재
  • Loop를 구성하는 Page들은 한꺼번에 allocate되는 것이 유리함
    • 최소한의 allocation이 없으면 매 loop 마다 page fault
• Allocation Sheme
  • Equal allocation: 모든 프로세스에 똑같은 개수 할당
  • Proportinal allocation: 프로세스 크기에 비례하여 할당
  • Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs. Local Replacement

• Global replacement
  • Replace 시 다른 프로세스에 할당된 frame을 뺏을 수 있음
  • 프로세스 별 할당량을 조절하는 또 다른 방법
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시에 해당
  • Working set, PFF 알고리즘 사용
• Local replacement
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 Page frame 수를 할당 받지 못한 경우 발생
• Page fault rate가 매우 높아짐
• CPU utilization이 낮아짐
• 운영체제는 Multiprogramming degree를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• CPU가 idle 해지는 현상 발생
• Low throughput

Working-set Model

• Locality of reference
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
  • 집중적으로 참조되는 해당 Page들의 집합을 Locality set이라 함
• Working-set Model
  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한 번에 메모리에 올라와 있어야 하는 Page들의 집합을 Working Set이라 정의
  • Working Set 모델에서는 프로세스의 Working Set 전체가 메모리에 올라와있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 Swap out
  • Thrashing을 방지!
  • Multiprogramming degree를 결정

• Working set의 결정
  • Working set window를 통해 알아냄
  • window size가 delta인 경우,
    • Working set에 속한 Page는 메모리에 유지, 속하지 않은 것은 버림
    • 즉, 참조된 후 delta 시간 동안 해당 page를 메모리에 유지한 후 버림
  • 시간 별로 Working set의 크기는 유동적으로 변함
• Window size delta
  • Working set을 제대로 탐지하기 위해서는 Window size를 잘 결정해야 함
  • delta 값이 너무 작으면 locality set 모두 수용하지 못할 우려
  • delta 값이 너무 크면 여러 규모의 locality set 수용
• Working-set Algorithm
  • 프로세스들의 working set size의 합이 page frame 보다 큰 경우
    • 일부 프로세스를 swap out 시켜 남은 프로세스의 working set을 우선적으로 충족시킴
  • Working set을 다 할당하고도 Page frame이 남는 경우
    • Swap out 되었던 프로세스에게 Working set 할당

PFF(Page Fault Frequency) Model

• Page fault rate의 상한값과 하한값을 설정
  • Page fault rate이 상한값을 넘으면 frame을 더 할당
  • Page fault rate이 하한값 이하이면 할당 frame 수를 줄임
• 빈 frame이 없으면 일부 프로세스를 Swap out

Page Size의 결정

• Page size를 감소시키면
  • Page 수 증가
  • Page table 크기 증가
  • Internal fragmentation 감소
  • Disk Transfer의 효율성 감소
    • Seek/Rotation vs. Transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality의 활용 측면에서는 좋지 않음
• 트렌드는 Larger page size

Memory Management

Logical vs. Physical Address

• Logical address(=Virtual address)
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소는 Logical address
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩: 주소를 결정 하는 것
  • Symbolic addr -> Logical addr -> Physical addr
  • cf. Symbolic addr: 프로그래머 입장에서의 주소(변수, 함수 등)

Address Binding

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
  • 컴파일 시 항상 논리적이자 물리적 주소를 알아야 하므로 비효율적(현대에는 사용 x)
• Load time binding
  • Loader의 책임 하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 사용 가능
• Execution time binding(=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
  • CPU가 주소를 참조할 때 마다 binding을 점검
  • 하드웨어적 지원이 필요(MMU)
  • 대부분의 현대 컴퓨터에서 지원

Memory Management Unit (MMU)

• Logical Addr를 Physical Addr로 매핑해주는 하드웨어 장치

• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더함
• User program
  • Logical addr만을 다룸
  • 실제 Physical addr를 볼 수 없으며 알 필요도 없음

• Relocation register는 접근할 수 있는 물리적 메모리의 최소값(프로그램의 시작점)
• Limit register는 악성 프로그램이 요청 프로그램의 크기를 벗어나는 주소 번지를 요청하는 경우를 방지하기 위해 사용

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 Load하는 것
  • Memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
  • ex) 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서(Library를 통해) 구현 가능
• Paging 기법과는 다른 기법

Overlays

• 메모리에 프로세스의 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원 없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수 작업으로 프로그래머가 구현
  • Manual Overlay -> 프로그래밍이 매우 복잡

Swapping

• 프로세스 전체를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing Store(=Swap area)
  • 디스크: 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in / Swap out
  • 일반적으로 중기 스케줄러(Swapper)에의해 Swap out 시킬 프로세스 선정
  • Priority-based CPU scheduling algorithm
    • 우선순위 높은 프로세스를 메모리에 올려 놓음
    • 우선순위 낮은 프로세스를 Swap out
  • Compile time 혹은 Load time binding에서는 원래 동작하던 메모리 위치로 Swap in 해야 함 (비효율)
  • Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음 (효율)

Dynamic Linking

• Linking을 실행 시간까지 미루는 기법
• Static Linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic Linking
  • 라이브러리가 실행 시 Link됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나누어 사용
  1. OS 상주 영역: interrupt vector와 함께 낮은 주소 영역 사용
  2. 사용자 프로세스 영역: 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation
    • 각각의 프로세스가 메모리의 연속적 공간에 적재되도록 하는 것
    • Fixed partition allocation / Variable partition allocation
  • Non-contiguous allocation (현대에 사용)
    • 하나의 프롯스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
    • Paging / Segmentation / Paged Segmentation

Contiguous Allocation

Fixed Partition

• 물리적 메모리를 몇 개의 영구적 분할로 나눔
• 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
• 분할 당 하나의 프로그램 적재
• 융통성이 없음
  • 동시에 메모리에 Load되는 프로그램의 수가 고정
  • 최대 수행 가능 프로그램 크기 제한
• Internal / External Fragmentation 발생

Variable Partition

• 프로그램의 크기를 고려해서 할당
• 분할의 크기, 개수가 동적으로 변함
• 기술적 관리 기법 필요
• External Fragmentation 발생

Internal Fragmentation

• 프로그램 크기보다 분할의 크기가 큰 경우 발생
• 하나의 분할 내부에서 발생하는, 사용되지 않는 메모리 조각
• 특정 프로그램에 배정되었지만 사용되지 않는 공간

External Fragmentation

• 프로그램 크기보다 분할의 크기가 작은 경우
• 아무 프로그램에도 배정되지 않은 빈 공간인데도 프로그램이 올라갈 수 없는 작은 분할

Hole

• 가용 메모리 공간
• 다양한 크기의 hole들이 메모리 여러 곳에 산재
• 프로세스가 도착하면 수용 가능한 hole 할당
• 운영체제는 할당 공간 / 가용 공간의 정보를 유지

Dynamic Allocation Problem

• First-fit
  • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
• Best-fit
  • Size가 n 이상인 가장 작은 hole 찾아 할당
  • hole들의 리스트가 크기 순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 함
  • 많은 수의 아주 작은 hole들이 생성됨
• Worst-fit
  • 가장 큰 hole에 할당
  • 역시 모든 리스트를 탐색해야 함
  • 상대적으로 아주 큰 hole들이 생성
• First-fit과 Best-fit이 속도와 공간 이용률 측면에서 효과적으로 알려짐

Compaction

• External fragmentation 문제를 해결하는 방법
• 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 모아 큰 block을 만드는 것
• 매우 비용이 많이 드는 방법
• Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 사용 가능

Non-contiguous Allocation

Paging

• Paging
  • 프로세스의 Virtual memory를 동일한 사이즈의 page 단위로 나눔
  • Virtual memory의 내용이 page 단위로 non-contiguous 하게 저장됨
  • 일부는 backing storage에, 일부는 physical memory에 저장
• Basic method
  • Physical memory를 동일한 크기의 Frame으로 나눔
  • Logical memory를 동일한 크기의 Page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • Page table을 사용하여 Logical addr를 Physical addr로 변환
    • 프로그램마다 Page table 존재
  • External fragmentation 발생 X
  • Internal fragmentation 발생 O

Implementation of Page Table

• Page Table은 main memory에 상주
• 모든 메모리 접근 연산에는 2번의 메모리 접근이 필요
  • Page table 1번 + 실제 data/instruction 1번
• 속도 향상을 위해 associative register 혹은 Translation Look-aside Buffer(TLB)라 불리는 고속의 Lookup Hardware Cache 사용

• TLB Search에도 시간이 오래 걸리므로, Parallel search를 지원
• TLB는 context switch 때 Flush 됨 (TLB도 프로세스에 따라 다르기 때문)

Two-Level Page Table

• 현대 컴퓨터는 address space가 매우 큰 프로그램 지원
• 그러나 대부분의 프로그램은 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비
• Page table 자체를 page로 구성하자!
• 사용되지 않는 주소 공간에 대한 Outer page table의 entry 값은 NULL -> 메모리 save 가능
• Multi-level Paging and Performance
  • 주소 공간이 더 커지면 다단계 Page table 필요
  • 각 단계의 Page table이 메모리에 존재하므로 Logical addr의 Physical addr 변환에 더 많은 메모리 접근 필요
  • TLB 통해 메모리 접근 시간 줄일 수 있음 -> Overhead 크지 않음!

Memory Protection

• Page Table의 각 entry 마다 아래의 bit를 둠
  • Protection bit
    • page에 대한 접근 권한(read/write/readonly)
  • Valid-Invalid bit
    • valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 의미(접근 허용)
    • invalid는 해당 주소의 frame에 유효한 내용이 없음을 의미(접근 불허)
      • 프로세스가 그 주소 부분을 사용하지 않는 경우
      • 해당 페이지가 메모리에 올라와 있지 않고, swap area에 있는 경우

Inverted Page Table

• Page frame 하나 당 page table에 하나의 entry를 두는 것
• 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시
• 장점: Page table entry 사용공간을 줄일 수 있음
• 단점: 테이블 전체를 탐색해야 위치를 알 수 있음
• 조치: TLB 사용 통해 Parallel search

Shared Page

• Shared code
  • Re-entrant code(=Pure code)
  • readonly로 하여 프로세스 간에 하나의 code만 메모리에 올림
  • Shared code는 모든 프로세스의 Logical addr space에서 동일한 위치에 있어야 함
    • 주소 변환 통해 같은 Physical addr로 가야 하기 때문에
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 Logical addr space의 아무 곳에 와도 무방

Segmentation

• 프로그램을 의미 단위인 여러 개의 Segment로 분할
  • 작게는 프로그램을 구성하는 함수 하나 하나로,
  • 크게는 프로그램 전체를 하나의 segment로 정의 가능
• 일반적으로는 code, data, stack 부분이 하나씩의 Segment로 정의됨
• Segmentation은 Paging 기법보다 메모리 낭비가 적음
• Segment의 길이가 균일하지 않을 수 있기 때문에, 주소 변환 시 길이를 의미하는 limit 변수를 함께 전달

Segmentation Architecture

• Protection
  • 각 Segment 별로 Protection bit 존재
  • Each entry:
    • valid bit = 0 -> illegal segment
    • read/write/execution 권한 bit

• Sharing
  • Shared segment
  • Same segment number
  • cf. Segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적
• Allocation
  • First fit / best fit
  • External fragmentation 발생
    • Segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들 발생

Paged Segmentation

• Segment 하나가 여러 개의 page로 구성
• 물리적 메모리에는 Page 단위로 올라감
  • Allocation 문제 발생 안 됨

Deadlocks

The Deadlock Problem

• Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태
• Resource
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) I/O device, CPU Cycle, Memory space, Semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request, Allocate, Use, Release
• Deadlock example 1
  • 시스템에 2개의 Tape drive가 있음
  • 프로세스 P1과 P2 각각이 하나의 Tape drive를 보유한 채 다른 하나를 기다림
• Deadlock example 2

Deadlock 발생의 4가지 조건

• Mutual exclusion
  • 매 순간 하나의 프로세스만이 자원의 사용 가능
• No preemption
  • 프로세스는 자원을 강제로 빼앗기지 않음
• Hold and wait
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 기다림
• Circular wait
  • 자원을 기다리는 프로세스 간 사이클이 형성됨
  • 프로세스 P0, P1, ..., Pn이 있을 때
    • P0은 P1이 가진 자원을 기다림
    • P1은 P2가 가진 자원을 기다림
    • Pn-1은 Pn이 가진 자원을 기다림
    • Pn은 P0이 가진 자원을 기다림

Resource-Allocation Graph (자원 할당 그래프)

• Deadlock 여부를 확인하기 위한 그래프

Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되 그에 대한 Detection 루틴을 두어 Deadlock 발견 시 Recovery
• Deadlock Ignorance
  • Deadlock을 시스템이 책임지지 않음
  • UNIX를 비롯한 대부분의 OS가 채택

Deadlock Prevention

• Mutual exclusion
  • 반드시 성립해야 하는 조건
• Hold and wait
  • 1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법
  • 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No preemption
  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원은 다른 프로세스에 의해 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작
  • state를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular wait
  • 모든 자원 유형에 할당 순서 정하여 정해진 순서대로만 자원 할당
• 생기지도 않을 Deadlock의 고려로 인해 비효율적 시스템 설계로 이어질 수 있음

Deadlock Avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원을 할당하는 것이 Deadlock으로부터 안전한지를 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• Safe State
  • 시스템 내의 프로세스들에 대한 Safe Sequence가 존재하는 상태
• Safe Sequence
  • 프로세스의 Sequence가 Safe하려면 Pi의 자원 요청이 가용 자원 + 모든 Pj(j < i)의 보유 자원에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi의 자원 요청이 즉시 충족될수 없으면 모든 Pj가 종료될 때 까지 기다림
    • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행

Resource Allocation Graph Algorithm

• 점선은 프로세스가 평생에 한 번은 해당 자원을 사용할 수 있다는 것을 의미

Banker's Algorithm

• 가정
  • 모든 프로세스는 자원의 최대 사용량을 미리 명시
  • 프로세스가 요청 자원을 모두 할당 받은 경우 제한된 시간 안에 이들 자원을 다시 반납
• 방법
  • 기본 개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당
  • 총 요청 자원의 수가 가용 자원의 수 보다 적은 프로세스를 선택 (해당 프로세스 없으면 unsafe 상태)
    • 그런 프로세스가 있으면 그 프로세스에게 자원 할당
  • 할당 받은 프로세스가 종료되면 모든 자원 반납
  • 모든 프로세스가 종료될 때 까지 이 과정 반복

Deadlock Detection and recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • Banker's algorithm과 유사한 방법 활용
      • 사실 single instance인 경우에도 이 방법 활용하는 것이 더 효율적
    • 낙관적으로 Request가 없는 프로세스는 소유한 자원을 반납할 것이라고 가정
• Wait-for graph Algorithm
• Resource type 당 single instance인 경우
• Wait-for graph

• 자원 할당 그래프의 변형
• 프로세스만으로 node 구성
• Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
• Algorithm
  • Wait-for graph에 cycle이 존재하는지를 주기적으로 조사
  • O(n^2): n(n-1) 만큼의 화살표가 존재할 수 있기 때문
• Recovery
  • Process termination
    • 1. Deadlock에 연루된 모든 프로세스 종료
    • 2. Deadlock cycle이 제거될 때 까지 한 번에 하나의 프로세스씩 종료
  • Resource Preemption
    • 비용을 최소화 할 Victim의 선정
    • Safe state로 Rollback하여 프로세스 재시작
    • Starvation 문제
      • 동일 프로세스가 계속해서 Victim으로 선정되는 경우
      • -> Cost factor에 Rollback 횟수도 같이 고려!

Deadlock Ignorance

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 느낀 프로그래머가 직접 프로세스를 죽이는 등의 방법으로 대처

Process Synchronization (2)

Classical Problems of Synchronization

Bounded-Buffer Problem(Producer-Consumer Problem)

• Shared data
  • buffer 자체 및 buffer 조작 변수
• Synchronizaiton variables
  • mutual exclusion: Need binary semaphore(Shared data의 mutual exclusion을 위해)
  • resource count: Need integer semaphore(남은 full/empty buffer의 수 표시)

Readers-Writers Problem

• 한 프로세스가 Database에 write 중일 때 다른 프로세스가 접근하면 안 됨
• read는 동시에 여럿이 해도 됨
• 해결책
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들은 다 DB에 접근 가능케 해줌
  • Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지
  • Writer가 DB에서 빠져나가야만 Reader의 접근 허용
• Shared data
  • Database 자체
  • int readcount; //(현재 DB에 접근 중인 Reader의 수)
• Synchronization variables
  • mutex: 공유 변수 readcount를 접근하는 critical section의 mutual exclusion을 보장하기 위해 사용
  • db: Reader와 Writer가 공유 DB 자체를 올바르게 접근 하는 역할

• 최초의 Reader는 readcount를 증가시켜주어, db에 lock을 걸어줌
• readcount 자체도 공유 변수이기 때문에 Semaphore 사용하여, Lock/Unlock 처리를 해줌
• readcount가 0이 되는 경우, db에 건 lock을 unlock 해주며 Reader 마무리
• 너무 늦게 들어온 Reader보다 Writer가 우선순위 높게 하는 방식 등으로 Starvation 문제 해결 가능할 것

Dining Philosophers Problem

• Problem
  • 모든 철학자가 동시에 왼쪽 젓가락을 집어버리면 Deadlock이 생김
• Solution
• 4명의 철학자만이 테이블이 동시에 앉을 수 있도록 함

• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 함(좌/우측 철학자가 식사 중이 아닐 때, 내가 젓가락을 들 수 있음)
• 비대칭
  • 짝수 철학자는 왼쪽 젓가락부터 잡음
  • 홀수 철학자는 오른쪽 젓가락부터 잡음

Monitor

• Semaphore의 문제점
  • 코딩의 어려움
  • 정확성의 입증이 어려움
  • 자발적 협력이 필요
  • 한 번의 실수가 모든 시스템에 치명적 영향

• Monitor: 동시 수행 중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한 high-level synchronization construct
  • Monitor 내부에 공유 데이터를 두고, 하나의 프로세스 씩 동작하게 하는 식으로 진행
  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩 할 필요가 없음
  • 프로세스가 모니터 안에서 기다릴 수 있도록 condition variable 사용
  • Condition variable은 _wait_와 signal 연산에 의해서만 접근 가능
    • signal을 사용할 때 suspend 상태인 프로세스가 없는 경우, 아무 일도 일어나지 않음

• Monitor를 이용한 Dining Philosophers 문제의 해결
  • 상대의 state를 변경할 수 있기에 공유 변수 처리

Process Synchronization (1)

데이터의 접근

1. 데이터가 스토리지에 저장
2. 연산할 데이터를 fetch
3. 데이터 연산
4. 연산 결과 스토리지에 저장

Race Condition

• 스토리지가 공유되어 여러 연산이 동시에 실행될 경우, Race Condition의 가능성이 있음
• CPU / Memory, Process / Address space와의 관계에서 생기는 문제
• 커널 내부 데이터를 접근하는 루틴들 간에도 문제가 있을 수 있음
  • ex) 커널 모드 수행 중 인터럽트로 커널 모드 다른 루틴 수행 시

OS에서 Race Condition은 언제 발생하는가?

• kernel mode 수행 중 interrupt 발생 시
  • 커널 모드 running 중 interrupt가 발생하여 interrupt 처리 루틴이 수행
  • 양 쪽 다 커널 코드이므로, kernel address space 공유
  • disable / enable interrupt로 문제 해결 가능

• Process가 System call을 하여 kernel mode로 수행 중인데, context switch가 일어나는 경우
  • 두 프로세스의 address space 간에는 data sharing이 없음
  • 그러나 system call을 하는 동안에는 kernel address space의 data에 접근하게 됨
  • 이 작업 중간에 CPU를 선점해가면 Race condition 발생
  • 커널 모드에서 수행 중일때는 CPU를 선점하지 않고, 사용자 모드로 돌아갈 때 선점하는 것으로 해결 가능

• 멀티프로세서에서 shared memory 내의 kernel data
  • 어떤 CPU가 마지막으로 count를 store 했는가에 대한 Race condition 발생
  • 해결책1: 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 함(비효율)
  • 해결책2: 커널 내부에 있는 각 공유 데이터에 접근할 때 마다 그 데이터에 대한 lock / unlock을 함

Process Synchronization 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
• 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요
• Race Condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• Race condition을 막기 위해서는 concurrent process는 동기화되어야 함

The Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• 문제: 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어가지 않아야 함

프로그램적 해결법의 충족 조건

• Mutual Exclusion
  • 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 됨
• Progress
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 함
• Bounded Waiting
  • 프로세스가 critical section에 들어가려고 요청한 그 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에는 한계가 있어야 함

Initial Attempts to solve problem

• 프로세스들의 일반적 구조

• 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있음 -> synchronization variable

Algorithm 1

• Synchronization variable
  • int turn;
  • initially turn = 0
    • Pi can enter its critical section if (turn == i)
• Process Pi

• Mutual Exclusion은 만족하지만 Progress 불만족
  • 반드시 한 번씩 교대로 들어가야 하기 때문에 critical section에 들어가 있는 프로세스가 turn 값을 바꾸어줘야 Progress가 생기기 때문
  • P1은 critical section에 1번 들어가고, P0은 지속적으로 들어가야 하는 상황이라면 P1이 turn을 반납하지 않아 아무도 critical section을 이용하지 못하게 될 가능성 존재

Algorithm 2

• Synchronization variable
  • boolean flag[2];
  • initially flag[모두] = false; //no one is in critical section
  • Pi ready to enter its critical section if (flag[i] == true)
• Process Pi

• Mutual Exclusion은 만족하지만 Progress 불만족
  • while 문에서 서로 끊임 없이 양보하는 상황 발생 가능

Algorithm 3 (Peterson's Algorithm)

• turn과 flag[] 변수 모두 사용
• Process Pi

• 두 프로세스 모두가 Critical section에 들어가고 싶을 경우에만 turn 변수를 따지는 구조
• 세 가지 요구사항을 모두 만족하지만, Busy Waiting(=Spin Lock) 문제
  • CPU와 Memory를 계속 사용하면서 대기 !

Synchronization Hardware

• Interrupt는 Instruction 단위로 발생
  • Instruction 하나에 읽기와 쓰기가 가능해진다면?
  • 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우, 문제의 해결 가능

• a가 0이든 1이든 a를 읽은 후, 1로 변경
• Mutual Exclution with Test & Set

Semaphores

• 이전 방식들을 추상화시킨 방법
• Semaphore S(자원의 갯수)
  • integer variable
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능

• P 연산은 자원을 가져가는 행위
• V 연산은 자원을 반납하는 행위

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

• block과 wakeup를 다음과 같이 가정
  • block: 커널은 block을 호출한 프로세스를 suspend. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김

• Semaphore 연산은 다음과 같이 정의됨

• cf. S.value를 빼고 잠 들었기 때문에, 내가 value를 내놓았음에도 value가 0 이하라는 것은 누군가가 잠들어 있다는 의미

Busy-wait vs. Block/wakeup

• Block/wakeup overhead vs. Critical section 길이
  • Critical section의 길이가 긴 경우 Block/wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
  • 일반적으로는 Block/wakeup 방식이 더 좋음

Two types of Semaphores

• Counting semaphore
  • 도메인이 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(= mutex)
  • 0 또는 1 값만 가질 수 있음
  • 주로 Mutual Exclusion(lock/unlock)에 사용

Deadlock and Starvation

• Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

• 자원을 요구하는 순서의 변경을 통해 해결이 가능
• Starvation: indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상