1. 김영한 실전 자바 - 기본편 (섹션 1~4)
2. 객체지향의 사실과 오해 (1장~3장)

김영한 실전 자바

참조형 변수는 어떻게 변수에 담긴 값이 참조값이라는 것을 알 수 있을까

참조형 변수에 대해서는 이전에 자바스크립트를 공부하면서 개념은 알고 있었다. 변수에 주소값이 들어 있다면 해당 주소로 가서 거기에 있는 데이터를 읽는다는 것에는 익숙했다. 하지만 이번에 강의를 다시 들으면서 과연 컴퓨터는 참조값(주소값)인 것을 어떻게 알 수 있을까? 주소값도 숫자로 해석할 수 있기 때문에 기본형 변수로 인식할 수 있는 것이 아닐까라는 생각이 들었다.

인텔리제이에서 직접 객체를 출력해보면, 패키지명.클래스명@주소값 이런 형식으로 출력된다. 뭔가 자바 안에서 구분할 수 있는 방식이 존재하는 것 같은데 객체형 변수와 참조형 변수를 치면 표면적인 차이점에 대해서 서술한 글이 대부분이었다.

메모리 구조에 대해서 더 알아보면 답을 얻을 수 있을 것 같아서 구글링을 해보니까 기본형 변수는 Stack 내의 기본 자료형을 넣는 영역에 들어가고, 참조형 변수의 참조값(주소값)은 Stack 내의 참조형을 넣는 영역에 들어간다라고 나온다. 뭔가 약간의 찝찝한 내용이었다. 추론을 해보자면, 스택안에서 기본형 변수와 참조형 변수의 참조값을 저장할 때 구분자를 통해서 구별을 할 수 있을 것 같은데 정확한 메커니즘을 모르겠다. 우선 인프런에 질문을 남긴 상태이다.

객체지향의 사실과 오해

이 책의 1장부터 3장까지 읽으면서 인상 깊었던 내용을 나만의 언어로 정리해보겠다

저자는 1장부터 3장까지 한결같은 내용을 말하는 것 같다. 클래스라는 개념에 매몰되지 말고, 객체지향에서 중요한 것은 객체 자체라는 점, 그리고 객체를 정의함에 있어서 중요한 것은 객체가 하는 행동이라는 점, 마지막으로 객체는 책임을 가지고 있고 이 책임을 완수함과 동시에 다른 객체들과 협력하는 존재라는 점이다.

아직 객체지향에 대한 감이 정확하게 오지는 않지만, 이 책에서 반복되서 언급되는 점들을 계속 곱씹어보면 언젠가는 이해되는 날이 오지 않을까라는 생각이 든다.

2023년 7월부터 인턴, 2023년 11월부터 정규직으로 금융권에서 IT직군으로 종사하면서 느낀 점이 여럿 있다. 현재 회사를 다니며 주관적인 느낀 점을 몇가지만 추려 작성해보겠다.

장점

1. 모난 사람이 없다.

부서마다 다를 수 있겠지만, 부서 내 분들이 모두 둥글둥글한 성격을 가지고 계셔서 인간관계에서 힘든 것을 느끼지 못했다. 이 부분에 있어서는 굉장히 큰 장점인 것 같다.

2. 급여와 복지가 만족스럽다.

사회초년생의 입장으로서 충분한 급여와 복지가 제공된다고 생각한다. 부족하다고 느낄 수 없이 풍족한 삶을 살 수 있다.

3. 워라밸이 잘 지켜진다.

물론 야근이 없는 것은 아니지만, 일이 없다면 칼퇴해도 되는 분위기이다. 매달 결산 같은 행위를 하는 날을 제외하고는 칼퇴가 가능하다.

단점

1. 개발자 커리어에 고민이 생긴다.

분명히 들어올 때는 플랫폼개발 직군으로 들어왔지만, 프로젝트를 하다보니, 실제 개발은 외주 직원분들이 한다. 내가 하는 일은 전체적인 프로젝트가 올바른 길로 나아갈 수 있게하는 관리 정도이다. 프로젝트 관리부분도 적성에 맞다고 생각하긴 하지만, 난 여전히 개발을 하고 싶다. 냉정하게 말해서 회사 생활 1년간 개발 역량은 크게 늘지 않았다고 생각한다. 이로 인해 시장 내에서의 개발자로서 나라는 사람의 가치도 떨어졌다고 생각한다.

2. 좋은 코드를 짜기 위해 고민할 시간이 많지가 않다.

현업 비즈니스 하시는 분들의 요청에 의해 프로그램을 개발하는데 이 분들과 협업하는 것에 있어서 아쉬운 점이 많다. 감사나 정책이 변경되었을 때 프로그램을 수정해야할 때가 많은데 이 분들은 기획을 하시는 분들도 아니고, 영업 업무가 1순위이고, 기획은 후순위이다. 그러다 보니, 개발이 1순위인 나와의 협업이 항상 후순위로 여겨지는 경우가 많아 아쉽다. 그 분들이 잘못했다기 보다는 인력 운영 측면에서의 아쉬움이 있다. 결국 마감 전에 요건이 겨우 확정되어 돌아가게만 개발하는 경우가 부지기수이다.

3. 사수가 없다..?

부서에 개발팀이 생긴지 얼마 안되서 팀장님을 제외한 다른 분들은 모두 IT직군이 아니었는데 회사 내 교육을 받고 IT직무를 배정받은 분들이다. 회사생활 측면에서는 배울 점이 많지만, 개발적인 측면은 오히려 내가 알려드리는 경우가 많다. 팀장님 조차도 관리자 역할을 하시는 분이다 보니 처음 개발을 할 때 정말 막막했다. 아예 다른 부서 직원분들께 물어물어가며 겨우 프로그램을 완성시켰던 기억이 있다. 그때 회사에서 개발자로 일하기 좋지 않은 환경이라고 느꼈다.

앞으로의 계획

현재 진행중인 프로젝트가 2025년 9월에 종료된다. 나는 그 이후로 회사를 떠나려고 한다. 위의 글을 봐도 장점은 짧게 썼고, 단점을 좀 길게 쓴 것을 보면 나는 어쩌면 현재 회사에 만족하지 못하는 것 같다. 현재 내 가치관으로는 급여, 워라밸 보다는 개인적 성장이 더 우선시 되는 것 같다. 그래서 요즘 퇴근하거나 주말에 공부를 하기 시작했다. 개발자로서 역량이 발전되지 않는 회사 환경에서 어떻게든 발전하기 위해 노력하려고 한다. 2025년 9월에는 이직 준비를 바로 할 수 있는 역량을 갖춘 사람이 되고 싶다.

TCP/IP 프로토콜을 사용한다는 것은 IP를 통해서 데이터의 실질적인 전송을 처리하고, TCP를 통해서 통신의 신뢰성을 보장한다는 의미이다.

통신의 신뢰성을 망치는 요인은 여러가지가 있다. 이미 전송된 패킷이 손실되거나, 패킷의 순서가 바뀌거나, 네트워크의 혼잡으로 인해 패킷이 이동하지 못하거나, 수신 측에서 패킷을 받을 공간이 없을 경우 가 있다. 결국 운영체제의 프로토콜 스택을 거쳐서 만들어진 패킷이 상대측에 제대로 전달되지 못하는 경우 통신의 신뢰성은 없다고 말한다. 앞에서 TCP를 통해서 통신의 신뢰성을 보장한다고 말했다. 위 4가지 문제를 TCP는 어떻게 해결할까?

흐름 제어

송신측이 데이터 처리 속도가 더 빠른 경우를 생각해보자. 수신측의 버퍼가 가득찼음에도 송신측에서 패킷을 지속적으로 보낸다면, 이미 버퍼가 찬 상태에서 수신된 패킷은 손실될 것이다. 이를 막기 위해 수신측 버퍼의 용량이 얼마나 남았는지 파악하고 패킷을 보내어 송신측과 수신측의 데이터 처리 속도 차이로 인한 패킷 손실을 막는다.

Stop and Wait

전송된 패킷에 대한 응답을 받고 나서야 다음 패킷을 보낸다. 딱 봐도 비효율적이라는 것이 느껴진다.

Sliding Window

3-way handshake 과정에서 수신측의 window size를 파악하고, 송신측의 window size를 설정한다. 그리고 마지막 전송 Bytes - 마지막 ACK Bytes <= 수신측의 남은 window size 를 만족하는지 확인하고, 이에 맞춰서 데이터를 추가 전송한다. 수신측에서 응답을 보낼 때 남은 window size를 세그먼트에 담아 보내기 때문에 송신측에서는 지속적으로 보내야할 양을 파악할 수가 있다. Stop and Wait 방법과 가장 큰 차이점은 수신측이 처리할 수 있는 데이터의 양을 알고 있다는 것이다. 이로 인해 더 유연한 처리가 가능해진다.

혼잡 제어

사용하는 네트워크가 혼잡하다면, 송신측에서 보낸 패킷이 수신측에 도달하지 못해서 처리를 할 수 없기 때문에 이를 손실된 데이터로 간주하고 재전송한다. 이렇게 되면 안그래도 혼잡한 네트워크가 더 혼잡한 상태로 된다. 이를 막기 위해 TCP는 송신측에서 보내는 데이터의 전송 속도를 조절한다. 이를 혼잡 제어라고 한다.

AIMD (Addictive Increase Multicative Decrease)

처음에 패킷 하나를 보내는 것으로 시작한다. 패킷이 문제 없이 도착한다면, Window Size를 1씩 늘린다. 하지만, 패킷 전송에 실패하거나, timeout이 발생하면 Window Size를 절반으로 줄인다.

이 방식의 특징은 여러 호스트가 네트워크를 공유하고 있다면, 나중에 전송을 시작한 호스트가 처음에는 네트워크 점유에 있어서 불리하지만, 시간이 지날수록 평형 상태로 맞춰진다. 단점으로는 초기에 많은 양의 데이터를 보내지 못하고, Window Size를 줄일 때면, 이미 네트워크가 혼잡해져 있는 상태라는게 문제다.

Slow Start

AIMD와 마찬 가지로 패킷 하나를 보내는 것으로 시작하지만, Window Size를 두 배씩 늘린다. 혼잡 현상이 일어나면, Window Size를 1로 줄인다. 초기에는 네트워크 혼잡에 관한 정보가 없기 때문에 Window Size가 두 배씩 증가하다가 1로 줄어든다. 이후에는 임계값까지는 2배씩 증가하다가 이후에는 혼잡 회피 단계로 전환한다.

혼잡 회피 : Window Size가 임계값보다 클 경우 데이터 손실이 발생할 가능성이 높기 때문에 Window Size를 보수적으로 늘릴 필요가 있다. Window Size를 1씩 늘리다가 timeout의 발생으로 네트워크 혼잡이 감지된다면, Window Size를 1로 줄이고, 임계값을 혼잡이 발생했던 때 Window Size의 절반으로 줄인다.

오류 제어

이제 남은 문제 상황은 패킷이 손실되었거나, 패킷의 순서가 바뀌었을 때이다. TCP는 ARQ(Automatic Repeat Request), 재전송 기반으로 오류를 제어한다. 언제 재전송을 해야하는지가 가장 중요한 포인트라고 볼 수가 있다.

중복된 ACK를 받았을 때

송신측에서 Sequence Number를 부여하여 패킷을 보내고, 이에 수신측은 송신측에게 다음에 보낼 패킷이 무엇인지 ACK를 통해 알려준다. 송신측이 동일한 ACK를 지속적으로 받는다면, 이는 해당 패킷이 제대로 수신측에 도달하지 못했음을 알 수가 있다. 하지만 한 번 중복된다고 바로 재전송을 하지는 않고, 3회 정도 같은 ACK를 받았을 때 해당 패킷을 재전송한다. 왜냐하면 송신측에서 보낸 패킷이 모두 동일한 속도로 수신측에 도달하는 것을 보장하지는 못하기 때문이다.

Stop And Wait

응답에 대한 요청을 받고 난 뒤 다음 데이터를 보내면, 자동적으로 재전송에 기반한 오류 제어가 가능해진다. 하지만 위에서 말했듯이 TCP는 슬라이딩 윈도우 방식으로 데이터를 보내기 때문에 여기에 맞춰진 오류 제어 방법이 필요하다.

Go Bank N

Go Bank N 방식을 사용하면, 수신 측에서 N번 패킷부터 에러가 발생함을 감지하면, 송신측에 N번 패킷부터 다시 전송해달라고 요청하고, 이후 데이터들을 모두 폐기한다. 송신측은 N번 패킷부터 재전송한다.

Selective Repeat

Go Bank N은 에러가 발생한 패킷 이후에 수신된 패킷들도 모두 폐기한다는 문제점이 있다. 이 문제를 해결하기 위해 Selective Repeat 방식이 등장한다. 문제가 있는 패킷에 대해서만 재전송을 요청한다. 하지만 이 방법을 사용하기 위해서는 별도의 버퍼가 추가적으로 필요하다. 중간에 에러가 발생한 패킷이 빠져 있을텐데 이를 재정렬 해야하기 때문이다.

위 두 방법 중 더 효율적인 것을 선택해서 사용한다. 하지만 불확실한 네트워크를 통해 재전송하는 것보다 수신 측에서 재정렬 하는 것이 더 낫다는 판단 하에 Selective Repeat을 많이 채택하는 것 같다.

참고한 글

https://evan-moon.github.io/2019/11/22/tcp-flow-control-error-control/ https://gyoogle.dev/blog/computer-science/network/%ED%9D%90%EB%A6%84%EC%A0%9C%EC%96%B4%20&%20%ED%98%BC%EC%9E%A1%EC%A0%9C%EC%96%B4.html

Memory Hierarchy

캐시 메모리

• 속도가 빠른 장치와 느린 장치 간의 속도차에 따른 병목 현상을 줄이기 위한 메모리
• 빠른 SRAM을 사용한다. 하지만 비싸다 -> 용량이 작다

크고, 싸고, 빠른 메모리를 만드려면 어떻게 하냐 -> memory hierarchy으로 그런 효과를 내자!

지역성

이를 위해 지역성을 활용한다.

시간 지역성

• 참조된 메모리 주소는 다음에도 참조될 수가 있다 => 가장 최근에 접근된 메모리를 CPU와 가까운 곳에 위치시키자!

공간 지역성

• 메모리 주소가 참조되었다면, 그 주변의 메모리 주소도 참조될 수가 있다 => 메모리 주소가 속한 블럭(주변 메모리 주소)을 CPU와 가까운 곳에 위치시키자!

캐시 관련 용어

Cache Block(Line)

캐시에 데이터를 저장할 때 특정 자료구조를 사용해서 묶음으로 저장하는데 이를 캐시 블럭이라고 한다. 저장된 데이터에 대한 정보가 있다! 캐싱된 데이터들이 흩어져있기 때문에 이에 바로 접근하기 위해 존재한다

Cache Hit

요청한 데이터가 캐시에 있을 때

Cache Miss

요청한 데이터가 캐시에 없을 때

Cache Miss 종류

1. Cold Miss : 메모리 주소를 처음 참조할 때
2. Conflict Miss : 데이터를 저장할 때 다른 데이터가 해당 캐시 블럭에 할당되어 있는 경우
3. Capacity Miss : 캐시 메모리의 공간이 부족할 때

캐시 동작 방식

캐시 블럭을 불러왔을 때 하위 몇비트를 활용해 캐시 메모리의 인덱스에 대응시킨다. 만약 캐시 메모리의 블럭의 수가 64개라면, 8비트를 사용하여 메모리 블럭에 인덱싱할 수 있다. 그리고 그 위의 비트들은 tag로 사용한다.

tag가 필요한 이유 캐시 메모리의 캐시 블럭이 8개이고, 캐시 블럭은 5비트라고 가정해보자. 그러면 캐시 메모리에 인덱싱하기 위해서 하위 3비트를 인덱스로 사용하고 상위 2비트를 태그로 사용한다.

만약에 처음에 26이라는 주솟값이 들어왔다. 이를 이진수 주소로 바꾸면 11010이다. 캐시 메모리 인덱스 010에 태그 11과 data 영역에 전체 메모리 주소를 저장한다. 이 다음에 18이라는 주솟값이 들어왔다. 이를 이진수 주소로 바꾸면 10010이다. 인덱스는 010이다. 앞서 26이라는 주소값과 같은 인덱스를 가지게 된다. 만약에 인덱스로만 판별을 했다면, 18이라는 주소가 들어왔음에도 26이라는 주소와 같다고 인식해서 메모리에 26주소에 저장된 값을 요청했을 것이다! -> 이를 막기 위해 tag가 필요하다!!

그래서 캐시는 다음과 같이 작동한다.

1. 들어온 주솟값에서 인덱스를 추출하여 이를 통해 캐시 메모리의 인덱스 부분에 접근한다.
2. Valid bit를 확인한다. (Valid bit -> 올바른 값이 존재하는지)
3. Valid bit가 1이면, 들어온 주소의 태그와 캐시 메모리의 태그가 같은지를 비교한다.
4. Valid bit와 비교결과를 AND 연산하여 1이 나오면 Cache Hit!!!

Valid bit가 0이면 들어온 주소에 대한 정보를 캐시에 기록하고 Valid bit를 1로 바꾼다.

태그가 불일치하면 교체 정책에 따라 교체되는 블럭이 달라진다.

Cache 구조

Direct Mapped Cache

여러 메모리 주소가 캐시 메모리의 하나의 캐시 블록에 대응되는 방식 간단하고 빠르지만, Conflict Miss가 발생활 확률이 높은 것이 단점이다. 캐시 동작 방식에서 설명한 방식이 Direct Mapped Cache가 동작하는 방식이라고 생각하면 된다.

Fully Associative Cache

비어있는 캐시 블록이 있다면, 마음대로 주소를 저장한다. 하지만 저장하고 나서 데이터를 찾을 때 문제가 있다.

Set Associative Cache

특정 블럭끼리 set으로 묶고 한 인덱스가 이 캐시 블럭의 set을 가리키는 방식이다. Direct Mapped Cache와 Fully Associative Cache의 중간 형태다. 캐시 히트인지 아닌지를 판단하기 위해 인덱스에 해당하는 set의 블럭을 모두 확인한다.

Stable

• stable한 정렬이라는 의미는 중복된 요소를 정렬할 때 초기 배열에서 주어진 순서를 유지하는 정렬을 의미한다!
• 이 의미는 알고 있었지만, 왜 쓰는지에 대해서는 고민이 부족했다. 이번 기회에 생각해봤다.

stable, unstable을 구별하는 이유(뇌피셜)

• 우선 숫자로만 이루어진 배열을 정렬할 때는 stable, unstable을 구별해서 사용하는 것이 의미가 없다고 판단했다. ex) [1,25,3,6,3,3]
• 하지만 배열의 요소가 복합적으로 구성되어 있고, 중복되는 key값을 가지는 요소에 대해 원래 순서를 유지해야하는 상황이라면 Stable Sort를 해야한다.

  # 주문 목록을 처리할 때, 수량이 작은 주문부터 처리하고, 
  # 수량이 같을 경우에는 들어온 순서대로 처리해야하는 상황을 가정해보자.
  

배열 => [(수량, 이름)]

arr = [(10, "김시환"), (3, "이수지"), (4, "임연수"), (3, "이다연")]

배열의 요소의 첫번째 요소를 기준으로 정렬!

이경우에 Unstable sort를 사용하면 원하는 결과값을 얻지 못할 수도 있다! Stable Sort를 사용하면 항상 원하는 결과값을 얻을 수 있다! 따라서 Stable Sort를 사용하는 것이 합리적이다.

위와 같은 가상 상황을 고려해봤을 때, Unstable Sort를 사용하면, 중복된 Key를 갖는 요소들의 이전 순서를 보장하지 못한다. 그러므로 추가적인 (비효율적인) 확인 과정이 필요하다. 

정렬을 해야하는 문제 상황이 주어지고, 목표에 따라서 정렬 알고리즘을 선택할 수 있는 기준 중 하나로 `Stable/Unstable` 이 사용된다고 결론내렸다.

## In-place

in-place 정렬은 원소들의 개수에 비추어 봤을 때 무시할만한 추가 공간을 사용하거나, 추가 공간을 사용하지 않는 정렬 알고리즘이다.

`in-place sort가 필요한 이유`
가장 처음 생각할 수 있는 이유는 공간 복잡도에서 이득이다. 그럼 공간이 충분할 경우에는 in-place sort인지 아닌지가 중요하지 않다는 결론이 나오는데 뭔가 찝찝해서 인터넷 서칭을 했다.

내가 읽은 블로그 글에서는 in-place sort를 쓰는 이유를 `공간 지역성` 때문이라고 말한다. 

메모리를 할당받을 때, page 단위로 할당받는다. 추가적인 공간을 사용한다는 것은 연속적이지 않은 메모리를 사용한다는 말이다. in-place sort를 했을 때는 배열의 요소들이 연속적인 메모리 상에 올라가 있을 것이다. 하지만, 그렇지 않은 정렬은 추가적인 메모리를 할당받는데, 이때 이 메모리들은 연속적이지 않다. 따라서 In-place sort의 공간 지역성이 좋다. 이를 통해 캐시의 성능을 높일 수 있기 때문에 성능적으로 차이가 날 것이다.

굉장히 합리적인 이유를 찾은 것 같다. 한 수 배웠다.

[참고한 글](https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=wjdwoaud159&logNo=222365210954&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView)

유니온 파인드 (Union-Find) : 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

그래프를 합치는 Union 연산과 루트 노드를 찾는 Find 연산으로 이루어져있다.

항상 써야 할 때마다 직접 구현하다 보면 시간이 좀 걸려서 전체적인 틀 자체는 외워두는 것이 좋다고 판단하여 정리한다.

우선 노드 별로 자신의 부모 노드를 저장하는 배열(parents)을 선언한다. 초기 부모 노드의 값은 자기 자신이다. 이후 Find와 Union을 구현한다.

Find 연산

def find(x) {
    if x == parents[x]:
        return x
    parents[x] = find(parents[x])
    return parents[x]
}

가장 눈여겨 보아야 할 점이 루트 노드를 탐색하면서 그와 동시에 parents 배열을 업데이트 한다는 점이다. 이를 통해 루트 노드를 접근하는데 필요한 시간을 줄일 수 있다. 이를 경로 압축이라고도 부른다.

Union 연산

def union(x,y) {
    x = find(x)
    y = find(y)
    if x != y:
        parents[y] = x
}

두 노드를 합치는 연산에서는 우선 두 노드의 루트 노드를 찾는다. 루트 노드가 같다면 이미 합쳐져 있는 상태이기 때문에 고려할 필요가 없고, 다르다면, 한 노드의 루트 노드를 다른 노드의 루트 노드로 설정한다. 이제 두 노드는 같은 루트 노드를 가지고 있기 때문에 한 그래프에 속한다고 볼 수가 있다!

HTTP (HyperText Transfer Protocol) : 인터넷 상에서 데이터를 주고 받는데 사용되는 프로토콜

HTTP의 특징

클라이언트 - 서버 구조

클라이언트는 서버에 요청을 하고, 서버는 해당 요청에 대한 응답을 클라이언트에게 보내는 구조로 데이터를 주고 받는다!

Stateless

Stateless : 서버가 클라이언트의 상태를 유지하지 않는다!

클라이언트가 A,B,C라는 요청을 순서대로 하고 이에 대한 결과를 이어 서버에 ABC라는 값을 저장하고 싶다고 해보자.

<서버가 상태를 유지할 경우> 클라이언트는 A,B,C 요청을 하기만 하면 서버에 클라이언트의 상태가 유지되어 있기 때문에 A 요청을 했다면 서버에 해당 클라이언트가 A를 요청했다는 상태가 유지되기 때문에 B와 C 요청이 들어왔을 때, 요청에 대한 결과를 이어 붙이기만 하면 된다!

<서버가 상태를 유지할 수 없는 경우> 클라이언트는 우선 A요청을 한다. 다음에 클라이언트가 B 요청을 할 때, 서버는 클라이언트가 A요청을 이미 했다는 사실을 알지 못한다. 따라서 클라이언트는 B 요청을 할 때, 이전에A요청을 했다는 사실도 같이 전달해야 한다.

Stateless의 장점 : 서버에서 상태를 유지하지 않기 떄문에 서버 증설이 쉽다! 따라서 과도한 트래픽이 발생하거나 서버 오류가 발생했을 떄, 대처하기가 쉽다.

하지만 실무에서 모든 것을 Stateless로 개발할 수는 없다!! -> 로그인 같은 기능을 구현할 때에는 로그인 상태가 유지되어야 한다!!

비연결성

HTTP는 기본적으로 연결을 유지하지 않는다! -> 이런 점의 문제 : HTTP를 사용할 때마다 TCP 연결을 새로해야함 -> 비용 발생! -> 이를 해결하기 위해 HTTP 지속 연결 : TCP 연결을 한번 하고 종료되기 까지 발생하는 많은 HTTP를 처리

거의 모든 형태의 데이터 전송 가능

HTTP 메시지에 거의 모든 형태의 데이터를 담아 전송할 수 있다!

HTTP 메서드

GET : 리소스 조회 POST : 요청 처리, 메시지 바디를 통해 서버로 요청 데이터 전달! PUT : 리소스 대체, 클라이언트가 리소스 위치를 알고 URI 지정! PATCH : 리소스 부분 변경 DELETE : 리소스 삭제

HTTP 메서드 속성

Safe

• 호출해도 리소스를 변경하지 않는다

Idempotent(멱등)

• 몇 번을 호출하더라도 결과가 같다
• GET, PUT, DELETE -> 멱등
• POST -> 멱등 x

Cachable

• GET,HEAD,POST,PATCH 캐시 가능!
• 실제로는 GET,HEAD 캐시로 사용
• POST, PATCH는 메시지 바디의 내용까지 캐싱하도록 구현이 쉽지 않다

HTTP Status code

상태 코드

상태 코드 : 클라이언트가 보낸 요청의 처리 상태를 응답에서 알려주는 기능

2xx (Successful)

• 200 : 요청 성공
• 201 : 요청 성공 -> 새로운 리소스 생성
• 202 : 요청이 접수되었으나 처리까지는 되지 않음
• 204 : 요청 성공헀지만, 응답의 본문 내용 없음

  3xx (Redirection)

• 웹브라우저는 3xx 응답의 결과에 Location 헤더가 있으면, Location 위치로 자동으로 이동한다!
• 301, 308 : 영구적으로 URI 이동, 301은 리다이렉트 시 요청 메서드가 GET으로 변함
• 302, 303, 307 : 일시적으로 URI 변경, 302와 303은 리다이렉트 시 요청 메서드가 GET으로 변한다.

4xx (Client Error)

• 오류의 원인이 클라이언트에 있다!
• 400 : 잘못된 요청
• 401 : 인증 필요!
• 403 : 승인 거부 -> 접근 권한이 불충분한 경우
• 404 : 요청 리소스가 서버에 없다!

5xx (Server Error)

• 오류의 원인이 서버에 있다!
• 500 : 서버 내부 오류
• 503 : 서버 과부하나 작업 등으로 요청 처리 일시적 불가

처음 프론트엔드 개발을 공부하고, 프로젝트를 하면서 API를 사용한 적이 있다. 이떄 CORS Error를 겪었다. 당시에는 구글링을 통해 해결책을 보고 공개되어 있는 CORS-ANYWHERE 프록시 서버로 우회하는 방법을 사용했다. 하지만 그 서버가 닫히고, 직접 cors-anywhere 를 배포하여 사용하는 과정을 겪으면서 근본적인 원인을 알고 싶었다.

SOP

SOP : Same Origin Policy, 다른 출처 리소스를 사용하는 것을 제한하는 보안 방식

출처 : URL의 Protocol, Host, Port이 3가지로 하나의 출처를 결정한다.

SOP를 쓰는 이유

• 악의적인 목적으로 해커가 제공하는 리소스에 접근하지 못하도록 막아서 보안을 유지한다.

SOP를 사용하면 보안에 도움이 된다. 하지만 현대의 웹에서 같은 출처의 리소스만을 사용하기에는 너무 아쉽다. 다른 출처의 리소스로의 접근이 필요하다.

CORS

SOP의 위와 같은 문제를 해결하기 위해 CORS가 등장한다.

Cross-Origin Resource Sharing (CORS) is an HTTP-header based mechanism that allows a server to indicate any origins (domain, scheme, or port) other than its own from which a browser should permit loading resources. - MDN

CORS 접근제어 시나리오

1. Preflight 요청

• Preflight : OPTIONS 메서드를 통해 실제 요청 전에 다른 출처의 리소스에 접근이 가능한지 확인하는 작업 => 요청 가능하다고 판단되면 실제 요청 전송
• 왜 Preflight가 필요한가
  • Preflight가 없이 바로 실제 요청을 하게 된다면, 요청이 서버로 도달하여 해당 작업을 끝내고 브라우저를 거쳐 클라이언트로 응답이 갈 때, CORS에러가 발생한다. 이렇게 되었을 경우에는 이미 클라이언트의 요청을 서버가 실행하고 난 후이다. 이렇게 되면 보안적으로도 문제가 생길 수 밖에 없기 때문에 Preflight를 사용한다.

2. 단순 요청

• Preflight 과정 없이 바로 요청 보낸다.
• 다음과 같은 조건을 모두 만족해야함
  • GET,POST,HEAD
  • CONTENT TYPE : application/x-www-form-urlencoded, multipart/form-data, text/plain
  • HEADER : Accept, Accept-Language, Content-Language, Content-Type

3. 인증정보 포함 요청

• 인증 관련 헤더를 포함할 때 사용하는 요청

그래서 CORS 에러를 어떻게 해결하나

cors-anywhere를 fork한다. 그리고 Koyeb에서 깃허브를 통한 배포를 하고, API요청 앞에 해당 서버의 URL을 붙여서 API요청을 시도하면 CORS에러가 해결되는 것을 볼 수가 있다.

cors-anywhere의 역할 : 응답 헤더에 요청 출처를 첨부하여 CORS에러가 발생하지 않게 해준다!

콜백 헬 비동기 함수의 콜백함수는 태스크 큐에 대기하고 있다가 콜스택이 비어 있으면 이벤트 루프에 의해 콜 스택으로 푸시되어 실행된다. => 이때문에 비동기 처리 결과를 반환하거나 상위 스코프에 전달할 수가 없다. => 이를 위해 비동기 함수의 처리 결과를 위해 비동기 함수의 처리 결과를 가지고 또다시 비동기 함수를 호출하게 된다. -> 콜백 헬

에러 처리 문제
콜백 함수는 태스큐 큐에 저장되어 있다가 콜 스택이 비어 있으면 이벤트 루프에 의해 콜 스택으로 푸시되어 실행된다고 말했다. 에러는 호출자 방향으로 전파된다. => 콜 스택의 아래 부분의 실행 컨텍스트로 전파된다. 하지만, 비동기 함수는 이미 콜 스택에서 제거된 상태이다. 따라서 에러 검출을 할 수가 없다.

Promise

Promise : 비동기 처리 상태와 처리 결과를 관리하는 객체 Promise는 인수로 resolve 함수와 reject 함수를 받는다. 비동기 처리가 성공하면 처리 결과를 resolve 함수에 인수로 전달하여 호출하고, 실패하면 reject 함수에 인수로 전달하여 호출한다.

Promise 상태

• pending : 비동기 처리가 수행되지 않은 상태
• fulfilled : 비동기 처리가 성공된 상태 (resolve 함수 호출 이후)
• rejected : 비동기 처리가 실패한 상태 (reject 함수 호출 이후)

  Prmoise 후속 처리 메서드

• then : 두 개의 콜백 함수를 인수로 전달받음 -> 첫번째 콟백 함수는 fulfilled 상태일 때 호출, 두번째 콜백 함수는 reject 상태일 때 호출
• catch : 한 개의 콜백 함수를 인수로 전달받음 -> 이 콜백 함수는 reject 상태일 때만 호출
• finally : 성공, 실패와 상관없이 무조건 한 번 호출

이 메서드들은 언제나 Promise를 반환하기 때문에 연속적으로 호출할 수 있다! -> 프로미스 체이닝 그리고 에러 처리 같은 경우도 후속 처리 메서드를 통해 쉽게 할 수 있다.

async/await

제너레이터

제너레이터 : 코드 블록의 실행을 일시 중지했다가 필요한 시점에 재개할 수 있는 특수한 함수

일반 함수와의 차이

1. 제너레이터 함수는 함수 호출자에게 함수 실행의 제어권을 양도할 수 있다.
2. 제너레이터 함수는 함수 호출자와ㅏ 함수의 상태를 주고받을 수 있다.
3. 제너레이터 함수를 호출하면 제너레이터 객체를 반환한다.

제너레이터 객체의 next 메서드를 실행하면 yield까지 실행되고 일시 중지된다. 이때 함수의 제어권이 호출자로 양도된다. 이후 다시 실행하려면 호출자가 next 메서드를 호출하면된다.

호출자는 yield 뒤의 값으로 제너레이터 객체의 상태 값을 꺼내올 수 있고, next메서드에 값을 통해 제너레이터로 값을 보낼 수도 있다!

async/await

async/await를 사용하면 프로미스의 후속 처리 메서드에 콜백 함수를 전달해서 비동기 처리 결과를 처리할 필요 없이, 동기 처리처럼 프로미스를 사용할 수 있다!! async : async 함수는 언제나 promise 반환 await : async 함수 내부에서만 사용 가능!, 프로미스가 settled 상태가 될때까지 대기하다가 settled 상태가 되면 프로미스가 resolve한 결과를 반환!

정규화 : 이상 현상을 제거하기 위한 테이블을 분리하는 행위

이상 현상

1. 삽입 이상 : 불필요한 데이터를 추가해야지만 추가할 수 있는 상황
2. 갱신 이상 : 일부만 변경되어 데이터의 불일치가 발생하는 상황
3. 삭제 이상 : 튜플 삭제로 인해 꼭 필요한 데이터까지 삭제되는 상황

이런 이상 현상을 제거하기 위해 정규화를 사용한다. 테이블을 분리하는 것으로 해결할 수 있다.

제1정규화

• 모든 속성의 값을 원자값(Atomic)으로 만든다!

  제2정규화

• 기본키가 복합키로 이루어진 경우, 키를 제외한 나머지 속성들은 완전 함수 종속을 유지해야한다!
• 예를 들어 기본 키가 A,B로 이루어져있다고 해보자. 만약 C라는 속성이 A만 사용해서 구별할 수 있는 상황이라면, C를 알아내는데 B는 필요가 없다. 그럼에도 B와 C가 같이 있어 불필요한 중복이 발생한다. => 기존 테이블에서 A,C를 따로 빼와 새로운 테이블로 만드는 것이 불필요한 중복을 제거하는 방법이다!

  제3정규화

• 이행적 함수 종속 제거!
• 만약 A,B,C,D의 속성을 가진 테이블이 있고, A가 기본키라고 가정해보자. 그런데 B만 알아도 C와 D가 결정된다고 해보자. 이럴 경우 테이블을 A,B 테이블과 B,C,D 테이블로 분리!
• 이렇게 분리하면, C나 D를 업데이트할 때, 이상 현상을 막을 수가 있다!

BCNF

• 모든 결정자가 후보키에 속하도록 하자!
• 후보키에 속하지 않은 속성이 어떤 속성을 결정할 수 있다면, 이상 현상 발생 가능!

대체적으로 3정규화와 BCNF까지 정규화한다고 한다. 정규화하면 이상 현상을 막을 수는 있지만, 결국 테이블을 분리하는 것이기 때문에 나중에 사용할 때 join같은 추가적인 연산이 발생해 실행 시간이 늘어날 수 있다.

IP주소를 기억하기 어렵다. DNS(Domain Name System) : 도메인 이름을 네트워크 주소로 변환하는 시스템 따라서 의미가 있는 도메인 이름을 도입해 이를 IP주소로 변환하는 DNS를 사용하여 편의성을 제공한다.

DNS 구성요소

로컬 DNS 서버 : 도메인 네임에 대한 IP주소를 검색할 때 가장 먼저 찾는 서버, 로컬 DNS 서버는 다른 DNS 서버와 통신을 한다. SKT,KT같은 인터넷 서비스 제공자들이 제공하는 DNS 서버

루트 DNS 서버 : 최상위 DNS 서버, 로컬 DNS 서버가 가장 먼저 요청하는 서버 TLD 서버 : 루트 도메인 바로 아래 단계 ex) .com, .io ... Sub DNS 서버 : .을 기준으로 DNS 도메인이 계층적으로 구분되어 있고, 이에 맞춰 DNS 서버도 계층적 구조를 가진다.

DNS 동작

브라우저에서 www.naver.com 을 검색했을 때, DNS가 어떻게 동작하는지 알아보자.

1. 웹 브라우저는 브라우저 캐시와 Hosts 파일을 확인하여 해당 도메인에 대한 IP주소가 캐싱되어 있는지 확인하고, 캐싱되어 있다면, 바로 해당 IP 주소로 접속한다. Hosts 파일 : 호스트 이름에 대응하는 IP주소가 저장되어 있는 파일

2. 로컬 DNS 서버에 호스트 네임에 대한 IP주소를 요청한다. 만약 로컬 DNS 서버에 해당 도메인에 대한 IP주소가 캐싱되어 있다면, 바로 해당 IP 주소로 접속

3. 캐싱되어 있는 것이 없다면, 도메인 네임에 대한 IP 주소를 위해 로컬 DNS 서버와 다른 DNS 서버와 통신 시작

4. 루트 DNS 서버에 www.naver.com에 대한 IP 주소를 요청 => 해당 IP주소가 없어 로컬 DNS 서버에게 com DNS 서버의 IP 주소를 알려준다.

5. com DNS 서버에 www.naver.com에 대한 IP 주소를 요청 -> 해당 IP주소가 없어 Authoritative DNS Server의 IP 주소를 알려준다. Authoritative DNS Server : 가비아 같은 도메인 관리 업체에서 운영하는 DNS 서버

6. Authoritative DNS Server에는 www.naver.com에 대한 IP주소가 있다. 로컬 DNS 서버는 응답으로 해당 IP주소를 받는다.

7. 로컬 DNS 서버는 해당 IP 주소를 캐싱하고 IP주소를 전달한다.

TCP는 네트워크 계층 중 전송 계층에서 사용하는 프로토콜로서, 논리적인 연결을 설정하여 신뢰성을 보장하는 연결형 서비스 이다.

3-way handshake

데이터를 전송하기 전에 신뢰성을 위해 상대방 컴퓨터와 논리적인 연결을 수립하는 과정

상대방을 어떻게 식별할 수가 있나 => TCP Header에 있는 컨트롤 비트 중 SYN과 ACK을 사용 => client와 server 모두 상대방이 보낸 SYN값에 1을 더하여 ACK에 넣어서 보낸다 => 이를 통해 내가 연결 요청을 보낸 상대방으로 부터 온 응답인지 확인할 수 있다!

4-way handshake

client가 서버로 부터 FIN을 받았음에도 바로 CLOSED가 되지 않는 이유 => FIN을 받자마자 CLOSED 된다면... => Server에서 FIN을 보내기 전에 보냈던 데이터가 네트워크 지연 같은 문제로 FIN요청보다 늦게 도착하는 경우 해당 데이터는 유실된다! => 이를 방지하기 위해 client는 FIN요청을 받더라도 일정시간 대기 후 CLOSED

패킷이 순서대로 서버에 도착하지 않아도 순서 보장을 할 수가 있는가? => TCP Header의 Sequence number를 통해서 수신 측에서 패킷을 재조합하는 과정을 거친다!!

위 과정들을 통해서 TCP는 신뢰성 있는 통신을 제공한다. TCP는 데이터를 보내고 그에 따른 응답 패킷(sequence number가 1 증가된)을 받아야 제대로 전송되었다고 파악 -> 그렇지 않다면 패킷 재전송!! (네트워크 성능에 영향 미칠 수 있다)

UDP

UDP는 전송계층의 비연결형 프로토콜이다. 데이터를 주고받기 전에 논리적 연결하는 과정을 거치지 않는다. 이때문에 TCP에 비해 빠르지만, 전달의 신뢰성이 떨어진다. TCP와 달리 패킷의 순서가 보장되지 않고, 유실되더라도 재전송 요청을 하지 않는다.

this : 자신이 속한 객체 또는 자신이 생성할 인스턴스를 가리키는 자기 참조 변수 this는 자바스크립트 엔진에 의해 암묵적으로 생성, 함수를 호출하면 this가 암묵적으로 함수 내부로 전달된다.

this 바인딩은 함수 호출 방식에 의해 동적으로 결정된다!!!

함수호출 방식에 따른 this 바인딩

1. 일반 함수 호출

• 일반함수에서는 this에는 전역 객체가 바인딩된다!
• 하지만 일반함수에서 this는 별 의미가 없음
• 어떤 함수라도 일반 함수로 호출된다면 전역 객체에 바인딩된다!!
• strict mode시, undefined에 바인딩됨

2. 메서드 호출

• 메스드를 호출한 객체에 바인딩된다! ("." 앞에 있는 객체를 의미)

3. 생성자 함수 호출

• 생성자 함수 내부의 this에는 생성자 함수가 생성할 인스턴스가 바인딩된다!

4. Function.prototype.apply / call / bind 메서드에 의한 간접 호출

• 메서드에 첫번째 인수로 전달한 객체에 바인딩된다!
• apply와 call은 함수를 호출하면서 this를 지정할 수 있다.
• bind는 함수를 호출하지 않는다. -> this 바인딩이 교체된 함수를 새롭게 생성해 반환한다!

화살표 함수

콜백 함수를 일반 함수로 호출되면 this가 전역 객체를 가리키게 되는 문제가 있었다. -> 이를 ES6에서 도입된 화살표 함수로 해결할 수 있다.

화살표 함수와 일반 함수의 차이

1. 화살표 함수는 non-constructor이다. -> 생성자 함수로 호출 불가
2. 중복된 매개변수 이름을 선언할 수 없다 -> 일반 함수는 가능 (비엄격 모드에서)

   function f(i,i) {return i+i}
   f(2,2) // 4
   

const a = (i,i) => i+i; // SyntaxError

3. 화살표 함수는 함수 자체의 this, arguments, super, new.target 바인딩을 가지고 있지 않다.
- 화살표 함수 내부에서 이를 참조하면 스코프 체인을 통해 상위 스코프의 것을 참조함

### this에서의 차이
콜백 함수의 this와 외부 함수의 this가 다르다는 문제점을 화살표 함수 등장 전에는 다음과 같이 해결했다

1. 외부함수에서 this를 다른 변수에 저장한 후, 콜백 함수에 그 변수를 this 대신 사용
```js
...
method(a) {
    const that = this;
    return a.map(function (item) {
      return that.~~~
    })
}

2. Function.prototype.bind 메서드를 사용!

ES6에서는 화살표 함수를 사용하여 콜백 함수의 this와 외부 함수의 this가 다른 문제를 해결할 수 있다!

...
method(a) {
    return a.map((item) => this.~~~
}

화살표 함수가 this 바인딩을 가지지 않기 때문에, 상위 스코프의 this를 참조한다.=> 이를 lexical this라고 한다. 화살표 함수의 this가 함수가 정의된 위치에 의해 결정된다는 의미이다.

메서드를 화살표 함수로 정의하면 안된다!! -> 이 경우 this가 메서드를 호출한 객체에 바인딩되는 것이 아니라 전역 객체에 바인딩된다!

Deadlock

Deadlock : 스레드들이 서로가 점유한 자원을 사용하기 위해 무한정 대기하는 상태

Deadlock 발생 조건

1. 비선점 : 다른 스레드가 사용하고 있는 자원을 강제로 빼앗아올 수 없음
2. 상호 배제 : 공유 자원에 하나의 스레드만 접근 가능
3. 점유와 대기 : 자원을 추가적으로 얻으려고 할 때, 기존의 자원을 계속 들고 있는 것
4. 원형 대기 : 스레드들이 원하는 자원이 서로 물리고 물려 원형 관계를 이루는 상태

이 네가지를 모두 충족해야 Deadlock이 발생한다.

Deadlock 해결 방법

Prevention

위의 네 가지 조건 중 하나라도 만족하지 않게 하여 Deadlock이 발생되지 않도록 하는 방법

1. 원형 대기 예방 : 모든 스레드에서 적용되는 락을 얻는 순서를 지정한다!
2. 점유와 대기 예방 : 필요한 모든 lock을 한번에 얻도록한다!
3. 비선점 예방 : 얻지 못하는 lock이 존재한다면, 오류를 발생시켜 나중에 시도하게 만든다 => 문제점 : livelock : lock을 얻고 해제하는 일만 계속 반복하는 현상 => livelock은 작업 사이에 지연 시간을 줘서 해결한다
4. 상호 배제 예방 : 뭔가 말이 안맞는 느낌, lock을 쓰는게 결국 상호배제를 목적으로 하는 것이 아닌가? => 하드웨어 명령어를 통해서 원자적으로 실행되게 한다. => 상호 배제를 고려할 필요가 없게됨 (lock을 안써도됨)

=> 하지만 이렇게 될 경우, 자원 사용에 있어 효율이 굉장히 떨어져 잘 사용하지 않는 방법이다

Avoidance

1. 서로 같은 공유 자원을 사용하는 스레드는 같은 CPU를 사용하도록 한다! => load balancing에 문제가 생긴다. => 특정 CPU에만 실행되어야할 스레드들이 몰릴 수가 있음!
2. Bnker's Algorithm

• 최악의 경우를 기준으로 하여 Deadlock을 피한다
• 각 프로세스는 자신이 사용할 최대 자원의 수를 OS에게 알려준다 -> 이를 통해 safe/unsafe 판단
• 가용가능한 자원의 수보다 크거나 같은 프로세스의 기대 자원이 있다면 -> safe!!

Avoidance 문제점

1. Process가 사용할 모든 자원을 미리 선언해야한다. -> 미리 알고 있어야 avoidance가 가능
2. 시스템의 전체 자원 수가 고정되어야함
3. 자원 낭비
4. 자원을 요청할 때마다 확인하는 과정의 비용이 매우크다

Detect & Recover

-> 그냥 deadlock이 발생하는 스레드를 발견한다면 kill한다. -> deadlock이 많이 발생하는 시스템에서 주로 채택

Ignore

-> Deadlock이 발생하지 않을 것처럼 동작한다.(무시한다) -> 놀랍게도 대부분의 OS에서 사용한다. -> Deadlock을 handling하는 것이 load가 너무 크기 떄문에!

결국 한 프로세스내에서 스레드는 메모리를 공유하기 때문에 병렬 처리를 할 때, 속도가 메모리 사용 측면에서 강점을 가진다. 하지만, 스레드를 제대로 사용하기 위해서는 몇 가지를 제대로 고려해야한다.

스레드 사용 시 발생하는 문제점

1. 개발자가 실행 순서를 정확히 알지 못한다 2개의 스레드가 존재하고, 각 스레드는 counter에 1을 더한 후 저장하는 작업을 수행한다. counter = counter + 1은 사실 원자적으로 수행되지 않는다. 기계어로 바꾸어 보면, counter에 있는 값을 eax레지스터에 옮기고, eax레지스터 값을 1 증가시킨 후, eax값을 다시 counter에 넣는다. 이렇게 3개의 기계어의 조합으로 코드가 작동된다. 그런데 기계어를 실행하는 도중에 context switch가 일어난다면? => 위 사진처럼 counter의 값이 기댓값인 52가 아니라 51이 나온다. 스레드 별로 레지스터를 독립적으로 보유하고 있다. 스레드1에서 eax레지스터 값을 증가시켜 51이 되었지만, 그와 동시에 context switch가 발생하여 CPU제어권이 스레드2로 넘어갔다. 스레드2에서 3개의 기계어를 모두 수행하면, counter에는 51이 들어가 있다. 그 후 스레드1로 CPU제어권이 다시 넘어온 뒤, 스레드1의 eax레지스터에 있는 51을 counter로 옮기면 counter는 51이다. => 개발자는 counter가 52가 되기를 바랬을 것이다. 하지만 원하는대로 코드가 작동되지 않는다.

2. 프로세스 내 주소 공간을 공유하기 때문에 critical section이 존재하고 이로 인해 race condition이 발생한다. 위 그림의 문제의 원인은 counter라는 변수를 스레드들이 공유해서 사용하고 있다는 것이다. 공유 변수에 접근하는 부분을 critical section이라고 한다. 여러 스레드들이 critical section에 접근할 때 발생하는 문제를 race condition이라고 한다.

이 문제점들을 해결하기 위해서는 명령어들이 원자적으로 실행되어야 한다. 이를 구현하기 위해서 lock이라는 개념이 등장한다.

Lock

Controlling Interrupts

명령어의 원자성을 해치는 요소 중 하나가 interrupt다. critical section에 있을 때 interrupt를 받지 않도록 해버린다면? => 원자성을 보장할 수는 있다.

문제점

1. interrupt를 활성화/비활성화 하는 것이 load가 많이 든다.
2. 활성화/비활성화 하는 스레드에 대한 100% 신뢰가 필요하다. 악의적 사용자가 CPU제어권을 독점할 수도 있다.
3. 멀티 프로세서에서는 동작하지 않는다. 다른 CPU의 스레드에서 critical section에 접근한다면, 스레드의 인터럽트 비활성화는 의미가 없다.
4. 인터럽트를 받지 않는 것 자체가 문제! ex) I/O

Using Simple Flag

lock이 되었는지 아닌지를 보관하는 flag 사용 lock이 걸리면, flag 1로 설정 lock을 가지지 않는 스레드가 CPU 제어권을 가졌을 때, flag가 1이라면 무한 루프를 돌면서 대기 lock을 해제하면, flag 0으로 설정

문제점

1. lock을 걸고 flag를 1로 설정하기 전에 context switch가 발생할 수도 있다!!
2. spin-waiting : while문을 사용해서 계속 대기하는 것이 비효율적이다!

Test And Set

원자적으로 lock과 flag를 동기화할 수가 있다 이로써 단순히 flag만 사용했을 때 발생하는 문제점1을 해결할 수 있다. 하지만 여전히 spin-waiting은 존재한다.

지금까지 구현한 lock을 평가해보자.

1. 정확성 : mutual exclusion을 구현할 수 있다
2. 공평성 : spin-lock은 공평함을 보장하지 못한다.
3. 성능 : spin-lock은 CPU를 계속 사용하면서 대기하는 것이므로 성능 bad

Fetch And Add

fairness를 보장하기 위해 등장! 원자적으로 값을 증가시킬 수 있다 lock을 호출하면 해당 스레드는 Fetch And Add를 통해서 기존 티켓 넘버를 가지고 티켓 넘버를 1증가시키는 것을 원자적으로 할 수가 있다! lock을 가졌던 스레드가 unlock을 하면 turn 값이 1씩 증가한다. 이때도 Fetch And Add사용함. turn 값과 같은 티켓 넘버를 가진 스레드가 lock을 얻게 됩니다. -> 모든 스레드 실행 보장(fairness)

하지만 여전히 spin-waiting이 발생하고 있다. -> OS의 도움 필요!

Just Yield

spin이 발생하면 다른 스레드들이 실행될 수 있도록 CPU제어권을 양보한다!

문제점

1. 여러 개의 스레드가 같은 lock을 얻으려 한다면, 계속 context switch 발생!!
2. fairness 보장 x

Using Queues

lock을 가진 스레드가 unlock을 할 때, 다음 lock을 얻을 스레드를 지정! 스레드가 lock을 얻지 못한다면 큐에 추가!

문제점

여전히 spin-waiting이 아예 없지는 않다. 하지만, 스레드들이 큐에 보관되기 때문에 spin-wait 할 때 쓰는 시간을 줄일 수 있다!

Semaphore

Semaphore : Lock과 동작 원리는 같지만, sem이라는 변수를 0과 1이 아니라 그 이상의 정수로 설정할 수 있게 하여 하나 이상의 스레드가 critical section에 접근할 수 있게 한다

lock과 unlock을 사용하는 것이 아니라 sem_wait와 sem_post를 사용하여 sem의 값을 조절한다. sem_wait : sem 1 감소, sem <= 0 라면, 큐에서 대기 sem_post : sem 1 증가

Lock과는 달리 Semphore는 락 해제의 주체와 락 획득의 주체가 같지 않을 수도 있다!

이벤트 루프

자바스크립트 엔진은 단 하나의 실행 컨텍스트 스택을 갖는다. -> 동시에 2개 이상의 함수를 실행할 수가 없다!! 실행 컨텍스트 스택 최상위에 있는 컨텍스트만이 실행되는 태스크 (싱글 스레드) 싱글 스레드 방식은 한 번에 하나의 태스크만 실행할 수 있다.

• 동기 처리를 했을 때, 실행 시간이 많이 걸리는 태스크를 실행하는 경우 -> 블로킹이 발생한다
• 비동기 처리를 하면 현재 실행 중인 태스크가 종료되지 않은 상태라 해도 다음 태스크를 곧바로 실행한다.

동기 처리는 실행 순서가 보장되지만, 블로킹 되는 단점이 있다. 비동기 처리는 블로킹이 발생하지 않지만, 실행 순서가 보장되지 않는다.

자바스크립트의 동시성을 지원하는 것이 이벤트 루프 이벤트 루프는 브라우저에 내장되어 있는 기능이다!

대부분의 자바스크립트 엔진은 크게 2개의 영역으로 구분이 가능하다

• 콜 스택 : 실행 컨텍스트 스택
• 힙 : 객체가 저장되는 메모리 공간, 실행 컨텍스트는 힙에 저장된 객체를 참조 객체는 크기가 정해져 있지 않기 때문에 할당할 메모리 공간의 크기를 런타임에 동적으로 결정해야함!

비동기 처리에서 소스 코드의 평가와 실행을 제외한 모든 처리는 브라우저 또는 node.js가 담당 ex) setTimeout의 콜백 함수의 평가와 실행은 자바스크립트 엔진이 담당하지만, 타이머 설정과 콜백 함수 등록은 브라우저 또는 node.js가 담당 -> 이를 위해 브라우저는 태스크 큐와 이벤트 루프를 제공한다.

• 태스크 큐 : 비동기 함수의 콜백 함수나 이벤트 핸들러가 일시적으로 저장됨
• 이벤트 루프 : 콜 스택에 현재 실행중인 실행 컨텍스트가 있는지, 태스크 큐에 대기 중인 함수가 있는지 반복해서 확인 -> 콜 스택이 비어 있고, 태스크 큐에 대기 중인 함수가 있으면, 이벤트 루프는 태스크 큐에 대기 중인 함수를 콜 스택으로 이동시킨다.

브라우저와 자바스크리트 엔진이 협력하여 비동기 함수를 실행한다!!

실행 컨텍스트 : 코드를 실행하기 위해 필요한 스코프, 식별자, 실행 순서 등을 관리를 구현한 내부 메커니즘, 모든 코드는 실행 컨텍스트에 의해 실행되고 관리된다.

소스코드의 평가와 실행

자바스크립트 엔진은 소스코드를 2개의 과정, 소스코드의 평가와 소스코드의 실행으로 나누어 처리한다

• 평가 과정
  • 실행 컨텍스트 생성
  • 변수, 함수 등의 선언문 먼저 실행
  • 식별자를 키로 실행컨텍스트가 관리하는 스코프에 등록함
• 실행 과정
  • 평가 이후 실행
  • 소스코드 실행에 필요한 변수나 함수의 참조를 실행 컨텍스트가 관리하는 스코프에서 검색
  • 소스코드의 실행 결과는 다시 실행 컨텍스트가 관리하는 스코프에 등록됨 ex) 변수 재할당

코드 실행 순서는 실행 컨텍스트 스택으로 관리 식별자와 스코프는 실행 컨텍스트의 렉시컬 환경으로 관리

실행 컨텍스트 스택

• 코드의 실행 순서를 관리
• 소스코드가 평가되면 실행 컨텍스트가 생성되고 실행 컨텍스트 스택 최상위에 들어간다
• 실행 컨텍스트 스택의 최상위에 있는 실행 컨텍스트는 언제나 현재 실행 중인 코드의 실행 컨텍스트다

렉시컬 환경

• 스코프와 식별자를 관리
• 환경 레코드 와 외부 렉시컬 환경에 대한 참조로 이루어진다
• 환경 레코드 : 스코프에 포함된 식별자를 등록하고 등록된 식별자에 바인딩된 값을 관리하는 저장소
• 외부 렉시컬 환경에 대한 참조 : 상위 스코프를 가리킴 -> 스코프 체인 구현

실행 컨텍스트와 블록 레벨 스코프

let,const 키워드로 선언된 변수는 블록 레벨 스코프를 따른다. 예를 들어, if문 같은 코드 블록이 실행되면, 코드 블록을 위한 블록레벨 스코프를 생성해야한다. 이때 렉시컬 환경을 새로 생성하여 전역 렉시컬 환경을 교체한다. 외부 렉시컬 환경에 대한 참조를 전역 렉시컬 환경을 가리키게 한다. if문이 끝나면, 이전의 전역 렉시컬 환경으로 돌아온다. for문의 변수 선언문에 let 키워드를 사용하면, 코드 블록이 반복될 때마다 코드 블록을 위한 새로운 렉시컬 환경을 생성한다.

클로저

자바스크립트는 렉시컬 스코프를 따른다! 렉시컬 스코프 : 함수를 어디서 선언했는지에 따라 상위 스코프가 결정된다 렉시컬 스코프를 따르기 때문에 함수는 자신이 어디서 정의되었는지 기억해야 하고, 상위 스코프의 참조를 자신의 내부 슬롯 [[Environment]]에 저장한다. 이는 현재 실행 중인 실행 컨텍스트의 렉시컬 환경을 가리킨다.

클로저 : 외부 함수보다 중첩 함수가 더 오래 유지되는 경우, 이미 생명 주기가 종료된 외부 함수의 변수를 참조할 수 있다. -> 이 중첩 함수를 클로저라 한다.

함수가 기억하는 상위 스코프는 어디서 호출하든 항상 유지된다! -> 함수는 언제나 자신이 기억하는 상위 스코프의 식별자를 참조할 수 있다. 식별자에 바인딩된 값을 변경할 수도 있다!

클로저의 활용

클로저는 상태를 안전하게 변경하고 유지하기 위해 사용한다! 상태를 안전하게 은닉하고, 특정 함수에게만 상태 변경을 허용한다!

순서에 조건이 붙어있는 경우 일반적인 DFS같은 것으로 구현했을 때, 깔끔하게 구현이 되지 않음을 많이 느꼈다. 이때마다 위상 정렬이라는 개념이 등장했고, 위상 정렬에 대해서 제대로 정리해보자

위상 정렬 : 주어진 조건을 위배하지 않으면서, 노드를 순서대로 정렬하는 것

위상 정렬의 조건

위상 정렬을 할 그래프는 DAG이어야 한다. DAG : Directed Acyclic Graph, 직접 연결된 사이클이 없는 그래프 한 마디로 사이클이 있는 그래프에서는 위상 정렬을 할 수가 없다 why? => 사이클이 존재하게 되면, 선행 조건이 없는 노드(시작점)을 찾을 수가 없기 때문에!!

위상 정렬 하는법

1. 진입차수가 0인 node를 큐에 삽입
   • 진입차수 : node에 들어오는 edge의 수(한마디로 선행 조건의 수)
2. 큐에서 원소를 꺼내 해당 노드와 연결된 edge를 제거
3. edge 제거 후 진입 차수가 0인 node를 큐에 삽입
4. 만약 모든 원소를 방문하기 전에 큐가 비면, 사이클이 존재한다!
5. 그렇지 않다면, 큐에서 꺼낸 순서가 위상 정렬의 순서!

4번 과정을 보면, 그래프에 사이클이 존재하는지를 파악하는 방법도 위상 정렬이다.

위상 정렬에 대해 알아봤는데 생각보다 어렵지 않았다. 개념을 적용해서 문제를 풀어보자.

백준_1766번

• 문제를 조건에 맞는 순서대로 풀어야 한다
• 조건 중에 가능한한 쉬운 문제부터 푼다는 조건때문에 heap이 필요하다!
• 진입차수를 저장할 배열과 그래프 경로를 저장할 공간이 필요하다
• 이를 활용하여 위에 적혀진 방법대로 구현하면 어렵지 않다
• 링크 : https://github.com/htogether7/algorithm/blob/main/graph/1766.py

CFS에서 레드 블랙 트리를 통해 프로세스를 관리하여 탐색시간을 줄인다. binary search tree를 사용하면 탐색 시 O(logN)의 시간복잡도를 가진다.

하지만.. 만약 트리가 편향된다면 어떻게 될까?

binary search tree가 편향된다면, 원소를 찾을 때, O(N)의 시간복잡도를 가지게 된다. 이럴 경우, binary search tree를 유지할 필요가 없다!! => 이를 보완하기 위해 자동으로 균형을 맞춰주는 balanced tree가 등장했고, 그 중 하나가 red-black tree다.

레드 블랙 트리

기본 규칙

1. 레드 블랙 트리는 트리의 노드를 빨간색 또는 검은색으로 칠한다
2. 루트 노드는 검은색이다
3. NIL(리프 노드)은 검은색으로 취급
4. 빨간색 노드의 자식들은 검은색 노드다.
5. 루트 노드에서 모든 리프 노드로 갈 때 거쳐가는 검은색 노드의 수는 같다

   위 규칙을 수행하면 높이를 제한할 수 있나?

b(x) = x부터 NIL까지 갈 때 거쳐가는 black node의 수 (x 미포함, NIL포함)

서브 트리가 모두 black 노드일 때가 서브 트리의 노드 수가 최소가 될 때이다!!

x를 루트로 하는 서브 트리의 노드 개수를 n(x)이라고 하자. n(x) >= 2^(b(x)) -1 를 만족한다. b(root) >= height/2를 만족한다. (기본 규칙 4번과 5번때문에.. ex) b(root) == 3이면, 높이의 최대는 red와 black을 번갈아 가면서 배치한 6이다!)

위 두 식을 합하면 n(root) + 1 >= 2^(height/2)이 되고, 이 양 변에 로그를 씌우면 height <= 2*log(n(root)+1) 가 된다.

따라서 red-black 트리에서 원소를 탐색할 때 걸리는 시간은 O(logN)이다!!

새로운 노드가 들어오면?

새로운 노드를 그대로 추가하면, red-black tree의 기본 규칙에 위배될 수가 있다! 단순히 노드를 추가하는 것이 아니라, 추가적인 동작이 필요하다!

새로운 노드를 삽입할 때는 red 노드를 삽입한다. 그리고 기본 규칙에 위배될 경우, 다음 2가지 방식 중 하나를 수행한다. 어떤 동작을 수행할지는 uncle node(부모의 형제 node)를 확인한다!

Reconstructing

• uncle node가 black node일 때
• 방법
  1. 삽입된 노드, 부모 노드, 조부모 노드를 정렬한다.
     2. 가운데 값을 부모 노드로 만들고, 다른 두 노드를 자식 노드로 만든다. 부모 노드는 black node, 자식 노드는 red node로
     3. 이후 아래에 다른 노드들을 이어준다.

Repainting

• uncle node가 red node일 때
• 방법
  1. 부모와 삼촌을 black node로 만든다.
     2. 조부모를 red node로 만든다.
     3. 조부모를 red node로 만들었을 때, 규칙 4가 위배될 수 있다.
     4. 이 경우 조부모 node를 삽입된 node라고 생각하고, 과정을 재귀적으로 진행

평소에 red-black tree에 대한 막연한 개념만 가지고 있었는데, 어떻게 red-black tree가 balanced하게 유지될 수 있는지에 대해서 구체적으로 알게 되었다.

메모리 주소

초기에는 프로그램을 실제 메모리에 직접 올려서 사용, 하지만 컴퓨터는 time sharing, multiprogramming을 하기 때문에 이보다 발전된 방법이 필요하다!

메모리 가상화 : 실제 메모리는 하나지만,OS는 프로세스에게 프로세스가 마치 자신만의 메모리를 갖고 있는 것 같은 illusion을 준다.

OS는 메모리를 추상화해서 프로세스들에게 배분한다. address space로 메모리를 추상화!!

주소 공간에 할당된 주소가 실제 메모리의 주소가 아니다! 주소 공간의 주소를 OS가 변환하여 실제 메로리 주소로 바꾼 후 사용한다. -> address translation

주소 변환

OS는 프로그램이 자신에게 할당된 메모리에만 접근하도록 제어한다! Virtual memory address -> Physical memory address

Dynamic Relocation

base 레지스터 ,bounds 레지스터 를 활용하여 Virtual Address -> Physical Address 실제 메모리 주소 = 가상 메모리 주소 + base bounds 레지스터는 bounds보다 큰 가상 메모리 주소를 변환하려고 하면 오류를 발생시킨다! MMU : 주소 변환을 돕는 프로세서 부분 문제점 : 주소 공간을 통째로 실제 메모리에 매핑하다 보니 heap과 stack 사이의 빈 공간이 낭비된다!! 실제 64bit 리눅스에서는 128TB 주소 공간을 할당하기 때문에 실제 메모리에 매핑하기도 곤란하다.

Segmentation

CPU의 MMU에 base 레지스터, bounds 레지스터가 하나만 존재하는 것이 아니라 base 레지스터와 bounds 레지스터가 쌍으로 segment(code, heap, stack)를 표현한다! code, stack, heap 별로 물리 메모리로 매핑 => stack과 heap 사이의 공간 낭비 x => 사용하는 메모리만 할당 제일 앞에 있는 2bit로 segment를 판별한다! -> segment table에서 base를 가져옴 -> offset + base = 실제 메모리 주소

segment table : 각 프로세스 별로 segment table을 가지고 있으며, segment 별 base, bounds 유지

문제점 : External Fragmentation External Fragmentation : 메모리를 할당/해제를 반복하다 보면, 사용가능한 메모리 공간의 합이 할당할 프로세스가 필요한 메모리보다 큼에도, 나뉘어져 있어 프로세스를 할당하지 못하는 경우 -> 메모리 공간이 파편화되어있다!

free space를 관리하는 여러 방법도 있지만, optimal solution이라고 볼 수 있는 방법은 딱히 없다. compaction : 파편화된 메모리 공간을 하나로 합치는 과정 -> 그러나 cost가 너무 크다!!

Paging

• 가상 주소 공간을 일정한 크기의 page로 나눈다.
• 실제 주소 공간을 일정한 크기의 page frame으로 나눈다.
• 프로세스 별로 가지고 있는 page table를 활용해 page를 page frame에 할당

Paging의 장점

• 고정 크기로 메모리를 다루기 때문에 고려해야할 것들이 줄어듬
• 여유 공간이 단순해진다 -> external fragmentation 방지

문제점

1. Internal fragmentation : page size보다 작은 데이터를 할당하면 page 안에 남는 공간이 발생한다!!
2. Page table에 접근하고, 거기서 얻은 PTE를 통해 실제 메모리로 접근한다. -> 총 2번의 메모리 접근 -> 성능 저하!
3. 매우 큰 page table

Translation Lookaside Buffers(TLB) MMU의 한 부분, VPN과 PFN이 쌍으로 존재하는 cache! 주소 변환을 할 때, page table(메모리)을 확인하기 전에 TLB를 먼저 확인! TLB를 사용하여 paging 속도를 높일 수 있다

TLB를 사용해 paging의 속도를 높이려고 할 때 고려할 Issue

• TLB도 다른 캐시와 마찬가지로 Cache Miss가 발생한다! Cache Miss를 어떻게 처리할 것인가..
  1. Hardware : page table의 위치와 내용을 정확히 알아야 한다! 빠르지만, intelligent하지 못하다(victim 선정), 그리고 비싸다!
  2. OS : TLB miss -> trap -> kernel mode -> page table -> TLB update -> return-from-trap -> retry

• 하드웨어로 처리하는 방식보다는 느리지만, CPU가 단순해진다.

• Context Switch
  • 여러 프로세스가 실행되다보면, TLB table 상에 같은 VPN을 사용하는 TLB entry가 겹칠 수 있다!
    • 프로세스를 구별하기 위해 추가 비트 사용(ASID)!

Page table의 크기를 줄이는 방법은 없을까?

• Page의 크기를 늘리면?
  • Page table은 줄어들지만, internal fragmentation이 발생할 가능성 높아짐!!
• segmentation + paging
  • 각 segment(code, heap, stack)별로 page table을 유지한다!
    • 하지만 segmentation을 사용하기 때문에 segmentation이 가지고 있는 문제점이 그대로 나타난다
• Multi-level Paging
  • page directory를 유지하여 page table을 계층적으로 만들고, 사용하지 않는 page table은 제거한다!
    • page table이 차지하는 공간을 줄여주지만, TLB miss가 발생했을 때의 메모리 접근 횟수가 더 늘어남

Swapping 메모리 크기보다 큰 프로세스를 실행하려고 한다면? -> 더 큰 저장공간이 필요하다! 프로세스의 모든 페이지가 메모리에 존재하는 것은 아니다! -> memory + 디스크(스왑 공간) 스왑 공간을 사용하려면, page가 메모리에 있는지 디스크에 있는지 알아야 한다! -> present bit

• page hit : 페이지가 메모리에 존재할 때
• page fault : 페이지가 메모리에 없을 때 -> PTE에서 page의 disk 주소를 알아낸다 -> page 를 메모리에 할당 -> TLB에 기록
• Thrashing : 실행 중인 프로세스들이 요구하는 메모리의 크기가 실제 보다 클때, OS는 계속 page fault를 발생시킴