바로 예시를 보자.

위와 같은 순서로 노드를 탐색한다.

구현 방식은 다음과 같다.

graph = {
    1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

def dfs_recursive(node,visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj,visited)

    return visited

def dfs_stack(start):
    visited = []
    #방문한 순서 담아놓는 용도
    stack = [start]

    #방문할 노드가 남아 있다면 아래 로직 반복
    while stack:
        #제일 최근 노드 꺼내고 방문 처리
        top = stack.pop()
        visited.append(top)

        #인접 노드 방문
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

어떤 문제에서 DFS를 사용하면 좋을지 백준에 나와 있는 문제를 보자. 백준 2606번 링크

정답 1번 컴퓨터가 바이러스에 걸렸을 경우, 이와 인접한 2,5번이 바이러스에 걸린다. 마찬가지로 2,5과 인첩한 3,6번도 바이러스에 걸린다. 문제에서 요구하는 건 1번이 바이러스에 걸렸을 경우 컴퓨터 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 것이므로 2,3,5,6번이 바이러스에 걸려 4개이다.

DFS를 사용해서 1번에서부터 최대로 연결할 수 있는 노드의 개수를 구하면 된다.

다른 문제를 살펴보자.

백준 2667번 링크

정답 모든 행렬을 탐색하면서 단지가 존재한다면, 해당 단지에서 부터 DFS를 하여 단지의 최대 개수를 구한 후 저장하는 방식으로 탐색한 후, 오름차순을 해주면 되는 문제이다.

이 문제는 연결할 수 있는 모든 노드를 구하는 것과 다를바 없다.

JVM의 구조

Class Loader

JVM내로 클래스 파일을 로드하고, 링크를 통해 배치하는 작업을 수행한다. 런타임시 한번에 모든 클래스 파일을 로드하는 것이 아니라, 필요한 클래스 파일의 바이트 코드를 JVM 메모리에 로드하는데, 여기에는 클래스의 메타데이터가 생성된다. JVM 실행중 더 이상 필요하지 않은 클래스나 인스턴스가 생기게 되면 Garbage Collector가 이를 감지하여 메모리 상에서 제거해줘 메모리 누수를 막는다.

Runtime Data area의 구성

JVM이 프로세스로 사용되기 위해 OS로부터 할당받는 메모리 영역이다.

• Method Area 모든 쓰레드에게 공유된다. 클래스 정보, 변수 정보, 메서드 정보, static변수 정보, 상수 정보등이 저장된다.
• Heap Area 모든 쓰레드에게 공유된다. new 명령어로 생성된 인스턴스와 객체가 저장됨. 공간이 부족하면 Garbage Collection 실행
• Stack Area 각 쓰레드마다 하나씩 생성. Method안에서 사용되는 값들(매개변수, 지역변수, 리턴 값 등)이 저장된다. 메서드가 호출될 때 LIFO로 하나씩 생성, 메서드 실행 완료되면 LIFO로 지워진다.
• PC Register 각 쓰레드마다 하나씩 생성. CPU Register와 역할이 비슷하다. 현재 수행중인 JVM 명령의 주소 값 저장

Execution Engine의 구성

1. 인터프리터: 바이트코드 명령어를 하나씩 읽어서 해석하고 실행
2. JUST IN TIME(JIT) Compiler: 인터프리터 + 캐싱 더 빠르게 수행
3. Garbage Collector: 메모리 영역의 메모리를 관리한다.

java 실행과정

우리가 작성하는 JAVA 코드인 JAVA source 파일들은 사실 컴퓨터는 알지 못하는 코드이다. 컴퓨터는 단지 0과 1만을 알고 있을 뿐이다. 따라서, 다음과 같은 순서로 컴퓨터가 코드를 이해할 수 있도록 해석한다.

1. java 언어로 코드를 작성한다.
2. java 컴파일러를 통해 소스코드를 바이트코드로 변환 (.class 파일에 저장)
3. JVM에서 class Loader를 통해 클래스파일이 Runtime Data Area(JVM 메모리)에 배치된다.
4. Execution Engine이 JVM 메모리 상에 있는 바이트 코드를 그때 그때 읽어서 각 OS에 맞는 바이너리 코드로 변환하고 이를 실행한다.

바이트 코드를 읽는 방식

JVM은 바이트 코드를 해석할 때, 인터프리터 방식 + JIT 컴파일 방식을 혼합해서 사용한다. 인터프리터 방식은 한줄씩 해석하고 실행하는 방식이다. 초기 방식이고 속도가 느리다는 단점이 있다. 느린 속도를 보완하기 위해서 나온것이 JIT 컴파일 방식이다. JIT 컴파일 방식은 같은 코드를 매번 컴파일 하지 않고, 실행할 때 컴파일을 하면서 해당 코드를 캐싱해버린다. 이후에는 바뀐 코드에 대해서만 컴파일하고, 나머지는 캐싱된 코드를 사용한다. 이 때문에, JIT 컴파일 방식이 인터프리터 방식보다 훨씬 빠르다.

동시성 문제란?

먼저, 동시성 문제란 한 자원에 여러 쓰레드가 동시에 접근 했을 때, 내가 예상했던 값이 결과로 나타나지 않는 것을 말한다.

예를 들어보면, 위의 그림처럼 i라는 자원에 대해서 두 쓰레드가 동시에 접근한다고 가정해보자. 동시에 접근한 후에 i++를 해주었다. 우리가 예상한 값은 2 이지만, i 값은 1이 되었다. 왜 이러한 결과가 나타났을까? 과정을 살펴보자.

1. thread1이 i를 읽는다. 동시에 thread2도 i를 읽는다. 두 쓰레드가 읽은 값은 0 이다.
2. 두 쓰레드는 0에다가 1을 더 해준 후 i에 값을 덮어씌운다.
3. i의 값은 1이된다.

결국은 i라는 값을 읽을 때, 두 쓰레드가 같은 값을 읽기 때문에 발생 하는 문제이다.

맨 처음에 말했듯이, 이번 프로젝트는 예약 구매 상황에서 많은 사용자가 동시에 결제를 하고자 접근했을 때, 발생한 문제를 해결하고자 하였다.

시뮬레이션

시뮬레이션 계획은 다음과 같다.

• 예약 구매가 가능한 A상품이 있고, 재고 수량은 10개이다.
• 동시에 몰리는 이용자의 수는 10000명이다.
• 시뮬레이션 진행과정

결제 진입 API를 자세하게 살펴보자. 결제 진입에서 체크할 부분은 두 가지 이다.

• 예약 상품이라면 현재 시간이 예약 시간을 지났는지 체크
• 재고 예약 가능한 상태인지 체크

동시성 문제가 발생할 수 있는 부분은 상품의 재고를 처리(재고 예약 or 취소)하는 부분이다. 재고를 예약하는 내부 로직은 다음과 같다.

public Boolean reserveStock(EnterPayRequestDto payRequestDto) {
     //상품 조회
      Item item = itemRepository.findById(payRequestDto.getItemId())
    .orElseThrow(() -> new ItemServiceException(ErrorCode.NO_ITEMS));

    //재고 예약으로 인한 재고 감소
    Long newStock = item.getStock() - payRequestDto.getCount();

    //재고 예약이 가능한 경우
    if (newStock >= 0) {
        //DB 재고 변경
        item.changeStock(newStock);
        return true;
    // 재고 예약이 불가능한 경우
     }else{
        return false;
     }
}

1. 먼저 상품 재고를 조회한다.
2. 재고를 예약 한 후에도 재고가 0개 이상이라면, 재고를 예약해주고, DB에 반영한 후 true를 return 한다.
3. 재고를 예약 한 후 재고가 0개 미만이라면, false를 return 한다.

위와 같은 메서드에 동시에 두개의 쓰레드가 접근한다면 어떻게 될까?

상품 개수가 10개 일때 Thread A와 B가 동시에 재고를 조회했다고 하자. A와 B가 조회한 상품 개수는 10개이다. 상품을 하나씩 구매한다고 했을 때, 예상되는 남은 상품 재고는 8개이다. 하지만 실제 결과는 9개가 남게 되었다.

위의 그림에서 i가 DB에서 상품의 재고 수 라고 해보자.
Thread A와 Thread B는 같은 재고 수를 조회 하게 된다. 따라서, 모두 하나씩 재고를 감소 시켜 재고 2개를 감소시켜야 하지만, 결과적으로는 1이 감소되게 된다.

이러한 동시성 문제는 어떻게 해결하면 좋을까? 이제부터 동시성 문제를 어떻게 해결 했는지 알아보도록 하겠다.

문제 해결 순서

그렇다면, 동시성 문제는 어떠한 방식으로 해결할 수 있을까? 나는 다음과 같은 순서로 동시성 문제 해결을 진행하려고 한다.

1. java @synchronized
2. RDB pessimistic Lock(write), 베타적 락 사용
3. 분산락
4. 분산락 + redis 캐시

운영체제에서의 Synchronization 및 Lock 알고리즘에 대해 자세히 알고 싶다면 아래 블로그를 참고하면 좋을 것 같다. 참고: [운영체제]Synchronization

@synchronized로 동시성 문제 해결하기

해결 1

lombok을 이용한 Synchronized 걸어주기

@Synchronized
@Transactional
public Boolean reserveStock(EnterPayRequestDto payRequestDto) {
     //상품 조회
      Item item = itemRepository.findById(payRequestDto.getItemId())
    .orElseThrow(() -> new ItemServiceException(ErrorCode.NO_ITEMS));

    //재고 예약으로 인한 재고 감소
    Long newStock = item.getStock() - payRequestDto.getCount();

    //재고 예약이 가능한 경우
    if (newStock >= 0) {
        //DB 재고 변경
        item.changeStock(newStock);
        return true;
    // 재고 예약이 불가능한 경우
     }else{
        return false;
     }
}

동시성 문제가 발생하는 이유는 java가 멀티쓰레드 환경이기 때문이다. @Synchronized는 싱글 쓰레드 방식으로 로직을 처리할 수 있도록 도와 준다. 즉, Thread A가 재고 예약을 다 끝내면, Thread B가 다음 재고 예약을 시작하는 방식이다.

이 방법이면, 해결이 될 줄 알았는데, 여전히 동시성 문제가 해결되지 않았다. 이유는, @Synchronized는 트랜잭션이 시작할때부터 끝날때까지만, 유효하기 때문이다. 이말인 즉슨, 트랜잭션이 끝나고 나서야 dirty checking으로 변경된 값을 DB에 반영하게 되는데, Synchronized는 변경된 값이 반영되기 전에 끝나기 때문에, 실제적으로 DB를 수정하기 전에 재고 조회가 가능해버리게 된다.

따라서, 트랜잭션이 끝나기 전에 변경된 엔티티를 DB에 flush 해주거나, 더 넓은 범위의 트랜잭션에서 Synchronized처리를 해주어야 한다.

해결 2

나는 더 넓은 범위인 결제 진입 API에서 @Synchronized를 적용했다. 이렇게 하게 되면, 아예 싱글 쓰레드 환경이 되어 data의 일관성이 보장된다. 10000명이 10개 상품에 대하여 동시 접근하여 결제를 시도 했을 때의 결과는 다음과 같았다.

문제점

synchronized는 한 트랜잭션에 대해서만 동시성을 보장 해주기 때문에 서버를 여러대로 두는 환경에서는 적합하지 않다고 생각했고, DB Lock을 생각하게 되었다.

2. DB Lock으로 동시성 문제 해결하기

DB Lock의 종류와 특징

먼저 DB Lock의 종류에는 어떤 것들이 알아보고, 각 Lock의 특징을 알아보자.

• 낙관적 락(Optimistic Lock) 낙관적 락은 DB의 version 컬럼을 두어 동시성 문제를 해결한다. 낙관적 락은 기본적으로 트랜잭션을 사용하지 않고, DB가 아니라 Application level에서 처리한다.

왼쪽을 Thread A, 오른쪽을 Thread B 라고 하자.

1. A와 B에서 id = 2인 값의 행을 읽어들였다. 둘다 읽어드린 행의 버전은 1이다.
2. B가 먼저 name을 업데이트 했고, version도 1 증가한 2로 업데이트 했다.
3. A가 name을 업데이트 하려고 했는데, version이 1이 아닌 2이기 때문에 업데이트 하지 못했다.

위의 예시에서 봤듯이, 낙관적 락은 버전 일치 여부를 통해 업데이트를 방지하여, 동시성 문제를 해결한다. 하지만 문제는, A가 버전이 일치하지 않아 업데이트를 하지 못했을 경우 rollback이 일어나지 않는다.

낙관적 락은 버전 충돌이 일어났을 경우 별도의 로직을 통해 롤백을 해줘야 한다. 따라서, 트랜잭션 충돌이 자주 일어나는 경우에는 사용하지 않는다.

이 프로젝트에서는 재고를 관리하는 과정에서 트랜잭션 충돌이 빈번하게 발생하므로 낙관적 락은 사용하지 않았다.

• 비관적 락(Pessimistic Lock)

비관적 락은 두가지 종류의 락이 있다.

1. 공유 락(S-Lock,read mode) 2. 베타적 락(X-Lock,write mode)

S-Lock은 읽기 전용 이라고 생각하면 된다. 다만, 공유 락이라는 이름의 특성 처럼 트랜잭션들이 락을 공유할 수 있다. 무슨 말인지 한번 구체적인 예시를 들어보겠다.

Transaction A가 공유락을 획득했을 경우, 다른 Transaction들도 공유락을 획득할 수 있다. 즉, A가 data를 읽고 있음에도, 다른 B,C Transaction들도 data를 읽을 수 있다는 것이다. 하지만, A가 S-Lock을 획득한 상태에서 D가 X-Lock을 획득한다고 한다면 이는 차단된다.

위에 그림을 보면, Transaction 1이 S-Lock을 획득한 상태에서 Transaction 2가 업데이트를 시도하려고 했지만, 차단됐다. Transaction 1이 commit을 한 이후에야 Transaction 2가 업데이트를 완료하는 것을 볼 수 있다.

위처럼, 업데이트 하기 위해 필요한 Lock이 바로 X-Lock이다. X-Lock은 쓰기 전용 이라고 생각하면 쉽다. 다만, X-Lock을 획득하게 되면, 다른 Transaction은 X-Lock과 S-Lock 모두를 획득하지 못한 채로 대기해야 한다.

결과적으로, 멀티 쓰레드 환경에서 동시에 많은 쓰레드가 재고를 조회하고 수정하려고 하기 때문에, 트랜잭션 충돌이 많이 발생할 것이고, 재고 관리에서 동시성을 보장하기 위해서는 X-Lock 처럼 한 쓰레드(유저)가 재고를 예약하여 감소시킨 값을 commit 할때까지, 다른 쓰레드가 접근하지 못해야 동시성 문제가 해결될 수 있다. 따라서, 이번 프로젝트에서는 X-Lock을 사용하게 되었다.

해결

X-Lock을 적용하는 과정은 간단하다. jpa repository에 다음과 같이 어노테이션만 붙여주면 된다.

public interface ItemRepository extends JpaRepository<Item,Long> {
    @Lock(LockModeType.PESSIMISTIC_WRITE)
    @Query("select i from Item i where i.id = :id")
    Optional<Item> findByIdForUpdate(@Param("id") Long itemId);
}

문제점

문제는 MSA 환경에서는 분산 DB를 사용하기 때문에 하나의 DB에서만 동시성 문제를 해결 할 수 있는 DB Lock 방식은 이 프로젝트의 해결방법이 될 수 없었다.

분산락

redis를 이용한 분산락 방식은 redis에서 Lock을 읽고 쓰는 작업을 통해, 동시성을 제어하는 방식이다. 분산 DB에서도 data의 일관성을 보장하고 동시성을 보장해 준다. 또한 Lock을 인메모리에서 read,write를 하기 때문에 속도도 빠르다. redis를 이용한 분산락 방식은 두가지가 있다.

분산락 종류

1. rettuce 이용한 분산락
2. redisson 이용한 분산락

두 방식에는 차이가 Lock을 획득하는 방식에 차이가 있다.

• rettuce는 spin Lock 방식이다. spin Lock은 Lock을 획득하기 위해서 계속해서 접근한다. 즉, A Thread가 Lock을 획득했을 경우, B Thread는 A가 Lock을 반환 할 때까지 계속 접근 하면서 물어본다. Lock을 획득하기 위해서 redis에 계속 요청한다는 것은 redis에게 큰 부담이 될 수 있다.

• redisson은 비동기 방식의 메세지 큐를 사용한다. A Thread가 Lock을 획득했을 경우, B Thread는 Lock을 획득하기 위해서 계속해서 접근할 필요가 없다. A thread가 Lock을 반환할 경우 B Thread에게 Lock이 반환되었다는 메세지가 도착한다. B Thread는 이때 Lock을 얻으려고 시도 한다.

redisson을 이용한 방식이 rettuce보다 redis에 부하를 적게 주고 성능이 훨씬 좋으므로, redisson 방식을 채택했다.

분산락 구현 With. redisson

1. redis bean 등록

   @Configuration
   public class RedisConfiguration {
    @Bean
    public RedisConnectionFactory redisConnectionFactory(){
        return new LettuceConnectionFactory(new RedisStandaloneConfiguration("localhost",79));
    }
   
    @Bean
    public RedisTemplate<String,Long> redisTemplate(){
        RedisTemplate<String,Long> redisTemplate = new RedisTemplate<>();
        redisTemplate.setConnectionFactory(redisConnectionFactory());
        redisTemplate.setKeySerializer(new StringRedisSerializer());
        redisTemplate.setValueSerializer(new GenericToStringSerializer<>(Long.class));
        return redisTemplate;
    }
   }

2. redisson bean 등록

     @Configuration
     public class RedissonConfig {
        private final String redisHost = "localhost";
        private final int redisPort = 79;
   
        private static final String REDISSON_HOST_PREFIX = "redis://";
   
        @Bean
        public RedissonClient redissonClient(){
            Config config = new Config();
            config.useSingleServer().setAddress(REDISSON_HOST_PREFIX + redisHost + ":" + redisPort);
            RedissonClient redisson = Redisson.create(config);
            return redisson;
        }
    }

3. 분산락 적용

   @Transactional
    public boolean reserveStockRequest(EnterPayRequestDto req) {
        //Lock 설정
        String lockKey = "lockKey:" + req.getItemId();
        RLock lock = redissonClient.getLock(lockKey);
        Boolean reserveStock = false;
   
        try {
            //락 획득
            if (!lock.tryLock(10, 1, TimeUnit.SECONDS)) {
                log.info("userId:{},lock 획득 실패", req.getUserId());
                return false;
            }
   
            ResponseEntity<Boolean> response = itemServiceClient.reserveStock(req);
            reserveStock = response.getBody();
            log.info("userId:{}\nitemId:{}\nstockCount:{}\n재고 예약 가능 여부:{}", req.getUserId(), req.getItemId(), req.getCount(), reserveStock);
   
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            //락 반환
            lock.unlock();
        }
   
        return reserveStock;
    }

• tryLock의 첫번째 argument는 Lock 획득을 위해 기다리는 시간이다. 이 시간이 지나면, Lock 획득에 실패하게 되고 false를 return 하여 결제를 취소 한다. Lock을 재획득하게 한다면, 모든 유저가 재고를 요청해 볼 수 있는 기회를 가지게 되겠지만, 성능이 느려지는 trade off가 있기 때문에, 성능을 더 최적화 하기 위해서 재획득 하지 않게 했다.

• tryLock의 두번째 argument는 lease Time이다. 즉, Lock이 지속되는 시간이다. 한 Thread가 Lock을 너무 오랜 시간 잡고 있으면, 그 만큼 CPU가 낭비 되는 시간이 길어지는 것이기 때문에, 적절한 lease Time을 주는 것이 중요하다.

• unlock은 반드시 finally에서 해주어야 한다. exepction이 발생한 상황에서도 Lock은 해제 해주어야 하기 때문이다.

문제점

분산락 방식이 MSA와 같은 분산 환경에서 동시성을 보장하기 위해 적합한 것은 사실이다. 하지만, 분산락 만으로 DB에 접근하게 되면, DB에서 I/O하는 것이 오버헤드가 크다. 따라서, redis를 캐시로 이용하여 재고를 조회 하도록 해 주었다.

분산락 + redis 캐시

재고를 조회하기 위해서 redis를 캐시로 사용한다. 인메모리에서 재고를 조회하기 때문에 DB에서 조회하는 것보다 훨씬 속도가 빠르다.

여러 캐시 전략 중에서 어떤 전략을 사용해야 할지 고민했다.

cache-aside 같은 읽기에 특화된 전략들은 재고 감소가 일어날 때 마다 DB에 업데이트 시켜줘야 하기 때문에 오버헤드가 크다.

반면, write back cache 전략은 감소시킨 재고를 cache에만 업데이트 해주고 있다가, 한번에 DB에 업데이트 해주는 방식이다. 예를 들어, 유투브 조회수나 좋아요 같은 것들은 매번 DB에 업데이트 하지 않는다. 너무 자주 일어나기 때문에, 한번에 bulk 연산해 주는 것이 성능면에서 훨씬 좋기 때문이다.

이 프로젝트에서는 재고 변경이 빈번하게 일어나기 때문에 write back cache가 알맞은 전략이라 생각하였다.

재고 예약

재고가 남아있는지 확인 한후, 재고를 예약할 수 있도록 하였다. 재고 예약시 캐시의 재고를 감소 시킨다. 마지막으로, 재고 예약이 가능하다면 true, 재고 예약이 가능하지 않다면 false를 return 해준다.

public Boolean reserveStock(EnterPayRequestDto payRequestDto) {
        // 캐시에서 재고 조회
        String key = "itemId:stock:" + payRequestDto.getItemId();
        Long stock = redisTemplate.opsForValue().get(key);

        //캐시에 재고가 존재 한다면
        if (stock != null) {
            //재고를 줄인다.
            if (stock - payRequestDto.getCount() >= 0) {
                Long newStock = redisTemplate.opsForValue().decrement(key, payRequestDto.getCount());

                return true;
            } else {
                //재고 부족
                return false;
            }
        }
        //캐시에 재고가 존재하지 않는다면
        else {
            Item item = itemRepository.findById(payRequestDto.getItemId()).orElseThrow(() -> new ItemServiceException(ErrorCode.NO_ITEMS));
            Long newStock = item.getStock() - payRequestDto.getCount();
            //재고 예약이 가능한 경우
            if (newStock >= 0) {
                //DB 재고 변경
                item.changeStock(newStock);

                //cache에 추가
                redisTemplate.opsForValue().set(key, newStock);
                return true;

            } else {
                return false;
            }
        }
    }

재고 예약 취소

재고 예약을 취소하게 되면 다시 캐시의 재고를 올려준다.

 public void cancelStock(EnterPayRequestDto payRequestDto) {
        // 캐시에서 재고 조회
        String key = "itemId:stock:" + payRequestDto.getItemId();
        Long stock = redisTemplate.opsForValue().get(key);

        //캐시에 재고가 존재 한다면
        if (stock != null) {
            //재고를 증가 시킨다.
            redisTemplate.opsForValue().increment(key, payRequestDto.getCount());
        }
        //캐시에 재고 존재하지 않는다면
        else {
            Item item = itemRepository.findById(payRequestDto.getItemId()).orElseThrow(() -> new ItemServiceException(ErrorCode.NO_ITEMS));
            Long newStock = item.getStock() + payRequestDto.getCount();
            item.changeStock(newStock);
            redisTemplate.opsForValue().set(key, newStock);
        }
    }

DB와 캐시 동기화

DB와 캐시의 동기화를 위해 @Scheduled를 사용했다. 5초마다 DB와 캐시의 동기화가 일어난다.

    @Scheduled(fixedRate = 5000)
    public void syncDB() {
        // SCAN 옵션 생성, 매치할 키 패턴 설정
        ScanOptions options = ScanOptions.scanOptions().match("itemId:stock:*").build();

        try (Cursor<byte[]> cursor = redisTemplate.getConnectionFactory().getConnection().scan(options)) {
            while (cursor.hasNext()) {
                String key = new String(cursor.next());
                // 캐시에서 itemId의 재고 조회
                Long stock = redisTemplate.opsForValue().get(key);

                // itemId 파싱
                String itemId = key.split(":")[2];

                // DB 업데이트
                Item item = itemRepository.findById(Long.parseLong(itemId)).orElseThrow(() -> new ItemServiceException(ErrorCode.NO_ITEMS));
                item.changeStock(stock);
            }
        } catch (Exception e) {
            // 예외 처리 로직 추가
            e.printStackTrace();
        }
    }

성능 테스트

Jmeter를 사용해서 테스트 하였고, 10000개의 Thread가 1초 동안 발생하도록 설정하였다. 성능을 측정하기 위해 내가 확인할 부분은 throughput이다.

throughput은 초당 처리 가능한 요청 수 이다. 따라서 throughput이 높다면 성능이 높다고 할 수 있다.

테스트의 주요 쟁점

1. 상품 10개를 결제 하기 위해 동시에 10000명이 접근했을 때, 10명만 결제가 완료 되도록 한다.
2. 성능

Synchronized

• throughput : 81.3/sec

하나의 서버를 두고 하나의 트랜잭션에 대해서만 동시성을 보장할 수 있다. 하지만, 서버가 여러대일 경우에는 동시성 보장이 되지 않는다. MSA 환경에서는 scale out을 해야하기 때문에 사용할 수 없다.

DB Lock

• throughput : 150/sec

synchronized에 비해 굉장히 빠르다. 하지만, 분산 DB 환경에서는 사용할 수가 없다.

분산락

• throughput: 66.1/sec

분산락은 MSA와 같은 분산 DB 환경에서 동시성을 보장해주는 장점이 있다. 하지만, 기본적으로 외부 서버에 API 요청을 자주 하기 때문에, 네트워크 지연으로 인한 오버헤드가 크다. 따라서 성능이 잘 나오지 않는다.

분산락 + 캐시

• throughput: 82.9/sec

• 분산락 사용만으로는 성능이 너무 낮기 때문에, 이를 보완하기 위해서 redis를 캐시로 사용하였다.

• 캐싱 전략: write back

• 이유: 재고를 매번 수정해야 하고, 캐시의 값으로만 재고를 조회하기 때문에, DB에 빠른 동기화는 필요하지 않다.

• 분산락만 사용했을때보다 25.42%의 성능 증가를 보였다.

RuntimeException을 상속하는 자식 클래스를 생성해 주었다.

예외의 종류

먼저, 예외에 대해서 살펴보자.

Java에서 예외는 Error,RuntimeException,OtherException으로 나눌 수 있다.

Error: JVM, 하드웨어 등 시스템에 문제가 발생했을때 나타나는 에러 RuntimeException: 컴파일러가 예외 체크 하지 않음.(unchecked Exception), 실행 단계에서 확인 OtherException: 컴파일러가 예외 체크 함.(checked Exception)

checked Exception 같은 경우는 반드시 예외 처리를 해줘야 하고, unchecked Exception은 꼭 예외처리를 해줄 필요는 없다.

checked Exception

• FileNotFoundException
• ClassNotFoundException

unchecked Exception

• ArrayIndexOutOfBoundsException
• NullPointerException

그렇다면, unchecked Exception에서 예외 처리를 강제하지 않는 이유는 뭘까??

public class Test{
    public static void main(String[] args){
        int[] list = {1,2,3,4,5}
    }
}

일반적으로 배열을 선언하는 코드이다. 만약, RuntimeException인 ArrayIndexOutOfBoundException이 강제처리를 해야하는 예외라면, 다음과 같이 예외 처리 해야 한다.

public class Test{
    public static void main(String[] args){
        try{
            int[] list = {1,2,3,4,5}
        }catch(ArrayIndexOutOfBoundException e){
            e.printStackTrace();
        }
    }
}

이렇게 모든 코드마다 번거롭게 예외처리를 해주어야 한다. RuntimeException은 보통 개발자들의 실수로 생기는 예외이기 때문에 강제 하지는 않는다.

예외 발생 시 트랜잭션 처리

더 나아가서, 예외 발생 시 트랜잭션 처리에 대해서 생각해보자.

checkedException

• 컴파일 단계에서 확인 하기 때문에, 무조건 예외 처리를 해줘야 하며, 예외 발생시에도 roll-back 되지 않는다. 즉, transaction이 commit까지 완료된다.

uncheckedException(RuntimeException)

• 실행 단계에서 확인 하기 때문에, 예외 처리를 해주지 않아도 되며, 예외 발생시 roll-back 해준다.

RuntimeException 상속 예외 클래스 생성 이유

위에서 설명한 내용을 토대로, RuntimeException을 선택한 이유를 들자면 다음과 같다.

• 실행과정에서 일어나는 에러이다. 일어날 수도 있고, 일어나지 않을 수도 있다.
• 예외 발생 시 roll-back이 된다.

구현 과정

LORException 클래스 생성

ErrorCode를 필드로 가지는 LORException을 생성하였다.

@Getter
public class LORException extends RuntimeException{
    private final ErrorCode errorCode;

    public LORException(ErrorCode errorCode){
        this.errorCode = errorCode;
    }
}

ErrorCode 클래스 생성

LORException의 필드인 ErrorCode는 다음과 같이 구성했다.

@Getter
public enum ErrorCode {
    NOT_EXIST_PHONE_NUMBER("존재하지 않는 핸드폰 번호"),
    ALREADY_EXISTS_USER("이미 있는 계정"),
    PASSWORD_NOT_MATCHED("일치하지 않는 비밀번호"),
    FAIL_TO_DELETE("유저 정보 삭제 실패"),
    FAIL_TO_DELETE_REVIEW("리뷰 삭제 실패"),
    PHONE_NUM_DUPLICATED("핸드폰 번호가 이미 존재합니다."),
    NO_SESSION("로그인을 하지 않았습니다."),
    NO_EXIST_STORE("조회할 store가 존재하지 않습니다."),
    NOT_EXIST_REVIEW("존재하지 않는 리뷰"),
    NOT_EXIST_MEMBER("존재하지 않는 회원"),
    NOT_EXIST_REPORT("존재하지 않는 신고내역"),
    WRONG_MEMBER_OR_STORE_ID("member id 혹은 store id가 잘못 되었습니다."),
    NO_WISHLIST("조회할 위시리스트가 없습니다."),
    RECEIPT_ERROR("영수증 인식 오류"),
    FAIL_TO_CREATE_STORE("가게 생성 오류"),
    DUPLICATE_REVIEW("이미 해당 가게에 리뷰를 작성함"),
    NOT_SUPPORT_AREA("지원하지 않는 지역"),
    NO_EXIST_PRE_RANKING("이전 시즌 랭킹에 해당 가게가 없습니다."),
    BLANK_PHONE_NUMBER("핸드폰 번호를 입력해주세요."),
    WRONG_FORMAT_PHONENUMBER("잘못된 형식의 전화번호 입니다.");

    private final String message;

    ErrorCode(String message) {
        this.message = message;
    }
}

여러 상황에 대한 오류를 세분화하여, 개발 단계에서 API test시 오류를 한눈에 파악하기 위해서 enum type에 message도 추가하였다.

LORException 발생시 핸들링

@ControllerAdvice
public class GlobalExceptionHandler {
    @ExceptionHandler(LORException.class)
    public ResponseEntity<ErrorResponse> handle(LORException ex) {
        final ErrorCode errorCode = ex.getErrorCode();
        return new ResponseEntity<>(new ErrorResponse(errorCode, errorCode.getMessage()), HttpStatus.BAD_REQUEST);
    }

    @Data
    public class ErrorResponse {
        private final ErrorCode errorCode;
        private final String message;
    }
}

@ControllerAdvice

@ControllerAdvice는 예외 처리가 발생했을 경우, 이를 핸들링 하기 위해 사용한다. 구현된 내용을 살펴보면,

@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Component
public @interface ControllerAdvice

• @component가 있는 것으로 봐서는 빈으로 등록되어 사용된다는 것을 알 수 있다.

• @Target은 annotation을 적용할 대상을 결정한다. @ControllerAdvice의 어노테이션 대상은 타입(클래스, 인터페이스, Enum)이다. @Target에 들어가는 ElementType을 살펴보자.

  @Target(ElementType.ANNOTATION_TYPE) : 어노테이션  @Target(ElementType.CONSTRUCTOR) : 생성자  @Target(ElementType.FIELD) : 필드(멤버 변수, Enum 상수)  @Target(ElementType.LOCALVARIABLE) : 지역변수  @Target(ElementType.METHOD) : 메서드  @Target(ElementType.PACKAGE) : 패키지  @Target(ElementType.PARAMETER) : 매개변수(파라미터)  @Target(ElementType.TYPE) : 타입(클래스, 인터페이스, Enum)  @Target(ElementType.TYPE_PARAMETER) : 타입 매개변수(제네릭과 같은 매개변수)  @Target(ElementType.TYPE_USE) : 타입이 사용되는 모든 대상

• @Retention은 해당 어노테이션의 life cycle을 결정한다.

  @Retention(RetentionPolicy.SOURCE) - 소스코드(.java)까지 남아 있는다. @Retention(RetentionPolicy.CLASS) - 클래스 파일(.class)까지 남아 있는다. @@Retention(RetentionPolicy.RUNTIME) - 런타임까지 남아 있는다.

• RetentionPolicy.SOURCE는 소스코드 까지는 남아 있다가 컴파일 시점에 어노테이션 정보가 모두 사라진다. 그렇다면, 왜 필요할까? 예시로,롬복의 Getter/Setter를 생각해보자. 이 경우에는 롬복이 직접 바이트 코드를 생성해서 넣어주기 때문에, 굳이 바이트코드에 어노테이션 정보가 들어갈 필요가 없다.

• RetentionPolicy.RUNTIME는 런타임에도 어노테이션 정보를 뽑아 쓸 수 있다는 의미이다. 스프링에서 예를 들자면, @Controller, @Service,@Autowired등이 있다. 이들은 스프링 컨테이너가 실행중인 시점에 컴포넌트 스캔을 해야하기 때문에, 런타임 시점까지 살아 있어야 한다.

• RetentionPolicy.CLASS는 클래스 파일(.class)까지 어노테이션이 살아있다. 즉, 바이트 코드까지는 살아 있지만, 런타임 시점에 수명을 다한다. 근데, 이게 왜 필요할까? 외부 라이브러리를 사용하는 경우를 예로 들 수 있다. 라이브러리를 다운 받게 되면, .jar 형태로 다운 받게 된다. .jar 파일은 .class 파일로 구성되어 있다. CLASS 정책을 사용하게 되면 .class 파일에서도 어노테이션이 유지되기 때문에, 해당 어노테이션을 확인하거나 사용할 수 있게 된다. 한 가지 예를 더 들어보면, 우리가 사용하는 IDE가 어노테이션 기반이라면, CLASS 정책을 사용해야만, 해당 기능들을 사용할 수 있게 된다.

• @Documented은 javadoc 파일에 추가시킬지에 대한 여부를 결정한다.

정리하자면, @ControllerAdvice는

• class,interface,enum을 대상으로 하는 어노테이션이다.
• Runtime까지 어노테이션의 life cycle이 유지된다.
• javadoc에 포함된다.

@ExceptionHandler

@ControllerAdvice
public class GlobalExceptionHandler {
    @ExceptionHandler(LORException.class)
    public ResponseEntity<ErrorResponse> handle(LORException ex) {
        final ErrorCode errorCode = ex.getErrorCode();
        return new ResponseEntity<>(new ErrorResponse(errorCode, errorCode.getMessage()), HttpStatus.BAD_REQUEST);
    }

    @Data
    public class ErrorResponse {
        private final ErrorCode errorCode;
        private final String message;
    }
}

@ExceptionHandler(LORException.class)는 LORException이 발생 했을때, 메서드가 실행될 수 있도록 해준다.

@ExceptionHandler의 내부는 다음과 같다.

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface ExceptionHandler {

    /**
     * Exceptions handled by the annotated method. If empty, will default to any
     * exceptions listed in the method argument list.
     */
    Class<? extends Throwable>[] value() default {};

}

설명을 읽어보면, 주석 처리된 메서드에 의해 핸들되는 예외 처리이며, 만약 비어 있으면, 모든 예외가 기본 값으로 처리된다고 되어 있다.

즉, 예외 클래스를 지정하면, 해당 예외에 대해서만 메서드가 실행되고, 지정하지 않으면, 모든 예외에 대해서 메서드가 실행된다는 것을 알 수 있다.

@ControllerAdvice
public class GlobalExceptionHandler {
    @ExceptionHandler(LORException.class)
    public ResponseEntity<ErrorResponse> handle(LORException ex) {
        final ErrorCode errorCode = ex.getErrorCode();
        return new ResponseEntity<>(new ErrorResponse(errorCode, errorCode.getMessage()), HttpStatus.BAD_REQUEST);
    }

    @Data
    public class ErrorResponse {
        private final ErrorCode errorCode;
        private final String message;
    }
}

LORException이 발생하면, 발생한 예외 객체 를 handle 메서드 의 파라미터에 주입 시킨다. 이후, 해당 예외 객체를 가지고, errorCode와 메세지 정보를 가져온 후, ErrorResponse 클래스의 새로운 객체를 생성한다.

ResponseEntity의 첫번째 파라미터는, HttpBody를 나타내고, ErrorResponse 객체를 가진다. 두번째 파라미터는 ,HttpStatus의 파라미터로 BAD_REQUEST 즉, 404에러를 발생시킨다.

정리하자면,

1. RuntimeException을 상속하는 LORException 클래스를 생성한다.
2. @ControllerAdvice 와 @ExceptionHandler를 통해 LORException이 발생할 경우 에러 메세지를 보내는 ResponseEntity를 생성한다.

출처

• https://jeong-pro.tistory.com/234 [기본기를 쌓는 정아마추어 코딩블로그:티스토리]
• https://ittrue.tistory.com/160 [IT is True:티스토리]

해시 충돌을 방지하기 위해 open addressing과 seperate chaining 방식을 사용한다. open addressing은 해시 충돌이 발생했을때, 비어 있는 주변 인덱스를 찾아 우회하는 방법이고, seperate chaining은 해시 충돌이 발생했을때, 같은 인덱스에서 linkedList로 관리한다. 자바에서는 아래 그림과 같은 seperate chaining 방식을 사용하고 있다.

출처: https://www.digitalocean.com/community/tutorials/java-hashmap

추가로, linkedList의 node가 8개 이상이 되면, red black tree 형태로 관리하게 된다.

ArrayList는 주소 공간이 쭉 나열되어 있는

배열과 같은 형태이지만, 크기를 동적으로 할당 할 수 있다는 장점이 있다.

조회

원하는 데이터에 무작위로 접근할 수 있어서 조회 성능이 좋다.

시간 복잡도: O(1)

추가

맨뒤가 아닌 곳에 추가 하기 위해서는 추가 하고나서 추가한곳보다 뒤에 있는 배열은 한칸씩 다 뒤로 밀어야 한다.

맨뒤가 아닐 경우 시간 복잡도: O(n)

맨 뒤일 경우: O(1)

삭제

추가와 마찬가지로 맨 뒤가 아니라면 삭제 한 뒤 모두 앞으로 땡겨줘야 한다.

맨뒤 값 삭제: O(1)

나머지 : O(n)

LinkedList

LinkedList는 각 node마다 앞,뒤 노드의 주소 값을 가지고 있어서, 내부 적으로 연결 되어 있고, 순차적으로 접근하게 되어 있다.

조회

연결리스트는 맨 앞에서부터 순차적으로 탐색하게 되어 있기 때문에

시간복잡도: O(n)

추가

추가하려는 위치를 맨 앞에서부터 하나씩 탐색해서 가야 하므로, 맨 앞이라면 O(1)

뒤로 간다면 O(n)이 된다.

삭제

추가와 마찬가지로 삭제하려는 데이터가 맨 앞이면 O(1), 아니라면 O(n)이다.

결국 연결리스트는 추가, 삭제 할때도 탐색으로 인해 시간복잡도가 생긴다.

@Test
    public void findMembers() {
        for (int i = 1; i <= 5; i++) {
            Member m = memberRepository.save(new Member("member" + i));
        }

        for (int i = 1; i <= 5; i++) {
            Team t = teamRepository.save(new Team("team" + i));
        }
        //영속성 컨텍스트를 비워준다.
        em.flush();
        em.clear();

        List<Member> members = memberRepository.findMembers();

        for (Member member : members) {
            System.out.println("member = " + member);
        }

    }

Member entity의 id가 1,2,3,4,5가 나오고

Team entity의 id가 6,7,8,9,10이 나왔다.

왜 다른 엔티티인데 각자 1,2,3,4,5를 갖는게 아니지?? 하고 검색해 보았다.

문제는 identity 전략이었다.

@Id
    @GeneratedValue
    @Column(name = "member_id")
    private Long id;

이렇게 사용하고 있었는데, 전략상 Auto는 엔티티가 만들어지는 순서대로 id가 증가한다.

해결 방법으로 전략을 IDENTITY로 바꿔주었다.

@Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    @Column(name = "member_id")
    private Long id;

join : 연관된 객체를 select하지 않고 주체만 select한다.

fetch join: 연관된 객체까지 select 한다.

따라서, 검색 조건에만 필요하고 데이터가 필요 없다면 join 데이터까지 필요하다면 fetch join을 쓰면 된다!

자세하게 들어가 보겠다.

//Member entity
@Entity
@Getter
@Setter
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@ToString(of = {"id", "username", "age"})
public class Member {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    @Column(name = "member_id")
    private Long id;
    private String username;
    private int age;

    public Member(String username, int age, Team team) {
        this.username = username;
        this.age = age;
        if (team != null) {
            changeTeam(team);
        }
    }

    public Member(String username, int age) {
        this.username = username;
        this.age = age;
    }

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "Team_id")
    private Team team;

    public Member(String username) {
        this.username = username;
    }

    public void changeUserName(String username) {
        this.username = username;
    }

    public void changeTeam(Team team) {
        this.team = team;
        team.getMembers().add(this);
    }


}

@Entity
@Getter
@Setter
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@ToString(of={"id","name"})
public class Team {
    @Id
    @GeneratedValue
    @Column(name = "Team_id")
    private Long id;
    private String name;
    @OneToMany(mappedBy = "team")
    private List<Member> members = new ArrayList<>();

    public Team(String name) {
        this.name = name;
    }
}

//MemberRepository
@Query("select m from Member m join m.team t")
    List<Member> findMembersWithTeam();

이렇게 Member와 team이 다대일로 매핑 되어 있다.

이때, Member 객체를 Team을 join해서 조회 해보자.

@Test
    public void findMembers() {
        Member member1 = new Member("member1", 10);
        Member member2 = new Member("member2", 10);
        Member member3 = new Member("member3", 10);

        memberRepository.saveAll(Arrays.asList(member1, member2, member3));

        Team team1 = new Team("team1");
        Team team2 = new Team("team2");
        Team team3 = new Team("team3");

        teamRepository.saveAll(Arrays.asList(team1, team2, team3));

        member1.changeTeam(team1);
        member2.changeTeam(team2);
        member3.changeTeam(team3);
        //영속성 컨텍스트를 비워준다.
        em.flush();
        em.clear();

        List<Member> members = memberRepository.findMembersWithTeam();

        for (Member member : members) {
          System.out.println("member.getTeam() = " + member.getTeam());
        }

    }

결과 select member0_.member_id as member_i1_0_, member0_.age as age2_0_, member0_.team_id as team_id4_0_, member0_.username as username3_0_ from member member0_ inner join team team1_ on member0_.team_id=team1_.team_id

select team0_.team_id as team_id1_1_0_, team0_.name as name2_1_0_ from team team0_ where team0_.team_id=?

select team0_.team_id as team_id1_1_0_, team0_.name as name2_1_0_ from team team0_ where team0_.team_id=?

select team0_.team_id as team_id1_1_0_, team0_.name as name2_1_0_ from team team0_ where team0_.team_id=?

//MemberRepository
@Query("select m from Member m join m.team t")
    List<Member> findMembersWithTeam();

왜 join으로 조회했을 때 쿼리가 4번이 나갈까?

(select member 1번, select team 3번)

1번째 쿼리에서는 member들을 조회, 2번째는 member중 1번째의 team을 조회, 3번째는 member중 2번째의 team을 조회, 4번째는 member중 3번째의 team을 조회하게된다. 그리고, 중요한 점은 join은 조회 했을때, join의 주체만 영속성 컨텍스트에 영속되고 join당한 엔티티는 영속되지 않는다. 이 때문에 쿼리를 다시 날리는 것이다.

여기서 fetchtype 'eager' 와 'lazy'의 차이점을 살펴보자면 lazy는 Member를 조회할때, 매핑되어 있는 Team은 proxy객체로 조회하기 때문에 쿼리를 날리지 않고 있는다. 그러다 team객체를 조회하려고 하면 그때서야 쿼리를 날려서 정보를 가져온다. eager는 Member를 조회할때, team도 조회하지만, 쿼리를 따로 날린다. member를 조회하고 나서 조회하다 보니 team도 있기 때문에 team에 대한 쿼리를 또 날린다.

N+1 문제라는 건 내가 날리고 싶었던 쿼리 1과 예상치 못한 쿼리 N개를 의미한다. 위에서 예를 들면, 1번째 쿼리가 1이고, 나머지 2,3,4번째 쿼리가 N인 것이다.

그렇다면 이 문제는 어떻게 해결 할 수 있을까??

이때 나오는 것이 join fetch이다.

@Test
    public void findMembers() {
        Member member1 = new Member("member1", 10);
        Member member2 = new Member("member2", 10);
        Member member3 = new Member("member3", 10);

        memberRepository.saveAll(Arrays.asList(member1, member2, member3));

        Team team1 = new Team("team1");
        Team team2 = new Team("team2");
        Team team3 = new Team("team3");

        teamRepository.saveAll(Arrays.asList(team1, team2, team3));

        member1.changeTeam(team1);
        member2.changeTeam(team2);
        member3.changeTeam(team3);
        //영속성 컨텍스트를 비워준다.
        em.flush();
        em.clear();

        List<Member> members = memberRepository.findMemberJoinFetchTeam();

        for (Member member : members) {
            System.out.println("member.getTeam() = " + member.getTeam());
        }

    }

결과 select member0_.member_id as member_i1_0_0_, team1_.team_id as team_id1_1_1_, member0_.age as age2_0_0_, member0_.team_id as team_id4_0_0_, member0_.username as username3_0_0_, team1_.name as name2_1_1_ from member member0_ inner join team team1_ on member0_.team_id=team1_.team_id

join fetch를 하게되면, member를 영속화 할때 team의 정보까지도 같이 영속화 된다. 따라서 쿼리를 한번만 보내게 되고, n+1 문제가 해결되는 것이다.

위에서 findListByUsername()은 List로 반환하고,

findMemberByUsername은 Member 객체 하나를 반환한다.

만약 두 반환값 모두에서 조회되는 값이 없다면 어떻게 될까??

결론을 먼저 말하자면

• List로 받는다면 null 값이 아니라 빈 객체가 반환되고, members.size()를 찍어본다면 값이 0 이나온다.
• Member 객체로 받는다면 null이 반환된다.

사실 Member 객체가 조회된 값이 없을때, 순수 jpa에서는 NoResultException이 터진다. 하지만 Spring data jpa에서는 Exception을 try-catch로 감싸서 null을 리턴 해주도록 만든다.

null을 리턴해주는 것도 Exception이 터지는 것보다는 좋지만, 더 좋은건 Optional을 사용하는 것이다. optional은 조회값이 없을 때, Optional.empty 로 반환한다.

그리고 Optional에 좋은점은 null일때 이렇게 뒤에 코드를 작성할 수 있다는 것이다.

findMember.orElse()
findMember.orElseGet()

📗 참고로, AAA인 사람을 조회하려고 했는데, 여러 사람이 나온다면, NoUniqueResultException 에러가 터진다. 근데 이 에러는 db마다 다르기 때문에 spring이 spring framework exception으로 변환해서 모든 db에서 사용 가능 하게 해준다. `

jpa에서 OSIV는 API가 끝날때까지 즉, view에 반환할때까지 DB Connection을 가지고 있는것을 말한다. OSIV가 켜져 있으면, Transaction이 끝나도 영속성 컨텍스트가 DB Connection을 붙들고 있기 때문에 lazy loading같은 fetch 전략을 사용가능하다. 하지만, 트래픽이 많을 때는 DB connection을 계속 유지하고 있으면 thread pool의 connection이 모자라 서비스 장애로 이어질 수 있다. 따라서 트래픽이 많은 곳에서는 OSIV를 꺼두어야 한다. OSIV를 끄면, transaction이 끝남과 동시에 DB Conn을 반납하기 때문에 지연로딩은 모두 transaction안에서 처리해야 한다.

OSIV에 따른 처리방법

OSIV가 켜져 있을때는 controller단에서도 지연로딩을 처리할 수 있지만 OSIV가 꺼져 있다면 service단의 한 transaction안에서 지연로딩을 처리하면 된다.

OSIV 설정방법

OSIV는 default가 true이고, 설정하는 방법은 다음과 같다. application.yaml 파일에 설정한다.

spring:
  datasource:
    url: jdbc:h2:tcp://localhost/~/test2
    username: sa
    password:
    driver-class-name: org.h2.Driver

  jpa:
    hibernate:
      ddl-auto: create
    properties:
      hibernate:
        default_batch_fetch_size: 100
        format_sql: true
    open-in-view: false

spring.jpa.open-in-view 에 false라고 설정하면 OSIV가 꺼진다.

file에 들어가는 정보(meta data)

• name
• indentifier : 사람이 file을 맵핑하는것은 name이 될 것이고, 운영체제는 file identifier로 맵핑한다.
• type
• location
• size
• protection/Permission
• time,data,user identification

file Operation

file은 abstract한 data type이다.

• create a file
• write a file
• read a file
• file 내에서 reposition
• delete
• truncate : contents를 지우지만 속성은 유지

file access

• 프로세스는 open file마다 "file pointer"를 가지고 있다.
• read와 written이 어디까지 진행됐는지 위치를 표시한다.
• current position이 file pointer 위치이다.
• read()/write()는 자동적으로 file pointer 위치를 변경한다.
• lseek()은 file pointer 위치를 재조정할 수 있다.

open file table

어느 파일이 몇개나 열려있는지,위치,permission등등을 관리한다.

file descripter(fd) table

• 각 프로세스는 file descripter table을 가지고 있고, 이 fd table은 open file들의 fd를 저장한다.
• 같은 process의 thread들은 fd table을 공유한다.
• fork()로 읽으면 fd table이 복제된다.

  open file들은 fd로 표시된다.

Directories

윈도우에서는 folder 라고도 하지만,원래는 directory이다. directory의 사전적 의미는 어디에 뭐가 있는지 방향을 알려주는 것이다. directory는 사실 folder안에 파일을 담는게 아니라, file이 어디있는지 알려주는 것이다. directory도 파일이고 이 파일이 다른 파일들의 meta data의 정보를 가지고 있는 것이다. 즉 파일의 이름의 위치나 사이즈 등을 가지고 있는 것이다. 실제 파일 데이터는 디스크 상의 데이터 블록에 저장되고, file descriptor를 통해서 파일의 데이터 블록에 접근하여 파일의 내용을 읽거나 쓸 수 있다.

위 그림에서 예를 들자면, root directory에는 directory 형태의 file 3개가 있고, spell이라는 파일을(file id 2) 열어보면 3개의 파일의 meta data가 들어 있다. mail은 directory 형태이고 나머지 2개는 file 형태이다. stat이라는 file을 들어가보면 43번 file id로 찾아가게 되고 이 file id는 file descriptor에 맵핑되어 있어서 해당 fd로 찾아가면 거기에 file data가 저장되어 있다. 그러면 이제 file descriptor를 가지고 write나 read를 하는것이다.

file id -> inod directory entry -> dentry

hard link

directory 하나하나를 dircetory entry라고 하는데 이 directory entry가 file data를 poining 할 수 있다. directory entry에서 해당하는 file id로 link를 건다. 이걸 hard link라고 한다. 한 file을 많은 directory entry가 pointing할 수 있기 때문에 한 file id에 대해 hard link는 여러개일 수 있다.

symbolic link

파일의 경로를 가지고 링크를 건다. directory entry가 hard link 처럼 file id 번호로 링크를 거는게 아니라, 다른 파일의 파일 이름(경로)으로 링크를 건다.
그래서, 해당 경로에 있는 파일이 지워지면 symbolic link로 들어가도 파일을 찾을 수가 없다.

file system 구현

그렇다면 이 파일들을 storage에는 어떻게 저장할 수 있을까?? 위 그림처럼 a.out이나 peng.jpg의 크기가 한 block에 저장하기가 힘들기 때문에 몇개로 나눠서 저장한다. 각 파일의 meta data들은 directory에 저장되어 있고 그 meta data는 실제 파일의 block을 찾아가도록 쓰여있다.

file system 종류

FAT

File Allocation Table directory entry가 16bit면 FAT16 directory entry가 32bit면 FAT32

file directory에 실제 파일의 block들이 어디있는지 적어놔야 하는데, file이 클경우 그걸 다쓸 수 없다. 그래서 FAT에는 해당 file의 시작 Cluster만 적어놨다.

만약, 12,3,11 block에 file data가 나눠서 담겨져 있다면 directory entry에서는 FAT 12번으로 가라고 써있고, FAT 12번으로가면 3이 써져 있어서 3으로 이동하고 11로가면 EOF가 써져있어서 file의 마지막 부분임을 알려준다.

그러면 파일을 저장할때는?? text.c라는 파일을 저장하려고 할때도 FAT을 뒤져본다. 아무것도 저장되어 있지 않은 entry(00)이 있으면 거기에 저장하고 다음번으로 갈 entry 번호를 적어 놓는다. 마지막이면 EOF를 적는다.

파일을 지울때는, FAT은 hard link를 지원하지 않는다. 따라서 지울때도 똑같이 번호를 따라가서 00으로 만든다.

FAT은 간단한 임베디드 시스템에 많이 사용된다. (디지털 카메라, 블랙박스...)

EXT4

unix 계열에서 많이 사용된다. SSD 파일 시스템에 맞춰서 만들어졌다.

other file systems

• microsoft:NTFS
• apple:HFS/HFS+ -> APFS
• android:F2FS
• redhat:XFS
• btrfs,LFS,RAMFS,...

Traditional FileSystem Internals

Hard Disk Drives(HDDs)

자석을 이용해서 데이터를 저장한다. 자석이 붙어있는 원판이 돌아가면서 헤더가 자석의 방향을 관측하고 0과 1을 쓴다.

• Seek time: 데이터를 찾기 위해 헤드가 디스크 표면에서 이동하는 데 걸리는 시간이다. 이동 거리가 짧을수록 seek time은 짧아진다. 하드 디스크 드라이브의 성능이 좋을수록 seek time은 낮아진다.

• Rotational delay: 회전 지연 시간은 하드 디스크 드라이브가 데이터를 찾기 위해 디스크가 회전하는 데 걸리는 시간이다. 회전 속도가 높을수록 rotational delay는 짧아진다. 일반적으로, 하드 디스크 드라이브는 초당 5400~15000회 회전한다. 모터를 빨리 돌린다는 것은 전기도 많이 쓰고 열도 많아지므로, 무조건 빨리 돌리는게 좋은 건 아니다.

SSD

controller도 있고 DRAM도 있다. 이거 자체가 computer라고 볼 수 있다.

NAND Flash Memory cells

평소에는 전류가 잘흐르다가 특정 전압을 주면 floating gate에 전자가 쌓인다. 이렇게 전자가 쌓인다와 안쌓인다로 0과 1을 만들 수 있다. NAND Flash를 쭉 이어붙혀서 구조를 만들었다. 문제는, 입력할때는 하나씩 입력이 되는데, 지울때는 특정 전압을 주어서 전자를 나가게 하기 때문에 전체가 다 지워져 버리는 문제가 생겼다. 그래서 데이터를 읽고 쓰는것은 page 단위로만 할 수 있는데 지우는것은 page들이 모인 단위인 block 단위로만 할 수 있다. contoller는 지울 메모리에 대한 판단을 한다. 사용자가 오랫동안 참조하지 않은 데이터의 주변을 싹 지울때 어떤걸 지울지 판단을 하는것이다.

FTL

• Flash Transition layer
• Hard disk는 특정 sector에 값을 써달라 하면 써주는데, NADN FLash는 읽고 쓰고 지우는게 너무 복잡해졌다. 그래서 file system의 근본적인걸 바꿔야 하는데 그걸 바꾸기는 너무 어려운 문제이다. 그래서 나온게 FTL 이다.
• FTL은 flash memory의 read, write, erase 부분을 read sector, write sector로 바꿔서 file system과 매치가 될 수 있게 해준다.
• SSD에 성능은 사실 FTL이 결정한다고 봐도 무방하다.

(secondary)storage

• main memory가 아닌것들 HDDs,SSDs,USB 등등...
• memory처럼 byte 단위로 읽고 쓰는게 되는게 아니라(word addressable) block단위로만 접근 가능하다.(block addresable)
• cpu가 직접 disk로는 접근 못함. 무조건 memory로 가져와야 한다.

김씨가 ATM기에서 돈을 인출하려고 한다.

인출할 수 있는 ATM에 프로그래밍 되어 있는 코드는 다음과 같다.

int withdraw(account,amount)
{
    balance = get_balance(account);
    balance = balance - amount;
    set_balance(account, balance);
    return balance;
}

김씨가 20만원이 있었는데 5만원을 뺐다. 위에 코드대로라면, 잔액을 조회하고, 잔액에서 인출할 금액을 빼서 잔액을 다시 업데이트 해준다. 문제는 ATM기가 하나만 있는게 아니라 여러개가 있다는 것이다. 만약에 2개의 ATM기에서 동시에 같은 통장에서 돈을 인출한다면 어떻게 될까??

위에 코드는 어떠한 상황이냐면, 잔고가 20만원인 상태에서 5만원을 A atm기에서 인출을 했는데 set_balance에서 업데이트 되기 직전에 B atm기에서도 5만원을 인출을 한 것이다. 아직 A에서 업데이트 하지 않았기 때문에 잔고는 줄어들지 않은 상태이고 B에서 5만월을 인출해 15만원이 업데이트 되었다. 문제는 A에서도 balance 값이 15만원이라 두 atm기에서 5만원씩 뺐는데도 최종적으로 15만원이 잔고로 남았다. 이러면 돈을 계속 복사할 수 있기 때문에 큰 문제가 될 것이다. 더 심각하게는, 만약 A atm기에서 1만원만 빼고, B에서 20만원을 뺐다. 그러면 결과적으로는 잔고가 19만원이 남게 된다. A atm기의 balance 변수가 overwrite 되버리기 때문이다.

이렇게 thread가 동시에 shared resource에 접근을 해서 조작했을때 문제가 발생한것을 race condition이 발생했다고 한다.

critical section

shared resource에 접근하고 수정하는 코드를 critical section이라고 한다. critical section에 thread들이 동시에 접근하게 되면 race condition이 일어난다.

int withdraw(account,amount)
{
    balance = get_balance(account);
    balance = balance - amount;
    set_balance(account, balance);
    return balance;
}

balance라는 global variable을 고치려고 동시에 접근할 수 있기 때문에, 이 파트가 critical section이 된다.

Synchronization

그렇다면 ATM a에서 돈을 다뽑고 프로그램이 끝날때까지 기다리고 ATM b가 뽑게하면 되지 않겠느냐 라는 생각을 할 수 있다. 그게 맞다. 이렇게 하면 critical section에서 race condition이 일어날 가능성을 차단할 수 있다. 이렇게 막는것을 Synchronization이라고 할 수 있다.

Locks

그러면 어떻게 synchronization할 수 있을까? 바로 Locks 자료구조를 이용하면 된다. resource를 한번에 한 process만 사용할 수 있게 하는 것이다.(mutual exclusion) 이 lock 자료구조는 두가지 함수를 제공한다.

• void acquire() :lock이 free될때까지 기다렸다가 잡는다.
• void release() :unlock하고, acquire()를 기다리고 있는 thread를 깨운다.
• lock은 처음에는 free하다.
• free 상태의 lock을 acquire하면 lock을 얻을 수 있고, lock이 할당되어 있는 상태에서 다른 process가 acquire() 하면 lock 잡고있는 process가 release 할때까지 기다려야 한다.
• critical section에 들어가기전에 acquire()를 호출하고, critical section을 지나고 나서 release()를 호출한다.

thread T1에서 lock을 잡고실행하고 있었는데, thread T2가 acquire()하려고 했다. 하지만 T1이 lock을 아직 release 하지 않았기 때문에 T2는 대기하게 된다. 그다음 T1도 마찬가지로 T2가 release 하기 전까지 대기하게 된다.

결국 정리하자면, mutual exclusion을 제공하는 lock을 사용해서 critical section을 보호해서 race condition이 일어나지 않게 했다.

Locks의 요구사항

Correctness

• mutual exclusion : critical section에 한번에 한 thread만 접근할 수 있다.
• progress: 아무도 resource를 쓰지 않고 있다면 아무나 쓸수 있게 해줘야 한다.
• bounded waiting: resource를 사용하고 싶을때 기다리다보면 언젠간 자기 차례가 온다.

Fairness

• 각 thread는 lock을 얻을때 공정한 기회를 얻는다.

performance

• 경쟁상대가 있을때와 없을때 lock에 대한 time overhead
• lock의 종류(spin lock, busy waiting)에 따라 달라진다.
• critical section이 크고 자주 실행될수록 lock의 사용빈도가 높아지고, lock의 overhead가 높아지게 된다.

  lock의 알고리즘

  Peterson's Alogorithm

  

turn을 두어서 어떤 thread가 쓸것인지 결정한다. interested는 0과 1만 있기때문에 1-my_id를 하면 상대방의 인덱스번호가 된다. 들어오면서 자신을 true로 만들어서 resource를 사용할 의사를 내비친다. 그리고 turn은 other를 해주어서 상대방이 먼저 사용할 수 있게 양보한다. while문으로 들어오면 상대방이 사용할 마음이 있고, turn도 상대방 턴이면 나는 while문을 계속 반복하면서 대기하고, 상대방이 둘중하나라도 아니게 된다면 내가 lock을 잡게 된다. 어쨌든 둘중 하나의 task만 들어올 수 있게 되고, 빈 리소스에 대해서 두 task가 대기하는 일은 없게 된다. 따라서 mutual exclusion(critical section에 한번에 하나의 thread만 들어옴), progress(resource가 free라면 thread가 lock을 가짐), bounded watiting(resource를 사용하고 싶을때 기다리다보면 언젠간 자기 차례가 온다.)

lock을 구현하기 위해 hardware로 도와줌

Test-And-Set

하드웨어가 새로운 값으로 업데이트해주고, 원래있던 값을 가져오는것을 한번에 처리해준다.

기존 spinlock에다가 Test-And-Set을 적용시켰다. 만약 thread A,B가 있다고 한다면, 기존에 lock은 0이었고, thread A가 lock에 접근하면 lock을 1로바꾸는 동시에 원래있던 값인 0을 리턴한다. 리턴값이 0이므로 while문을 빠져나오게 된다. 이상태에서 thread B가 접근한다면 똑같이 lock의 값을 1로 바꾸는데 기존에 1이었기때문에 1을 리턴받아서 while문에 갇혀있게 된다.

threadA가 release를 통해 lock을 0으로 바꾸면 그제서야 thread B가 lock을 1로바꾸고 0을 리턴받으면서 빠져나가게 된다.

소프트웨어로 코드로 구성하면 안되나??라고 생각할 수 있는데

int TestAndSet(int *v,int new){
    int old = *v;
    *v = new;
    return old;
}

이렇게 짜볼수 있다. 하지만 결국에는 critical section이 되어 두 프로세스가 동시에 접근하게 되면 원하는 결과를 도출할 수 없게 된다. 하드웨어가 한번에 처리해줘야만 하는 부분이다.

이렇게 읽고-수정하고-쓰고를 한번에처리해주는 걸 Atomic instruction이라고 한다.

compare-and-swap

• x86, Sparc, 등등에서 지원된다. 당연히 하드웨어에서 일어난다.
• test-and-set 처럼 새로운 값을 쓰고 old 값을 리턴하는건 같지만, 여기에는 expected 값이 추가된다.
• expected는 내가 예상하는 값이다. 코드로 나타내보자면,

  int CompareAndSwap(int *v, int expected, int new){
    int old = *v;
    if(old == expected)
        *v = new;
    return old;
  }
  

void acquire(struct lock *1){ while(CompareAndSwap(&1->held, 0 ,1)); }

old 값이 expected 값과 같다면 new값으로 바꿔주고 old값을 리턴한다.
old 값이 expected 값과 다르다면 old값만 리턴해준다.

한 예로, process가 lock을 acquire할때는 CAS(0,내PID)를 해서 lock이 0이라면 내PID로 바꿔주고 lock을 가져간다. 그러면 다른 process들은 0을 expected하고 있기 때문에 lock이 0이 될때까지 대기하게 된다.

### mut(aul)ex(clusive) lock
busy-wait:resource를 할당받을때까지 계속 두드려본다.

blocked: 다른 thread가 lock을 잡고 있다면 lock을 release해서 깨워줄때까지 blocked 되어서 기다리고 있는다.

#### spinlock
- mutex lock중에서 `busy-wait`를 하는 lock 구현체를 `spinlock`이라고 한다.

✍️장점
- 구현하기가 쉽다.
- critical section이 짧을때 유리하다. critical section이 길다면 계속 두들겨보는건 시간낭비가 된다.
- context switch가 필요없다.

✍️단점
- busy-waiting은 system resource(cpu,memory,etc..) 낭비가 심하다.

### semaphore
- 숫자 값 S를 가진다.
- S개까지 동시에 semaphore를 잡을 수 있다.
- wait() : semaphore를 잡을때 사용, S가 1씩 줄어든다. 당연히 S가 0보다 커야한다.
- signal(): semaphore를 반환할때 사용, S가 1 늘어난다.

#### busy-waiting semaphore 

struct semaphore{ int S; };

void wait(struct semaphore *sem){ while(sem->S <= 0); sem->S --; }

void signal(Struct smaphore *sem){ sem->S++; }

semaphore가 2개인 상태에서
만약 6개의 thread가 동시에 wait에 접근한다면 -4가 되어 버린다. 이 구현으로는 우리가 원하는 대로 구현이 되지 않는다.
이렇게 단순히 카운팅하는 방식으로는 동시에 접근하는 thread들을 관리할수가 없다.
semaphore 자체가 synchronization을 위한 구조체인데 이 semaphore를 구현하기 위해서는 synchronization이 필요한 상황이다.

Mutex lock을 사용해보자.

Mutex M

struct semaphore{ int S; };

void wait(){ retry: M.acquire() if(sem->S <= 0){ M.release() goto retry }else{ sem->S -- M.release() } }

위 코드에서 볼 수 있듯이
먼저 mutex lock을 acquire하고 semaphore가 남아있다면 seamphore를 하나 가지고 lock을 release해주고, semaphore가 없다면 lock을 release 해주고 다시 시도하게 한다.

#### Implementing Blocking Semaphore
busy-waiting semaphore는 cpu와 memory 낭비가 심하기 때문에 이를 대체할 수 있는 semaphore 방식이 필요하다. 

struct semaphore{ int S; struct task *Q; };

void wait(struct semaphore *sem){ sem->S--; if(sem->S < 0){ add_this_task_to(sem->Q); block(); } } void signal(struct semaphore *sem){ sem->S++; if(sem->S <= 0){ P = remove_a_task_from(sem->Q); wakeup(p); } }

blocking semaphore는 들어갈때 토큰(semaphore->S)을 무조건 하나 가져간다. 그리고 나갈때 토큰을 무조건 하나 반납한다. 토큰을 가져갔는데 남아있는게 0보다 크거나 같다면 기다리고 있는 task가 없으므로 그냥 가져가면 되고, 토큰수가 0보다 작다면, 내가 들어가면 안되기 때문에 task가 block되어서 waiting된다.

이 코드도 기본적으로는 돌지 않는다. 왜냐하면 sem->S--이러한 증감 코드는 thread가 동시에 여러개가 들어왔을때, 나올수 있는 경우에 수가 다양하다. 따라서 synchronization 처리를 해줘야한다.

#### semaphore type
✍️Binary semaphore(= mutex)
- semaphore 초기값이 1이다.
- resource에 대해서 mutant exclusive를 보장한다.(한번에 하나만 들어갈 수 있다.)

✍️Couting semaphore
- Semaphore값이 N이다.
- resource를 N개의 thread가 잡게 해준다.
- semaphore가 남아있다면 thread가 접근할 수 있다.

### Monitors
언어 수준에서 synchronization을 제공. 자바에서 사용한다.

member나 method에 synchronized를 붙여주면 한번에 한thread만 접근 가능하다.
컴파일러가 알아서 랭귀지 수준에서 처리해줌

### Pthreads Synchronization
![](https://velog.velcdn.com/images/tg-96/post/458842f0-2b7a-4cde-affc-4b58d6925e5f/image.png)
여러 lock과 semaphore를 구현할 수 있는 함수를 제공한다.
![](https://velog.velcdn.com/images/tg-96/post/f77cbe4e-7a49-4b9e-8eb7-1c026844d52c/image.png)

### Deadlock 
Thread A,B가 있고 mutex m1,m2가 있다.
![](https://velog.velcdn.com/images/tg-96/post/6c2a569e-9077-4d7d-84b7-ce3754c1715f/image.png)
이러한 상황에서 thread A는 m2를 acquire()을 해야지만 m1을 release할 수 있다.
thread B는 m1을 acquire()해야지만 m2를 release할 수 있다.
thread A와 B가 모두 원하는 mutex를 acquire하지 못해 waiting에 빠지게 된다.  
이러한 현상을 `deadlock`이라고 한다.

리소스가 한개이상 필요한 상황에서 잘 발생한다.
리소스를 잡고있는데 추가적으로 더 잡으려고 할때 잡지못했을때, 지금 리소스를 잡고 waiting이 되면 deadlock이 발생할 수 있다.
정리하자면, thread들이 원하는 리소스가 서로에게 dependency에 걸려버린 상황이다. 

### Bounded buffer problem
✍️producer/consumer problem
producer들과 consumer들이 리소스 buffer로 연결되어 있다.
producer에서 buffer로 resource를 넣고, consumer는 buffer에서 resource를 꺼내온다. 하지만 producer와 consumer의 처리 속도는 다르다. producer가 consumer보다 훨씬 빠르다면, buffer는 overflow될 것이고(무제한 버퍼가 될 수는 없다.), 반대상황이라면 consumer는 버퍼에서 꺼내올 resource가 없을 것이다.

### circular buffer
![](https://velog.velcdn.com/images/tg-96/post/9babd91c-6731-4fc3-a8df-7533236ae014/image.png)
- in:data를 넣을 포인터
- out:data를 빼올 포인터
- in에 data를 넣으면 다음 칸으로 in 포인터를 전진시킨다.
- out포인터의 값을 빼면 다음으로 out 포인터를 전진시킨다.

두가지 기능을 구현해야한다.
1. buffer가 꽉차있는데 data를 넣지 않도록하기
2. buffer가 비어있는데 data를 빼지 않도록하기

- option
data가 증가할때마다 count를 센다. 
count가 buffersize와 같아질때 까지만 data를 넣고
count가 0이면 data를 뺄 수 없다.
코드로 구현해보면
![](https://velog.velcdn.com/images/tg-96/post/d6f7dedf-a550-435a-bc30-cba5ba0ed1be/image.png)
하지만 count를 세는것은 여러 쓰레드가 동시에 들어오면 코드가 잘 돌아갈 수가 없다.

1.mutex를 사용해서 critical section을 보호
![](https://velog.velcdn.com/images/tg-96/post/96875ac2-495f-4f1c-8900-449f46a10b9d/image.png)

2.semaphore 이용해서 구현   
![](https://velog.velcdn.com/images/tg-96/post/cf742c8d-e3df-48f5-958d-498f660c1cd5/image.png)
full은 빈공간, empty는 data가 차있는 공간이라고 볼 수 있다.

producer의 wait(&full)와 consumer의 signal(&full)이 대칭되는데, producer에서는 data를 넣었으니까 full을 하나 줄여주고, consumer에서는 data를 빼주는거니까 full을 하나 늘려준다.

empty도 마찬가지로 producer에서는 data를 넣어주니까 signal(&empty)을통해 empty를 늘려주고 Consumer에서는 data를 빼주니까 wait(&empty)를 통해 empty를 빼준다.

이 코드도 잘 돌지 않는다. semaphore가 thread들이 리소스를 N개까지 가져가는건 조절해주지만 그 안에서 thread끼리 resource를 순서대로 잘 가져갈 것이냐는 별개의 문제이다. 즉, semaphore는 동시에 thread가 몇개까지 들어가는지는 보장해주지만, thread끼리 서로 어떻게 상호작용하는지는 관여하지 않는다. 

위 코드에서는 in에 여러 thread가 동시에 접근하게 되면 값을 예상할 수가 없을 것이다. 그래서 이 critical section을 보호해줄 mutex를 사용해야 한다.
![](https://velog.velcdn.com/images/tg-96/post/78cc2ca5-0d8c-44e2-9459-1e8dbd712f5e/image.png)

### Readers-writers Problem
게시판을 만들었다고 해보자. 해당 게시판에 많은 사람들이 동시에 들어왔다가 나갈 수 있다. Reader들은 상관없지만 Reader들과 writer가 겹친다면?? 아니면 writer와 writer가 겹친다면 해당 게시판은 예상할 수 없는 값으로 바뀔 것이다.
따라서 synchronization을 해줘야 한다. reader나 writer나 상관없이 한 사람이 들어가면 lock을 걸어서 다른 사람이 못들어오게 한다면?? 너무 프로그램의 성능이 떨어질 것이다. 따라서 다른 방법을 생각해봐야 한다.
Reader의 개수를 세는 변수를 하나 만들어주고, Reader가 모두 나가면 writer가 접근하게 해준다. 또한 writer가 있을때는 다른 reader나 writer가 접근하지 못하게 lock을 건다. 
![](https://velog.velcdn.com/images/tg-96/post/8bb0fcee-39c7-47e9-896c-40352d7718f6/image.png)

위 그림에서 Reader()를 보자.
`wait(&mutex)`: reader가 들어오면 일단 mutex의 semaphore를 가져와서 다른 사람이 들어오지 못하게 막는다.(nr_reader를 동시에 접근하지 못하게 하기위해)
`nr_reader++` : reader count를 하나 올려준다.
`if(nr_readers == 1)`: reader수가 1이면 
`wait(&rw)` : rw semaphore를 가져가서 rw를 0으로 만들고 writer가 접근하지 못하게 한다.
`signal(&mutex)` : semaphore mutex를 1로바꿔준다.(release해줌)
`do_read()`: 게시판을 읽는다
`wait(&mutex)`: semaphore mutex를 잡아서 다른 사람들이 접근하지 못하게한다.(nr_reader에 동시에 접근하지 못하게 하기 위해서) 
`nr_readers--`: 다읽고 나갈때, reader카운트를 다시 줄여준다.
`if (nr_readers == 0) signal(&rw)` : 안에 reader가 없으면 write가 접근할 수 있게 다시 rw를 1로 바꿔준다.
`signal(&mutex)` : mutex를 1로 바꿔줘서 다른 사람들이 접근하게 해준다.  

void writer()를 보자.
`wait(&rw)`: writer가 들어가면 rw semaphore를 잡고 rw를 0으로 바꿔줘서 reader가 들어가지 못하게 막는다. reader가 들어오면 Reader()에서 wait(&rw)에 걸려서 기다리게 된다.
`do_write()`: 게시판을 작성한다.
`signal(&rw)`: rw를 다시 1로바꿔줘서 reader가 접근하게 해준다.

하지만 이게 잘 동작을 할것인가를 생각해보자.
이런 경우는 성능이 잘 나오고 싶다면 writer가 가끔 들어올때 이득이 많이 있을 수 있는 구조다. writer가 많이 들어오는 경우는 single lock으로 해도 큰 문제가 없을 것이다. 위 그림과 같은 경우는 writer에게 많이 불리하다. 왜냐하면, reader가 먼저들어가면 다른 reader들도 계속 들어올 수 있기 때문에 reader가 0이 안되고 계속 들어오게 된다면 writer가 무제한으로 기다릴 수 있는 상황이 올 수도 있다. 즉, starvation이 발생한다. 

어떻게 고칠 수 있을까??

FIFO를 생각해보자. 만약에 reader가 줄 서있는 상황에서 writer가 들어오고 싶어서 줄을 섰다. 그러면 writer가 들어왔을때부터는 reader들이 들어오지 않고 기다리다가 기존에 있던 reader가 다 나가고 writer가 끝내고 나면 그 뒤에 들어오려고 했던 reader들이 들어오게 하면 된다. 이렇게 되면 writer가 기다려야 되는 시간이 bound 돼서 starvation이 발생하지 않는다.

어떻게 구현할 수 있을까??
reader가 들어올때 count만 하는게 아니라 writer가 누가 기다리고 있는지 봐야되고, 만약 writer가 기다리고 있다면 waiting queue에 해당 reader의 PCB를 대기시킨다. 언제까지 기다리냐면, writer가 자기 일을하고 rw semaphore를 놓을때가지 기다린다.

### Dining Philosophers Problem
![](https://velog.velcdn.com/images/tg-96/post/a3d57978-f352-4316-acbc-eb1bc627b330/image.png)
위 그림을 젓가락 한 개씩 이라고 생각해보자. 한사람이 젓가락 하나로는 밥을 먹을 수없지만, 양쪽에 있는 젓가락을 하나씩 잡으면 두개가 되므로, 밥을 먹을 수 있게 된다.
이렇게 하면 모든 사람이 행복하게 밥을 먹을 수 있게 될줄 알았다. 하지만 현실은 모든 사람이 먹지 못하게 됐다. 왜 이렇게 됐을까?
모든 사람이 자신의 왼쪽 젓가락을 잡고 오른쪽 젓가락을 잡는 규칙이라고 해보자.
모든 사람이 왼쪽 젓가락을 잡았다. 그러고 나서 오른쪽을 잡으려고 했더니 옆 사람들에 의해 오른쪽 젓가락은 이미 다른 사람에게 잡힌 상태이다. 바로 `deadlock`이다.
프로그램을 대입해보면,
프로그램 5개가 리소스가 2개씩이 필요하다. 모든 프로세스가 첫번째 리소스를 잡았는데 두번째 리소스를 잡지 못해서 모두 deadlock이 되어버린 상태이다.
#### solution
이 사람들이 밥을 먹을 수 있게 하는 방법은 무엇이 있을까?
1. 모든 사람들은 양쪽 젓가락을 동시에 잡으려고 한다. 만약 잡았다면 밥을 먹을 것이고, 못잡았다면 밥을 먹지 못한다. 
이 방식은 컴퓨터에서 적용하기는 힘들다. 동시에 리소스를 두개를 잡는다는건 매우 힘든 문제이다.

2. 젓가락을 왼쪽 잡고 오른쪽 잡으려고 시도를 하는데 안되면 다시 모두 내려놓는다. 그러고 나서 다시 왼쪽 오른쪽 순서로 잡으려고 한다. 이렇게 해서 둘다 잡히면 밥을 먹고 안잡히면 반복한다.
이렇게 하면 어쨋든 거의 모든 사람이 먹을 수 있게 된다.(운이 정말 나쁘면 굶을 수도 있다...)
컴퓨터에서는
thread가 리소스를 하나를 잡고 두번째까지 잡으려고 하는데 잡지 못한다면 모든 리소스를 내려놓고 다시 시도한다. 

3. 모든 사람들이 왼쪽을 잡고 오른쪽을 잡는다. 하지만 모든 사람이 옆사람의 젓가락을 기다리다가 결국 맨처음까지 돌아오게 되면 deadlock이 걸려버린다. 이걸 없애고자 첫번째 사람은 왼쪽이 아닌 오른쪽을 잡으려고 한다. 오른쪽은 이미 다른사람이 잡고 있기 때문에 기다리게 되고, 이 과정에서 첫번째 사람의 옆사람이 밥을 먹을 수 있게 된다. 그러면 모든 사람이 결국 밥을 먹을 수 있게 된다.

#### implementation
1. ![](https://velog.velcdn.com/images/tg-96/post/225c806d-a504-485d-bcb6-02cbe43ecdee/image.png)
모든사람이 왼쪽잡고 오른쪽 잡고 먹고 내려놓고를 구현해 놓았다. 하지만 이런 방식은 deadlock에 걸린다. pickup에서 왼쪽을 잡으려고 할때 모두 deadlock에 걸릴것이다.

2.![](https://velog.velcdn.com/images/tg-96/post/d86c6b18-ad9e-4d9a-a4b5-d311a2910fd7/image.png)
모든 사람은 왼쪽잡고 오른쪽 잡지만, 마지막 사람만 오른쪽 잡고 왼쪽 잡는 식이다. 이렇게 하면 deadlock을 해결할 수 있다.

pre-router control plane

Pre-Router Control Plane은 네트워크에서 데이터 패킷을 전송하기 전에 라우터에서 수행되는 제어 작업을 의미합니다. 이러한 제어 작업은 라우터가 제대로 동작하고 네트워크에서 데이터 패킷이 올바르게 전송되도록 보장합니다. 각각의 모든 라우터의 개별 라우팅 알고리즘 구성 요소는 컨트롤 플레인에서 서로 상호 작용하여 포워딩 테이블을 계산합니다.

Pre-Router Control Plane의 기능

1. 라우팅(Routing) 라우터는 라우팅 프로토콜(Routing Protocol)을 사용하여 네트워크에서 최적의 경로를 찾아 데이터 패킷을 전송합니다. 이러한 라우팅 작업은 Pre-Router Control Plane에서 수행됩니다.

2. 스위칭(Switching) 라우터는 스위칭 프로토콜(Switching Protocol)을 사용하여 데이터 패킷을 전송합니다. 이러한 스위칭 작업은 Pre-Router Control Plane에서 수행됩니다.

3. QoS(Quality of Service) 라우터는 QoS 기능을 사용하여 네트워크에서 데이터 패킷의 우선순위를 관리합니다. 이러한 QoS 작업은 Pre-Router Control Plane에서 수행됩니다.

Pre-Router Control Plane은 라우터의 제어 작업을 수행하는 중요한 영역이며, 네트워크의 안정성과 성능을 보장하는 데 중요한 역할을 합니다.

Logical Centralized CP(Control Plane)

Logical Centralized Control Plane은 분산된 네트워크에서 중앙 집중식으로 제어 작업을 수행하는 제어 평면입니다. 이러한 제어 평면은 네트워크의 전반적인 상태를 모니터링하고, 이를 기반으로 네트워크 장비들의 동작을 조정합니다.

Logical Centralized Control Plane은 SDN(Software-Defined Networking)에서 사용되는 기술 중 하나입니다. 이러한 제어 평면은 네트워크 장비들이 데이터 패킷을 전송하기 전에 최적의 경로를 찾아주는 역할을 합니다. 이를 위해 Logical Centralized Control Plane은 네트워크에서 발생하는 데이터 패킷의 전송 정보를 수집하고, 이를 기반으로 최적의 경로를 계산합니다.

Logical Centralized Control Plane은 분산된 네트워크에서 일관된 정책을 적용하기 위해 필요합니다. 이러한 제어 평면은 네트워크 장비들 간의 통신을 단순화시키고, 관리 작업을 효율적으로 수행할 수 있도록 도와줍니다.

Routing 목표

routing은 라우터를 거쳐서 sending host가 receiving host에게 데이터 패킷을 보낼 수 있는 good path를 결정하는 것입니다.

good 이라는 것은 "가장 적은 비용", "가장 빠른 경로","최소 congest"를 의미합니다.

routing은 현재 network 분야에서 10가지 도전과제 중 하나입니다. 최근에는 인터넷 트래픽이 급격하게 증가하면서, 라우팅 알고리즘의 성능이 더욱 중요해졌다.

network Abstract graph model

Routing 분류

global routing algorithm

네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 즉 모든 라우터가 연결 상태와 링크 비용을 알고 있다는 것이다. Link State 알고리즘이 여기에 속하며 주로 다익스트라 알고리즘을 사용한다.

decentralized algorithm

최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 라우터도 모든 링크 비용에 대한 완전한 정보를 갖고 있지 않지만, 각 라우터는 자신에게 연결된 인접 노드에 대한 링크 비용 정보를 알고 있다. 이후 반복된 계산과 인접 노드와의 정보 교환을 통해 목적지까지의 최소 비용 경로를 계산한다. Distance Vector 알고리즘이 여기 속하며 주로 벨만-포드 알고리즘을 사용한다.

static routing algorithm

경로의 변경이 느리고 사람이 직접 링크에 대한 비용을 수정해야 한다. 규모가 큰 네트워크에서 일일이 수정하기 불가능하며 사람이 하기에 역부족이다.

dynamic routing algorithm

네트워크 트래픽 부하나 topology 변화에 따라 라우터가 자체적으로 경로를 바꾼다. 동적 알고리즘은 주기적으로 topology나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다. 동적 알고리즘은 네트워크 변화에 더 빠르게 대응할 수 있지만 경로의 loop나 경로 진동과 같은 문제에 취약하다.

Link state(LS) algorithm

LS 알고리즘은 중앙 집중형 알고리즘에 속한다. 즉 모든 라우터(노드)가 링크(간선)의 비용을 알고 있기 때문에 다익스트라 알고리즘을 이용해 최적의 경로를 계산할 수 있다. 한 노드(source node)에서 다른 모든 노드까지의 최적경로를 계산해 routing table에 저장해 놓는다.

다익스트라 알고리즘

• global 정보를 사용한 알고리즘이다.
• 해당 노드에 대한 forward table을 준다.
• 한 노드에서 모든 다른 노드에 대한 최소 비용 경로를 찾는다.

• c(x,y): node x 에서 y까지 link cost 만약 x에서 y까지 direct link가 없다면 c(x,y) = infinite
• D(v): source로부터 dest v까지 경로의 비용의 현재 값
• P(v): v node로 갈때 전 노드가 어디인지
• N' : 최소 비용으로 갈 경로중 정해진 경로를 포함한 집합

example

아래 그림의 최소 비용 경로를 찾는다.

1. 처음 시작 노드는 u이다. 최소 경로에서 정해진 노드는 u이므로, N' = {u} v까지 가는데 드는 비용 D(v) = C(u,v)와 같으므로 2 최소 경로중 v 바로전 노드 p(v) = u 이런식으로 D(w), D(x)까지 진행해주었다. 노드 y와 z는 u에서 인접해있지 않으므로 무한대이다.

최종적으로 D(v),D(x),D(w)중 가장 cost가 적은 값을 다음 경로로 결정한다. 따라서 N' = {u,x}가 된다. 2. N' = {u,x}까지 결정되어 있는 상황에서 모든 노드에 대한 경로의 cost를 구한다. 그전 step보다 cost가 작아진다면 값을 바꿔준다. 3. 4. 5. 6.

u에서 도착 노드까지 최소 cost를 기록해 놓은 table을 forwarding table 이라고 한다.

LS Algorithm의 complexity

n개의 노드가 주어졌을때

1. 첫번재 iteration

• n개의 노드를 모두 search
• N' 에 있는 최소비용 노드는 한개이다.

2. 두번째 iteration

• n-1 node가 체크된다.(N' 안에 있는 노드는 제외된다.)

3. 세번째 iteration

• n-2 node 체크 ...

결국 n+(n-1)+(n-2)+...(1) = n(n+1)/2 = O(n^2)

LS(Link State) inforamtion Flooding

각 노드는 인접한 모든 노드에 대한 자신의 link state 정보를 가지고 있다. flooding을 사용해서 모든 다른 노드에게 정보를 보낸다.

flooding

• source node에 의해 packet이 모든인접노드에게 보내진다.
• 각 노드로 들어오는 패킷은 들어온 link를 제외하고 모든 link에 재전송된다.
• 복사본의 다수가 도착지에 도착할것이다.

패킷에 적혀있는 숫자는 남은 hop 수이다. 패킷이 노드로 들어가면 들어온 방향의 link를 제외한 나머지 link로 패킷을 복사해서 보내고 hop count를 1 감소시킨다. hop count가 0이되면 패킷은 소멸한다.

example2

Network에서 Link State를 살펴보자. 모든 노드(라우터)는 link state Database를 가지고 있다. 1. F노드에서 인접노드까지의 cost를 보았을때, C-G보다 C-F-G가 코스트가 낮으므로 C-G에서 G를 지워준다. 2. 마찬가지로 C-B-E에서가 C-F-E에서 보다 코스트가 낮으므로 E를 지워준다. 3. 4.

Distance Vector(DV) 알고리즘

DV 알고리즘은 분산형 알고리즘에 속한다. 즉 각 노드는 자신에게 연결된 이웃의 링크의 비용만 알고 있기 때문에 벨만-포드 알고리즘을 이용해 최적의 경로를 계산할 수 있다. DV 알고리즘은 반복적이고 비동기적이며 분산적이다. 이웃끼리 반복해서 정보를 교환해 최적의 경로를 갱신하는 식이다.

Bellman-Ford algorithm

예를 들어서 빠르게 이해해보자. u -> z 의 최소비용 경로를 구해보자.

u의 인접노드는 v,x,w이다.

인접노드들을 거쳐서 u -> z 경로를 구하는 식은 $$c(u,v)+d_x(z)$$ or $$c(u,x)+d_x(z)$$ or $$c(u,w)+d_w(z)$$이다.

$$c(u,v)+d_x(z)$$식을 조금더 자세하게 들여다 보자.

$$d_x(z)$$는 x의 인접노드인 u,v,w,y까지 비용 + 인접노드로부터 z까지 비용이라고 할 수 있다. 이중 가장 작은 값은 $$d_x(z) = c(x,y) + d_y(z)$$이다. $$d_y(z)$$에서 y와 z는 인접노드이므로 c(y,z)로 바꿀 수 있다.

따라서 정리하자면

$$d_u(z) = c(u,x)+c(x,y)+c(y,z)$$ = 1+1+2 = 4이다.

결국 d()에 대해서 recursion이 일어난다고 할 수 있다.

LS와 DV 비교

• message complexity LS: n nodes, E links, O(nE) msgs 보낸다. DV: 인접노드 사이에서만 교환한다.

• speed of convergence(수렴) LS:O(n^2) algorithm은 O(nE) msgs를 필요로한다. DV:수렴(convergence)시간이 다르다.

routing loops 있을수있다. count-to-infinity problem이 있다.

• 만약 라우터가 오작동한다면?

Link State Algorithm에서는 망가진 라우터로부터 정보를 수신하지 못하게 되므로, 해당 라우터와 연결된 링크의 상태를 "링크 다운" 상태로 변경합니다. 그리고 이 상태를 인접 라우터에게 알리기 위해 "LSU(Link State Update)" 메시지를 전송합니다. 이후 인접 라우터는 이 정보를 받아 자신의 라우팅 테이블을 업데이트하게 됩니다.

반면, Distance Vector Algorithm에서는 망가진 라우터로부터 정보를 수신하지 못하더라도, 해당 라우터와 연결된 링크가 "링크 다운" 상태인지를 알지 못합니다. 이 경우, 라우팅 루프가 발생할 가능성이 있으므로, 이를 방지하기 위해 "hold-down timer"라는 메커니즘이 동작합니다. 이 메커니즘은 라우터가 "링크 다운" 상태를 감지하면 일정 시간 동안 정보를 업데이트하지 않도록 하여 라우팅 루프를 방지합니다.

Routing protocol

routing protocol이란?

• 네트워크에서 데이터를 전송하기 위한 경로를 결정하는 프로토콜이다. 라우터 간에 경로 정보를 교환하고, 최적의 경로를 결정하여 데이터를 전송한다.

• Autonomous System(자율 시스템) ✍️인터넷에서 자율 시스템을 말하며, 하나 이상의 IP 주소 범위와 라우팅 정책을 갖는 네트워크 그룹을 의미한다. ✍️AS number: 인터넷에서 자율 시스템을 구분하기 위해 사용되는 고유한 식별자이다. 16bit이다.

routing protocol 분류

• intra-AS routing:IGP(interior gateway protocol) 하나의 자체적인 네트워크에서 라우터 간의 경로 정보를 교환하는 프로토콜입니다. 대표적인 내부 라우팅 프로토콜로는 RIP(Routing Information Protocol), OSPF(Open Shortest Path First), EIGRP(Enhanced Interior Gateway Routing Protocol) 등이 있다.
• inter-AS routing:EGP(exterior gateway protocol) 다른 네트워크와의 연결에서 사용되는 프로토콜. 대표적인 외부 라우팅 프로토콜로는 BGP(Border Gateway Protocol)가 있다.

RIP(Routing Information Protocol)

• IGP(interior gateway protocl)에서 가장 많이 사용되는 것중 하나이다.
• Distance vector algorithm ✍️distance: hop의 갯수 ✍️각 link는 cost가 1이다. ✍️vertor: next hop router
• RIP advertisement

✍️RIP 프로토콜에서 라우터 간에 경로 정보를 교환하기 위해 사용되는 메시지 ✍️RIP Advertisement에는 라우터가 가지고 있는 네트워크의 IP 주소, 서브넷 마스크, 라우터까지의 거리 등의 정보가 포함된다.이러한 정보를 교환하여 각 라우터는 최적의 경로를 결정하고, 데이터를 전송한다. ✍️RIP Advertisement는 주기적으로 교환되며, 기본적으로 30초마다 전송된다. 이 때문에 RIP는 반응성이 떨어지는 프로토콜로 알려져 있다. 최근에는 OSPF나 BGP와 같은 라우팅 프로토콜이 RIP에 대한 대안으로 널리 사용되고 있다. ✍️RIP Advertisement는 UDP를 사용하며 포트번호는 520이다.

routing table processing

• RIP routing table ✍️routed라고 불리는 application level process에의해 관리된다. ✍️UDP 패킷에서 알 수 있고, 주기적으로 반복된다.

RIP-DV operation example

첫번째 표를 보면 라우터 D입장에서의 routing table이다. z가 도착지일때, 다음라우터가 B인 방향으로 가면 hops가 7이었다.

두번째 표를 보면 A입장에서의 routing table이고 z가 도착지일때, 다음 라우터가 C인 방향으로해서 hops가 4였다.

A에서 D로 라우팅 테이블 정보를 주면 즉,A to D advertisement 하면, 세번째 표처럼 D는 A방향으로 갔을때 z까지 hops가 5밖에 안되는 루트를 알 수 있게 된다.

문제점

아래와 같은 상황에서 잘못하면 loop에 걸릴 수 있다.

OSPF(Open Shortest Path First)

• "open"은 public 하게 이용가능하다는 뜻이다.
• link state algorithm을 사용한다. ✍️각 라우터는 LS packet을 자율시스템에 있는 다른 라우터들모두에게 broadcast(floods)한다. ✍️각 노드는 topology map을 얻고, Dijkstra 알고리즘을 사용해서 라우팅 테이블을 계산한다. ✍️OSPF는 Ip를 거쳐서 직접 운반된다. ✍️모든 OSPF message는 인증기능을 사용해서 라우터 간의 교환된 정보의 안전성을 보장한다.
  ✍️여러 개의 경로중에서 비용이 같은 경로들을 모두 사용해서 트래픽을 분산시킬 수 있다. ✍️unicast와 multicast routing을 통합적으로 지원한다. 즉, OSPF는 유니캐스트와 멀티캐스트 라우팅 모두를 지원하는 라우팅 프로토콜이다. OSPF는 라우터 간의 경로 정보를 교환하고, 이를 기반으로 최적의 경로를 결정한다. 이 과정에서 유니캐스트와 멀티캐스트 트래픽을 모두 고려하여 최적의 경로를 결정한다. 따라서, OSPF를 사용하면 유니캐스트와 멀티캐스트 트래픽을 모두 효율적으로 라우팅할 수 있다. ✍️single routing domain내에서 계층구조를 지원한다.이를 통해 대규모 네트워크에서도 효율적으로 동작할 수 있습니다. OSPF에서는 라우터를 Area라는 단위로 그룹화하여 계층 구조를 형성한다. 라우터 간의 정보 교환은 Area 단위로 이루어지며, 각 Area는 자체적으로 SPF(Shortest Path First) 알고리즘을 수행한다. 이를 통해 라우팅 테이블의 크기를 줄이고, 라우팅 정보 교환의 효율성을 높일 수 있다.

OSPF operation

1. Neighbor Discovery: OSPF 라우터 간에 인접 관계를 형성한다. 이를 위해 OSPF는 Hello 메시지를 주기적으로 전송하고, 이를 수신한 라우터끼리 인접 관계를 형성한다.

2.Link State Advertisement: OSPF 라우터는 자신의 링크 상태 정보를 생성하여 Link State Advertisement(LSA)라는 형태로 전파한다. 이를 통해 모든 라우터는 전체 네트워크의 링크 상태 정보를 가지게 된다.

3.Shortest Path First Calculation: OSPF 라우터는 수신한 LSA 정보를 기반으로 SPF(Shortest Path First) 알고리즘을 사용하여 최단 경로를 계산한다.

4.Routing Table Update: SPF 알고리즘을 통해 계산된 최단 경로 정보를 라우팅 테이블에 업데이트합니다.

OSPF Area

• OSPF network는 ` area 라고 부르는 sub-domain들로 나눌 수 있다.
• area는 routing database size를 줄여줄 수 있다.
• 네트워크 계층구조를 만드는게 가능하다.

출처

https://code-lab1.tistory.com/37

single and multithreaded processes

thread들은 address space를 모두 공유한다. 즉, 한쪽 쓰레드에서 데이터값을 바꾸면 다른쪽 쓰레드도 바뀐값을 알 수 있다.

Using thread

pthread_create()는 thread를 만드는 system call이다. thread를 만들어서 나온 thread id를 tid에 담고, 생성된 쓰레드가 hello() 함수를 가리킨다. 만약 전역변수인 values 배열의 어떤 값이 바뀌어도 thread는 address space를 공유하기 때문에 공유된 값들을 알 수가 있다.

thread는 결국 프로세스를 진행시키는것을 말하고, 이것을 abstraction 시키면 마치 바늘이 실을 꿰어나가는것 같다고 해서 thread이다.

single-threaded process: process 하나에 thread가 한개이다. multi-threaded process: process 하나에 thread가 여러개이다.

thread에서의 address space

왼쪽이 single thread, 오른쪽이 multi thread이다. multi thread 같은 경우, PC와 SP가 여러개가 있어서 thread2에서 함수호출이 일어나면 $SP(T2)에서 실행이될것이고, thread1에서 함수호출이 일어나면 $SP(T1)에서 실행이 될것이다. thread는 address space를 공유함으로 한 thread가 다른 thread에서 변경된 값들도 공유할 수 있다.

Processes vs threads

• process가 multiple threads를 가질 수 있다.

• 하나의 thread는 single process에 바인딩 된다.

• process들은 thread들이 실행될 수 있는 컨테이너이다.

  PID, address space, user and group ID, open file descriptors, current working directory etc.

• 모든 thread들은 같은 address space를 공유한다.

• thread는 scheduling 될 수 있는 한 유닛이다.

• process는 static하고 thread는 dynamic하다.

Multi-threading의 이점

• concurrency 만들기가 쉽다. pthread systemcall을 호출하면 thread를 만들어준다.
• multi-core architectures에서 사용하기가 좋다. thread가 없다면 fork를 통해서 process를 하나더 만들고 process끼리 data를 공유까지 해줬어야 하지만 그럴필요가 없다.
• 같은 address space를 공유하기 때문에 resource를 공유하게 된다.
• 프로그램 구조가 간단해진다. 큰 task를 여러 쓰레드로 나눠서 작업할 수 있다. 예를들어 event를 입력을 받는 thread와 처리하는 thread로 나눠질 수 있다.
• 한 thread가 I/O작업을 수행하는 동안 다른 thread는 다른 계산을 처리할 수 있어서 성능이 빨라진다.
• web server에서 처럼 동시에 발생하는 이벤트들을 처리할 수 있다.

Councurrency vs Parallelism

• concurrency: single core로 여러개의 thread를 번갈아가며 처리한다. 마치 동시에 처리되는것 같이 보이게 한다.
• parallelism: 여러개의 코어가 동시에 thread를 처리한다.

parallelism 없이 concurrency를 갖을 수 있다. ex) 스케줄러가 single processor에서 concurrency를 제공한다.

types of Parallelism

예를들어 한 반에서 신상을 조사한다고 하자. 이름과 전화번호를 조사해야 한다.

🤔Data parallelism 조사하는 사람들은 한번에 이름과 전화번호를 물어본다. 한명은 115번까지의 이름과 전화번호를 물어보고 한명은 1630번까지의 이름과 전화번호를 물어본다.

🤔Task parallelism 전체 학생에 대해서 한 사람은 이름만 물어보고 다른 한사람은 전화번호만 물어본다.

User thread - kernal thread

one-to-one

• user thread가 만들어지면 1대1 대응되게 kernal thread가 만들어지는 것이다.
• many-to-one보다 더 concurrency하다.
• 만약에 user thread를 10000개 만들면 kernal thread를 10000개 만들어야 하기 때문에 overhead가 커져서 user마다 thread를 만들 수 있는 제약이 있다.
• e.g. Linux,Windows,Solaris 9 and later

Many-to-one

many user-thread가 single keranl thread에 맵핑되어있다. 운영체제에서 thread를 하나 받아와서 user-level에서 여러개의 thread로 만들어서 돌아가는 형태로도 만들 수 있다. 그래서 user-level에서 mapping 시켜주는 라이브러리로 구현되는 경우가 많다. 하지만 문제가 있다. kerenl에서 넘겨준 thread를 user-level에서 돌려가면서 써야하는데, 어느정도 실행했다가 다음으로 넘기고 스위칭하고, 스케줄하고 하는것을 구현하기가 너무 제약적이다. 만약에, 어느 하나의 thread가 무한루프에 걸려서 다음으로 넘어가지 못한다면 다음으로 스케줄되지 않는 경우도 발생한다. 그래서 어느정도의 concurrency를 만들수는 있지만 어느 하나의 thread가 실행이 잘안되면 다른 thread까지 모조리 망해버릴 수 있어서 좋지는 않다.

이에 더해서 many-to-many도 있다.

Thread Libraries

thread를 사용자가 일일이 생성하고 관리하는 것은 어렵기 때문에 liabrary를 제공한다. 구현방법에는 두가지가 있다.

1. OS가 지원하는 kernel-level library
2. 완전히 user space에 있는 library

pthreads(POSIX Threads)

POSIX는 여러 운영체제 에서의 API의 표준을 정의해준다. 프로그램을 짰는데 어떤 다른 운영체제에서 돌려봤더니 프로그램이 먹통이라면 상당히 난감할 수 있다. 그래서 thread의 표준을 만들어 낸것이 pthreads이다. 구체적으로 구현이 되어 있는 것은 아니고, specification만 정의되어 있다.

Thread Creation/Termination

thread의 헤더를 보면 다음과 같다.

thread 예제코드

pthread_create()에서 runner 함수를 가리키는 thread를 만든다. main thread에서는 pthread_join()에 의해 runner함수가 return 할때까지 기다린다. runner가 전역변수인 sum에 값을 수정한다면 main thread에서도 같은 sum값을 읽게 된다.

fork(),exec()

• exec() exec() system call을 호출하면 해당 process의 메모리는 전부 날라가고 새로운 process에서 exec()만 실행되게 된다. thread 환경에서도 마찬가지다. thread 여러개가 실행되고 있더라도 exec()을 호출하면 thread가 모두 날라가고 single thread로써 exec()을 실행하게 된다.

• fork() fork() system call을 실행하면 모든 process의 메모리를 복사해서 새로운 process를 복제해준다. UNIX에서는 thread 환경에서도 fork()는 똑같이 모든 thread를 복사해서 새로운 process를 만든다. 반면 fork1()은 내가 호출하고자 하는 thread만을 복사해서 새로운 thread를 만든다. LINUX에서는 fork1()만 지원하고 있다. 실행할때는 fork()를 호출하면 fork1()과 같은 기능을 갖는 함수를 호출하게 된다.

Signal handling

process가 실행되다가 signal을 받으면 interrupt가 일어나서 signal handling을 한후에 다시 돌아가서 실행된다. single thread 에서는 signal을 받았을때 처리해야될 대상이 명확한데, thread가 여러개 있다면 어떨까?? 예를들어 control key를 눌렀을때 특정 thread에서 처리하고 싶다거나, I/O만 처리하는 thread를 따로 만들고 싶을수가 있다. 그렇다면 signal을 어떤 thread에서 처리해야할지 어떻게 정할 수 있을까??
어떤 signal에서 어떤 작용을 해야하는지 적어놓은 signal handler는 모든 thread들이 공유하고 있다. 따라서 thread들은 어떤 signal을 받고 받지 않을지를 정해놓는데 이것을signal masking 이라고 한다. masking을 해놓으면 해당 signal을 받지 않는다. 즉, signal masking이 되어있지 않은 thread로 signal handling이 일어나는 것이다.

demand paging(memory를 캐시로 사용)을 효율적으로 하기 위해선 page fault를 줄이는게 가장 중요하다. 왜냐하면 page fault가 일어났을때 disk로 접근하는 시간이 memory 접근 시간보다 훨씬 커서 속도에 큰 영향을 미치기 때문이다.

예를들어, memory access: 200ns, avearge disk access: 8ms 라고 하자. page fault가 일어나는 빈도는 p = page fault rate, 0 <= p <= 1이고, 실제적으로 memory와 disk에 접근하는 시간은 Effective access time = p$$\times$$page fault handling time+ (1-p)$$\times$$memory access 와 같다.

만약 p = 0.001이라면 effective access time = 8.2us이다. momory access time보다 40배가 느려진 것이다.

결국, page fault가 최소로 일어나게 해야 demand paging에 효율이 높아질 수 있다.

Page Replacement

page replacement는 물리 메모리 공간이 부족할때 발생한다. 물리 메모리가 부족하면 사용하던 page를 제거하고 storage에 저장한후에 새로운 page를 PF에 load해야한다. 그렇다면, PF에 있던 어떤 page를 replacement해야 page fault가 최소로 일어날 수 있을까?(page를 찾는데 계속 page fault가 일어나면 효율이 떨어지므로) 결국, 가장 쓸모없는 page를 replacement해야하는데 그렇다면, 가장 쓸모없는 page는 어떻게 정의할 수 있을까?

OPT(optimal page replacement)

Belady's alogrithmr 이라고도 불리는 OPT는 미래에 가장 쓸모없는 page를 replacement 하겠다고 하는 algorithm이다. 3개의 page frame이 있다고 하자. Reference String은 앞으로 참조하고자 하는 것이다. 1번을 참조할때는 PF가 비어있기 때문에 miss이다. 2번을 참조할때는 PF에 2가 없기 때문에 miss이다. 3번도 마찬가지로 3이 없어서 miss이다. 그렇다면 4번을 참조할때는 어떨까?? 4번을 참조하려고 했더니 PF가 꽉차있다. 1,2,3 중에 어떤걸 빼줘야 할지 결정을 할때 Reference String 중에서 가장 참조가 나중에 되는것을 빼준다. 결국 3이 가장 나중에 참조되기 때문에 3대신 4를 넣어주었다.

cache가 충전되어 있지 않은 상태에서 miss나는 것을 cold miss라고 한다.

page fault가 7번이 났다. 이 replacement가 최적의 solution이라고 belady는 생각했다. 하지만 가장 큰 문제가 있다. OPT는 computer가 미래정보를 알고 있다고 가정했지만 computer는 미래정보를 알 수 없다. 그래서 실제적으로 시스템에 사용할 수는 없다. 다만, program이 돌면서 memory 접근한 정보를 받아서 그중에서 최적의 repalcement를 찾을 수는 있다. 그래서 이방식은, replacemnet 정책에 대해서 효율이 있는지 없는지 판단할 때 쓰인다. 그래서 미래정보 없이 어떻게 replacement할 수 있을까를 생각해보았다.

FIFO

먼저 들어온 page가 제일 쓸모없지 않을까?? 라고 생각한 것에서 나왔다. 위에서 볼 수 있듯이, page fault가 일어났을때 가장 먼저 들어온 page 순으로 replacement를 해준다. 위에서는 9번의 page fault가 나왔다. 근데 만약, 더 많은 frame을 사용한다면 어떻게 될까? page fault가 더 줄어들지 않을까?? 그런데 반전이 있다. 4 frames 으로 해보자. page fault가 10번이 나왔다. 충격적인 결과다. 돈을 더써서 frame수를 늘렸지만 오히려 page fault가 증가해버리는 결과가 나왔다.

Belady가 이러한 현상을 보고 연구결과 다음과 같은 결과가 나왔다. 위 처럼 frame수를 증가시켰지만 page fault가 늘어나서 성능이 나빠지는 경우를 Belady anomaly가 있다고 한다.

LRU(Least Recently Used)

그렇다면, 제일 나중에 참조된 page를 빼는것을 어떨까??

MRU(Most Recently Used): 가장 최근 참조. LRU(Least Recently Used): 가장 나중 참조.

가장 최근에 들어온 page를 MRU에 넣고, PF에 있던 값들은 한칸씩 밑으로 내려간다. 결국, LRU에 있던 page는 빠져나가게 된다. 3 frame일때보다 5frame일때가 훨씬 pagefault가 적게 나왔다. 어떻게 다른 alogrithm들과는 다르게 LRU는 frame수가 증가했을때 더 효율적일 수 있을까?? 그림을 잘보면 3개 frame일때 PF안에 있는 page number들이 5 frame일때 PF에 모두 포함되어 있다. stack algorithm이라고 하는데 n개일때의 결과가 n+1일때 결과에 포함되어 있다는 algorithm이다.

FIFO 같은 경우는 stack algorithm이 아닌걸 볼 수 있다.

결국, stack algorithm은 frame이 증가했을때 성능이 더 좋아지는걸 보장하고(Belady anomaly 발생x, e.g. OPT,LRU) 아닌 것들은 frame이 증가해도 성능이 어떻게 변할지 보장되지 않는다라고 결론지을 수 있다..(Belady algorithm 발생,e.g. FIFO)

LRU 사용한 page replacement

VPN이 PFN을 LRU를 사용해서 page replacement하는 방법에는 두가지가 있다.

clock 사용

VPN이 PFN을 참조한 clock을 기록한다.(제일 큰 Clock이 현재 시간이다.) 만약 VPN 7(새로운 page) 이 PFN을 참조하려고 하는데 PF가 남는 자리가 없다. 그렇다면 가장 오래된 clock인 11을 가진 page를 storage로 보내고 replacement해준다.

그런데 이런식으로 했을때 큰 문제가 있다. 가장 작은 clock을 찾으려면 page table을 모두 뒤져봐야 한다. 이건 생각보다 많이 오래 걸린다. 그리고, clock은 결국 비트로 표현해야 하는데, 한계가 있으므로, overflow가 발생할 수밖에 없다. 비트수를 늘려주면 memory를 많이 써야하므로 좋지않다.

access 속도는 빠르지만 victim 찾기가 오래걸린다.

linked list 사용

그래서 생각할 수 있는 방법이 linked list이다. page가 1,2,3,4 page frame에 올라와 있다고 하자. page 3을 참조하면 헤더로 3을 보내면 된다. 만약 새로운 page인 5를 참조한다면 tail을 제거하고 5를 헤더로 넣으면 된다.(victim 찾기에 빠르다.)
근데 문제가 있다.

1. linked list도 참조할때마다 해당 page를 찾기위해서 linked list를 모두 뒤져봐야 한다.
2. linked list 중간에 껴있는 page를 참조하면 헤더로 보내줘야 하는데, 이런식으로 구현하기 위해서는 doubled linked list로 구현해야하고, page를 header로 옮길때 양옆에있는 포인터를 수정해줘야 한다. 수정해야 하는 포인터만 4개다. 그래서 상당히 비효율 적이게 된다.

   victim찾기는 빠르지만 access 속도가 느리다.

LRU Approximation Algorithms

위와 같은 문제들로 인해서 LRU를 구현할때 하드웨어에 도움을 받는다. 완전한 LRU는 아니지만 LRU스러운 algorithm을 만들 수 있다.

Additional-Reference-Bits Alogrithms

위에서 table을 사용해 clock을 기록했던 방식과 비슷한 방식이다. 그렇다면 하드웨어에 어떤 기능을 요구하면 될까? page table entry에서 R은 referenc bit을 해당한다. MMU(하드웨어)가 해당 PTE를 참조했을때 참조했다고 표시를 해주게 된다. 이를 통해서 page table entry가 참조되었는지 안되었는지 쉽게 판별할 수 있다.

위에서 clock을 사용한 page table의 문제는 clock을 어떻게 관리할수 있을지에 대한 것이었다. clock 체크 문제의 어려움을 해결하기 위한게 Additional-Reference-Bit이다.

table에서 clock part를 지우고 ABR(Additional-Reference-Bit),R(Reference) 항목을 추가한다. MMU가 돌면서 참조한 page에 대해서는 R을 1로 업데이트 한다. 일정시간이후에 운영체제가 R의 비트를 그대로 ARB에서 상위비트로 옮기고 R을 0으로 초기화 한다. 그것을 반복한다.

1. 참조한 page R 업데이트
2. ARB 업데이트 이렇게 하다보면 가장 최근에 참조한 page의 ARB가 가장 클것이다.

결론적으로, ARB중 가장 낮은 bit를 가지고 있는 PTE를 빼준다. 문제는 clock처럼 ARB의 가장 낮은 비트가 뭔지 traveling해야 하는데, 하드웨어로 동작하면 쉽고 빠르게 동작할 수 있다.

Second-Chance Algorithm

clock algorithm 이라고도 불린다. 각 알파벳들은 모두 PTE이다. 해당 page가 참조되면 R을 1로 업데이트 해준다. page fault가 일어난다면 시계바늘이 가리키고 있는 PTE의 R을 본다. R이 1이면 0으로 초기화 하고 다음으로 넘어간다. R이 만약 0이면 해당 PTE를 replacement한다. 물론 모든 PTE가 R이1이면 한바퀴 돌고 클리어하고 replacement 하겠지만 대부분은 그러지 않고 victim을 빠르게 찾는다.

Enhanced Second-Chance Algorithm

M은 dirty 혹은 modify로 사용하기 위한 bit이다. 기본적으로 Second-Chance Algorithm과 똑같은 알고리즘인데 여기에 PTE마다 M표시를 추가해준다. M은 해당 page에 write가 되었을경우 MMU(하드웨어)가 체크하고 M을 1로 바꿔준다. page fualt가 일어났을때 M이 1이면 버릴때 디스크에 저장을 해줘야 한다.

page fault가 일어났을때 해당 페이지가 !R,!M 이면 replace하기 가장 좋은 경우이고 !R,M 이면 값을 storage에 써주고 replacement해줘야한다. R,!M 이면 다음으로 바늘이 넘어가고(최근에 참조한적 있어서 다시 참조될것이기 때문) R, M 이면 다음으로 바늘 넘어간다.(최근에 참조되기도 했고, write되었기 때문에 storage에 값을 써주기에 비용이 많이들어서 replace로는 적합하지 않다.)

Counting-based Page Replacement

• Least Frequently Used(LFU) count를 PTE마다 놓고 참조될때마다 count를 하나씩 늘려준다. page fault가 일어나 victim을 선택하게 되면, count가 가장 낮은 page를 replacement 해준다.

하지만 이방법은 count 하는데 메모리를 많이 사용할 수 있다. 예를들어, 8번까지 count하려면 bit가 3개 필요하고 16번하려면 bit가 4개 필요하다. 그리고 overflow가 일어날 가능성이 존재한다. 또한 흐름을 따라가지 못한다. 무슨 얘기냐면, 과거에 많이 참조되어서 200번이 참조되었다고 하자. 그런데 현재 흐름으로는 더 이상 사용하지를 않는 page이다. 하지만 과거에 많은 참조가 일어나 count가 높기 때문에 replacement가 되지 못하고 자리만 차지하고 있게된다.

• Most Frequently Used(MFU) 가장 자주 사용된 페이지를 교체한다.

Paging Virtual Memory

🤔Code(file-backed pages)

• 우리가 프로그램을 실행할때 disk로 부터 메모리로 불러온다.(demand paging)

• code는 file에서부터 불러온다

  file-backed pages: 실행 file에서부터 불러온 page (e.g. code,data) anonymous pages: 실행될때 만들어짐 어디서부터 오거나 하지 않았다. e.g. Heap,stack

• 코드가 실행하면서 바뀌는 경우는 없다. 따라서 code section은 reclaim할때(다시 disk로 돌아갈때) 버리면 된다.

🤔stack,heap(anonymous pages)

• 처음에 reference가 read인 상태에서는 zero page로 맵핑이 된다. 하지만 사용자가 write를 하면 새로운 page를 만들어서 맵핑해준다.
• reclaim을 하려고 하면 값을 swap file에 써놔야 한다.
• heap에 있던 값을 swap file에 써주고 다시 그값을 paging하게 된다면 마치 file-backed page처럼 사용하게 된다. 따라서 해당 heap이 dirty(값이 변경됨)상태가 아니라면 그냥 버리면 되고, dirty면 다시 swap file에 값을 변경해준다.

🤔data

• global variable이 들어간다.
• 프로그램에서 globla 변수 값이 바뀌어도, 프로그램이 꺼지면 다시 초기화 된다. 즉, disk에 변경된 값이 반영되지 않는다.
• 시작은 file-backed로 시작하지만, write가 일어날때 copy-on-write가 일어난다. copy-on-write된 page는 disk로 다시 돌아오면 안된다. 따라서 anonymous 형태로 변경된 값을 swap-file에 써준다.

network layer는 encapsulation을 통해서 address를 datagram header에 추가하고 그 address 주소에 맞는 다른 end system의 network layer까지 올라간다. 다른 end system을 찾아갈때는 routing과정이 필요하다.

🤔routing이란? 패킷을 source에서 dest까지 전달할 경로를 정하는것이다. 어디 end system으로 갈지 정하는거라고 생각하면 된다.

network layer functions

• forwarding: router input으로부터 알맞은 router output으로 패킷을 전달하는것을 말한다.

• routing:패킷을 source에서 dest까지 전달하는 경로를 결정하는것

virtual circuit and datagram networks

• datagram packet 각 패킷은 독립적이기 때문에, 각 패킷은 어느 루트든지 갈 수 있다. 즉, 각 패킷마다 라우팅 결정이 필요하다. 패킷은 비순서적으로 도착할 것이고, 손실되는 패킷도 생길것이다. 그래서 receiver는 패킷을 다시 re-order하고 손실된 패킷을 복구하는것이 필요하다.

✍️no call setup at network layer: 네트워크 계층에서 통화 설정이 없다는 것을 의미한다. 이는 보통 음성 통화나 비디오 통화와 같은 실시간 통신을 처리하는 데 필요한 기능이 없다는 것을 나타낸다. 이 경우, 통화 설정은 애플리케이션 계층에서 처리된다.

✍️routers: end-to-end connection들에 대한 state가 없다. 네트워크 수준의 연결개념이 없다.

✍️패킷은 dest host address를 이용해서 forward한다.

overview of network layer

✍️data plane(데이터 평면)

• 네트워크에서 데이터를 전송하는 데 사용되는 물리적 경로이다. 데이터 평면은 네트워크 장비에서 패킷을 전달하는 데 사용되는 라우팅 및 스위칭 프로세스를 의미한다. 이러한 프로세스는 주로 라우터, 스위치, 방화벽 등의 네트워크 장비에서 처리된다.
• forwarding을 한다.
• local,router별 기능이다.
• router input port에 도착하는 데이터그램이 router output port로 forward하는 방법을 결정한다. ouput 1,2,3중 어디로 갈지 결정

✍️control plane

• 제어 평면은 네트워크 장비 간에 라우팅 및 스위칭 결정을 수행하는 논리적 프로세스이다. 제어 평면과 데이터 평면의 분리는 일반적으로 네트워크의 확장성과 유지 관리를 개선하는 데 도움이 된다.
• network-wide logic
• source host에서 dest host로 어떤 라우터를 거쳐가 가야할지 결정
• control plane 접근방식 두가지 traditional routing algorithm: router에 구현 software-defined networking(SDN): remote server에서 구현

정리하자면, data plane은 어느 output router로 패킷을 내보낼지, control plane은 어느 라우터에서 어느 라우터로 갈지 결정한다.

Pre-Router Control plane

Pre-Control Plane은 네트워크 장비에서 제어 평면과 데이터 평면을 분리하기 전에 사용되던 방식입니다. Pre-Control Plane에서는 각 장비에서 라우팅 프로토콜이 실행되어 다른 장비와 라우팅 정보를 교환하고, 라우팅 테이블을 구축하고 유지합니다.

Pre-Control Plane은 일반적으로 네트워크가 작고 단순한 경우에 사용됩니다. 대규모 네트워크에서는 Pre-Control Plane에서 발생하는 라우팅 정보의 중복, 불일치 및 일관성 문제가 있다.

centralized Control plane

중앙 집중식 제어 평면(Centralized Control Plane)은 네트워크에서 모든 제어 작업이 단일 컨트롤러 노드에서 수행되는 아키텍처이다. 이 아키텍처는 전체 네트워크에서 일관된 정책 및 구성 관리를 제공할 수 있다.

중앙 집중식 제어 평면은 일반적으로 소프트웨어 정의 네트워크(SDN)에서 사용된다. SDN은 네트워크에서 데이터 평면과 제어 평면을 논리적으로 분리하여, 네트워크를 더 유연하고 관리하기 쉽게 만들 수 있다. 중앙 집중식 제어 평면은 SDN에서 중요한 요소 중 하나이다.

Router 내부

router architecture

input port functions

Input Port Function은 스위치나 라우터와 같은 네트워크 장비에서 패킷을 수신하는 포트에서 수행되는 기능이다. 이 기능은 패킷을 처리하여 데이터 평면으로 전달하는 역할을 한다.

Input Port Function에는 다음과 같은 기능이 포함된다.

• 물리적인 신호를 전기 신호로 변환하고, 수신된 패킷을 디코딩하여 데이터 링크 계층에서 사용되는 비트를 추출한다.
• 패킷의 목적지 주소를 확인하고, 목적지 주소를 기반으로 라우팅 결정을 수행한다.
• 패킷의 우선 순위를 확인하고, 우선 순위에 따라 큐잉을 수행한다.
• 패킷을 버리거나 포워딩할 포트를 결정하고, 해당 포트로 패킷을 전달한다.

Input Port Function은 네트워크 장비에서 매우 중요한 기능 중 하나이며, 빠르고 정확한 처리가 요구된다.

Destination-Based Forwarding

🤔 만약 도착 주소 범위가 깔끔하게 나눠지지 않는다면 무슨일이 일어날까?

✍️Destination-based forwarding에서 대상 주소 범위가 깔끔하게 분할되지 않으면 라우팅 결정이 더 복잡해질 수 있습니다. 대상 주소 범위가 균등하게 분할되지 않으면 일부 경로는 더 많은 트래픽을 처리하게 되고, 다른 경로는 덜 사용될 수 있습니다. 이러한 불균형은 네트워크의 성능을 저하시키고, 일부 경로에서 병목 현상이 발생할 수 있습니다. 따라서 대상 주소 범위를 균등하게 분할하기 위해 가장 일반적인 방법은 가장 긴 접두사 일치(Longest Prefix Match)를 사용하는 것입니다. 이를 통해 각 경로가 최대한 균등하게 분할되어 트래픽이 분산될 수 있습니다.

Longest-prefix Match

가장 긴 접두사 일치(Longest Prefix Match)는 라우팅 테이블에서 패킷의 대상 주소와 가장 일치하는 라우팅 엔트리를 찾는 과정이다. 이를 통해 패킷이 올바른 경로로 전달된다.

가장 긴 접두사 일치를 수행하려면 라우팅 테이블의 모든 엔트리를 대상 주소와 비교해야 한다. 이때 대상 주소는 이진 트리 형태로 구성된 라우팅 테이블을 순회하면서 검색한다. 이진 트리에서는 각 노드가 하위 노드의 비트 값과 다음 노드로 이동할 방향을 나타내는 비트를 포함한다.

예를 들어, 대상 주소가 192.168.1.100인 경우, 이진 트리에서 첫 번째 노드는 192로 시작하는 엔트리를 가리키고, 다음 노드는 168로 시작하는 엔트리를 가리킵니다. 이 과정을 대상 주소와 일치하는 노드가 나올 때까지 계속 반복합니다. 가장 긴 접두사 일치를 찾으면 해당 엔트리에 지정된 인터페이스로 패킷을 전달합니다.

Switching Fabrics

Switching rate는 스위치나 라우터와 같은 네트워크 장비에서 패킷을 처리하는 속도를 의미한다. 즉, 장비가 패킷을 수신하고, 처리하고, 전달하는 데 걸리는 시간이다. Switching rate는 일반적으로 패킷의 크기와 처리 방식에 따라 달라진다.

반면, Line rate는 네트워크 링크에서 전송 가능한 최대 데이터 속도를 의미한다. 이는 링크의 대역폭과 데이터 전송 방식에 따라 달라진다. 예를 들어, 1Gbps 링크의 Line rate는 1Gbps이다.

Switching rate는 장비가 패킷을 처리하는 속도를 나타내고, Line rate는 링크에서 전송 가능한 최대 데이터 속도를 나타낸다.

switching rate는 입력 포트 수에 비례해서 증가하지만, Line rate는 입력포트 수와 무관하게 일정하다.

예를 들어, 10개의 입력 포트를 가진 스위치에서 Switching rate가 1Tbps이고, Line rate가 10Tbps이라면, 적절한 속도 비율은 1:10이다. 하지만, 입력 포트의 수가 100개인 스위치에서는 Switching rate가 10Tbps로 증가하지만, Line rate는 여전히 10Tbps이므로 적절한 속도 비율은 1:1이 된다.

🤔Switching rate가 입력 포트의 수(N)에 비례하여 증가하는 이유? 입력 포트가 많을수록 스위치나 라우터에서 처리해야 할 패킷의 양이 많아지기 때문이다. 예를 들어, 4개의 입력 포트를 가진 스위치에서는 4개의 입력 포트로부터 들어오는 패킷을 처리해야 하지만, 8개의 입력 포트를 가진 스위치에서는 8개의 입력 포트로부터 들어오는 패킷을 처리해야 한다. 따라서, 입력 포트의 수가 증가할수록 처리해야 할 패킷의 양이 증가하게 되고, 이에 따라 Switching rate가 증가하게 된다. 하지만, 입력 포트의 수가 증가할수록 Switching rate가 선형적으로 증가하지는 않는다. 이는 입력 포트의 수가 증가할수록 스위치나 라우터에서 처리해야 할 패킷의 양이 증가하지만, 장비의 처리 용량이 한계를 가지기 때문이다.

N개의 input이 있을때,

• 다음과 같이 세가지 타입의 switching fabric들이 있다.

switching via memory

✍️1세대 라우터

• cpu가 직접제어하는 switching을 가지는 컴퓨터

• system의 memory에 패킷을 복사

• momory bandwidth에 의해 속도가 제한된다.

  🤔momory bandwidth? Memory bandwidth는 메모리 시스템에서 데이터를 전송할 수 있는 속도를 나타내는 지표입니다. 일반적으로 초당 전송 가능한 데이터 양으로 측정됩니다. 높은 메모리 대역폭은 시스템의 성능을 향상시키는 데 중요합니다.

• datagram 하나당 2개의 버스가 지나간다.

switching via bus

• shared bus를 통해서 input port memory에서 output port memory로 가는 datagram
• bus connection: switching bus는 bus bandwidth 에의해 제한된다.
• access router, enterprise router의 충분한 속도는 32Gbps bus, Cisco 5600이다.

  액세스 라우터는 일반적으로 인터넷에 연결된 사용자 또는 장치에 대한 로컬 네트워크 연결을 제공하는 데 사용되며, 기업 라우터는 기업의 네트워크 트래픽을 관리하고 보안을 제공하는 데 사용됩니다. 따라서, 충분한 속도는 이러한 라우터가 효과적으로 작동하고 빠른 데이터 전송을 제공할 수 있도록 보장합니다.

switching via Crossbar

• bus bandwidth 한계를 극복할 수있다.
• banyan network,cross bar 그리고 다른 interconnection net들은 multiprocessor에서 processor들에게 연결하기 위해 개발되었다.
• advanced design: 고정된 길이의 cell들로 datagram을 fragmenting하고, fabric을 통해서 cell들을 switch한다.
• Cisco 12000: interconnection network를 통해서 60Gps로 switch 한다.

input port queuing

input port에 있는 datagram이 fabric을 통해서 output port로 이동하려고 하는데, 서로 다른 input port에서 동시에 같은 output port로 접근할때, 둘다 갈 수 없으므로, lower packet은 block된다. 그렇게 되면 block된 queue쪽에서는 delay가 일어나게 된다. queue에 head가 뒤에 있는 다른 queue들을 막아서 delay 되는것을 Head-of-the-Line(HOL) blocking 이라고 한다.

output port queuing

• congestion이 발생했을때, buffer가 부족해진다면 datagram loss가 일어날 수도 있다.

• buffering이 발생하는 경우는, output port의 이동속도보다 더 빠르게 fabric으로 부터 datagram이 도착할경우이다.

• 대기중인 datagram들중에서 scheduling 하는 방법은 priority scheduling이다. 즉, performance가 좋은것을 먼저 scheduling 한다.

• input port에서 fabric을 통해 같은 output port에 도착하는 datagram이 있을때, datagram들을 output port에 buffer에 queue 형태로 저장해 놓는다.

• datagram의 output port로의 도착 속도가 output line speed보다 빠르다면 buffering이 생기게 된다. 만약, ouputport의 buffer가 overflow 된다면 datagram이 손실될 수 있다.

Scheduling mechanisms

scheduling은 link로 보낼 다음 패킷을 선택하는것이다.

FIFO

FIFO(First In First Out)scheduling은 queue에 도착한 순서대로 내보내는 것이다.

discard policy: 꽉 차있는 queue에 패킷이 도착했을때 어떤걸 지워야할까?

• tali drop: 도착한 패킷을 제거
• priority: 가장 priority가 낮은 것을 제거
• random: 랜덤으로 제거

schduling: priority

가장 높은 priority를 가지는 대기중인 패킷을 보낸다. priority에 따라 high priority queue와 low priority queue로 분류된다. 주로 header 정보를 가지고 분류를 하게 된다. IP source/dest, port number등이 그 예이다.

Round Robin(RR scheduling

Round Robin(RR) 스케줄링은 네트워크에서 사용되는 스케줄링 알고리즘 중 하나이다. 이 알고리즘은 여러 대기 중인 작업들 간에 시간을 분할하여 처리하는 방식으로, 각 작업은 일정 시간 동안 CPU 자원을 할당받는다. 이후, CPU는 다른 작업에게 자원을 할당하고, 이전 작업은 대기 상태로 전환된다. 이러한 프로세스가 반복되면서 모든 작업이 처리된다.

네트워크에서 RR 스케줄링은 대부분 트래픽 관리에서 사용된다. 예를 들어, 라우터에서 트래픽을 처리할 때, 여러 개의 패킷이 대기열에 쌓이게 된다. 이때 RR 스케줄링을 사용하면, 각 패킷은 일정 시간 동안 CPU 자원을 할당받아 처리된다. 이러한 방식으로, 모든 패킷이 공평하게 처리된다. 대기열에 쌓인 패킷 중 우선순위가 높은 패킷이 먼저 처리되는 것을 방지할 수 있다.

Weighted Fair Queuing (WFQ)

WFQ에서는 각각의 세션 또는 플로우에 대해 가중치를 부여한다. 이 가중치는 세션 또는 플로우의 중요도를 결정하며, 높은 가중치를 가진 세션 또는 플로우는 더 많은 대역폭을 할당받는다. WFQ에서는 각 세션 또는 플로우에 대한 패킷을 여러 개의 가상 큐에 배치하고, 가상 큐에서 패킷을 균등하게 처리하여 대역폭을 공정하게 분배한다.

WFQ는 다양한 네트워크 장비에서 사용되며, VoIP나 스트리밍 등의 대역폭이 중요한곳에 사용된다.

WFQ는 대부분의 라우터에서 지원되며, 다양한 네트워크 환경에서 사용된다. WFQ는 공정성과 우선순위를 모두 고려하는 효율적인 트래픽 관리 알고리즘이며, 대역폭이 한정된 네트워크에서 유용하게 사용된다.

Internet Protocol(IP)

netowrk layer의 주요 구성요소는 다음 세가지 이다.

• IP protocol
• Routing protocol
• ICMP protocol

IP datagram format

datagram : network layer packet

🤔 hop? 네트워크에서 hop은 라우터나 스위치와 같은 네트워크 장비를 거치는 것을 의미한다. 데이터 패킷이 출발지에서 목적지로 이동할 때, 중간에 거치는 모든 장비를 1 hop씩 거친다고 한다. 예를 들어, 컴퓨터 A에서 컴퓨터 C로 데이터 패킷을 보내는 경우, 만약 패킷이 라우터 B를 거쳐야 한다면, A에서 B까지 1 hop, B에서 C까지 1 hop이 총 2 hops가 거치게 된다. hop 수는 대개 네트워크 성능을 평가하는 데 사용된다. 두 지점 사이의 hop 수가 적을수록, 데이터 전송 속도가 더 빠르고 안정적일 가능성이 높다.

MTU(maximum transmission Unit) link layer frame이 가져갈수있는 데이터의 최대량 경로를 따라 있는 각 링크는 서로 다른 링크 계층 프로토콜을 사용할 수 있으며 프로토콜은 서로 다른 MTU를 가질 수 있다.

IP datagram fragmentation 한 route에서 IP datagram size가 해당 route의 link's MTU를 초과하면 IP datagram은 fragment로 나눠져야 된다. 그리고 fragments는 마지막 도착지에서 재조합된다.

Type of services(ToS)

datagram에 대한 서비스 레벨을 명시한다. 하지만 현대의 router에서는 사용되지 않는다

IP fragmentation and reassembly

✍️IP datagram header에서 연관된 fields

🤔예를들어 한 router가 4000 byte datagram을 받았으며,이 라우터의 MTU는 1500이다. 이 경우에는 datagram이 3조각으로 나뉘어서 다른 라우터로 이동할 것이고, 도착지에서는 3개의 datagram이 reassemble 될것이다. 하나의 datagram이 3개의 data로 쪼개지고, 각각의 data에 fragment header를 붙였다. 그리고 각 header에는 ID(같은 데이터인지 구분), M(1이면 뒤에 붙을 추가 데이터 있음/0이면 뒤에 붙을 추가 데이터 없음),offset(데이터 조각의 순서)가 포함되어 있다. reassemble 되기 위해서는 각 datagram의 순서를 알아야 한다. 순서를 비교하기 위해 사용하는게 offset인데, 첫번째 fragment는 offset이 0이고 두번째 fragment는 185이다. 185인 이유는 1offset당 8byte이므로, 185*8 = 1480 이기때문이다. 따라서 첫번째 fragment 길이만큼이 offset이된다. 세번째도 같은원리로 두번째 fragment 까지가 offset이므로 (1480+1480)/8 = 370 즉, offset은 370이다.

IP Address

🤔 internet에서 컴퓨터의 각 네트워크 인터페이스에 주어지는 유일한 식별자이다.

🤔 interface

• host,router,physical link 사이의 연결이다.
• router들은 일반적으로 다수의 인터페이스를 갖는다.
• host는 일반적으로 하나 혹은 두개의 인터페이스를 갖는다.(e.g wired Ethernet, wireless 802.11)

🤔IP address in IPv4 점으로 구별된 10진수 표기법에서 32 bit로 쓰여진다. ex) 11000001 00100000 11011000 00001001 -> 193 . 32 . 216 . 9

🤔IP address in IPv6 16진수 표기법에서 128bit로 쓰고 colon으로 나눈다. ex) 3ffe:1900:65455:3:230:f804:7ebf:12c2

각 인터페이스와 연결된 IP 주소

각 컴퓨터에는 network interface cards(NICs) 일명 랜카드가 있다. 이 인터페이스에 서로 다른 ip주소가 할당된다.

IPv4 주소의 두 파트

• network part(network address) 해당 ip주소가 속한 네트워크를 식별하는데 사용된다.
• host part 해당 ip 주소가 속한 네트워크 내에서 식별되는 호스트를 나타낸다.

즉 network part는 지역의 network ip주소이고, host part는 우리집의 ip주소라고 생각할 수 있다.

classful IPv4 addressing

• 초기단계 ip address는 두파트: network,host number를 가진다.(최상위 옥텟만 network number로 지정된다.)
• 1981년에 classful network address architecture가 소개되었다.
• five classes of A,B,C,D,E A,B,C classes는 universal unicast addressing D는 mulicast E는 future use를 위한 것이었다.

위 그림과 표를 같이 보자. Leading bits class A:0 B:10 C:110이다. 클래스가 증가할 때마다 앞에1이 붙는다. class A를 보면 네트워크 비트 수는 8인데 왜, network의 수는 2^7일까? network portion에 맨첫번째가 Leading bit으로써 1비트를 차지하고 있기 때문이다. 같은 이유로, class B,C도 각각 2^14, 2^21이된다.

network당 address의 수는 host ip의 수를 말하고 network portion을 제외한 나머지 비트로 구한다.

class가 A에서 D로하나씩 이동할때마다 network portion이 하나씩 증가한다.

🤔subnet mask? network portion에대한 비트수이다. "/number"로 나타낸다. 즉, 네트워크의 비트수를 나타낸것이다. 예를 들어, 192.168.0.0/24라는 IP 주소에서 /24는 서브넷 마스크를 의미하며, 이는 첫 24비트가 네트워크 부분이고 나머지 8비트가 호스트 부분임을 나타낸다. 따라서 이 IP 주소에서 네트워크 부분은 192.168.0이 되고, 호스트 부분은 0이다.

address type

1. unicast

• class A,B and C addresses
• point-to-point(1:1) connetcion
• 두 unicast hosts 사이에서는 bi-directional

2. Broadcast

• host part는 모두 1이다.
• point-to-multipoint(1:N) unidirectional connection
• broadcast messages는 LAN segment내에 있는 모든 host에 동시에 보내진다. 하지만,LAN router에서는 block 당한다. 즉, 같은 네트워크 상에 있는 host끼리만 통신이 가능하다. 예를 들어, 192.168.0.1과 192.168.0.2는 같은 네트워크 상에 있다. 이는 두 IP 주소가 같은 네트워크 ID인 192.168.0을 가지고 있기 때문이다.

3. Multicast

• class D address

• group communications에 대한 one-to-many(1:N) unidirectional connection

• Multicast는 하나의 송신자가 여러 개의 수신자에게 데이터를 전송하는 방식이다. 이는 Broadcasting과는 달리, 전체 네트워크 상의 모든 호스트에게 데이터를 전송하지 않고, 멀티캐스트 그룹에 속한 호스트들만 데이터를 수신할 수 있다.

• 멀티캐스트 그룹은 IP 주소 범위 중 Class D 주소인 224.0.0.0 ~ 239.255.255.255 범위 내에서 할당된다. 이 주소 범위 내에서, 멀티캐스트 주소는 224.0.0.0 ~ 224.0.0.255까지 할당되며, 이는 로컬 네트워크 상에서 사용된다.

• 멀티캐스트는 IPTV, 동영상 스트리밍 등에서 사용되며, 같은 멀티캐스트 그룹에 속한 호스트들끼리만 데이터를 수신하기 때문에, 대역폭을 절약할 수 있다.

public IP addresses

공인 IP 주소는 인터넷 상에서 고유하게 할당되는 IP 주소로, 인터넷 서비스 제공업체(ISP)로부터 할당받는다. 이는 인터넷 상에서 유일한 주소이므로, 인터넷 상에서 컴퓨터나 장치를 식별하는 데 사용된다.

공인 IP 주소는 IPv4와 IPv6 두 가지 버전이 있다. IPv4의 경우, 32비트로 이루어져 있으며, 현재는 대부분의 인터넷 서비스 제공업체에서 고갈되어 IPv6로 전환하고 있다.

공인 IP 주소는 인터넷 상에서 직접 접속 가능하며, 전 세계적으로 고유하다. 이를 통해 인터넷 상에서 컴퓨터나 장치를 식별하고, 다른 컴퓨터나 장치와 통신할 수 있다.

private IP addresses

Private IP 주소는 인터넷 상에서 공인 IP 주소와 구분하기 위해 로컬 네트워크에서 사용되는 IP 주소이다. 이는 인터넷 서비스 제공업체(ISP)에서 할당받은 공인 IP 주소와 달리, 로컬 네트워크에서 직접 할당하거나 DHCP(Dynamic Host Configuration Protocol) 서버를 통해 자동으로 할당된다.

Private IP 주소는 3가지 범위로 나누어져 있다. 첫 번째로, 10.0.0.0 ~ 10.255.255.255 범위 내의 IP 주소는 Class A Private Address로, 대규모 네트워크에서 사용된다. 두 번째로, 172.16.0.0 ~ 172.31.255.255 범위 내의 IP 주소는 Class B Private Address로, 중간 규모의 네트워크에서 사용된다. 세 번째로, 192.168.0.0 ~ 192.168.255.255 범위 내의 IP 주소는 Class C Private Address로, 소규모 네트워크에서 많이 사용된다. Private IP 주소는 로컬 네트워크 상에서만 유효하며, 인터넷 상에서 직접 접속하려면 NAT(Network Address Translation) 기술을 사용하여 공인 IP 주소로 변환해야 한다. 이를 통해 여러 대의 컴퓨터가 하나의 public IP 주소를 공유하여 인터넷에 접속할 수 있습니다.

Subnets와 subnetting

subnet

서브넷(Subnet)은 IP 네트워크를 더 작은 네트워크로 분할하는 것을 말한다. 이를 통해 네트워크 관리가 용이해지며, 보안성도 향상된다.

서브넷 마스크(Subnet Mask)는 IP 주소의 네트워크 부분과 호스트 부분을 구분하는 역할을 합니다. IP 주소와 서브넷 마스크를 AND 연산하면, 해당 IP 주소가 속한 서브넷의 네트워크 주소를 얻을 수 있다.

예를 들어, IP 주소가 192.168.1.100이고 서브넷 마스크가 255.255.255.0인 경우 and 연산하면, 이 IP 주소는 192.168.1.0/24 서브넷에 속한다는 것을 알 수 있다. 여기서 /24는 서브넷 마스크의 비트 수를 나타내며, 255.255.255.0은 24비트가 1로 설정된 것입니다.

서브넷을 사용하면, 하나의 대규모 네트워크를 여러 개의 작은 네트워크로 분할하여 관리할 수 있으며, 보안성도 향상됩니다.

subnetting

단일 IP network address를 더작은 subnetworks로 나눠주기위해 사용되는 기술

• 모든 hosts은 subnet addressing을 위해 필요하다.
• 서브넷팅을 통해 사이트는 여러 물리적 네트워크 간에 하나의 인터넷 주소를 공유할 수 있다.

b가 subnetting을 위해 쓸 bit의 수라면 사용가능한 subnet은 2^b개 이다.

r이 남아있는 host bits의 수라면 사용가능한 host는 2^r-2이다.

🤔그렇다면 host는 왜 2개를 빼야될까?

그 이유는 1. host part에서 전부 0인 부분은 network 자신이 쓰고, 2. host part에서 전체가 1인 부분은 broadcast address이다.

예를들어, 5개의 subnet을 만들기위해, 빌려와야 하는 bit의 최소 수는 3이다 2^3 =8 >5

CIDR(Classless InterDomain Routing)

• 임의 길이 주소의 subnet 부분
• address format:a.b.c.d/x, x가 주소의 서브넷 부분의 비트수이다.

Network Layer Support protocols - DHCP

🤔DHCP(Dynamic Host Configuration Protocol)는 클라이언트가 네트워크에 접속할 때 자동으로 IP 주소, 서브넷 마스크, 기본 게이트웨이 등의 네트워크 정보를 할당해주는 프로토콜이다.

• 사용 중인 주소에 대한 임대를 갱신할 수 있습니다

• 주소들을 재사용하게 해준다.(연결이 켜져있는 동안에 주소를 유지한다.)
• network에 참여하길 원하는 모바일 유저를 지원한다.(더빠르게)

🤔DHCP 작동 개요 클라이언트는 네트워크에 접속하면 DHCP Discover 메시지를 브로드캐스트한다. DHCP 서버는 이를 수신하면 DHCP Offer 메시지를 클라이언트에게 보내며, 이 메시지에는 IP 주소, 서브넷 마스크, 기본 게이트웨이 등의 정보가 포함된다.

클라이언트는 이 정보를 확인한 후 DHCP Request 메시지를 보내며, 이를 수신한 DHCP 서버는 DHCP Acknowledge 메시지를 클라이언트에게 보내 IP 주소를 할당한다. 클라이언트는 이를 확인한 후 할당받은 IP 주소를 사용하여 네트워크에 접속한다.

DHCP Format

Message Format

DHCP가 IP 말고도 줄 수 있는것

DHCP는 서브넷에 할당된 IP 주소 말고도 더 많은것을 반환할 수 있다.

• 클라이언트의 첫번째 hop 라우터 주소
• DNS server의 name과 IP address
• network mask

  🤔network mask란? 네트워크 마스크(Network Mask)는 IP 주소의 네트워크 부분과 호스트 부분을 구분하는 역할을 합니다. 이를 통해 IP 주소가 속한 네트워크를 식별할 수 있습니다.

  IPv4에서 네트워크 마스크는 32비트로 이루어져 있으며, 보통 255.255.255.0과 같은 형태로 표현됩니다. 이는 32비트 중에서 네트워크 부분이 1로, 호스트 부분이 0으로 설정되어 있음을 나타냅니다.
  예를 들어, IP 주소가 192.168.1.100이고 네트워크 마스크가 255.255.255.0인 경우, 이 IP 주소는 192.168.1.0/24 네트워크에 속한다는 것을 알 수 있습니다. 이는 IP 주소의 처음 24비트가 네트워크 부분으로 사용되고, 나머지 8비트가 호스트 부분으로 사용되기 때문입니다.
  네트워크 마스크는 서브넷(Subnet)을 구분하는 데도 사용됩니다. 서브넷 마스크(Subnet Mask)는 IP 주소의 네트워크 부분과 호스트 부분을 더 작은 네트워크로 분할하는 데 사용됩니다.

DHCP relay

DHCP Relay는 DHCP 클라이언트와 DHCP 서버가 서로 다른 네트워크에 위치한 경우, DHCP Discover 메시지를 브로드캐스트하여 DHCP 서버를 찾을 수 없는 문제를 해결하기 위한 프로토콜입니다.

DHCP Relay는 네트워크의 경계를 넘어 DHCP Discover 메시지를 전달하는 역할을 합니다. 이를 위해 라우터나 스위치 등의 장비에 DHCP Relay 에이전트를 설치해야 합니다. DHCP Relay 에이전트는 DHCP Discover 메시지를 브로드캐스트한 클라이언트의 IP 주소와 MAC 주소를 유지하며, 이를 DHCP 서버에 전달합니다.

DHCP 서버는 DHCP Relay 에이전트로부터 받은 DHCP Discover 메시지에 대해 DHCP Offer 메시지를 만들어 DHCP Relay 에이전트로 전송합니다. DHCP Relay 에이전트는 이를 다시 클라이언트에게 전달합니다. 이 과정에서 DHCP 서버와 클라이언트는 서로 다른 네트워크에 있더라도 IP 주소 등의 네트워크 정보를 주고 받을 수 있습니다.

Network Layer Support Protocols - NAT

NAT(Network Address Translation)

NAT는 private IP 주소를 public IP 주소로 변환하여 하나의 public IP 주소로 여러 대의 private 네트워크 장치에 접속할 수 있도록 해주는 프로세스이다. 일반적으로, NAT는 라우터에서 구현되며, 라우터는 private 네트워크와 public 네트워크 간의 중개자 역할을 담당한다. 라우터는 private 네트워크에서 나가는 패킷의 출발지 IP 주소를 public IP 주소로 변환하고, public 네트워크에서 들어오는 패킷의 목적지 IP 주소를 private IP 주소로 변환한다.

인터넷에 접속할 때, private IP 주소를 가진 호스트에서 나가는 패킷은 public IP 주소를 가진 라우터의 IP 주소로 바뀌어 인터넷 상에서 유효한 주소로 인식된다. 그리고 인터넷 상에서 들어오는 패킷은 라우터에서 private IP 주소로 바뀌어서 private 네트워크 내의 호스트에 전달된다.

Network Layer Support Protocols-ICMP

🤔ICMP(Interent Control Message Protocol)란? ICMP(Internet Control Message Protocol)는 인터넷 프로토콜 스위트(IP)에서 사용되는 제어 메시지 프로토콜이다. ICMP 메시지는 네트워크 장애 진단, 라우팅 문제 해결, 패킷 전송 실패 알림 등의 목적으로 사용된다.

ICMP는 IP 패킷을 이용하여 전송되며, IP 패킷의 데이터 부분에 포함된다. ICMP 메시지는 대부분 IP 패킷 손상, 목적지 도달 불가능, TTL(Time to Live) 초과 등의 오류를 알리는 데 사용된다. 또한, ICMP Echo Request와 Echo Reply 메시지를 이용하여 네트워크 장비 간의 연결 상태를 확인하는 데에도 사용된다. 이러한 ICMP 메시지는 네트워크 관리자가 네트워크 상태를 모니터링하고 문제를 해결하는 데에 매우 유용하게 사용된다.

🤔ICMP의 위치는?

🤔message format

🤔ICMP message encapsulation

🤔ICMP - ping ICMP의 Echo Request와 Echo Reply 메시지를 이용하여 네트워크 장비 간의 연결 상태를 확인하는 것을 'ping'이라고 한다.

ping 명령어를 사용하여 호스트 이름이나 IP 주소를 입력하면, 해당 호스트가 응답하는지 여부와 응답 시간 등의 정보를 확인할 수 있다. ping 명령어는 대부분의 운영 체제에서 지원되며, 네트워크 문제점을 진단하는 데 유용하게 사용된다.

ping 명령어는 목적지 호스트에 ICMP Echo Request 패킷을 보내고, 해당 호스트가 이를 수신하면 ICMP Echo Reply 패킷을 송신자에게 반환한다. 이 때, 송신자는 반환된 ICMP Echo Reply 패킷을 수신하여 목적지 호스트와의 연결 상태를 판단하게 된다.

ICMP-traceroute

ICMP의 TTL(Time to Live) 필드를 이용하여 네트워크 경로 상의 라우터들을 추적하는 것을 'traceroute'라고 한다.

traceroute 명령어를 사용하여 목적지 호스트에 도달하는 데 거쳐가는 라우터들의 IP 주소와 응답 시간 등의 정보를 확인할 수 있다. traceroute 명령어는 대부분의 운영 체제에서 지원되며, 네트워크 문제점을 진단하는 데 유용하게 사용된다.

traceroute 명령어는 ICMP Echo Request 패킷을 보내고, TTL 값을 점차 증가시켜서 목적지 호스트까지 도달하는 데 거쳐가는 라우터들의 IP 주소를 추적한다. 이때, TTL 값이 각 라우터에서 1씩 감소하며, TTL 값이 0이 되면 해당 패킷은 폐기된다. 이를 통해, 각 라우터가 패킷을 전달하는 데 소요되는 시간을 계산할 수 있다.

IP

IPv6

🤔IPv6가 생겨난 이유

• IPv4의 메모리 고갈이 예상되면서 대책을 찾게 되었다.
• header format이 processing/forwarding에 도움을 준다.
• Oos를 용이하게 하기 위한 헤더 변경

  😎Oos란? OOS(Out of Service)는 일반적으로 시스템, 장비 또는 서비스가 작동하지 않거나 서비스를 제공하지 못하는 상태를 나타내는 용어입니다.

한사람당 network에 연결된 device수가 점점 증가하고 있다.

🤔IPv6 주소

• 16진수로 나타내며 128bit이고, colon으로 구별한다 ex) 3ffe:1900:65455:3:230:f904:7ebf:12c2
• IPv4는 2^32만큼의 IP address수가 있었고, IPv6는 2^128 만큼의 IP address가 있다.

🤔IPv6의 unicast address format

• IANA가 할당한다.

🤔IPv6 datagram

• base header는 40 byte 고정
• Extension header
  • optional internet layer 정보를 가져온다.
  • base header와 upper-layer protocol header 사이에 위치한다.
  • options에서 IPv4의 40-byte 제한을 제거

🤔IPv6 header

• fragmentation이 허용되지 않는다.
• 각 hop에서 processing 시간을 줄이기 위해 checksum을 삭제했다.
• flow labeling 및 우선 순위 개념이 채택되었다.

🤔Next header

🤔Ipv6 transition 전략

1. Dual stack

• IPv6 node들은 완성된 IPv4를 구현체를 갖고있다. 이러한 노드를 "IPv6/IPv4 node"라고 부른다.
• IPv6/IPv4 node는 IPv4와 IPv6 모두에서 send와 receive를 할 수 있다.

2. Tunneling approach

• Tunneling은 인터넷 프로토콜(IP) 기반의 네트워크에서, 하나의 프로토콜 패킷을 다른 프로토콜 패킷으로 캡슐화하여 전송하는 기술이다. 이러한 기술을 사용하면, 서로 다른 네트워크 간에 안전하게 통신할 수 있다.
• IPv6에서 IPv4로, 또는 그 반대로 데이터를 전송하는 기술로도 사용된다. 이를 통해, IPv4와 IPv6 간의 호환성 문제를 해결할 수 있다.

IPv6로 접근하는 비율이 점점 상승하고 있다.

W=16인 이 트리구조가 어떻게 나온건지 알아보자.

먼저 value값은 실제적으로 넣은 값을 넣어준다. 반면 bound 값은 현재 노드 상황에서 Item들을 쪼갤 수는 없지만 무게에 맞춰 쪼개서까지 가방에 넣을수 있다고 했을때의 최대 가치 값이다. 이걸 기억하면서 접근해보자.

1. 트리구조의 자식중 왼쪽은 Item을 넣었을때, 오른쪽은 넣지 않았을때이다.
2. bound > max profit 이라면 promising하고 bound <= max profit nonpromising하다. nonpromising한 경우에는 가지치기를 멈춘다. 생각해보면, nopromising 이라는건 같은 레벨의 max profit보다 bound가 작다는건데 bound라는게 앞으로 최대로 커질수 있는 값이라는 것이기 때문에, 당연히 가지치기를 그만두는게 맞다.
3. bound 값을 구하는 방법을 쉽게 예를들어보자면, 루트 노드에서는 Item1부터 순서대로 넣는다. Item1,2를 넣으면 profit =70 ,w = 7이다. 여기에는 들어갈 수 있는 무게가 9(16-7)가 남는다. 하지만 Item3은 무게가 10이므로 통째로 넣었을때 무게를 초과해 버린다. 그래서 Item3은 9/10만 넣는다. 따라서 가치도 50*9/10이 되므로 루트노드의 bound는 40+30+50*9/10 = 115가 된다.
4. w(무게)가 16을 넘어가면 bound를 0으로 reset해준다.
5. value값이 이제까지 구한 값중 가장 크고 w < W(16) 이라면 max profit값을 수정해준다.

이제 순서대로 계산을 해보자.

(1,1)

(1,1)은 Item1을 넣었을 경우이다. 이경우에는 40+30+40+30+50*9/10 = 115로 바운드 값을 줄 수 있다. 그리고 1만 넣어주었으므로 value = 40 w = 2이다.

(1,2)

Item1을 넣지 않았을 경우이다. 이때 bound는 Item1을 제외하고 생각해야한다. Item2,3을 합쳐도 w가 15이므로 item4를 무게1 만큼(1*10/5) 집어넣을수 있다. 따라서 30+50+(1*10/5) = 82이다.

(2,1)

Item 1을 넣고 2도 넣었을 경우이다. 1,2를 모두 넣었으므로 (1,1)노드처럼 결국 item3을 w를 9만큼만 넣을 수 있다. 따라서 bound 값이 115가 나오고 실제적으로는 1과 2를 넣었으므로 value는 70 w는 7이다.

이런식으로 순서대로 진행하면 된다.

참고로 BFS는 queue로 구현하기 때문에, 예를들어 (3,2)의 bound가 80이고, (3,3)의 maxprofit이 90이기 때문에 (3,2)가 분기하면 안되는거 아닌가 하겠지만, (3,2)는 먼저 일어나서 미래의 일을 예측할수 없다. 따라서 분기는 하고 다음번에 nopromising하게 되어 분기를 멈춘다.

best-first search with branch-and-bound pruning

위에 breadth-first search처럼 기본작동방식은 같다. 다만, 전체 확장되지 않은 노드 중에서 가장 유망한 즉, bound값이 가장 큰 노드를 확장함으로써 빠르게 결과를 도출할 수 있게 한다.

1. (1,1)를 확장한다.(bound가 가장크다.)
2. (2,1)를 확장한다.
3. (2,2)를 확장한다.
4. (3,3)를 확장한다.

h2는 java기반으로 실행되기 때문에 java는 깔려있어야 한다.

1. http://www.h2database.com/html/download.html 여기서 다운받는다.

2. 압축을 풀어주고나서 H2/bin 파일을 찾아간다.

3. 윈도우라면 h2.bat 맥이라면 h2.sh를 실행한다. 이때 권한이 없다고 하면 chmod 755 h2.bat 이라는 명령어를 부여한다.

4. 실행이 되고나면 http://123.456.78.123:8082/login.jsp?jsessionid=12312asdfsf131241421adfsf123213adfsf 이러한 페이지가 뜨는데 ,뒤에 세션id는 중요하기 때문에 건드리지 않는다. 만약 페이지가 정상적으로 뜨지 않는다면 123.456.78.123:8082 요 부분을localhost:8082로 변경해준다.

5. 처음에 연결할때는 최소한번, 세션키 유지한 상태로 실행한다. 파일모드로 접근해야 해서 jdbc url 부분에 jdbc:h2:/[package명]을 작성해준다 ex) jdbc:h2:/Hello

6. 그러고 나서 이 버튼을 눌러서 연결을 해제하고 내 home 디렉토리에 [패키지명].mv.db가 있는지 확인한다.

7. 그 다음부터는 연결할때 jdbc:h2:tcp://localhost~/[package명] 이렇게 네트워크 모드로 접속한다.

아까 실행했던 h2.bat을 끄면 h2를 들어갈 수 없게 된다.

transport Layer

• 다른 host에서 실행되는 app process 사이에서 logical한 communication을 한다.(end system) ✍️send side: app message를 segment로 쪼개서 network layer로 보낸다. ✍️receiver side: segment를 메세지로 재조합해서 app layer로 보낸다.

network layer

• host들 사이에서 logical한 communication을 한다.

logical communication이란? 라우터가 네트워크 상에서 패킷을 전달할때, logical 주소를 참조해서 목적지로 패킷을 전달한다.

그렇다면, transport와 network는 어떤식으로 일어날까? 예를 들어보자. Ann과 bill은 각 집에 12명의 자식들이 있다. ann집의 12명의 아이들이 bill의 12명의 아이들에게 편지를 보내려고 한다. ann의 집에서는 ann이 12명의 아이들의 편지를 받아서 모아서 ann집의 우체통에 넣어준다. 우체통에 들어간 편지는 집배원에 의해서 ann집의 지역 우체국으로 이동하고 우체국에서는 bill집의 지역 우체국으로 편지들을 배달한다. bill집의 지역 우체국에 근무하는 집배원이 bill집에 우체통에 편지들을 가져다준다. bill은 우체통으로가서 편지를 가져와서 집에 있는 아이들에게 편지를 나눠준다.

실제에서 적용해보자면

1.Application layer(집에 있는 아이들): 송신자의 애플리케이션에서 데이터가 생성된다. 예를 들어, 이메일 클라이언트에서 이메일 메시지가 작성한다.

2.Transport layer(ann,bill): 데이터는 송신자의 포트 번호와 수신자의 포트 번호를 가지고 있는 세그먼트로 나누어집니다. 이 세그먼트에는 에러 검출 및 복구를 위한 체크섬 값도 포함됩니다.

3.Network layer(우체통): 세그먼트는 송신자의 IP 주소와 수신자의 IP 주소를 가진 패킷으로 묶입니다. 이 패킷에는 라우터가 패킷을 전달할 때 사용하는 logical 주소인 IP 주소가 있습니다.

4.Data link layer(우체국,집배원): 패킷은 송신자와 수신자 간의 물리적인 연결을 통해 전송됩니다. 이 때, 패킷은 송신자와 수신자 간의 물리적인 주소인 MAC 주소를 가진 프레임으로 캡슐화됩니다.

5.Physical layer: 프레임은 전기 신호나 광 신호로 변환되어 물리적인 매체를 통해 전송됩니다.

TCP vs UDP

• 공통점 ✍️데이터를 segmentation으로 만들고 다시 재조합한다.

✍️port number를 사용해서 다른 application을 구별한다.

• TCP TCP(Transmission Control Protocol)는 인터넷 프로토콜 스위트의 한 프로토콜로, 데이터를 신뢰성 있게 전송하는 연결형 프로토콜입니다. TCP는 데이터 전송 시 신뢰성을 보장하며, 데이터가 손실되거나 손상될 경우 재전송을 수행합니다. 이러한 특성 때문에, TCP는 파일 전송, 이메일 전송, 웹 브라우징 등에서 많이 사용됩니다.

TCP의 주요 특성은 다음과 같습니다.

1. 연결형 프로토콜: TCP는 연결 설정 과정을 거쳐 데이터 전송을 수행합니다. 이 연결 설정 과정에서 양측의 소켓이 서로 정보를 교환하고, 데이터 전송을 위한 세션을 설정합니다.

2. 신뢰성 있는 프로토콜: TCP는 데이터 전송 시 신뢰성을 보장합니다. 데이터가 손실되거나 손상될 경우, 재전송을 수행하여 데이터의 무결성을 보장합니다.

3. 흐름 제어와 혼잡 제어: TCP는 흐름 제어와 혼잡 제어를 수행하여, 네트워크 상황에 따라 데이터 전송 속도를 조절합니다.

4. 멀티플렉싱과 디멀티플렉싱: TCP는 멀티플렉싱과 디멀티플렉싱을 지원하여, 하나의 커넥션으로 여러 개의 데이터 스트림을 동시에 전송할 수 있습니다.

5. 복잡한 구조: TCP는 복잡한 구조를 가지고 있어 구현이 어렵고, 처리 속도가 느립니다.

• UDP UDP(User Datagram Protocol)는 인터넷 프로토콜 스위트의 한 프로토콜로, 데이터를 신뢰성 없이 빠르게 전송하는 비연결형 프로토콜입니다. UDP는 데이터 전송을 보장하지 않고, 데이터가 손실되어도 재전송을 하지 않습니다. 이러한 특성 때문에, UDP는 실시간 게임이나 스트리밍 서비스 등에서 많이 사용됩니다.

UDP의 주요 특성은 다음과 같습니다.

1. 비연결형 프로토콜: UDP는 연결 설정 과정이 없으며, 데이터 전송도 연결 설정 없이 이루어집니다.

2. 신뢰성 없는 프로토콜: UDP는 데이터 전송 시 신뢰성을 보장하지 않습니다. 데이터가 손실될 가능성이 있으며, 이를 재전송하지 않습니다.

3. 빠른 전송 속도: UDP는 데이터 전송 시 TCP와 같은 오버헤드가 적으므로, 빠른 전송 속도를 보장합니다.

4. 단순한 구조: UDP는 간단한 구조를 가지고 있어 구현이 용이하며, 처리 속도가 빠릅니다.

5. 멀티캐스트와 브로드캐스트 지원: UDP는 멀티캐스트와 브로드캐스트를 지원하여, 한 번에 여러 대상에게 데이터를 전송할 수 있습니다.

6. 순서 상관없이 data가 전달된다. data가 datagram으로 나뉘어지고,각 datagram은 다른 루트를 통해서 도착지까지 이동한다. 이 과정에서 순서대로 들어오지 않고, 순서가 재배열 되지도 않는다.

✍️ UDP 사용하는 application layer

• streaming
• DNS
• SNMP(simple network management protocol)
• DHCP(Dynamic Host Configuration Protocol)
• (RIP)Routing inforamtion protocol 등등

Multiplexing과 Demultiplexing

멀티플렉싱(Multiplexing)은 하나의 통신 채널을 이용하여 여러 개의 데이터 스트림을 전송하는 기술입니다. 멀티플렉싱을 이용하면, 여러 개의 데이터 스트림을 하나의 물리적인 매체를 통해 전송할 수 있으므로, 효율적인 대역폭 사용이 가능해집니다.

multiplexing을 수행하는 장비를 멀티플렉서(Multiplexer)라고 하며, 멀티플렉서는 여러 개의 데이터 스트림을 하나의 통신 채널로 결합하여 전송합니다. 이때, 각각의 데이터 스트림은 고유한 식별자를 가지고 있어, 수신 측에서는 이 식별자를 이용하여 각각의 데이터 스트림을 구분합니다.

Demultiplexing 은 멀티플렉싱과 반대로, 하나의 통신 채널에서 여러 개의 데이터 스트림을 분리하는 기술입니다. Demultiplexing을 수행하는 장비를 Demultiplexer 라고 하며, Demultiplexing은 전송된 데이터를 각각의 데이터 스트림으로 분리하여, 각각의 데이터 스트림을 수신 측으로 전달합니다. 이때 port번호를 통해서 각각의 application을 구분합니다.

multiplexing과 Demultiplexing을 이용하면, 하나의 통신 채널을 이용하여 여러 개의 데이터 스트림을 전송할 수 있으므로, 대역폭 사용이 효율적이고, 네트워크 구성이 간단해집니다. 따라서, multiplexing과 Demultiplexing은 네트워크에서 매우 중요한 역할을 합니다.

port

각 application은 유일한 port 번호를 가진다. port 번호를 통해서 다양한 application protocol들을 구별할 수 있다.

포트 번호는 0부터 65535까지 총 65536개가 존재하며, 이 중에서 일부 포트 번호는 특별한 용도로 사용됩니다.

• Well-known port: 포트 번호 0부터 1023까지의 범위를 말하며, 잘 알려진 서비스들이 사용합니다. 예를 들어, HTTP 서비스는 포트 번호 80을 사용하고, FTP 서비스는 포트 번호 21을 사용합니다.

• Registered port: 포트 번호 1024부터 49151까지의 범위를 말하며, 사용자가 등록한 서비스나 애플리케이션에서 사용합니다. 이 범위의 포트 번호는 IANA에서 등록을 받아 사용합니다.

• Private port: 포트 번호 49152부터 65535까지의 범위를 말하며, 개인적인 용도로 사용됩니다. 이 범위의 포트 번호는 IANA에서 할당하지 않으며, 개인이나 기업에서 필요에 따라 사용할 수 있습니다.

• Dynamic port: 포트 번호 49152부터 65535까지의 범위 중에서, 클라이언트 측에서 임시로 사용하는 포트 번호를 말합니다. 클라이언트는 서버와 통신할 때, 동적으로 포트 번호를 할당하여 사용합니다. 이러한 포트 번호는 일반적으로 클라이언트 측에서 자동으로 선택되며, 서버 측에서는 이 포트 번호를 이용하여 클라이언트와의 통신을 수행합니다.

따라서, 포트 번호는 위와 같이 구분됩니다. Well-known port와 Registered port는 IANA에서 관리하며, Private port와 Dynamic port는 개인이나 기업에서 자유롭게 사용할 수 있는 범위입니다. ✍️source port number: sending host 에서 app process와 연관된 port number ✍️destination port number: remote host에서 destination process와 연관된 port number source와 destination port number가 일치해야만 전송가능하다.

servers는 동시에 TCP connection을 지원할 수 있다. 이때, 한 서버에 여러 host가 접속한다면 host마다 port번호가 다를것이고, 같은 호스트가 다른 ip주소로 찾아 갈수가 있다. 그래서 host는 먼저 ip주소를 찾고 해당 ip주소의 port번호를 찾아간다. 이렇게 하면 여러 연결에 대해서 각각 원하는 데이터를 전달 할 수 있게 된다. 그렇다면, 이렇게 말할 수 있다. 각 connection은 4개 영역으로 구분될 수 있다.

1. source IP addr
2. dest IP addr
3. source port
4. dest port

IANA

IANA(Internet Assigned Numbers Authority)는 인터넷 프로토콜 스위트에서 사용되는 포트 번호, 프로토콜 번호, IP 주소 등과 같은 인터넷 자원을 할당하는 기관 중 하나입니다. IANA는 인터넷의 안정적인 운영을 위해 전 세계적으로 공유되는 자원에 대한 할당과 관리를 담당하고 있으며, 포트 번호 할당 또한 그 중 하나입니다. IANA는 이러한 포트 번호를 관리하고, 새로운 포트 번호를 할당하거나 기존 포트 번호의 변경을 수행합니다.

netstat command

netstat 커맨드를 입력하면 현재 ip와 port number를 확인할 수 있다.

UDP-segment structure

UDP-checksum

UDP 프로토콜에서는 데이터를 전송하기 전에 checksum을 계산하여 데이터의 오류를 검출한다(값이 변경된건 아닌지).

• Sender의 관점:

1. 데이터를 패킷으로 나눕니다.
2. 패킷 헤더에 checksum 필드를 추가합니다.
3. 데이터와 패킷 헤더를 이용하여 checksum을 계산합니다.
4. 계산된 checksum 값을 패킷 헤더의 checksum 필드에 저장합니다.
5. 패킷을 수신하는 receiver에게 패킷을 전송합니다.

• Receiver의 관점:

1. 패킷을 수신하면 패킷 헤더의 checksum 필드를 확인합니다.
2. 데이터와 패킷 헤더를 이용하여 checksum을 계산합니다.
3. 계산된 checksum 값과 패킷 헤더의 checksum 필드 값을 비교합니다.
4. 두 값이 일치하면 데이터를 추출하고, 일치하지 않으면 패킷을 폐기합니다.

이렇게 sender와 receiver 모두에서 checksum을 이용하여 데이터 오류를 검출할 수 있습니다. 이 과정에서 checksum 값이 일치하지 않으면 패킷이 폐기되므로, 데이터의 신뢰성을 보장할 수 있습니다

checksum 계산

pseudo header와 UDP header UDP data의 모든 값들을 16비트로 나누어서 모두 더한다. 모두 더해서 carry 된 값들은 다시 마지막 값에 더해주고 나서 보수 취해주면 checksum이 된다. 이 값을 UDP header에 checksum에 넣어준다.