알고리즘 고수가 되기까지

코테 준비

1. 백준 14921 - 용액 합성하기

: 정렬되어있는 수를 양쪽 끝에서부터 투 포인터로 찾아가며, 절댓값이 0이랑 가장 가까운 수를 구하는 문제. 투포인터 기본문제라고 생각함

2. 백준 20366 - 같이 눈사람 만들래?

: 눈덩이를 정렬한 후에, 한 눈사람을 만들 두 개의 눈덩이를 구함. 이 후 그 사이에서 투포인터를 이용해서 그 눈사람과 가장 작은 차이가 나는 눈사람을 구함. 문제를 풀기위한 핵심은 두 눈덩이를 정하고, 거기서 정답이 나올 수 있는 것은 두 눈덩이 사이에서 눈사람을 만들 경우라는 것.

오늘도 고생했다!!!

설명 순서는 다음과 같습니다.

1. Monitor 방법
2. Java에서 Monitor 방법
3. 예시를 보며 이해
4. Java에서 Lock & Condition 방법

1. Monitor 방법

   - Java는 프로그래밍 레벨에서 동기화 문제 해결을 돕기 위해, Monitor 방법을 채택해서 제공

   - Monitor의 전체적인 흐름 : Lock을 획득 -> 임계영역 진입 -> Lock반환. Lock을 획득하지 못할 경우 잠시 대기 상태에 들어가고, 누군가 Lock을 반환할 때 스레드를 깨우는 방법

   - Monitor의 구조

      ① 임계영역 : 한 스레드만 들어가서 실행 가능한 영역

      ② Entry Set : Lock을 얻기위해 대기하는 영역

      ③ Wait Set : Lock을 얻었지만, 실행할 수 있는 조건에 맞지 않아 Lock을 반납하고 대기하는 영역

2. Java에서 Monitor 방법

   - Java 객체는 내부적으로 하나의 Monitor를 가짐

   - 동기화를 위한 키워드

      ① synchronized : 메서드 또는 블럭 앞에 붙임. 이 메서드 또는 블럭은 내부적으로 모니터 락을 획득해서, 상호배제를 보장함

      ② wait() : lock을 획득해서 synchronized 블럭에 들어왔는데 만약 어떤 해당 조건에 만족하지 않아서 일을 진행할 수 없을 때, 내가 갖고 있는 lock을 풀고 wait set에 들어감

      ③ notify() : wait set에 있는 thread 중 하나를 깨워서 entry set에 넣음

      ④ notifyAll() : wait set에 있는 모든 thread를 깨워서 entry set에 넣음

   - 전체적인 흐름

      * Lock획득(synchronized 블럭 진입) -> 임계영역 실행 -> Lock반환(synchronized 블럭 탈출)

      * entry set에 있는 하나의 스레드를 빼서 synchronized 블럭에 진입

      * synchronized 블럭에 들어갔더라도, 조건이 맞지 않은 경우 lock을 풀고 wait set에 들어가고 블럭 탈출

      * 다른 스레드가 synchronized 실행 후 notify로 wait set에 있는 하나를 깨워서 entry set에 넣음

3. 예시를 보며 이해

   - Producer 1번, 2번을 P1, P2로 하고, Consumer 1,2,3번을 C1, C2, C3라 하자

   - 그림의 Buffer는 한번에 한 스레드만 사용해야 함

   - 진행

      ① C1이 Buffer(Buffer의 Lock) 획득. 하지만, Buffer가 비어있으므로(실행할 수 없는 조건) C1은 wait set에 진입

      ② P1, P2, P3가 모두 Buffer를 획득하기를 원해서 P1만 Buffer 획득. 나머지는 entry set에 진입

      ③ P1은 Buffer하나를 채운 후 notify -> wait set에 있는 하나를 깨움 -> C1은 entry set에 진입

      ④ entry set에 있는 P2, P3, C1 중 하나가 Buffer 획득

      ⑤ ... 반복

   - wait set중 어떤 것을 깨울 것인가? entry set중 어떤 것에 Lock을 줄 것인가? -> 이러한 문제는 starvation을 야기할 수 있음.

   - 또한, wait set에 Producer와 Consumer가 같이 관리되기 때문에 만약 Producer가 Buffer를 가득 채우고 wait set에 있는 다른 Producer를 깨우면, 이 Producer는 Buffer를 획득하더라도 채울 수 없기 때문에 또 wait set에 들어감. Producer가 Buffer를 채웠다면, wait set에 있는 Consumer를 깨우는게 더 효율적인 상황임

4. Java에서 Lock & Condition 방법

   - 위와 같은 문제를 해결하기 위해 Lock & Condition 방법을 제공함

   - Monitor 방법과 다른 점은 Condition에 따라 wait set을 따로 구분하는 것임. 위 문제에서는 Producer wait set과 Consumer wait set을 따로 구분함

   - 만약 P1이 Buffer를 채웠다면, Consumer wait set중 하나를 깨워서 entry set에 넣음

   - 반대로 C1이 Buffer를 소비했다면, Producer wait set중 하나를 깨워서 entry set에 넣음

   - 이렇게 스레드의 상태에 따라 종류를 나눠서 wait set을 만들 경우, 더 효율적인 상황이 됨

   - 하지만, 같은 종류의 스레드(ex. P1, P2)끼리의 경쟁은 있기 때문에 기아현상이 발생할 가능성은 여전히 있고, Entry Set중 어떤 스레드에 lock을 줄 것인지에 대한 문제도 있기 때문에 기아현상 여전히 존재

   - 공정하게 lock을 주기 위해서 java에서는 Lock lock = new ReentrantLock(boolean fair) 라는 공정성 매개변수를 제공하는데(true일 경우 오래 기다린 스레드에게 lock을 획득하게함), 그런데 그만큼 성능이 떨어지고, 대부분의 경우 공정함보다는 성능을 채택함

Java에서 Programming Level에서의 동기화 문제를 어떻게 해결하는지 알아볼 수 있었습니다.

설명 순서는 다음과 같습니다.

1. 자원을 공유할 때 생기는 문제
2. 동기화란
3. 임계영역
4. 임계영역 문제 해결 방법

1. 자원을 공유할 때 생기는 문제

   - 두 개의 스레드가 counter라는 변수를 공유한다고 가정하고, 두 스레드 모두 counter++ 메서드를 실행할 때

   - counter++ 명령문은 실제 cpu에서 실행될 때는 3개의 복합 명령문으로 되어있음(counter 변수를 로드하고, counter 값을 1증가시키고, counter에 다시 저장)

   - 그래서 만약 한 스레드가 counter를 로드하고 값을 1증가시키기만 하고 Context-Switching이 발생하고 다른 스레드가 counter++을 한 경우, 업데이트되지 않은 counter값을 참조하게 됨

   - 이렇게 여러 프로세스 또는 스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라서 데이터의 결과가 달라질 수 있는 상황을 'Race Condition'이라고 하고, 이것이 자원을 공유할 때 생기는 문제

2. 동기화란

   - 여러 프로세스 또는 스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것임

   - 위 문제를 보면 3개의 복합 명령문이 실행하는 도중에 Context-Switching이 발생해서 문제가 생겼으므로, '복합 명령문이 실행하는 도중에 Context-Switching이 발생하지 않게끔 하면 해결할 수 있겠다'라고 생각할 수 있음

   - 하지만, 이 해결방법 Single Core일 때만 가능하고 Multi Core일 때는 불가능함. 왜냐하면, 두 스레드 모두 다른 코어에서 동시에 변수를 Load하면 아까와 같은 문제는 피할 수 없음

   - 근본적인 해결방법은 공유 데이터를 한번에 한 스레드나 프로세스만 사용하도록 해야함

3. 임계영역

   - 이렇게 공유 데이터의 일관성을 보장하기 위해서 한 스레드나 프로세스만 진입해서 실행 가능한 영역을 임계 영역이라고 부름

   - 그리고 임계영역의 문제에 대한 해결책이 되기 위한 조건으로 아래 3가지가 있음

      ① 상호배제 : 한번에 하나의 프로세스 또는 스레드만 임계영역에 들어갈 수 있음

      ② 진행 : 만약에 임계영역이 비어있고 그 임계영역에 들어가고 싶은 프로세스나 스레드가 있을 경우, 그 중에 하나는 임계영역에 들어가서 진행이 되어야함

      ③ 한정된 대기 : 어떤 프로세스나 스레드가 무한정 임계영역에 들어가지 못하고 기다리고 있으면 안되는 조건

   - 이 3가지 조건을 모두 만족해야 임계영역 문제에 대한 해결책이 될 수 있음

4. 임계영역 문제 해결 방법

   - 임계영역의 문제를 해결하기 위한 방법은 'Lock'을 사용하는 것

   - 임계영역에 들어가기 전에 락을 걸고, 한 프로세스만 임계영역을 사용한 후, 락을 풀면 이제 다음 프로세스가 임계영역에 락을 걸고 사용하는 방법임

   - 락을 이용한 대표적인 임계영역 구현 방법 : Spinlock, Blocking & Wake up

      ① Spinlock

         * 한 프로세스나 스레드가 임계영역에 들어가기 전에 lock을 걸고, 나머지는 임계영역에 들어가기 위해 lock을 획득하려고 계속 기다리는 상태

         * 하지만, lock을 기다리는 동안 CPU를 낭비함. 락을 계속 확인하는 과정에 다른 프로세스나 스레드가 유용하게 사용할 수 있기 때문임

         * 한정된 대기 조건을 만족시키지 못할 수 있음. 한 스레드만 계속해서 락을 가져가고, 한 스레드는 계속 락을 기다릴 수 있기 때문임

      ② Blocking & Wake up

         * Spinlock의 단점을 극복한 것

         * lock을 획득하기 위해 계속 기다리지 않고 Ready Queue에 들어가서 휴식하는 방법임

         * 그러나 Mutex가 Spinlock 항상 좋은 것은 아님. 멀티코어 환경에서 임계영역에서의 작업이 Context-Switching보다 빠르다면 Spinlock이 더 좋은 성능을 가짐

   - 락을 이용한 대표적인 임계영역 해결 방법 : Mutex, Semaphore

      ① Mutex

         * 하나의 스레드 또는 프로세스만 임계영역에 들어갈 수 있도록 하는 방법

         * 사용하려는 스레드가 lock을 걸고 임계영역을 사용한 후에 unlock을 해야, 다른 스레드가 이 임계영역을 사용할 수 있음

      ② Semaphore

         * 정해진 수의 스레드 또는 프로세스만 임계영역에 들어갈 수 있도록 하는 방법

         * 한 스레드가 임계영역에 들어가서 lock을 획득하고 unlock을 하지 않아도, 옆에 있는 스레드가 unlock을 할 경우 다른 스레드가 임계영역에 들어올 수 있음

동기화에 대해 알아볼 수 있었습니다.

설명 순서는 다음과 같습니다.

1. 가상 메모리
2. 페이지 교체 알고리즘

1. 가상 메모리

   - 메인 메모리의 크기는 한정되어 있어서, 메모리 크기보다 더 큰 프로세스는 현실적으로 실행시킬 수 없음. 또한, 실행하는 여러개의 프로세스의 크기가 메모리보다 크다면 많은 프로세스를 함께 실행시킬 수 없음

   - 이러한 문제를 해결하기 위해 물리적으로 메모리의 크기를 키우지 않고, 메모리를 사용하는 사용자에게 마치 매우 큰 메모리처럼 보이게하는 것이 '가상 메모리' 기법임

   - 해결방법의 핵심은 프로세스 전체를 메모리에 로드하지 않고, 당장 실행에 필요한 프로세스의 페이지만을 메모리에 올리는 것임

   - 여기서 프로세스의 페이지는 프로세스를 책으로 생각했을 때, 그 안에 있는 페이지라고 생각할 수 있음. 그래서 책에서 내가 지금 읽을 페이지만 따로 떼서 읽는 것

2. 페이지 교체 알고리즘

   - 메인 메모리에 필요한 페이지가 없을 때(page fault발생 시), 디스크에서 페이지를 찾아 메모리의 빈 프레임에 로드해야 함

   - 이 때 만약 메모리에 빈 프레임이 없을 경우, 한 프레임을 디스크로 내리고 비워야 함. 이 때 교체될 프레임을 고르는 알고리즘이 페이지 교체 알고리즘임

   - 페이지 교체 알고리즘의 목적은 'page fault 발생 비율을 줄이는 것'임

   - 주요 알고리즘

      ① FIFO(First In First Out)

         * 가장 먼저 메모리에 올라온 페이지를 내보내는 방법

         * 성능이 좋지 않음. 프로세스에 프레임을 많이 할당해도 page fault가 역설적으로 늘어나는 현상 발생할 수 있음

      ② OPT(Optimal)

         * 이상적인 방법. 앞으로 가장 오랫동안 사용하지 않을 페이지를 내보내는 방법

         * 성능이 가장 좋음

         * 하지만, 프로세스가 사용할 페이지를 미리 모두 알아야함. 사실상 구현 불가능

      ③ LRU(Least Recently Used)

         * 가장 오랫동안 사용하지 않은 페이지를 내보내는 방법

         * 성능이 좋은 편

      ④ LFU(Least Frequently Used)

         * 가장 적게 참조된 페이지를 내보내는 방법

         * 시간 지역성을 이용하지 못하므로 성능이 좋지 않다고 생각함. (1번 페이지를 방금 1번 사용했는데, 1번은 또 사용될 가능성이 높기 때문)

      ⑤ MFU(Most Frequently Used)

         * 가장 많이 참조된 페이지를 내보내는 방법

페이지 교체 알고리즘에 대해 알아볼 수 있었습니다.

코테 준비

1. 백준 11723 - 집합

: 집합을 비트로 관리해서 푸는 문제. 비트연산자를 골고루 사용해볼 수 있었던 문제

2. 백준 1194 - 달이 차오른다, 가자

: 가지고 있는 열쇠를 비트 연산으로 푸는 문제. 현재 좌표, 가지고 있던 열쇠 조합으로 방문 처리를 해서 bfs를 이용해 최단 경로를 찾는 문제

오늘 하루도 고생했다!!!

설명 순서는 다음과 같습니다.

1. 트랜스포트 계층
2. TCP란
3. UDP란

1. 트랜스포트 계층

   - 트랜스포트 계층은 송신자와 수신자 간 데이터의 전달을 담당하는 계층

   - 이 계층에서 사용되는 대표적인 프로토콜이 TCP와 UDP임

   - 이 둘은 '어떻게 데이터를 전달할 것인가?' 가 다른 프로토콜임

2. TCP란

   - TCP는 초점을 '신뢰성' 에 둔 데이터 전송방식 임

   - 여기서 '신뢰성'이란 송신자가 보낸 데이터가 수신자에게 그대로 전달됨은 보장함을 뜻함

   - 그래서 데이터를 보내기 전에 미리 3 way handshake를 맺고, 패킷에 번호를 붙여 순서와 유실성을 판단하고, 데이터를 다 보낸 후에는 4 way handshake를 통해 연결을 종료함

   - 데이터의 신뢰성이 중요한 서비스에서 사용됨

3. UDP란

   - UDP는 초점을 '속도' 에 둔 데이터 전송방식 임

   - 여기서 '속도'란 송신자가 보낸 데이터가 빠르게 수신자에게 전달하는 것이 목적임을 뜻함

   - 단순히 보낼 패킷을 수신자에게 보낼 뿐이어서, 중간에 유실될 수도 있고 패킷의 순서 또한 보장할 수 없음

   - 신뢰성보다 속도가 중요한 서비스에서 사용됨(ex. 스트리밍)

TCP와 UDP에 대해 알아볼 수 있었습니다.

설명 순서는 다음과 같습니다.

1. 데드락이란
2. 데드락의 발생 조건
3. 데드락 해결 방법

1. 데드락이란

   - 두 개 이상의 프로세스가 서로가 가진 리소스를 기다려서 더 이상 진행되지 못하는 상태

2. 데드락의 발생 조건

   - 아래의 4가지 조건을 모두 만족해야 데드락이 발생함

   - 조건

      ① 상호 배제 : 한 리소스는 한번에 한 프로세스(스레드)만 사용할 수 있음. 동시에 같이 사용할 수 없음.

      ② 점유 대기 : 한 리소스를 점유하고 다른 프로세스(스레드)가 사용하는 리소스를 기다리는 상태.

      ③ 비선점 : 다른 프로세스가 사용하는 리소스를 강제로 빼앗을 수 없음.

      ④ 순환 대기 : 프로세스들이 순환 형태로 서로의 자원을 기다리고 있는 상태.

3. 데드락 해결 방법

   - 해결 방법은 크게 3가지로 나누어 볼 수 있음. 예방, 회피, 탐지 & 회복.

   - 예방은 데드락 발생 조건 중 하나라도 만족하지 못하게 해서, 데드락의 발생을 예방하는 방법.

   - 회피는 자원을 할당하기 전에, 할당하더라도 데드락이 발생하지 않는지 확인 후 자원을 할당하는 방법.

   - 탐지 & 회복은 데드락이 발생하게끔 둔 다음, 회복하는 방법.

   - 예방

      ① 상호 배제를 부정 : 리소스를 같이 사용할 수 있게끔 만들어야함. 그렇지만, 이럴 경우 동기화 문제 발생. 사실상 불가능한 방법

      ② 점유 대기를 부정 : 사용할 리소스를 모두 얻은 후에 진행 가능. 대기하는 상황을 없애는 것임. 하지만, 지금 당장 사용하지 않는 리소스를 가져가는 바람에 다른 프로세스는 이 리소스를 사용하지 못함. 리소스 사용효율이 떨어짐. 또한, 사용할 리소스가 인기가 많아서 한꺼번에 확보하기가 쉽지 않다면, 진행할 수 없음.

      ③ 비선점을 부정 : 다른 프로세스가 리소스를 강제로 빼앗을 수 있게 만듬.(기아현상 발생 가능할 듯)

      ④ 순환 대기를 부정 : 자원에 번호를 붙이고, 번호가 작은 것부터 요청할 수 있도록 하는 것

   - 회피

      ① 리소스를 요청했을 때, 데드락이 발생할 가능성이 있는지 확인 후에 없으면 할당하는 방법

      ② 리소스를 요청할 때마다 특별한 알고리즘으로 매번 확인해야하는 오버헤드가 발생함

      ③ 미리 어떤 자원을 요구할 지 알아야 함

   - 탐지 & 회복

      ① 자원 할당 상태를 파악하여, 데드락이 발생했는지 탐지한 후에, 데드락을 해결(회복)하는 방법

      ② 데드락을 탐지하는 방법은 자원 할당 그래프 등을 통해서 알 수 있음

      ③ 회복하는 방법은 한 프로세스씩 종료하거나 아니면 일시적으로 리소스의 선점을 가능하도록 함

      ④ '어떤 프로세스를 종료' 하거나 '어떤 프로세스가 리소스를 선점' 할 때, '어떤 프로세스'를 정해야하는데 이 때 특정 프로세스만 자원을 할당받아 다른 프로세스는 '기아현상'이 벌어지지 않도록 해야함

      ⑤ 기아현상을 해결하기 위해 리소스를 오래 대기할 수록 우선순위를 높여주는 방식을 채택할 수 있음

데드락에 대해 알아볼 수 있었습니다.

코테 준비

1. 백준 7579 - 앱

: dp에서 cache배열을 이용할 때 메모리나 범위가 넘어선다면, 생각을 전환해서 cache배열을 만들자. 위 문제로 예를 들면, 최소의 cost를 구하는 문제라면 최대의 memory로 바꿔서 생각하자

2. 백준 2629 - 양팔저울

: 어떤 탐색이 중복되는지 확인하자. 결국 knapsack은 dp이다

오늘 하루도 고생했다