2주차 면접 스터디

DFS와 BFS에 대해서 설명해주세요

 

DFS

스택 자료구조와 재귀를 사용하여 깊이 우선 탐색을 진행합니다. 

 

• DFS를 진행하며 얻은 결과값이 최단 경로라는 보장이 없습니다. 
  • 각 노드를 방문하는 순서에만 집중하며 경로의 길이는 고려하지 않습니다. 그 이유는 깊이를 우선적으로 탐색하기 때문에 특정 경로를 끝까지 탐색한 후에 탐색할 수 없는 경우에 다른 경로를 탐색하는데, 그 과정에서 해당 경로의 길이가 최단 거리임을 알 수 없습니다.
• 인접 행렬로 구현한 경우, 시간 복잡도는 O(N^2)이고, 인접 리스트인 경우 해당 정점에 연결되어 있는 간선의 갯수만큼 탐색을 진행하므로 O(N+E), N: 정점의 갯수, E: 간선의 갯수 입니다.
• 각각의 경로마다 특징을 저장해둬야 할 때는 DFS가 BFS보다 유리합니다. -> why? 

BFS

큐 자료구조를 사용하여 넓이 우선 탐색을 진행합니다.

• 넓이를 우선적으로 탐색하므로 최단경로를 찾는데 용이한 알고리즘 입니다.
• 큐를 이용하여 다음에 탐색할 정점들을 저장하므로 더 큰 저장공간이 필요하다. 
  • DFS는 한 정점에 대해 끝까지 탐색하므로, 저장 공간은 그래프의 깊이 만큼만 필요합니다. 반면에, BFS를 사용하는 경우 해당 정점의 인접한 모든 이웃 노드들을 큐에 저장해야하기 때문에, DFS에 비해 메모리 사용이 더 큽니다.

DFS에 큐를 사용해서 구현하면 안되나요? 반대로 BFS에서 스택을 사용해서 구현하면 안되나요?

큐는 기본적으로 FIFO(선입 선출) 구조입니다. 그렇기 때문에, 현재 방문중인 정점을 집어넣으면 해당 정점이 먼저 처리되기 때문에 깊이 우선 알고리즘엔 적합하지 않은 자료 구조입니다.

 

반면에, BFS는 현재 정점을 방문하고, 인접한 정점들을 모두 확인을 해야하는데 스택을 사용한다면 스택은 LIFO(후입 선출)이기 때문에 스택의 맨 위에 쌓인 정점부터 처리를 해줍니다. 그렇기 때문에 해당 자료구조들은 적합하지 않은 구조 입니다.

 

DFS와 BFS가 어떤 상황에서 비효율적일까요?

DFS는 최단 경로를 찾아야하는 상황에서 비효율적이고, BFS는 깊이 우선 탐색을 진행할 때나 메모리 사용량이 많은 경우에 DFS에 비해 비효율적입니다.

 

DFS에서 사이클을 찾는 방법이 무엇인가요?

노드의 상태를 방문하지 않음, 방문 완료 및 방문중이라는 상태값을 추가로 만들어서 DFS를 사용합니다.

 

 

 

패킷 지연 종류에는 무엇이 있는지 설명해 주세요

네트워크 통신에서 JPEG나 MP3같은 파일들을 보내기 위해, 출발 종단 시스템은 패킷이라는 작은 덩어리 데이터로 분할하여 목적지 종단 시스템까지 보냅니다. 즉, 패킷은 데이터 전송의 기본 단위로 사용됩니다.

 

링크와 스위치의 네트워크를 통해 데이터를 이동시키는 데는 두가지 방식이 있는데, 패킷 교환과 회선 교환이 있습니다.

 

패킷교환 (Packet Switching)

패킷 단위로 전송이 독립적으로 이루어지며, 네트워크 트래픽 상태에 따라 각자 다른 전송 경로를 가질 수 있습니다. 고정된 경로가 존재하지 않으므로 동일한 경로를 다른 목적지로 가는 패킷들이 공유하여 효율적으로 사용이 가능합니다.

 

효율적으로 사용이 가능한 반면에, 각 패킷이 다른 경로를 통해 전달되기 때문에 지연 시간이 각 패킷마다 다르기도 합니다. 지연 종류에는 대표적으로 4가지가 존재하는데,

 

+) 패킷 교환 vs 회선 교환 비교

회선 교환 같은 경우 대용량 데이터를 보내는데 용이 ex) 전화

네트워크 같은 패킷 교환을 사용 

처리 지연 (Processing Delay)

패킷의 헤더를 조사하고 그 패킷을 어떤 출력 링크로 보낼지 결정하는 시간을 처리 지연이라고 합니다.

 

큐잉 지연 (Queuing Delay)

출력 버퍼에서 링크로 송신하려고 하는 패킷을 저장하고, 해당 링크가 패킷을 전송하고 있을 때 패킷 스위치에 방금 도착한 패킷은 출력 버퍼에서 대기하는데, 이 때의 대기 시간을 큐잉 지연이라고 합니다. 트래픽이 많고, 많은 패킷이 전송 대기 중이면 큐잉 지연이 매우 길어집니다. 

 

큐가 가득찼을 때 패킷 손실이 발생할수 있습니다. TCP의 경우에는 손실이 된 것을 알고 다시 전송을 하는데, UDP는 몰라서 그대로 손실이 됩니다.

 

실시간 어플리케이션에서 지연이 발생할 떄 어떻게 해결할 수 있는지?

-> 라우터의 큐 사이즈는 개발자가 조절할 수 없음!

-> QS(패킷 우선 순위를 정하거나), 로드밸런싱을 하거나 (요청 자체를 처음에 분산시켜 버리면)

-> 가급적이면 어플리케이션 내에서 요청을 덜 받도록 구현을 하거나 패킷 우선 순위를 정하는게 좋습니다.

-> TCP를 안쓰고 UDP를 쓰면 빨라짐. (실시간은 UDP를 주로 사용) 

 

전송 지연 (Transmission Delay)

패킷의 모든 비트를 링크로 밀어내는데 걸리는 시간 입니다.

 

저장-후-전달 방식에 의해 수신 링크에서 라우터까지 하나의 패킷이 완전하게 도착했을 때, 이 때 완전한 패킷을 라우터가 출력 링크로 밀어내는데 이 때 시간을 전송 지연이라고 합니다.

 

전파 지연 (Propagation Delay)

한 라우터에서 다른 라우터까지 전파되는데 걸리는 시간 입니다. 전파 지연을 구하는 공식이 (거리 / 전파속도) 이므로 거리가 멀어질 수록 전파 지연이 길어집니다.

 

저장 후 전달 방식에 대해 설명해주세요.

패킷을 전송할 때 중간 노드가 데이터를 완전히 수신한 후에 다음 노드로 전달하는 방식입니다. 즉, 패킷이 한번에 전송되지 않고 중간 노드에서 임시로 저장되고, 다음 노드로 이동합니다.

 

+) 빠른 재전송 방식에 대해서 알고 계신가요?

-> 패킷이 손실된 경우, 똑같은 응답 3개를 보내서 수신이 이를 보고 판단해서 재전송을 합니다.

TCP 혼잡 제어 중 하나

 

전송 지연과 전파 지연의 차이점이 뭘까요?

전송 지연은 라우터가 패킷을 내보는데 필요한 시간으로, 하나의 링크에서 링크를 타기 전 까지의 시간입니다. 따라서, 거리 여부가 지연 시간에 영향을 주지 않습니다.

 

반면에, 전파 지연은 비트가 한 라우터에서 다음 라우터로 전파되는데 걸리는 시간으로, 두 라우터 사이의 거리가 멀수록 지연이 길어집니다.

 

Thread safe하다는 것은 어떤 의미인가요? 어떻게 thread safe하게 설정할 수 있을까요?

Thread형태의 어플리케이션이 가질 수 있는 이슈는 두가지가 있습니다.

• Accessing shared variable without locking
• Deadlock caused by mutual dependency on shared variable

정리해서, 멀티 스레드 프로세스 환경에서 여러 개의 스레드가 같은 자원을 공유할 때 서로의 작업에 영향을 주는 문제 입니다. (데드락이나, race-condtion)

 

thread-safe 설정 방법

synchronized와 thread-safe의 연관관계?

스레드의 동기화는, 스레드의 배타적 실행을 보장해줘서 한 스레드가 진행중인 작업을 다른 스레드가 간섭하지 못하도록 합니다.

 

동기화 문제는, 스레드가 변수를 읽어올 때 Main Memory에 바로 접근하지 않고, CPU Cache memory에 데이터가 있다면 캐시에서 읽어옵니다. 이 때, Main Memory에 존재하는 변수값이 바뀌더라도 스레드는 캐시 메모리에서 값을 읽어오기 때문에 변경 사항을 알 수 없습니다. 이러한 문제를 동시성 프로그래밍에서의 가시성 문제라고 합니다.

 

synchronized 키워드는 블럭으로 들어갈 때와 나올 때 락을 통해서 캐시와 메모리간에 동기화를 시켜주기 때문에 값이 일치하는 문제를 해결해 줍니다. 

 

하지만, 해당 작업이 실행 중일 때 락이 걸리기 때문에 다른 스레드가 병렬적으로 작업을 수행하지 못하는 문제가 생깁니다. 이 때 등장한 것이 atomic 변수 입니다. atomic 변수를 사용하면 락 없이도, thread-safe하게 설정할 수 있다고 합니다.

 

atomic변수가 어떻게 락 없이 thread-safe하게 설정되나요?

atomic 변수는 CAS연산 (Compare-And-Swap)을 기반으로 동작합니다. CPU의 원자적인 특성을 이용해서 값의 조회, 비교, 변경도 원자적으로 처리가 됩니다. 값을 비교할 때 이전의 값과 다르다면 원자적으로 실행할 수 없기 때문에 변경이 이루어지지 않습니다. 이는

 

synchronized와 달리 락이 걸리지 않기 때문에 스레드를 대기시키지 않습니다. (논-블로킹 방식) 

 

삽입이나 교체 같은 메서드에는 synchronized가 걸려있어서 락이 걸려있습니다. (O) 그래서 일부는 락을 걸리게 동작합니다. 

나머지 메서드는 락을 사용하여 동작하지 않습니다.

 

원자성을 보장하기 위해서는 CPU cache가 아닌 CPU를 바라봐야 합니다. ConcurrentHashMap도 CAS연산을 사용하기 때문에 thread-safe한 구조를 가지고 있습니다. 

 

race-condition이 무엇이고, 방지하는 방법

-> 스레드가 동시에 공유자원에 접근할 때 일어나는 상태 , mutex, semaphore를 통해 해결할 수 있습니다. 

 

스프링 Bean은 thread-safe 한가요?

-> 싱글톤 스코프를 사용하기 떄문에 멀티 프로세스 환경에서 thread-safe하지 않습니다. 

 

volatile -> 램에서 바로 직접 읽고 쓰는 작업을 수행합니다. 

 

불변객체 사용하기
a class instance is immutable when its internal state can’t be modified after it has been constructed.

클래스 변수가 생성되고 난 후에, 내부의 상태가 변경되지 않을 때 불변이라고 합니다. private이나 final하게 설정하는 것이, 자바에서 외부에서 상태가 변경되지 않게끔 구현해 줍니다. Collections.unModifiableList() 같은 메서드도 불변성을 유지시켜 줍니다.

 

하지만, 원본 리스트가 변경될 때 UnmodifiableList도 영향이 받는 이슈가 있습니다.

List<Integer> unmodifiableList = Collections.unmodifiableList(list);

위 코드에서 새로 생성된 List는 원본을 가르키고 있지만, 

List<Integer> unmodifiableList = List.copyOf(list);

이 코드에서 unmodifiableList는 복제된 리스트를 가르키고 있기 때문에 원본 값이 변하더라도 영향을 받지 않습니다.

 

 

데드락에 대해서 설명해주세요

데드락이란?

데드락은 교착상태라고 표현하기도 하며, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 기다리며 무한 대기에 빠지는 상태를 말합니다.

 

Deadlock 이 동작하기 위한 4가지 조건에 대해 설명해 주세요.

상호배제

한 프로세스가 사용중인 자원을 다른 프로세스가 사용할 수 없는 것을 말합니다.

ex) 프린터를 사용하는 동안 다른 프로세스가 프린터를 사용할 수 없습니다.

 

점유와 대기

자원을 할당받은 상태에서 다른 자원을 할당받기 위해 기다리는 상태를 말합니다.

ex) 프로세스 A가 프린터를 사용중이며 스캐너 사용을 요청하며 대기하고, 프로세스 B는 스캐너를 사용하며 프린터 사용을 요청하며 대기하는 상황을 말합니다.

비선점

이미 할당된 프로세스의 자원을 다른 프로세스가 강제로 뺴앗지 못하는 상황을 말합니다.

 

원형 대기

프로세스들이 원의 형태를 이루며 자원을 대기하는 것을 원형 대기라고 말합니다. 

ex) 프로세스 A가 자원 1을 점유하고 자원 2를 대기하고, 프로세스 B가 자원 2를 점유한 채 자원 1을 기다리는 경우 입니다.

 

그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요?

앞서 이야기한 4가지 조건 중 하나만 충족시키지 않더라도 교착 상태가 발생하지 않는데, 그 이유는

• 상호 배제를 충족하지 않는 경우 모든 자원을 공유하게끔 함에 따라서 대기 상태가 발생하지 않습니다.
• 점유와 대기가 없는 경우, 점유와 대기 상태가 없어짐으로써 특정 프로세스에 자원을 모두 할당하거나, 할당하지 않게 됩니다.
  • 프로세스가 새로운 자원을 얻을 때, 이미 점유한 자원들을 모두 해제해야하기 떄문에 데드락이 발생하지 않습니다.
• 비선점 조건이 없는 경우, 한 프로세스가 CPU를 할당받아 실행중인 경우, 다른 프로세스는 해당 프로세스가 작업이 종료되어야 비로소 실행됩니다.
• 원형 대기를 없애는 경우, 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당받게 합니다. 이렇게 번호를 붙인다면, 앞서 말한 예시에서 프로세스가 자원1을 점유한 상태에서 자원 2를 대기할 수 있지만, 그 반대는 불가능하기 때문에 데드락이 발생하지 않습니다.

왜 현대 OS는 Deadlock을 처리하지 않을까요?

 효율성과 복잡성을 고려했을 떄, 교착상태를 다루는 것이 오히려 추가적인 비용과 성능 저하를 일으킬 수 있기 때문입니다.

 

현대 OS에선 교착 상태의 발생 빈도가 낮고, 따라서 이를 위해 방지 매커니즘을 설정하는 것이 비효율적이기 때문입니다. 앞서 이야기 한 데드락 예방 조건 중에서 상호 배제, 점유 대기, 비선점 조건이 없는 경우는 현실적이지 않습니다.

 

• 상호 배제가 없는 경우엔 모든 자원을 공유하기 때문에 문제가 발생합니다. (I/O 자원같은 것들은 본질적으로 공유가 불가능하다고 합니다)
• 점유와 대기가 없는 경우, 새로 CPU를 할당받기 위해선 이미 점유한 자원을 모두 해제하거나 프로세스가 한번에 요청을 해야하기 때문에 자원 낭비가 많습니다.
• 비선점 조건이 없는 경우, 선점형 방식으로 동작하게 되며 이렇게 동작할 때 프로세스 대기 시간이 굉장히 길어질 것 입니다.

원형 대기 조건이 없는 조건이 그나마 현실적인데, 하지만 모든 자원에 번호를 붙이는 작업 또한 득보다 실이 크기 때문에 고려해야 할 문제입니다.

 

 

+) 회피 기법에서 은행원 알고리즘을 알고 계신가요?

 

Wait Free와 Lock Free를 비교해 주세요.

 

참고

https://castlejune.tistory.com/23

동기화(synchronization)와 Thread Safe 제대로 이해하기

 

https://velog.io/@appti/CASCompare-And-Set

CAS(Compare And Swap)

https://colabear754.tistory.com/185

[Java] UnmodifiableList는 진짜 불변 리스트가 아니다

https://velog.io/@pakxe/%EB%8B%A4%EC%96%91%ED%95%9C-%EC%A7%80%EC%97%B0-%EA%B7%B8%EB%A6%AC%EA%B3%A0-%ED%8C%A8%ED%82%B7-%EC%8A%A4%EC%9C%84%EC%B9%AD

[컴퓨터 네트워크] 다양한 지연 그리고 패킷 스위칭

https://dkswnkk.tistory.com/480

[네트워크] 데이터 교환 방식 - 패킷 교환