• 목차
    • Connection Pool에 대한 개념과 기본적인 원리
    • Commons DBCP로 Connection Pool 이해하기

Connection Pool이란?

  • 클라이언트의 요청에 따라 각 어플리케이션의 스레드에서 데이터베이스에 접근하기 위해서는 Connection이 필요하다
  • Connection pool은 이런 Connection을 여러 개 생성해 두어 저장해 놓은 공간, 또는 이 공간의 Connection을 필요할 때 꺼내 쓰고 반환하는 기법을 만한다
스크린샷 2021-08-13 오후 9 44 34

DB에 접근하는 단계

  1. 웹 컨테이너가 실행되면서 DB에 연결된 Connection 객체들을 미리 생성하여 pool에 저장한다
  2. DB에 요청 시, pool에서 Connection 객체를 가져와 DB에 접근한다
  3. 처리가 끝나면 다시
스크린샷 2021-08-13 오후 9 44 45

Connection이 부족하면?

  • 모든 요청이 DB에 접근하고 있고 남은 Connection이 없다면, 해당 클라이언트를 대기 상태로 전환시키고 Pool에 Connection이 반환되면 대기 상태에 있는 클라이언트에게 순차적으로 제공된다

왜 사용할까?

  • 매 연결마다 Connection 객체를 생성하고 소멸시키는 비용을 줄일 수 있다
  • 미리 생성된 Connection 객체를 사용하기 때문에, DB 접근 시간이 단축된다
  • DB에 접근하는 Connection 수를 제한하여, 메모리와 DB에 걸리는 부하를 조정할 수 있다

Commons DBCP로 Connection Pool 이해하기

Commons DBCP 속성 설정

  • Commons DBCP의 속성은 BasicDataSource 클래스의 setter 메서드로 설정할 수 있다

  • Spring 프레임 워크를 사용한다면 다음과 같이 bean 설정으로 속성을 등록한다

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    <bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource"  
    destroy-method="close"
    p:driverClassName="${db.driverClassName }"
    p:url="${db.url}"
    p:username="${db.username}"
    p:password="${db.password}"
    p:maxActive="${db.maxActive}"
    p:maxIdle="${db.maxIdle}"
    p:maxWait="${db.maxWait}"
    />

커넥션의 개수

커넥션 풀의 저장 구조

  • 커넥션 생성은 Commons DBCP에서 이루어진다
  • Commons DBCP는 PoolableConnection 타입의 커넥션을 생성하고 생성한 커넥션에 ConnectionEventListener를 등록한다
  • ConnectionEventListener에는 애플리케이션이 사용한 커넥션을 풀로 반환하기 위해 JDBC 트라이버가 호출할 수 있는 콜백 메서드가 있다
  • 생선된 커넥션은 commons-pool의 addObject() 메서드로 커넥션 풀에 추가된다
  • commons-pool은 내부적으로 현재 시간을 담고 있는 타임 스탬프와 추가된 커넥션의 레퍼런스를 한 쌍으로하는 ObjectTimestampPari라는 자료구조를생헝한다
  • 이들을 LIFO(last in first out) 형태의 CursorableLinkedList로 관리한다
스크린샷 2021-08-13 오후 9 58 31

커넥션 개수 관련 속성

속성 이름 설명
initialSize BasicDataSource 클래스 생성 후 최초로 getConnection() 메서드를 호출할 때 커넥션 풀에 채워 넣을 커넥션 수
maxActive 동시에 사용할 수 있는 최대 커넥션 개수 (기본값: 8)
maxIdle 커넥션 풀에 반납할 때 최대로 유지될 수 있는 커넥션 개수 (기본값: 8)
minIdle 최소한으로 유지할 커넥션 개수 (기본값: 0)
  • 8개의 커넥션을 최대로 활용할 수 있고 4개는 사용중이고 4개는 대기 중인 상태

    스크린샷 2021-08-13 오후 11 06 15
  • 커넥션 개수와 관련된 가장 중요한 성능 요소는 일반적을 커넥션의 최대 개수이다

  • maxActive 값은 DBMS의 설정과 애플리케이션 서버의 개수, Apache, Tomcat에서 동시에 처리할 수 있는 사용자 수 등을 고려해서 설정해야 한다.

  • DBMS가 수용할 수 잇는 커넥션 개수를 확인한 후에 어플리케이션 서버 인스턴스 1개가 사용하기에 적절한 개수를 설정한다

  • 사용자가 몰려서 커넥션을 많이 사용할 때는 maxActive 값이 충분히 크지 않다면 병목 지점이 될 수 있다

  • 반대로 사용자가 적어서 사용자가 적어서 상요 중인 커넥션이 많지 않은 시스템에서는 maxActive 값을 지나치게 작게 설정하지 않는 한 성능에 영향이 없다

커넥션을 얻기 전 대기 시간

  • BasicDataSource 클래스의 maxWait 속성은 커넥션 풀 안의 커넥션이 고갈됐을 때 커넥션 반납을 대기하는 시간이며 기본값은 무한정이다
  • 사용자가 갑자기 급증하거나 DBMS에 장애가 발생했을 때 장애를 더욱 크게 확산시킬 수 있어 주의해야 한다.
  • 적절한 maxWait 값을 설정하려면 TPS(transaction per seconds)와 Tomcat에서 처리 가능한 스레드 개수 등을 이해해야 한다

TPS(transaction per seconds)

  • maxActive = 5과 maxIdle = 5, minIdle = 5로 설정한 상황을 가정한다
  • 요청 하나당 쿼리 10개를 실행한다고 가정한다
  • 각 쿼리의 평균 실행 시간은 50밀리초라고 하면 전체 10개 쿼리의 실행 시간은 500밀리초 이다.
  • 요청에 대한 초종 응답 시간은 500밀리초라고 생각할 수 있다.
스크린샷 2021-08-13 오후 11 36 50
  • 커넥션 풀에 이용 가능한 유휴 상태의 커넥션이 5개일 때는 동시에 5개의 요청을 500밀리초 동안 처리한다
  • 따라서 1초 동안에는 10개의 요청을 처리할 수 있고 성능 지수는 10TPS라고 볼 수 있다
스크린샷 2021-08-13 오후 11 39 35

TPS와 커넥션 개수와의 관계

  • 처리할 요청 수가 증가해도 커넥션 풀의 커넥션 개수가 5개이면 10TPS 이상의 성능을 낼 수 없다
  • 1번부터 5번까지 요청이 실행되는 동안은 커넥션 풀에 여분의 커넥션이 없다
  • 6번부터 10번까지 요청은 대기(wait)상태가 되 여분의 커넥션이 생길 때까지 maxWait 값만큼 기다린다
스크린샷 2021-08-13 오후 11 39 41
  • 이를 해결하는 가장 수운 방법은 maxActive 값을 높여서 커넥션 풀의 개수를 늘리는 것이다
스크린샷 2021-08-13 오후 11 42 44
  • 커넥션의 개수를 5에서 10으로 늘리면 전체적인 성능도 10TPS로 증가한다
  • 하지만 일반적을 DBMS의 리소스는 다른 서비스와 공유해 사용하는 경우가 많기 때문에 무조건 커넥션 개수를 크게 설정할 수 없다
  • 따라서 예상 접속자 수와 서비스의 실제 부하를 측정해 최적의 값을 설정하는 것이 중요하다
  • 대기 시간 (wait) 값 조절이 커넥션의 개수를 무한히 늘리지 않고 최적의 시스템을 환겨을 구축하는데 중요한 역할을 한다
  • maxWait 값을 어떻게 설정했는지가 일시적인 과부하 상태에서 드러나는 시스템의 전체적인 견고함을 결정짓는다
스크린샷 2021-08-13 오후 11 47 36
  • 적당한 maxWait 값은 Commons DBCP 외에 Tomcat의 동작 방식도 고려해야 한다
  • Tomcat은 스레드 기반으로 동작해 사용자의 요청을 처리한다
  • Tomcateh 내부에 스레드 풀을 가지고 잇어서 사용자의 요청이 들어올 때마다 스레드 풀에서 하나씩 스레드를 꺼내 요청을 처리한다
  • 1 ~ 5번의 요청이 처리되기 전에 또 다른 요청이 들어온다
  • 즉 동시에 6개의 요청이 들어왔을 때 6번 요청은 여분의 커넥션이 없으므로 maxWait 값 만큼 기다린다 (Tomcat의 스레드가 기다리는 주체이다)

적절한 maxWait 값은?

  • 위의 그림에서 maxWait 속성에 설정한 시간이 10,000 밀리초이면 처리량을 넘어서는 요청의 스레드는 10초 동안 대기 상태에 있게 된다
  • 그리고 사용자의 요청이 계속 증가하면 결국 Tomcat 스레드 풀의 모든 스레드가 소진돼 Tomcat은 아래와 같은 오류를 출력하며 응답을 멈출 것이다
    1
    심각: All threads (512) are currently busy, waiting. Increase maxThreads (512) or check the servlet status
  • 10초 동안의 대기 상태가 해제되고 커넥션을 획득해 사용자의 요청을 열심히 처리하고 응답을 보내도 그 응답을 받을 사용자는 이미 떠나고 난 뒤인 경우도 있다
  • 이럴 경우 사용자가 인내할 수 있는 시간을 넘어서는 maxWait 값은 아무런 의미가 없다
  • 반대의 경우에는 커넥션 풀에 여분이 없을 때마다 오류가 반환된다
  • maxWait 값도 사용자의 대기 가능한 시간 같은, 어플리케이션의 특성 및 자원의 상황을 고려해야한다
  • 만약 갑작스럽게 사용자가 증가해 maxWait 값 안에 커넥션을 얻지 못하는 빈도가 늘어난다면 maxWait을 줄여서 스레드가 한도에 도달하지 않도록 한다
  • 전체 시스템의 장애는 피하고 ‘간헐적 오류’가 발생하는 정도로 장애의 영향을 줄인다
  • 이런 상황이 자주 있다면 Commons DBCP의 maxActive 값과 Tomcat의 maxThread 값을 동시에 늘이는 것을 고려한다
  • 그러나 시스템 자원의 한도를 넘어선다면 시스템을 확충해야한다

커넥션의 검사와 정리

  • 유효성 검사 쿼리 (validation query)와 Evictor 스레드 관련 설정으로도 애플리케이션의 안정성을 높일 수 있다

유효성 검사쿼리의 설정

  • JDBC 커넥션의 유효성에 대한 validationQuery 옵션
    • testOnBorrow: 커넥션 풀에서 커넥션을 얻어올 때 테스트 실행(기본값: true)
    • testOnReturn: 커넥션 풀로 커넥션을 반환할 때 테스트 실행(기본값: false)
    • testWhileIdle: Evictor 스레드가 실행될 때 (timeBetwwenEvictionRunMills > 0) 커넥션 풀 안에 있는 유휴 상태의 커넥션을 대상으로 테스트 실행 (기본값: false)
  • 검증에 지나치게 자원을 소모하지 않게 testOnBorrow와 testOnReturn 옵션을 false로 설정한다
  • 오랫동안 대기상태였던 커넥션이 끊어지는 현상을 막기위해 testWhileIdle 옵션은 true로 설정한다
  • 부적절한 상태의 커넥션이 반납되었을 때 testWhileIdle = true이면 커넥션 풀에서 오류가 발생하는 커넥션을 제외할 수 있다

Evictor 스레드와 관련된 속성

  • Evictor 스레드는 Commons DBCP 내부에서 커넥션의 자원을 정리하는 구성요소이며 별도의 스레드로 실행된다

  • 관련 속성

    • timeBetweenEvictionRunsMills: Evictor 스레드가 동작하는 간격, 기본값은 -1이며 Evictor 스레드의 실행이 비활성화되어있다
    • numTestsPerEvictionRun: Evictor 스레드 동작 시 한 번에 검사할 커넥션 수
    • minEvictableIdleTimeMillis: 스레드 동작 시 커넥션의 유휴 시간을 확인해 설정 값 이상일 경우 커넥션을 제거한다 (기본값: 30분)
  • 역할

    1. 커넥션 풀 내의 유휴 상태의 커넥션 중에서 오랫동안 사용되지 않은 커넥션을 추출해 제거한다

      • Evictor 스레드 실행 시 설정된 numTestsPerEvictionRun 속서값만큼 CursorableLinkedList의 ObjectTimestampPar을 확인한다
      • ObjectTimestampPair의 타임 스탬프 값과 현재 시간의 타임 스탬프 값의 차이가 minEvictableIdleTimeMillis 속성을 초과하면 해당 커넥션을 제거한다
      • 커넥션 숫자를 적극적으로 줄여야한다면 사용하지 않기
    2. 커넥션에 대해서 추가로 유효성 검사를 수행해 문제가 있을 경우 해당 커넥션을 제거한다

      • testWhileIdle = true 일때만 이 동작을 수행한다
      • 첫 번째 작업 시 minEvictableIdleTimeMillis 속성값을 초과하지 않은 커넥션에 대해서 추가로 유효성 검사를 수행하는 것이다.
    3. 앞의 두 작업 이후 남아있는 커넥션의 개수가 minIdle 속성값보다 작으면 minIdle 속성값 만큼 커넥션을 생성해 유지한다

      testWhileIdle=true && timeBetweenEvictionRunMillis > 0이면 위의 3가지 역할을 다 수행하고,

      testWhileIdle=false && timeBetweenEvictionRunMillis > 0이면 두 번째 동작은 수행하지 않는다.

  • 주의점

    • Evictor 스레드는 동작 시에 커넥션 풀에 잠금(lock)을 걸고 동작하기 때문에 너무 자주 실행하면 서비스 실행에 부담을 줄 수 있다
    • numTestsPerEvictionRun 값을 너무 크게 설정하면 Evictor 스레드가 검사해야하는 커넥션 수가 많아져 잠금 상태에 있는 시간이 길어지므로 실행에 부담이 된다.
  • 유용한 방안

    • IDC(internet data center) 정책에 따라서는 서버 간의 소켓 연결 후 정해진 시간 이상 아무런 패킷도 주고받지 않으면 연결을 종료한다
    • timeBetweenEvictionRunsMills 속성으로 의도하지 않게 연결이 끊어지는 것을 방어할 수 있다.
    • ex) 30분 동안 통신이 없을 때 연결이 끊어지는 정책으로 네트워크를 운영한다면, BasicDataSource가 풀링(pooling)하는 커넥션의 수가 30개라고 가정할 때
      • 30분 안에 모든 커넥션에 유효성 검사 쿼리를 한 번씩은 실행하는 것이 바람직하다.
      • Evictor 스레드가 5분에 한 번씩 실행되도록 설정했을 때 30분 동안 Evictor 스레드 실행 횟수는 6번이므로 매번 5개의 커넥션을 검사해야 전체 커넥션을 테스트할 수 있다.
      • 30분 안에 5분마다 Evctor 스레드가 실행되면 6번 실행되지만 오차를 감안해 5번으로 가정하면 이때 설정해야 할 numTestsPerEvictionRun 값은 다음과 같이 구할 수 있다
      • 6 * numTestsPerEvictionRun > 30개
      • 따라서 numTestsPerEvictionRun 속성값은 최소 6 이상이어야 한다. 일반적인 공식으로 정리하면 다음과 같다
      • ('IDC 정책에서 허용하는 최대 유휴 커넥션 유지 시간' / timeBetweenEvictionRunsMillis 속성값) * numTestsPerEvictionRun 속성값) > 전체 커넥션 개수

reference

읽어보면 좋은 것들

Comment and share

  • our goals
    • understand principles behind transport layer services
      • multiplexing, demultiplexing
      • reliable data transfer
      • flow control
      • congestion control
    • learn about Internet transport layer protocols
      • UDP: connectionless transport
      • TCP: connection-oriented reliable transport
      • TCP congestion control

Transport services and protocols

  • provide logical communication between app processes on different hosts
  • transport protocols run in end systems
    • send side: breaks app messages into segments, passes to entwork layer
    • receive side: reassembles segments into messages, passes to app layer
  • more than one transport protocol abailable to apps
    • Internet: TCP and UDP
스크린샷 2021-08-10 오후 4 24 35

Transport vs network layer

  • network layer: logical communication between hosts
  • transport layer : logical communication between processes
    • relies on, enhances, network layer services

Internet transport-layer protocols

  • reliable, in-order delivery (TCP)
    • congestion control
    • flow control
    • connection setup
  • unreliable, unordered delivery (UDP)
    • no-frills extension of “best-effort” IP
  • service not available
    • delay guarantees
    • bandwidth guarantees

Multiplexing/demultiplexing

스크린샷 2021-08-10 오후 4 35 55

How demultiplexing works

  • host receives IP datagrams
    • each datagram has source IP address, destination IP address
    • each datagram carries one transport-layer segment
    • each segment has source, destination port number
  • host uses IP address & port numberes to direct segment to appropriate socket

Connectionless demultiplexing

  • recall: created socket has host-local port #:

    • DatagramSoket mySocket1 = new DatagramSocket(12534)
  • recall: when creating datagram to send into UDP socket, must specify

    • destination IP address
    • destination port #
  • when host receives UDP segment

    • checks destination port # in segment

    • directs UDP segment to secket with that port #

      IP datagrams with same dest. post #, but different source IP addesses and/or source port numbers will be directed to same socket at dest

Connectionless demux: example

스크린샷 2021-08-10 오후 4 54 33

Connection-oriented demux

  • TCP socket identified by 4-tuple
    • source IP address
    • source port number
    • dest IP address
    • dest port number
  • demux
    • receiver uses all four values to direct segment to appropriate socket
  • server host may support many simutaneous TCP sockets
    • each socket identified by its own 4-tuple
  • web servers have different sockets for each connecting client
    • non-persistent HTTP will have different socket for each request

Connection-oriented demux: example

스크린샷 2021-08-10 오후 5 01 17
스크린샷 2021-08-10 오후 5 01 34

UDP: User Datagram Protocol

  • “no frills”, “bare bones” Internet transport protocol
  • “best effort” service, UDP segments may be
    • lost
    • delivered out-of-order to app
  • connectionless
    • no handshaking between UDP sender, receiver
    • each UDP segment handled independently of others
  • UDP use:
    • streaming multimedia apps (loss tolerant, rate sensitive)
    • DNS
    • SNMP
  • reliable transfer over UDP
    • add reliability at application layer
    • application-specific error recovery

UDP: segment header

스크린샷 2021-08-10 오후 5 13 04

UDP checksum

  • Goal: detect “errors” in transmitted segment
  • sender
    • treat segment contents, including header fields, as sequence of 16-bit integers
    • checksum: additon (one’s complement sum) of segment contents
    • sender puts checksum value into UDP checksum field
  • receiver:
    • compute checksum of received segment
    • check if computed checksum equals checksum field value
      • No - error detected
      • YES - no error detected. But maybe errors nonetheless?

Internet checksum: example

스크린샷 2021-08-10 오후 5 21 30

carry된 비트를 더해주고 1의 보수를 취하면 checksum

TCP

  • point-to-point
    • one sender, one receiver
  • reliable, in-order byte stream
    • no “messge boundaries”
  • pipelined
    • TCP congestion and flow control set window size
  • full duplex data
    • bi-directional data flow in same connection
    • MSS: maximum segment size
  • connection-oriented
    • handshaking (exchange of control msgs) inits sender, receiver state before data exchange
  • flow controlled
    • sender will not overwhelm receiver

TCP segment structure

스크린샷 2021-08-10 오후 7 19 58

TCP seq. numbers, ACKs

  • sequnce number
    • byte stream “number” of first byte in segment’s data
  • acknowledgements
    • seq # of next byte expected from other side
    • cumulative ACK
    • Q: how receiver handles out-of-order segments
      • A: TCP spec doesn’t say, up to implementor
스크린샷 2021-08-10 오후 7 27 34
스크린샷 2021-08-10 오후 7 28 49

TCP round trip time, timeout

  • Q: how to set TCP timeout value?
    • longer than RTT
      • but RTT varies
    • too short: premature timeout, unneceessary retransmissions
    • too long: slow reaction to segment loss
  • Q: how to estimate RTT
    • SampleRTT: measured time from segment transmission until ACK receipt
      • ignore retransmissions
    • SampleRTT will vary, want estimated RTT “smoother”
      • average several recent measurements, not just current SamplRTT
스크린샷 2021-08-10 오후 7 35 40
스크린샷 2021-08-10 오후 7 36 00

TCP: reliable data transfer

  • TCP creates rdt(reliable data transfer) service on top of IP’s unreliable service
    • pipelined segments
    • cumulative acks
    • sigle retransmission timer
  • retransmissions triggered by
    • time out
    • duplicate acks
  • let’s initially consider simplified TCP sender
    • ignore duplicate acks
    • ignore flow control, congestion control

TCP sender events

  • data rcvd from app
    • create segment with seq #
    • seq # is byte-stream number of first dta byte in segment
    • start timer if not already running
      • think of timer as for oldest unacked segment
      • expiration interval : TimeOutInterval
  • timeout
    • retransmit segment that caused timeout
    • restart timer
  • ack rcvd
    • if ack acknowledges previously unacked segemtns
      • update what is known to be ACKed
      • start timer if there are still unacked segments
스크린샷 2021-08-11 오후 8 13 14

NextSeqNum은 보내야하는 Seq 번호, SendBase는 보냈지만 ACK 받지 않은 Seq 번호

TCP: retransmission scenarios

스크린샷 2021-08-11 오후 8 17 16
스크린샷 2021-08-11 오후 8 19 12

TCP ACK generation

스크린샷 2021-08-11 오후 8 42 40

TCP fast retransmit

  • time-out period often relatively long
    • long delay before resending lost packet
  • detection lost segments via duplicate ACKs
    • sender often sends many segments back-to-back
    • if segment is lost, there will likely be many duplicate ACKs
  • TCP fast retransmit
    • if sender receives 3 ACKs for same data (“triple duplicate ACKs), resend unacked
      • likely that unacked segment lost, so don’t wait for timeout
스크린샷 2021-08-11 오후 8 49 24

TCP: flow control

스크린샷 2021-08-11 오후 8 52 26
  • receiver “advertises” free buffer space by including rwnd value in TCP header of receiver-to-sender segments
    • RcvBuffer size set via socket options (typical default is 4096 bytes)
    • many operating systems autoadjust RcvBuffer
  • sender limits amount of unacked (“in-flight”) data to receiver’s rwnd value
  • guarantees receive buffer will not overflow
스크린샷 2021-08-11 오후 8 58 14

TCP: connection management

  • before exchanging data, sender/receiver “handshake”
    • agree to establish connection (each knowing the other willing to establish connection)
    • agree on onnection parameters
스크린샷 2021-08-11 오후 9 02 50

Agreeing to establish a connection

  • Q: will 2-way handshake always work in network?
    • variable delays
    • retransmitted messages (e.g. req_conn(x)) due to message loss
    • message reordering
    • can’t “see” other side
스크린샷 2021-08-11 오후 9 05 37

2-way handshake failure scenarios

스크린샷 2021-08-11 오후 9 08 34

TCP 3-way handshake

스크린샷 2021-08-11 오후 9 14 04
스크린샷 2021-08-11 오후 9 15 40

TCP: closing a connection

  • client, server each close ther side of connection
    • send TCP segment with FIN bit = 1
  • responsd to receved FINB with ACK
    • on receiving FIN, ACK can be combined with own FIN
  • simultaneous FIN exchanges can be handled
스크린샷 2021-08-11 오후 9 18 57

client가 마지막에 2 * max segment lifetime을 대기하는 이유는

server측에서 FIN 요청을 하고 ACK를 못 받아서 다시 FIN 요청을 보낼 경우를 대비해서 대기한다

TCP congetion control

  • congestion
    • informally: “toioi many sources sending too much data too fast for network to handle”
    • different from flow control!
    • manifestations
      • lost packets (buffer overflow at routers)
      • long delays (queueing in router buffers)

TCP congestion control: additive increase, multiplicative decrease

  • approach: sender increases transmission rate (window size), probing for usable bandwidth, until loss occurs
    • additive increase: increase cwnd by 1 MSS every RTT until loss detected
    • multiplicative decrease: cut cwnd in half after loss
스크린샷 2021-08-11 오후 11 59 18

TCP Congestion Control: details

스크린샷 2021-08-12 오전 12 06 26
  • sender limits transmission
    • LastByteSent - LastByteAcked <= min(cwnd, rwnd)
  • cwnd is dynamic, function of perceived network congestion
  • TCP sending rate
    • roughly: send cwnd bytes, wait RTT for ACKS, then send more bytes
    • rate = cwnd / RTT (bytes/sec)

TCP Slow Start

  • when connection begins, increase rate exponentially until first loss event
    • initially cwnd = 1 MSS
    • double cwnd every RTT
    • done by incrementing cwnd for every ACK received
  • summary: initial rate is slow but ramps up exponentially fast
스크린샷 2021-08-12 오전 12 10 14

TCP: detecting, reacting to loss

  • loss indicated by timeout
    • cwnd set to 1 MSS
    • window then grows exponetially (as in slow start)
  • loss indicated by 3 duplicate ACKs: TCP RENO
    • dup ACKs indicate network capable of delivering som segments
    • cwnd is cut in half window then grows linearly
  • TCP Tahoe always set cwnd to 1 (timeout or 3 duplicate acks)

TCP: switching from slow start to CA

  • Q: when should the exponential increase switch to linear?
  • A: when cwnd gets to 1/2 of its value before timeout
  • Implementation
    • variable ssthresh
    • on loss event, ssthresh is set to 1/2 of cwnd just before loss event

TCP throughput

  • avg. TCP throughput as function of window size, RTT?
    • ignore slow start, assuum always data to send
  • W: window size (measured in bytes) where loss occurs
    • avg. window size (# in-flight bytes) is 3/4 W
    • avg. throughput is 3/4W per RTT
스크린샷 2021-08-12 오전 12 24 56

TCP Fairness

  • fairness goal
    • if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/K
스크린샷 2021-08-12 오전 12 29 34

Why is TCP fair?

  • two competing sessions
    • additive increase gives slope of 1, as throughout inscreases
    • multiplicative decrease decreases throughput proportionally
스크린샷 2021-08-12 오전 12 29 41

참조

  • 컴퓨터 네트워크 이미정 교수님 강의
  • Computer Networking: A Top-Down Approach Featuring the Internet

Comment and share

Socket programming

  • goal: learn how to build client/server applications that communicate using sockets
  • socket: door between application process and end-end-transport protocol
스크린샷 2021-08-10 오후 1 56 42
  • Two socket types for two transport services
    • UDP : unreliable datagram
    • TCP : reliable, byte stream-oriented
  • Application Example
    1. client reads a line of characters (data) from its keyboard and sends data to server
    2. server receives the data and converts characters to uppercase
    3. server send modified data to client
    4. client receives modified data and displays line on its screen

Socket programming with UDP

  • UDP: no “connection” between client & server
    • no handshaking before sending data
    • sender explicitly attaches IP destination address and port $ to each packet
    • receiver extracts sender IP address and port # from received packet
  • UDP : transmitted data may be lost or received out-of-order
  • Application viewpoint
    • UDP provides unreliable transfer of groups of bytes (“datagrams”) between client and server

Client/server socket interaction: UDP

스크린샷 2021-08-10 오후 2 07 36

Example app: UDP client

스크린샷 2021-08-10 오후 2 09 01

Example app: UDP server

스크린샷 2021-08-10 오후 2 10 30

Socket programming with TCP

  • client must contact server
    • server process must first be running
    • server must have created socket(door) that welcomes client’s contact
  • client contacts server by
    • Creating TCP socket, specifying IP address, port, number of server process
    • when client creates socket
      • client TCP establishes connection to server TCP
    • when contacted by client, server TCP creates new socket for server process to communicate with that particular client
      • allows server to talk with multiple clients
      • source port numbers userd to distinguish clients
  • application viewpoint
    • TCP provides reliable, in-order byte-stream transfer (“pipe”) between cient and server

Client/server socket interaction: TCP

스크린샷 2021-08-10 오후 2 21 11

Example app: TCP client

스크린샷 2021-08-10 오후 2 23 25

Example app: TCP server

스크린샷 2021-08-10 오후 2 26 56

연결을 담당하는 serverSocket 1개와 각 연결이 완료되면 요청마다 처리를 담당하는 connectionSocket이 생성된다

참조

  • 컴퓨터 네트워크 이미정 교수님 강의
  • Computer Networking: A Top-Down Approach Featuring the Internet

Comment and share

Web and HTTP

  • web page consists of objects

  • object can be HTML file, JPEG image, Java applet, audio file, …

  • web page consists of base HTML-file which includes several referenced objects

  • each object is addressable by a URL, e.g.,

    스크린샷 2021-08-04 오후 5 08 42

HTTP overview

HTTP: hypertext transfer protocol

  • Web’s application layer protocol
  • client/server model
    • client: browser that requests, revceives, (using HTTP protocol) and displays Web objects
    • server: Web server sends (using HTTP protocol) objects in response to requests
스크린샷 2021-08-04 오후 5 11 59
  • uses TCP
    1. client initiates TCP connection(creates socket) to server, port 80
    2. server accepts TCP connection from client
    3. HTTP messages (application-layer protocol messages) exchanged between browser (HTTP client) and Web server (HTTP server)
    4. TCP connection closed
  • HTTP is “stateless”
    • server maintains no information about past client requests
    • aside : protocols that maintain "state" are complex!
      • past history (state) must be maintained
      • if server/client crashes, their views of “state” may be inconsistent, must be reconciled

HTTP connections

  • non-persistent HTTP
    • at most one object sent over TCP connection
      • connection then closed
    • downloading multiple obejcts requires multiple connections
  • persistent HTTP
    • multiple objects can be sent over single TCP connection between client, server

Non-persistent HTTP

suppose user enters URL:

www.someSchool.edu/someDepartment/home.index

스크린샷 2021-08-04 오후 6 39 30 스크린샷 2021-08-04 오후 6 39 52

Non-persistent HTTP: response time

  • RTT (definition): time for a small packet to travel from client to server and back
  • HTTP response time
    • one RTT to initiate TCP connection
    • one RTT for HTTP request and first few bytes of HTTP response to return
    • file transmission time
    • non-persistent HTTP response time = 2RTT + file transmission time
스크린샷 2021-08-04 오후 6 45 50

Persistent HTTP

  • non-persistent HTTP issues
    • requires 2 RTTs per object
    • browsers often open parallel TCP connections to fetch referenced objects
    • OS overhead for each TCP connection (each tcp buffer, socket)
  • persistent HTTP
    • server leaves connection open after sending response
    • subsequent HTTP messages between same client/server sent over open connection
    • client sends request as soon as it encounters a referenced object
    • as little as one RTT for all the referenced objects

HTTP request message

  • two types of HTTP messages: request, response
  • HTTP request message
    • ASCII (human-readable format)
스크린샷 2021-08-04 오후 6 57 53

Keep-Alive Header is persistent HTTP configure

general format

스크린샷 2021-08-04 오후 7 00 07

Uploading form input

Method types

  • HTTP/1.0
    • GET
    • POST
    • HEAD
      • asks server to leave requested object out of response
  • HTTP/1.1
    • GET, POST, HEAD
    • PUT
      • uploads file in entity body to path specified in URL field
    • DELETE
      • deletes file specified in the URL field

HTTP response message

스크린샷 2021-08-04 오후 7 07 22

HTTP response status codes

  • status code appears in 1st line in server to client response message
  • some sample codes
    • 200 OK
      • request succeeded, requested object later in this msg
    • 301 Moved Permanently
      • request object moved, new location specified later in this msg (Location Header)
    • 400 Bad Request
      • request msg not understood by server
    • 404 Not Found
      • requested document not found on this server
    • 505 HTTP Version Not Supported

User-server state: cookies

  • many Web sites use cookies four components
    1. cookie header line of HTTP response message
    2. cookie header line in next HTTP request message
    3. cookie file kept on user’s host, managed by user’s browser
    4. back-end database at Web site
  • example
    • Susan always access Internet from PC
    • visits specific e-commerce site for first time
    • when initial HTTP requests arrives at site, site creates
      • unique ID
      • entry in backend database for ID
스크린샷 2021-08-04 오후 4 19 27
  • what cookies can be used for
    • authorization
    • shopping carts
    • recommendations
    • user session state (Web e-mail)
  • how to keep “state”
    • protocol endpoint: maintain stat at sender/receiver over multiple transactions
    • cookies: http messages carry state
  • aside : cookies and privacy
    • cookies permit sites to learn a lot about you
    • you may supply name and e-amil to sites

Web caches (proxy server)

  • goal: satisfy client request with out involving origin server
  • user sets browser: Web access via cache
  • browser sends all HTTP requests to cache
    • object in cache: cache returns object
  • else cache requets object from origin server, then returns object to client
스크린샷 2021-08-04 오후 7 28 32
  • cache acts as both client and server
    • server for original requesting client
    • client to origin server
  • typically cache is installed by ISP (university, company, residential ISP)
  • why Web cacing?
    • reduce response time for cient request
    • reduce traffic on an institution’s access link
    • Internet dense with caches: enables “poor” content providers to effectively deliver content (so Too does P2P file sharing)

Conditional GET

  • Goal: don’t send object if cache has up-to-date cached version
    • reduce delay
    • lower link utilization
  • cache: specify date of cached copy in HTTP request
    • If-modified-since: date
  • server response contatins no object if cached copy is up-to-date
    • HTTP/1.0 304 Not Modified
스크린샷 2021-08-04 오후 7 37 57

참조

  • 컴퓨터 네트워크 이미정 교수님 강의
  • Computer Networking: A Top-Down Approach Featuring the Internet

Comment and share

Application architectures

  • possible structure of applications
    • client-server
    • peer-to-peer (P2P)

Client-server architecture

  • server
    • always-on host
    • permanent IP address
    • data centers for scaling
  • clients
    • communicate with server
    • do not communicate directly with each other
    • may be intermittently(on and off) connect
    • may have dynamic IP addresses

P2P architecture

  • no always-on server
  • arbitrary end systems directly communicate
  • peers request service from other peers, provide service in return to ohter peers
    • self scalability - new peers bring new service capacity, as well as new service demands
  • peers are intermittently connected and change IP address
    • complex management

Processes communicating

  • process: program running within a host

    • within same host, tow processes communicate using inter-process communication (defined by OS)
    • processes in different hosts communicate by exchanging messages
  • clients, servers

    • client process: process that initiates communication

    • server process: process that waits to be contacted

      aside: applications with P2P architectures have client processes & server processes

Sockets

  • process sends/receives messages to/from its socket
  • socket analogous to door
    • sending process shoves message out door
    • sending process relies on transport infrastructure on other side of door to deliver message to socket at receiving process
스크린샷 2021-08-04 오후 2 48 00

Addressing processes

  • to receive messages, process must have identifier
  • host device has unique 32-bit IP address
  • Q: does IP address of host on which process runs suffice for identifying th process?
    • A: no, many processes can be running on same host
  • identifier include both IP adderss and port numbers
  • example port numbers:
    • HTTP server: 80
    • mail server: 25
  • to send HTTP message to www.naver.com web server
    • IP address: 121.33.223.11
    • port number: 80

What transport service does an app need?

  • data integrity
    • some apps (e.g., file transfer, web transactions) require 100% reliable data transfer
    • other apps (e.g., audio) can tolerate some loss
  • timing
    • some apps (e.g., Internet telephony, interactive games) require lo delay to be “effective”
  • throughput
    • some apps (e.g., multimedia) require minimum amount of throughtput to be “effective”
    • other apps (“elastic apps”) make use of whatever throughtput they get

Transport service requirements: common apps

스크린샷 2021-08-04 오후 3 21 17

Internet transport protocols services

  • TCP service
    • reliable transport between sending and receiving process
    • flow control: sender won’t overwhelm receiver
    • connection-oriented: setup required between client and server processes
    • congestion control: throttle sender when network overloaded
    • does not provide: timing, minimum throughput guarantee, security
  • UDP service
    • unreliable data transfer between sending and reveiving process
    • does not provide: reliability, flow control, congestiong control, timing, throughput guarantee, security, or connection setup

      Internet apps: application, transport protocols

스크린샷 2021-08-04 오후 3 33 28

Application layer protocol defines

  • types of messages exchanged
    • e.g., request, response
  • message syntax
    • what fields in messages & how fields are delineated
  • message semantics
    • meaning of information in fields
  • rules for when and how processes send & responsd to messages

참조

  • 컴퓨터 네트워크 이미정 교수님 강의
  • Computer Networking: A Top-Down Approach Featuring the Internet

Comment and share

Disk Structure

  • logical block
    • 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
    • 주소를 가진 1차원 배열처럼 취급
    • 정보를 전송하는 최소 단위
  • Sector
    • Logical block이 물리적인 디스크에 매핑된 위치
    • Sector 0은 최외각 실린더의 첫 트랙에 있는 첫 번째 섹터이다

Disk Scheduling

  • Access time의 구성
    • Seek time
      • 헤드를 해당 실린더로 움직이는데 걸리는 시간
    • Rotational latency
      • 헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간
    • Transfer time
      • 실제 데이터의 전송 시간
  • Disk bandwidth
    • 단위 시간 당 전송된 바이트의 수
  • Disk Scheduling
    • seek time을 최소화하는 것이 목표
    • Seek time := seek distance
스크린샷 2021-08-03 오후 2 01 34

Disk Management

  • physical formatting (Low-level formatting)
    • 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
    • 각 섹터는 header + 실제 data(보통 512 bytes) + trailer로 구성
    • header와 trailer는 sector number, ECC (Error-Correcting Code) 등의 정보가 저장되며 controller가 직접 접근 및 운영
  • Partitioning
    • 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
    • OS는 이것을 독립적 disk로 취급 (logical disk)
  • Logical formatting
    • 파일 시스템을 만드는 것
    • FAT, inode, free space 등의 구조 포함
  • Booting
    • ROM에 있는 “small bootstrap loader”의 실행
    • sector 0 (boot block)을 load하여 실행
    • sector 0은 “full Bootstrap loader program”
    • OS를 디스크에서 load하여 실행

Disk Scheduling Algorithm

  • 큐에 다음과 같은 실린더 위치의 요청이 존재하는 경우 디스크 헤드 53번에서 시작한 각 알고리즘의 수행 결과는? (실린더 위치는 0-199)

    • 98, 183, 37, 122, 14, 124, 65, 67
  • FCFS

  • SSTF

  • SCAN

  • C-SCAN

  • N-SCAN

  • LOOK

  • C-LOOK

FCFS (First Come First Service)

스크린샷 2021-08-03 오후 2 17 35

SSTF (Shortest Seek Time First)

스크린샷 2021-08-03 오후 2 19 20

SCAN

  • disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리한다
  • 다른 한쪽 끝에 도달하면 역방향으로 이동하며 오는 길목에 있는 모든 요청을 처리하며 다시 반대쪽 끝으로 이동한다
  • 문제점: 실린더 위치에 따라 대기시간이 다르다 (중앙에 위치한 것이 2배 더 많이 실행된다)
스크린샷 2021-08-03 오후 2 22 43

C-SCAN

  • 헤드가 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리
  • 다른쪽 긑에 도달했으면 요청을 처리하지 않고 곧바로 출발점으로 다시 이동
  • SCAN보다 균일한 대기 시간을 제공한다
스크린샷 2021-08-03 오후 2 26 31

Other Algorithms

  • N-SCAN
    • SCAN의 변형 알고리즘
    • 일단 arm이 한 방향으로 움직이기 시작하면 그 시점 이후에 도착한 job은 되돌아올 때 service
  • LOOK and C-LOOK
    • SCAN이나 C-SCAN은 헤드가 디스크 끝에서 끝으로 이동
    • LOOK과 C-LOOK은 헤드가 진행 중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동한다

C-LOOK

스크린샷 2021-08-03 오후 2 30 03

Disk-Scheduling Algorithm의 결정

  • SCAN, C-SCAN 및 그 응용 알고리즘은 LOOK, C-LOOK 등이 일반적으로 디스크 입출력이 많은 시스템에서 효율적인 것으로 알려져 있음
  • File의 할당 방법에 따라 디스크 요청이 영향을 받음
  • 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 OS와 별도의 모듈로 작성되는 것이 바람직하다

Swap-Space Management

  • Disk를 사용하는 두 가지 이유
    • memory의 volatile한 특성 -> file system
    • 프로그램 실행을 위한 memory 공간 부족 -> swap space (swap area)
  • Swap-space
    • Virtual memory system에서는 디스크를 memory의 연장 공간으로 사용
    • 파일 시스템 내부에 둘 수도 있으나 별도 patition 사용이 일반적
      • 공간 효율성보다는 속도 효율성이 우선
      • 일반 파일보다 휠씬 짧은 시간만 존재하고 자주 참조됨
      • 따라서, block의 크기 및 저장 방식이 일반 파일시스템과 다름
스크린샷 2021-08-03 오후 2 49 13

RAID

  • RAID (Redundant Array of Independent Disks)
    • 여러 개의 디스크를 묶어서 사용
  • RAID의 사용 목적
    • 디스크 처리 속도 향상
      • 여러 디스크에 block의 내용을 분산 저장
      • 병렬적으로 읽어 옴 (interleaving, striping)
    • 신뢰성(reliability) 향상
      • 동일 정보를 여러 디스크에 중복 저장
      • 하나의 디스크가 고장시 다른 디스크에서 읽어옴 (Mirroring, shadowing)
      • 단순히 중복 저장이 아니라 일부 디스크에 parity를 저장하여 공간의 효율성을 높일 수 있다
스크린샷 2021-08-03 오후 2 53 00

Comment and share

File and File System

  • File
    • “A named collection of related information”
    • 일반적으로 비휘발성의 보조 기억 장치에 저장
    • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해 줌
    • Operation
      • create, read, write, reposition (lseek), delete, open, close 등
  • File attribute (혹은 파일 metadata)
    • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들
      • 파일 이름, 유형, 저장된 위치, 파일 사이즈
      • 접근 권한 (읽기/쓰기/실행), 시간 (생성/변경/사용), 소유자 등
  • File system
    • 운영체제에서 파일을 관리하는 부분
    • 파일 및 파일의 메타 데이터, 디렉토리 정보 등을 관리
    • 파일의 저장 방법 결정
    • 파일 보호 등

open()

스크린샷 2021-07-30 오후 5 07 37
  • open(“/a/b/c)

    • 디스크로부터 파일 c의 메타 데이터를 메모리로 가지고 옴

    • 이를 위하여 directory path를 search

      • 루트 디렉토리 “/“를 open하고 그 안에서 파일 “a”의 위치 획득
      • 파일 “a”를 open한 후 read하여 그 안에서 파일 “b”의 위치 획득
      • 파일 “b”를 open한 후 read하여 그 안에서 파일 “c”의 위치 획득
      • 파일 “c”를 open한다
    • Directory path의 search에 너무 많은 시간 소요

      • Open을 read/write와 별도로 두는 이유임
      • 한 번 open한 파일은 read/ write 시 directory search 불필요
    • Open file table

      • 현재 open된 파일들의 메타데이터 보관소 (in memory)
      • 디스크의 메타데이터보다 몇 가지 정보가 추가
        • Open한 프로세스 수
        • 한 번 open한 파일은 read/ write 시 directory search 불필요
    • File descriptor (file handle, file control block)

      • Open file table에 대한 위치 정보 (프로세스 별)
      스크린샷 2021-07-30 오후 5 23 03
    • /a/b/c search 및 파일 읽기 과정

      1. OS가 hard disk의 root metadata의 저장 위치를 알기 때문에 Open file table에 root metadata 정보를 저장한다
      2. root metadata에서 a의 metadata 위치정보를 통해 metadata 정보를 불러온다
      3. 앞의 과정을 반복한다
      4. file descripter를 통해서 fd에 b의 metadata 정보를 읽는다
      5. b의 metadata 정보로 file b의 내용을 OS의 메모리에 올린다
      6. OS 메모리에 올라간 정보를 Process A의 메모리에 올린다

File Protection

  • 각 파일에 대해 누구에게 어떤 유형의 접근(read/write/execution)을 허락할 것인가?

  • Access Control 방법

    • Access Control Matrix

      스크린샷 2021-07-30 오후 5 52 46 - Access control list: 파일별로 누구에게 어떤 접근 권한이 있는지 표시 - Capability: 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시
    • Grouping

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

      • 각 파일에 대해 세 그룹의 접근 권한 (rwx)을 3비트씩으로 구분

        스크린샷 2021-07-30 오후 5 57 58
    • Password

      • 파일마다 password를 두는 방법
      • 모든 접근 권한에 대해 하나의 password: all or noting
      • 접근 권한별 password: 암기 문제, 관리 문제

File System의 Mounting

  • 물리적 디스크로 논리적 디스크 disk1 disk2, disk3으로 파티셔닝
  • 이후에 disk1의 root 디렉토리의 하위 디렉토리 중 하나로 disk1, disk2를 위치시킴 (= Mounting)
스크린샷 2021-07-30 오후 6 02 03
스크린샷 2021-07-30 오후 6 03 03

Access Methods

  • 시스템이 제공하는 파일 정보의 접근 방식
    • 순차 접근 (sequential access)
      • 카세트 테이프를 상요하는 방식처럼 접근
      • 읽거나 쓰면 offset은 자동적으로 증가
    • 직접 접근 (direct access, random access)
      • LP 레코드 판과 같이 접근하도록 함
      • 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있음

Allocation of File Data in Disk

  • Contiguous Allocation
  • Linked Allocation
  • Indexed Allocation

Contiguous Allocation

  • 단점
    • external fragmentation
    • File grow가 어려움
      • file 생성시 얼마나 큰 hole을 할당할 것인가?
      • grow 가능 vs 낭비 (internal fragmentation)
  • 장점
    • Fast I/O
      • 한 번의 seek/rotation으로 많은 바이트 transfer
      • Realtime file 용으로, 또는 이미 run중이던 process의 swapping 용
      • swap area의 저장 데이터는 영구저장용이 아니기 때문에 공간 효율성을 중요하게 여기지 않는다
    • Direct access(=random access)가능
스크린샷 2021-07-30 오후 11 28 16

Linked Allocation

  • 장점
    • External fragmentation 발생 안 함
  • 단점
    • No random access
    • Reliability 문제
      • 한 sector가 고장나면 pointer가 유실되면 많은 부분을 잃음
    • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
      • 512 bytes/sector, 4 bytes/pointer
  • 변형
    • File-allocation table (FAT) 파일 시스템
      • 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결
스크린샷 2021-07-30 오후 11 40 18

Indexed Allocation

  • 장점
    • External fragmentation이 발생하지 않음
    • Direct access 가능
  • 단점
    • Small file의 경우 공간 낭비 (실제로 많은 file들이 small)
    • Too Large file의 경우 하나의 block으로 index를 저장하기에 부족
      • linked scheme
      • multi-level index

UNIX 파일 시스템의 구조

스크린샷 2021-07-30 오후 11 54 03

inode에서 index allocation 사용하며 파일 사이즈에 따라 multi level index의 수가 달라집니다

스크린샷 2021-07-31 오전 12 04 25

FAT File System

스크린샷 2021-07-31 오전 12 12 16

Linked Allocation 방식으로 파일을 저장합니다

사용하면 파일에 파일 시작 주소값 217을 저장하고 다음 데이터가 저장된 주소값은 FAT에 217번지에 저장되어있는 주소값을 제공하는 방식으로 파일 데이터의 저장 위치를 제공합니다

VFS and NFS

  • Virtual File System (VFS)
    • 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스 (API)를 통해 접근할 수 있게 해주는 OS의 layer
  • Network File System (NFS)
    • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다
    • NFS는 분산 환경에서의 대표적인 파일 공유 방법이다
스크린샷 2021-07-31 오전 12 20 00

Page Cache and Buffer Cache

  • Page Cache

    • Vitrual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
    • Memory-Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용
  • Memory-Mapped I/O

    • File의 일부를 virtual memory에 mapping 시킴

    • 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함

    • OS를 거치지 않고 File에 접근 할 수 있다.

      Process의 code, data, stack 영역중 code 영역은 read-only 파일이 때문에

      swap area에 존재하지 않으며 memory-mapped I/O 빙식을 사용할 수 있다.

  • Buffer Cache

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

    • 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨
스크린샷 2021-07-31 오전 1 51 01
스크린샷 2021-07-31 오전 1 52 46

참고

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

Comment and share

Demand Paging

  • 실제로 필요할 때 page를 메모리에 올리는 것
    • I/O 양의 감소 -> 많은 프로세스가 메모리에 올라올 수 있기 때문에
    • Memory 사용량 감소
    • 빠른 응답 시간
    • 더 많은 사용자 수용
  • Valid / Invalid bit의 사용
    • Invalid의 의미
      • 사용되지 않은 주소 영역인 경우
      • 페이지가 물리적 메모리에 없는 경우
    • 처음에는 모든 page entry가 invalid로 초기화
    • address translation 시에 invalid bit이 set되어 있으면
    • -> page fault
스크린샷 2021-07-28 오전 11 11 02

Page Fault

  • invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
  • Kernel mode로 들어가서 page fault handler가 invoke됨
  • 다음과 같은 순서로 page fault를 처리한다
    1. Invalid reference? (e.g. bad address, protection violation) => abort process
    2. Get an empty page frame. (없으면 뺏어온다: replace)
    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을 재개
스크린샷 2021-07-28 오전 11 19 35
  • Demand Paging의 성능
    • Page Fault Rate 0 <= p <= 1.0
      • if p = 0, no page faults
      • if p = 1, every reference is a fault
    • Effective Acess Time
      1
      2
      3
      4
      5
      = (1 - p) * (memory access) 
      + p * (OS & HW page fault overhead
      + [swap page out if needed]
      + swap page in
      + OS & HW restart overhead)

Free frame이 없는 경우

  • Page replacement
    • 어떤 frame을 빼앗아올지 결정해야 함
    • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
    • 동일한 페이지가 여러 번 메모리에 쫓겨났다가 다시 들어올 수 있음
  • Replacement Algorithm
    • page-fault을 최소화하는 것이 목표
    • 알고리즘의 평가
      • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
스크린샷 2021-07-28 오전 11 32 51

Page Replacement Algorithm

Optimal Algorithm

  • MIN(OPT): 가장 먼 미래에 참조되는 page를 replace
  • 4 frames example 스크린샷 2021-07-28 오전 11 39 36
  • 미래에 참조를 어떻게 아는가?
    • Offline algorithm
  • 다른 알고리즘의 성능에 대한 upper bound 제공
    • Belady’s optiaml algorithm, MIN, OPT 등으로 불림

FIFO (First In First Out) Algorithm

  • FIFO: 먼저 들어온 것을 먼저 내쫓음

    스크린샷 2021-07-28 오전 11 43 13

    FIFO Algorithm은 Page frame을 늘렸을 때 Page fault가 더 발생할 수 있다

LRU (Least Recently Used) Algorithm

  • LRU: 가장 오래 전에 참조된 것을 지움 스크린샷 2021-07-28 오전 11 45 03

LFU (Least Frequently Used) Algorithm

  • LFU: 참조 횟수(reference count)가 가장 적은 페이지를 지움
    • 최저 참조 횟수인 page가 여럿 잇는 경우
      • LFU 알고리즘 자체에서는 여러 page 중 임으로 선정한다
      • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
    • 장단점
      • LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
      • 참조 시점의 최근성을 반영하지 못함
      • LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 비교

스크린샷 2021-07-28 오전 11 51 44
스크린샷 2021-07-28 오전 11 00 29

다양한 캐슁 환경

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

Clock Algorithm

  • Clock algorithm
    • LRU의 근사(approximation) 알고리즘
    • 여러 명칭으로 불림
      • Second chance algorithm
      • NUR (Not Used Recently) 또는 NRU (Not Recently Used)
    • Reference bit을 사용해서 교체 대항 페이지 선정 (circular list)
    • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
    • 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈
    • Reference bit이 0인 것을 찾으면 그 페이지를 교체
    • 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함
    • 자주 사용되는 페이지라면 second chance가 올 때 1
  • Clock algorithm의 개선
    • reference bit과 modified bit (dirty bit)을 함께 사용
    • reference bit = 1 : 최근에 참조된 페이지
    • modified bit = 1 : 최근에 변경된 페이지 (swap area에 변경된 정보를 반영하는 I/O 작업이 동반된다)
스크린샷 2021-07-28 오후 2 04 57

Page Frame의 Allocation

  • Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?

  • Allocation의 필요성

    • 메모리 참조 명령어 수행시 명령어, 데이터등 여러 페이지 동시 참조
      • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
    • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
      • 최소한의 allocation이 없으면 매 loop마다 page fault
  • Allocation Scheme

    • Equal allocation: 모든 프로세스에 똑같은 갯수 할당
    • Proportional allocation: 프로세스 크기에 비례하여 할당
    • Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

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

Thrashing

  • 프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
  • Page fault rate이 매우 높아짐
  • CPU utilization이 낮아짐
  • OS는 MPD (multiprogramming degree)룰 높여야 한다고 판단 (I/O 작업때문에 CPU이 이용률이 낮아지기 때문에)
  • 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
  • 프로세스 당 할당된 frame의 수가 더욱 감소
  • 프로세스는 page는 swap in/ swap out으로 바쁨
  • 대부분의 시간에 CPU는 한가함
  • low throughput
스크린샷 2021-07-28 오후 2 23 36

Working-Set Model

  • Locality of reference
    • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
    • 집중적을 참조되는 해당 page들의 집합을 locality set이라 함
  • Working-set Model
    • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 page들의 집합을 Working Set이라 정의함
    • Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반남한 후 swap out (suspend)
    • Thrashing을 방지함
    • Multiprogramming degree를 결정함
스크린샷 2021-07-28 오후 3 15 27

PFF (Page-Fault Frequency) Scheme

  • page-fault rate의 상한값과 하한값을 둔다
    • page fault rate이 상하값을 넘으면 frame을 더 할당한다
    • page fault rate이 하한값 이하이면 할당 frame 수를 줄인다
  • 빈 frame이 없으면 일부 프로세스를 swap out
스크린샷 2021-07-28 오후 3 18 55

Page Size의 결정

  • Page size를 감소시키면
    • 페이지 수 증가
    • 페이지 테이블 크기 증가
    • internal fragmentation 감소
    • Disk transfer의 효율성 감소
      • Seek/rotation vs transfer
    • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
      • Locality의 활용 측면에서 좋지 않음
  • Trend
    • Larger page size

참고

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

Comment and share

Logical vs Physical Address

  • Logical address (=virtual address)
    • 프로세스마다 독립적으로 가지는 주소 공간
    • 각 프로세스마다 0번지부터 시작
    • CPU가 보는 주소는 logical address다
  • Physical address
    • 메모리에 실제 올라가는 위치
  • 주소 바인딩: 주소를 결정하는 것
    • Symbolic Address -> Logical Address -> Physical address

주소 바인딩

  • Compile time binding
    • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
    • 시작 위치 변경 시 재컴파일
    • 컴파일러는 절대 코드(absolute code) 생성
  • Load time binding
    • Loader의 책임하에 물리적 메모리 주소 부여
    • 프로그램이 메모리에 올라갈 때 물리적 메모리 주소가 정해짐
    • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
  • Execution time binding(= Run time binding)
    • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
    • CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
    • 실행중에 메모리에 쫓겨나고 다시 메모리에 올라갈 때 (Swapping)
    • 하드웨어 지원이 필요하다 (e.g., base and limit registers, MMU)
스크린샷 2021-07-26 오전 11 31 44

Memory-Management Unit (MMU)

  • MMU (Memory-Management Unit)
    • logical address를 physical address로 매핑해 주는 Hardware device
  • MMU scheme
    • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (= relocation register)의 값을 더한다
  • user program
    • logical address만을 다룬다
    • 실제 physical address를 볼 수 없으며 알 필요가 없다
스크린샷 2021-07-26 오전 11 39 27

Hardware Support For Address Translation

  • 운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터
  • Relocation register(= base register) : 접근할 수 있는 물리적 메모리 주소의 최소값
  • Limit register: 논리적 주소의 범위
스크린샷 2021-07-26 오전 11 43 43

용어 정리

Dynamic Loading

  • 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
  • memory utilization의 향상
  • 가끔식 사용되는 많은 양의 코드의 경우 유용 (ex. 오류 처리 루틴)
  • 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능 (OS는 라이브러리를 통해 지원 가능)
  • Loading: 메모리로 올리는 것

Overlays

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

Swapping

  • Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
  • Backing store(=swap area)
    • 디스크
      • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
  • Swap in/ Swap out
    • 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
    • priority-based CPU scheduling algorithm
      • priority가 낮은 프로세스를 swapped out 시킴
      • priority가 높은 프로세스를 메모리에 올려 놓음
    • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함
    • Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
    • swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임
스크린샷 2021-07-26 오전 11 54 35

Dynamic Linking

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

Allocation Of Physical Memory

  • 메모리는 일반적으로 두 영역으로 나뉘어 사용
    • OS 상주 영역
      • interrupt vector와 함께 낮은 주소 영역 사용
    • 사용자 프로세스 영역
      • 높은 주소 영역 사용 스크린샷 2021-07-26 오후 1 31 47
  • 사용자 프로세스 영역의 할당 방법
    • Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
      • Fixed partiion allocation
      • Variable partition allocation
    • Noncontigous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
      • Paging : 논리 메모리를 같은 크기로 자른다
      • Segment : 논리 메모리를 의미있는 단위로 자른다 (code, data, stack)
      • Paged Segmentation

Contiguous Allocation

  • 고정 분할(Fixed partition) 방식
    • 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
    • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
    • 분할당 하나의 프로그램 적재
    • 융통성이 없음
      • 동시에 메모리에 load되는 프로그램의 수가 고정됨
      • 최대 수행 가능 프로그램 크기 제한
    • 가변 분할(Variable partition) 방식
      • 프로그램의 크기를 고려해서 할당
      • 분할의 크기, 개수가 동적으로 변함
      • 기술적 관리 기법 필요
      • External fragmentation 발생
스크린샷 2021-07-26 오전 11 05 55
  • Fragmentation
    • External fragmentation(외부 조각)
      • 프로그램 크기보다 분할의 크기가 작은 경우
      • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
    • Internal fragmentation(내부 조각)
      • 프로그램 크기보다 분할의 크기가 큰 경우
      • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
      • 특정 프로그램에 배정되었지만 사용되지 않는 공간
  • Hole
    • 가용 메모리 공간
    • 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있음
    • 프로세스가 도착하면 수용가능한 hole을 할당
    • 운영체제는 다음의 정보를 유지
      • 할당 공간
      • 가용 공간 (hole)
스크린샷 2021-07-26 오후 1 48 24
  • Dynamic Storage-Allocation Problem

    • 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

    • 방식 종류

      1. First-fit
        • Size가 n 이상인 것 중 최초로 찾아지는 hole에 할당
      2. Best-fit
        • Size가 n 이상인 가장 작은 hole을 찾아서 할당
        • Hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야함
        • 많은 수의 아주 작은 hole들이 생성됨
      3. Worst-fit
        • 가장 큰 hole에 할당
        • 역시 모든 리스트를 탐색해야 함
        • 상대적으로 아주 큰 hole들이 생성됨

      First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐(실험적인 결과) -> Worst-fit은 탐색 + 더 큰 프로그램의 메모리 hole을 차지하기 때문이다

  • Compaction

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

Paging

  • Paging
    • Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
    • Virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
    • 일부는 backing storage에, 일부는 physical memory에 저장
  • Basic Method
    • physical memory를 동일한 크기의 frame으로 나눔
    • logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)
    • 모든 가용 frame들을 관리
    • page table을 사용하여 logical address를 physical address로 변환
    • External fragmentation 발생 안함
    • Internal fragmentation 발생 가능 (마지막으로 나눠진 Page의 크기가 작기 때문)
스크린샷 2021-07-26 오후 3 30 43

Implemntation Of Page Table

  • Page table은 main memory에 상주
  • Page-table base register (PTBR)가 page table을 가리킴
  • Page-table length register (PTLR)가 테이블 크기를 보관
  • 모든 메모리 접근 연산에는 2번의 memory access필요
    • page table 접근 1번, 실제 data/instruction 접근 1번

속도 향상을 위해

associatve register 혹은 translation look-aside buffer(TLB)라 불리는

고속의 lookup hardware cache 사용

TLB

스크린샷 2021-07-26 오후 3 38 24
  • Associative registers (TLB): parallel search가 가능

    • TLB에는 page table 중 일부만 존재
  • Address translation

    • page table 중 일부가 associative register에 보관되어 있음
    • 만약 해당 page #가 associative register에 있는 경우 곧바로 frame #를 얻음
    • 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
    • TLB는 context switch 때 flush (remove old entries)
  • Effective Access Time

    스크린샷 2021-07-26 오후 3 43 22

Two-Level Page Table

  • 현대의 컴퓨터는 address space가 매우 큰 프로그램 지원

    • 32 bit address 사용시: 2^32(4G)의 주소 공간

      • page size가 4K시 1M개의 page table entry 필요

      • 각 page entry가 4B시 프로세스 당 4M의 page table 필요

      • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

        -> page table 자체를 page로 구성

        -> 사용하지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응하는 inner page table이 없음

스크린샷 2021-07-26 오후 3 53 42
  • Example

    • logical address (on 32-bit machine with 4K page size) 구성

      • 20bit의 page number
      • 12bit의 page offset
    • page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다 (각 page table entry가 4B)

      • 10-bit의 outer page number
      • 10-bit의 inner page number
      • 12bit의 page offset
    • 따라서, logical address는 다음과 같다

      스크린샷 2021-07-26 오후 3 58 15
    • P1은 outer page table의 index이고

    • P2는 outer page table의 page에서의 변위(displacement)

  • 2단계 페이징에서 Address-translation scheme

    스크린샷 2021-07-26 오후 4 00 12 ## Multilevel Paging and Performance
  • Address space가 더 커지면 다단계 페에지 테이블 필요

  • 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요

  • TLB를 통해 메모리 접근 시간을 줄일 수 있음

  • 4단계 페이지 테이블 을 사용하는 경우

    • 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
    • TLB hit ratio가 98%인 경우
      • effective memory access time = 0.98 * 120 + 0.02 * 520 = 128 nanoseconds
    • 결과적으로 주소변환을 위해 28ns만 소요

Memory Protection

  • Page table의 각 entry마다 아래의 bit를 둔다
    • Protection bit
      • page에 대한 접근 권한 (read/wrtie/read-only)
    • Valid-invalid bit
      • “valid”는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
      • “invalid”는 해당 주소의 frame에 유효한 내용이 없음을 뜻함 (접근 불허)
        • 프로세스가 그 주소 부분을 사용하지 않는 경우
        • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우
스크린샷 2021-07-27 오후 2 06 58

Inverted Page table

  • page table이 매우 큰 이유
    • 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
    • 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
  • Inverted page table
    • Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
    • 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)
    • 모든 프로세스에 대해서 한 개의 페이지 테이블로 관리
    • 단점
      • 테이블 전체를 탐색해야한다
    • 조치
      • associative register 사용 (expensive)
스크린샷 2021-07-27 오후 2 17 32

Shared Page

  • Shared code
    • Re-entrant Code (=Pure code)
    • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (eg. text editors, compilers, window systems)
    • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
  • Private code and data
    • 각 프로세스들은 독자적으로 메모리에 올림
    • Private data는 logical address space의 아무 곳에 와도 무방
스크린샷 2021-07-27 오후 2 57 02

Segmentation

  • 프로그램은 의미 단위인 여러 개의 segment로 구성
    • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
    • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
    • 일반적으로 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
  • Segment는 다음과 같은 logical unit 들임
    • main()
    • function
    • global variables
    • stack
    • symbol table, arrays
스크린샷 2021-07-27 오후 3 28 07

Segmentation Architecture

  • Logical address는 다음의 두 가지로 구성
    • < segment-number, offset >
  • Segment table
    • each table entry has:
      • base : starting physical address of the segment
      • limit : length of the segment
    • Page 보다 테이블 크기가 작아서 메모리 낭비가 적다
  • Segment-table base register (STBR)
    • 물리적 메모리에서의 segment table의 위치
  • Segment-table length register (STLR)
    • 프로그램이 사용하는 segment의 수
      • segment number s is legal if s < STLR
스크린샷 2021-07-27 오후 3 20 54
  • Protection
    • 각 세그먼트 별로 protection bit가 있음
    • Each entry:
      • Valid bit = 0 -> illegal segment
      • Read/Write/Execution 권한 bit
  • Sharing
    • shared segment
    • same segment number
    • segment는 의미 단위이기 때문에 공유와 보안에 있어서 paging보다 훨씬 효과적이다
  • Allocation
    • first fit/ best fit
    • external fragmentation 발생
    • segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점이 발생한다
스크린샷 2021-07-27 오후 3 29 13

Segmentation with Paging

  • pure segmentation과의 차이점
    • segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음
스크린샷 2021-07-27 오후 3 34 24

사용 이유는 Segmentation의 의미 단위로 묶였을 때 Protection과 Sharing등의 장점과

Paging를 통해 외부 단편화를 없애는 장점을 같이 사용하기 위해서 이다

참고

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

Comment and share

스크린샷 2021-07-24 오후 11 46 58

길을 점유하면서 상대방의 길을 점유하길 원한다

The Deadlock Problem

  • Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

  • Resource (자원)

    • 하드웨어, 소프트웨어 등을 포함하는 개념
    • (예) 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

    • Binary semaphores A and B

      P0가 A 자원을 점유한 후 인터럽트가 걸려서 context switching하여 P1이 B 자원을 점유 이후에서로의 자원을 할당받기 위해서 대기한다

      스크린샷 2021-07-25 오전 12 22 50

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

스크린샷 2021-07-25 오전 12 32 35 스크린샷 2021-07-25 오전 12 34 14
  • 그래프에 cycle이 없으면 deadlock이 아니다
  • 그래프에 cycle이 있으면
    • if only one instace per resource type, then deadlock
    • if several instances per resource type, possibility of deadlock

2번째 그림에서 P4가 사용후 자원 R2를 반납하고, P2가 자원 R1을 반납하기 때문에 때문에 deadlock은 없다

Deadlock의 처리 방법

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

Deadlock Prevention

  • Mutual Exclusion
    • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
  • Hold and Wait
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
    • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
  • No Preemption
    • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
    • 모든 필요한 저원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
    • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memeory)
  • Circular Wait
    • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당
    • 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야한다

-> Utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

  • Deadlock avoidance

    • 자원 요청에 대한 부가 정보를 이요해서 자원 할당이 deadlock으로 부터 안전한지 동적으로 조사해서 안전한 경우에만 할당
    • 가장 단순하고 일반적인 모델은 프로세스들이 필요하는 각 자원별 최대 사용랴을 미리 선언하도록 하는 방법임
    • 평생 쓸 자원들을 선언함으로써 자원에 Deadlock 가능성이 있을 경우를 피한다
  • safe state

    • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
  • safe sequence

    • 프로세스 sequence<P1, P2, …, Pn>이 safe하려면 Pi(1 <= i <= n)의 자원 요청이 “가용 자원 + 모든 Pj(j < i)의 보유 자원”에 의해 충족되어야 함

    • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장

      • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다
      • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다
      스크린샷 2021-07-25 오전 12 59 56
  • 시스템이 safe state에 있으면 no deadlock, 시스템이 unsafe state에 있으면 possibility of deadlock

  • Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다

  • 2가지 경우의 avoidance 알고리즘

    • Single instance per resource types -> Resource Allocation Graph algorithm
    • Multi instance per resource types -> Banker's Algorithm

Resource Allocation Graph algorithm

스크린샷 2021-07-25 오전 1 04 10

Banker’s Algorithm

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

Deadlock Detection and Recovery

  • Deadlock Detection

    • Resource type 당 single instance인 경우
      • 자원 할당 그래프에서 cycle이 곧 deadlock을 의미
    • Resource type 당 multiple instance인 경우
      • Banker’s algorithm과 유사한 방법 활용
  • Wait-for graph 알고리즘

    • Resource type ekd single instance인 경우

    • Wait-for graph

      • Resource type당 single instance인 경우

      • Wait-for graph

        • 자원 할당 그래프의 변형
        • 프로세스만으로 node 구성
        • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
      • Algorithm

        • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
        • O(n^2)
        스크린샷 2021-07-25 오후 5 10 58
      스크린샷 2021-07-25 오후 5 12 18
  • Recovery

    • Process termination
      • Abort all deadlocked processes
      • Abort one process at a time until the deadlock cycle is eliminated
    • Resource Preemption
      • 비용을 최소화할 victim을 선정
      • safe state로 rollback하여 process를 restart
      • Starvation 문제
        • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
        • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

  • Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
    • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다
    • 만야그 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 직점 느낀 후 직접 process를 죽이는 등의 방법으로 대처
    • UNIX, Windows등 대부분의 범용 OS가 채택

참고

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

Comment and share

Yechan Kim

author.bio


author.job