게임 프로그래머

프로그램은 하드디스크 같은 저장장치에 보관되어 있는 정적인 상태를 의미

프로세스는 프로그램이 실행되어 메모리에 올라온 동적인 상태를 의미

CPU가 타임 슬라이스를 여러 프로세스에 적당히 배분함으로써 동시에 실행하는 것처럼 보임

프로그램에서 프로세스로의 전환

프로세스는 컴퓨터 시스템의 작업 단위로 태스크라고도 부름

1. 운영체제는 프로그램을 메모리에 적재하고, 프로세스 제어 블록(PCB, Process Control Block)을 생성

• PCB는 운영체제가 해당 프로세스를 관리하는 데이터 구조이기 때문에 메모리의 운영체제 영역에 만들어짐
• 운영체제도 프로그램이므로 프로세스(커널 프로세스)로 실행되기 때문에 PCB가 있음

2. 프로세스가 종료되면 프로세스가 메모리에서 삭제되고 PCB도 폐기됨

프로세스의 상태

생성 상태

프로세스가 메모리에 올라와 실행 준비를 완료한 상태

운영체제로부터 PCB를 할당받은 상태

준비 상태

생성된 프로세스가 CPU를 얻을 때까지 기다리는 상태

CPU 스케줄러가 준비 상태의 프로세스 중 하나를 실행 상태로 바꿔 CPU에 PCB를 전달하는 작업을 디스패치라고 함

실행 상태

준비 상태에 있는 프로세스 중 하나가 CPU를 얻어 작업을 수행하는 상태

타임 슬라이스 동안 CPU를 사용할 권리를 갖고, 작업이 끝나지 않았다면 준비 상태로 돌아와 CPU를 얻기 위해 기다림(타임아웃)

CPU는 타임 슬라이스가 지난 뒤 클럭이 인터럽트를 전송

대기 상태

입출력을 요청한 프로세스가 입출력이 완료될 때까지 기다리는 상태

효율을 높이기 위해 입출력을 요청한 프로세스가 대기 상태가 되면 CPU 스케줄러는 준비 상태에 있는 프로세스를 실행함

입출력이 완료되면 입출력 관리자로부터 인터럽트를 받아 대기 상태로 전환, 만약 실행 상태로 전환한다면 현재 진행 중인 프로세스를 중단해야 하므로 복잡하기 때문에 대기 상태로 기다림

인터럽트가 들어왔을 때 효율적으로 프로세스를 찾기 위해 같은 입출력을 요구한 프로세스끼리 모아 놓음

완료 상태

실행 상태의 프로세스가 작업을 마친 상태

코드, 사용했던 데이터, PCB를 메모리에서 삭제

만약 오류나 다른 프로세스에 의해 비정상적으로 종료된다면 디버깅하기 위해 종료 직전의 메모리 상태를 저장장치로 옮기는데 이를 코어 덤프라고 함

PCB(프로세스 제어 블록)

프로세스를 실행하는 데 필요한 중요한 정보를 보관하는 자료 구조

보통 커널 내에 프로세스 테이블의 형태로 관리됨

모든 프로세스는 고유한 PCB를 가지며, 프로세스 생성 시 만들어지고 실행을 완료하면 폐기됨

PCB 구성

포인터 : PCB를 연결하여 프로세스의 준비 상태나 대기 상태의 큐를 구현할 때 포인터를 사용

프로세스 우선순위 : CPU 스케줄러가 준비 상태에 있는 프로세스 중 실행 상태로 옮겨야 할 프로세스를 선택할 때 프로세스 우선순위를 기준으로 삼음

각종 레지스터 정보 : 프로세스가 실행되는 중에 사용하던 레지스터 값들이 저장하여 다음에 실행할 때 저장된 레지스터 값을 사용

메모리 관리 정보 : 프로세스의 메모리 주소를 나타내는 메모리 위치 정보, 메모리 경계 레지스터 값과 한계 레지스터 값, Segmentation Table, Page Table 등 저장

할당된 자원 정보 : 프로세스를 실행하기 위해 사용하는 입출력 자원이나 오픈 파일 등에 대한 정보

계정 정보 : 계정 번호, CPU 할당 시간, CPU 사용 시간 등

PPID(Parent PID), CPID(Child PID)

Context Switch(문맥 교환)

기존 프로세스를 종료하고 새로운 프로세스의 실행을 준비하는 과정

기존 프로세스의 PCB에 작업 내용을 저장하고, 실행하는 프로세스의 PCB 내용으로 CPU를 설정

프로세스에 할당된 타임 슬라이스를 모두 사용한 경우, 인터럽트가 발생하여 인터럽트를 처리하는 경우 등에 컨텍스트 스위치가 일어남

잦은 컨텍스트 스위칭은 캐시 미스가 발생할 가능성이 높아져 메모리로부터 실행할 프로세스의 내용을 가져오는 작업이 빈번해져 큰 오버헤드 발생 가능

• 시스템 콜을 사용하면 사용자 모드에서 커널 모드로 전환하는 과정에서 컨텍스트 스위칭이 발생

프로세스의 구조

프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 구성됨

코드 영역

프로그래머가 작성한 프로그램은 코드 영역에 저장됨

읽기 전용(자기 자신을 수정하는 프로그램은 없기 때문)

데이터 영역

프로그램이 실행되는 동안 유지할 데이터(정적(static)/전역 변수)가 저장되는 공간

BSS(Block Started by Symbol) 영역 : 초기값이 없는(0으로 초기화) 데이터가 저장되는 공간

읽기/쓰기가 모두 가능한 영역과 읽기 전용 영역으로 나뉨

힙 영역

프로세스가 실행되는 동안 동적으로 할당되는 영역

스택 영역

프로세스를 실행하기 위해 일시적으로 사용할 값들이 저장되는 공간으로 지역 변수(매개 변수 포함), 함수 복귀 주소 등이 저장됨

프로세스가 실행되는 동안 만들어지는 동적 할당 영역은 레지스터 값, 스택, 힙 등

스레드

프로세스의 코드에 정의된 절차에 따라 CPU에 작업 요청을 하는 실행 단위

(운영체제 입장에서의 작업 단위는 프로세스, CPU 입장에서의 작업 단위는 스레드)

프로세스는 하나 이상의 스레드로 구성됨

하나의 스레드에는 스레드 ID와 프로그램 카운터, 레지스터 값, 스택 등으로 구성

스레드마다 다음에 실행할 주소와 연산 과정의 임시 저장 값을 가짐

프로세스와 스레드의 차이

프로세스는 다른 프로세스에 큰 영향을 미치지 않기 때문에 순서를 바꾸어도 문제 없음

• 서로 독립적인 프로세스는 데이터를 주고받을 때 프로세스 간 통신(IPC, Inter Process Communication)을 이용

스레드는 다른 스레드에 큰 영향을 미칠 수 있기 때문에 순서를 바꾸면 문제가 될 수 있음

(예를 들면 B 스레드는 A 스레드가 끝난 뒤 실행해야 한다면 순서를 바꿀 때 문제 발생)

• 멀티스레드는 변수나 파일 등을 공유할 수 있고, 전역 변수나 함수 호출 등의 방법으로 스레드 간 통신을 함

프로세스 내의 다른 스레드로 컨텍스트 스위칭할 때 다른 프로세스로 컨텍스트 스위칭하는 것보다 빠른 이유는 스레드는 독립적인 스택 영역만 있어 비교적 적은 메모리를 컨텍스트 스위칭하여 적은 캐시 미스, 적은 메모리 접근 횟수, 적은 레지스터 변경 때문

스레드 관련 용어

멀티스레드 : 프로세스 내 작업을 여러 개의 스레드로 분할함으로써 작업의 부담을 줄이는 프로세스 운영 기법

멀티태스킹(시분할 시스템) : 운영체제가 CPU에 작업을 줄 때(스레드에) 시간을 잘게 나누어 배분하는 기법

멀티프로세싱 : 독립적인 여러 개의 프로세스를 여러 개의 CPU 혹은 하나의 CPU 내 여러 개의 코어에 스레드를 배정하여 동시에 처리하는 작업 환경

• 예시 : 네트워크로 연결된 여러 컴퓨터에 스레드를 나누어 협업하는 분산 시스템

(CPU) 멀티스레드 : 한 번에 하나씩 처리해야 하는 스레드를 파이프라인 기법을 이용하여 동시에 여러 스레드를 처리하도록 만든 병렬 처리 기법

멀티스레드 장점

한 스레드가 입출력으로 인해 작업이 진행되지 않더라도 다른 스레드가 작업을 계속하여 사용자의 작업 요구에 빨리 응답할 수 있음

한 프로세스 내에서 독립적인 스레드를 생성하면 프로세스가 가진 자원(코드, 데이터, 힙)을 모든 스레드가 공유

여러 개의 프로세스를 생성하는 것과 달리 불필요한 자원의 중복(중복되는 프로세스의 정적 영역)을 막음으로써 메모리 할당 시간 및 공간 감소

2개 이상의 CPU를 가진 컴퓨터에서 멀티스레드를 사용하면 다중 CPU가 멀티스레드를 동시에 처리하여 CPU 사용량이 증가하고 프로세스의 처리 시간이 단축

멀티스레드 단점

멀티스레드는 모든 스레드가 자원을 공유하기 때문에 한 스레드에 문제가 생기면 전체 프로세스에 영향을 미침

사용자 레벨 스레드

라이브러리에 의해 구현된 일반적인 스레드

운영체제가 멀티스레드를 지원하지 않을 때 사용하는 방법으로, 초기의 스레드 시스템에서 이용됨

사용자 레벨에서 스레드를 구현하기 때문에 관련 라이브러리를 사용하여 구현하며, 라이브러리는 커널이 지원하는 스케줄링이나 동기화 같은 기능을 대신 구현해주기 때문에 커널 입장에서 하나의 프로세스처럼 보임

따라서 사용자 프로세스 내의 여러 스레드가 존재하지만 커널의 스레드 하나와 연결되기 때문에 1 to N 모델이라고 부름

라이브러리가 직접 스케줄링을 하고 작업에 필요한 정보를 처리하기 때문에 문맥 교환이 필요 없어 속도가 빠름

(서로 다른 프로세스를 동시에 실행하지 않기 때문)

여러 개의 스레드가 하나의 커널 스레드와 연결되기 때문에 커널 스레드가 입출력 작업을 위해 대기 상태가 되면 모든 사용자 레벨 스레드가 같이 대기 상태가 되는 단점

한 프로세스의 타임 슬라이스를 여러 스레드가 공유하기 때문에 여러 개의 CPU를 동시에 사용할 수 없는 단점

기능을 커널이 아닌 라이브러리에 구현해야 하기 때문에 보안에 취약

커널 레벨 스레드

커널이 직접 생성하고 관리하는 스레드

커널이 멀티스레드를 지원하는 방식으로, 하나의 사용자 스레드가 하나의 커널 스레드와 연결되기 때문에 1 to 1 모델이라고 부름

독립적으로 스케줄링이 되므로 특정 스레드가 대기 상태가 되어도 다른 스레드는 작업을 계속할 수 있음

커널이 제공하는 보호 기능과 같은 모든 기능을 사용할 수 있음

커널 레벨에서 모든 작업을 지원하기 때문에 멀티 CPU를 사용할 수 있음

스레드(혹은 프로세스) 전환이 발생할 때 문맥 교환으로 인한 오버헤드 때문에 느리게 작동

멀티레벨(하이브리드) 스레드

사용자 레벨 스레드와 커널 레벨 스레드를 혼합한 방식으로 M to N 모델이라고 부름(M >= N)

하나의 커널 스레드가 대기 상태가 되면 다른 커널 스레드가 대신 작업하여 사용자 레벨 스레드보다 유연하게 작업을 처리할 수 있음

커널 레벨 스레드를 같이 사용하기 때문에 여전히 문맥 교환 오버헤드가 있어 사용자 레벨 스레드만큼 빠르지 않음

따라서 빨리 작업해야 하는 스레드는 사용자 레벨 스레드로 작동하고, 안정적으로 작업해야 하는 스레드는 커널 레벨 스레드로 작동함

운영체제

새로운 기능의 추가나 성능의 변경이 가능하게 하여 컴퓨터의 성능 및 효율성 향상

컴퓨터의 자원을 여러 프로세스에 적절히 할당하여 효율적으로 관리

컴퓨터를 쉽게 사용할 수 있도록 다양한 인터페이스를 제공하여 자원을 보호하고 사용자의 편의를 도모

다중 프로그래밍(시분할) 시스템

하나의 CPU로 여러 작업을 실행하는 기술로, 한 번에 하나의 작업만 가능한 일괄 작업 시스템에 비해 효율성이 뛰어남

CPU 사용 시간을 작은 단위의 시간(타임 슬라이스/타임 퀀텀) 분배를 매우 빠르게 진행하여 여러 작업이 동시에 실행하는 것처럼 보임

여러 작업을 동시에 처리하기 위한 추가 작업이 필요

중요한 작업이 일정 시간 안에 끝나는 것을 보장하지 못함

운영체제 구조

커널

프로세스/메모리/저장장치 관리와 같은 운영체제의 핵심적인 기능을 모아 놓은 것

운영체제의 성능을 좌우

운영체제의 인터페이스는 커널에 사용자의 명령을 전달하고 실행 결과를 사용자에게 전달

시스템 콜

자원을 보호하기 위해 사용자나 응용 프로그램이 자원에 직접 접근하는 것을 차단하고 자원에 이용하기 위해 커널이 제공하는 시스템 콜이라는 인터페이스를 이용해 접근해야 함

시스템 콜을 이용하면 커널이 데이터를 가져오거나 저장하는 것을 전적으로 책임지기 때문에 자원을 관리하기 수월

커널이 제공하는 시스템 관련 서비스를 함수 형태로 제공함

어떤 응용 프로그램이 데이터를 하드디스크에 저장한다고 가정하자

직접 자원에 접근한다면 응용 프로그램이 원하는 위치에 데이터를 저장하여 원치 않는 데이터를 덮어쓸 수 있음

시스템 호출을 통해 접근한다면 커널이 제공하는 write() 함수를 사용하여 데이터를 저장해달라고 요청하여 응용 프로그램은 데이터가 하드디스크의 어느 위치에 어떤 방식으로 저장됐는지 알 수 없어 안전

커널이 주로 하는 일

프로세스 관리 : 프로세스에 CPU를 배분

메모리 관리 : 프로세스에 작업 공간을 배치하고 가상 메모리를 제공

파일 시스템 관리 : 데이터를 저장하고 접근할 수 있는 인터페이스 제공

입출력 관리

프로세스 간 통신(IPC) 관리 등

기타

32bit 기반 프로그램은 X86, 64bit 기반 프로그램은 X64로 표시

소켓 통신

데이터를 전송하거나 수신하기 위한 창구 역할이므로 반드시 송신지 프로세스는 소켓에 쓰고 수신지 프로세스는 소켓으로부터 읽음

소켓이 파일처럼 프로세스가 열고 읽고 쓸 수 있는 대상이므로 많은 운영체제에서 파일로 간주됨

많은 운영체제의 소켓도 소켓 디스크럽터(파일 디스크럽터와 본질적으로 동일)을 통해 소켓을 식별하고, 소켓 입출력이 가능하고 IPC의 수단으로도 사용됨

특징

서버와 클라이언트가 계속 연결을 유지하는 양방향 통신

서버와 클라이언트가 실시간으로 데이터를 주고받는 상황(온라인 게임)에 사용됨

클라이언트는 소켓을 생성한 후 connect()를 사용하여 서버와 접속을 시도

서버와 접속되면 read 혹은 write 작업을 하며 작업이 끝나면 사용한 소켓 기술자(socket descriptor)를 닫고 종료

서버는 동시에 여러 클라이언트에 서비스를 하기 위해 하나의 포트 번호에 여러 개의 소켓을 생성

소켓을 생성한 후 bind를 사용하여 생성한 소켓을 특정 포트에 등록

listen을 실행하여 클라이언트의 접속을 기다림

클라이언트의 connect가 도착하면 accept를 진행하고, 여러 명의 클라이언트가 동시에 connect 하는 경우 하나를 골라 작업을 시작하게 해줌

따라서 클라이언트가 accpet 되면 소켓 기술자가 생성되고 작업이 시작됨

read 혹은 write 작업을 마치면 소켓 기술자를 닫고 다음 클라이언트를 기다림

소켓 종류(TCP와 UDP)

TCP와 UDP의 목적과 특징

포트를 통한 프로세스 식별

패킷의 최종 송수신 대상은 프로세스이므로 포트 번호를 통해 프로세스를 식별

네트워크 패킷을 주고받는 프로세스는 포트 번호가 할당되어 {IP : 포트 번호}로 함께 표기됨

포트를 통한 프로세스 식별이 전송 계층(TCP, UDP)의 주된 목적이므로 헤더에 송신지 포트 번호와 수신지 포트 번호를 포함

포트 번호는 16비트로 총 2^16(65536)개로, 잘 알려진 포트(0~1023), 등록된 포트(1024~49151), 동적 포트(49152~65535)로 나뉨

서버로서 동작하는 프로그램은 잘 알려진 포트와 등록된 포트가 할당되는 경우가 많고, 클라이언트로서 동작하는 프로그램은 동적 포트로 할당되는 경우가 많음

NAT(Network Address Translation)

공인 IP와 사설 IP 간 변환에 사용되는 기술

패킷이 사설 네트워크에서 네트워크 외부로 전송될 때 사설 IP -> 공인 IP 변환

패킷이 네트워크 외부에서 사설 네트워크로 전송될 때 공인 IP -> 사설 IP 변환

NAPT(Network Address Port Translation)

사설 IP와 공인 IP를 일대일로 대응하지 않고 다수의 사설 IP가 적은 수의 공인 IP로 변환될 때 포트를 사용

서로 다른 사설 IP가 같은 공인 IP로 변환돼도 포트 번호에 따라 사설 IP를 구분

공인 IP의 부족 문제를 개선

(비)신뢰성과 (비)연결형 보장

TCP : 신뢰, 연결형

UDP : 비신뢰, 비연결형

TCP는 패킷을 주고받기 전에 연결 수립 과정을 거치며 패킷의 신뢰성을 보장하기 위해 상태 관리, 흐름 제어, 오류 제어, 혼잡 제어 등의 각종 기능을 제공, 패킷의 송수신이 모두 끝나면 연결 종료

UDP는 연결의 수립이나 종료 단계를 거치지 않고, 신뢰성을 높이기 위한 기능도 제공하지 않아 헤더가 비교적 작음

신뢰할 수 있는 연결형 송수신에는 시간과 연산이 필요하기 때문에 일반적으로 TCP가 UDP에 비해 송수신 속도가 느림

따라서 패킷의 유실 없는 송수신을 원하면 TCP를 선택하고, 비교적 빠른 송수신(실시간 스트리밍, 온라인 게임, 인터넷 전화 등)을 원한다면 UDP를 선택하는 것이 유리

UDP 헤더에는 송신지 포트, 수신지 포트, 길이(UDP 데이터그램의 바이트 크기), 체크섬(checksum, 송수신 과정에서 데이터그램 훼손 여부)가 명시됨

TCP는 연결의 수립과 종료, 신뢰성 보장을 위한 다양한 기능을 제공하여 헤더 필드 수가 많음, 그 중 순서 번호, 확인 응답 번호, 제어 비트가 중요

애플리케이션 레벨에서 커스텀 프로토콜을 정의하여 UDP의 신뢰성 문제를 보완할 수 있음

• 클라이언트가 데이터를 보내면, 서버는 수신 확인 메시지(ACK)를 전송
• 클라이언트가 일정 시간 내에 ACK를 받지 못하면 데이터를 다시 전송, 이 과정에서 연결이 유효한지 확인
• 각 패킷에 시퀀스 번호를 부여해 데이터의 순서를 보장하거나, 중복된 패킷을 식별할 수 있음

순서 번호

TCP 세그먼트의 올바른 송수신 순서를 보장하기 위해 세그먼트 첫 바이트에 매겨진 번호

순서 번호를 통해 현재 주고받는 TCP 세그먼트가 송수신하고자 하는 데이터의 몇 번째 바이트에 해당하는지 알 수 있음

확인 응답(acknowledgement) 번호

상대 호스트가 보낸 세그먼트에 대한 응답으로, 다음으로 수신하길 기대하는 순서 번호

일반적으로 올바르게 수신한 순서 번호에 1을 더한 값으로 설정됨

호스트 A가 순서 번호 100인 세그먼트를 전송했고 호스트 B가 받아서 다음으로 101번 세그먼트를 받기 위해 확인 응답 번호에 101을 명시

각각 순서 번호와 확인 응답 번호가 함께 사용되므로 한 쌍 처럼 기억

제어 비트(control bit, 플래그 비트)

세그먼트에 대한 부가 정보

기본적으로 8비트로 구성

ACK

세그먼트의 확인 응답 번호가 포함됐는지 여부

제어 비트에서 승인을 나타내는 비트로, 확인 응답 번호를 보내기 위해서는 ACK 플래그가 1로 설정돼야 함

SYN

연결을 수립하기 위한 비트

FIN

연결을 종료하기 위한 비트

TCP의 연결부터 종료까지

TCP의 연결 수립(3-way handshake)

1. [A->B] SYN 세그먼트 전송

호스트 A가 SYN 비트가 1인 세그먼트를 호스트 B에게 전송

세그먼트의 순서 번호에는 호스트 A의 순서 번호가 포함됨

2. [B->A] SYN + ACK 세그먼트 전송

호스트 B는 SYN, ACK 비트가 1인 세그먼트를 호스트 A에게 전송

1번에 대한 호스트 B의 응답

세그먼트의 순서 번호에는 호스트 B의 순서 번호와 1번에서 보낸 세그먼트에 대한 확인 응답 번호가 포함됨

3. [A->B] ACK 세그먼트 전송

호스트 A는 ACK 비트가 1인 세그먼트를 호스트 B에게 전송

세그먼트의 순서 번호에는 호스트 A의 순서 번호와 2번에서 보낸 세그먼트에 대한 확인 응답 번호가 포함됨

TCP 연결 수립 과정에서 SYN 비트가 설정된 패킷을 처음으로 보내는 호스트가 처음으로 연결 요청을 보내는 호스트

액티브 오픈

호스트 A처럼 처음 연결을 시작하는 과정

패시브 오픈

호스트 B처럼 연결 요청을 수신한 뒤 그에 대한 연결을 수립하는 과정

서버-클라이언트 관계에서 액티브 오픈은 주로 클라이언트에 의해 수행되고 패시브 오픈은 주로 서버에 의해 수행됨

TCP의 오류, 흐름, 혼잡 제어

재전송을 통한 오류 제어

TCP는 송수신 과정에서 잘못 전송된 세그먼트가 있을 경우 재전송하여 오류를 제어

잘못 전송된 경우는 중복된 ACK 세그먼트가 도착했을 경우와 타임아웃이 발생했을 경우

TCP의 송수신은 기본적으로 순서 번호(n) 세그먼트를 보내고 확인 응답이 담긴 세그먼트를 받고 다음 순서 번호(n+1) 세그먼트를 보내는 과정이 반복하며 이루어짐

중복된 ACK 세그먼트를 수신하는 상황

송신한 세그먼트가 유실되어 다음 순서 번호(n+1)이 아닌 n을 보내는 상황

타임아웃이 발생한 상황

TCP 세그먼트를 송신하는 호스트는 세그먼트를 전송할 때마다 재전송 타이머를 시작하여 타이머의 카운트다운이 끝났을 때까지 ACK 세그먼트를 받지 못한 상황

파이프라이닝 전송

순차적으로 세그먼트를 송수신하는 것은 비효율이므로 오늘날 TCP가 송수신하는 방식

한 번에 세그먼트를 송신하고 한 번에 세그먼트에 대한 확인 응답을 받는 방식

흐름 제어

수신 호스트가 한 번에 처리할 수 있는 만큼만 전송하여 송수신 속도를 균일하게 맞추는 기능

수신 호스트가 한 번에 받을 수 있는 전송량은 TCP 수신 버퍼의 크기에 결정됨

수신 버퍼는 수신된 세그먼트가 애플리케이션 프로세스에 의해 읽히기 전에 임시 저장되는 공간으로 커널에 정의됨

수신 호스트가 TCP 헤더의 윈도우 필드를 통해 송신 호스트에게 수신 버퍼의 크기를 알려주고 송신 호스트는 전달받은 값을 토대로 세그먼트를 전송

혼잡 제어

많은 트래픽으로 패킷의 처리 속도가 느려지거나 유실될 수 있는 상황을 제어하는 기능

혼잡 제어의 주체는 송신 호스트

송신 호스트는 중복된 ACK 세그먼트가 도착했을 때, 타임아웃이 발생했을 때 혼잡할 수 있다고 판단하고 혼잡 윈도우(congestion window, 혼잡 없이 전송할 수 있는 정도의 양)의 값을 넘지 않게 송신

혼잡 윈도우 크기는 혼잡 제어 알고리즘(혼잡 윈도우 크기를 연산하는 방법)을 통해 계산

AIMD(Additive Increase/Multiplicative Decrease)

가장 기본적인 혼잡 제어 알고리즘

세그먼트를 송수신할 때 혼잡이 감지되지 않으면 혼잡 윈도우를 1씩 증가하고, 혼잡이 감지되면 절반으로 떨어뜨림

RTT(Round Trip Time)

패킷을 보내고 응답이 수신되기까지의 시간

흐름 제어에 사용되는 윈도우와 혼잡 제어에 사용되는 혼잡 윈도우는 모두 커널에 정의된 값

TCP의 종료(4-way-handshake)

1. [A->B] FIN 세그먼트 전송

호스트 A는 FIN 비트가 1로 설정된 세그먼트를 호스트 B에게 전송

2. [B->A] ACK 세그먼트 전송

1번에 대한 호스트 B의 응답

호스트 B는 ACK 세그먼트를 호스트 A에게 전송

3. [B->A] FIN 세그먼트 전송

호스트 B는 FIN 세그먼트를 호스트 A에게 전송

4. [A->B] ACK 세그먼트

3번에 대한 호스트 A의 응답

호스트 A는 ACK 세그먼트를 호스트 B에게 전송

액티브 클로즈(close)

먼저 연결을 종료하려는 호스트에 의해 수행되는 동작

패시브 클로즈

연결 종료 요청을 받아들이는 호스트에 의해 수행되는 동작

TCP의 상태 관리

TCP는 상태를 유지하고 관리하는 프로토콜로 Stateful 프로토콜로 부름

상태

현재 어떤 통신 과정에 있는지를 나타내는 정보

TCP의 상태 정보를 토대로 현재 TCP 송수신 현황을 판단할 수 있고, 디버깅의 힌트로도 활용할 수 있음

TCP 상태 플로우

연결이 수립되지 않았을 때

CLOSED : 연결이 없는 상태

LISTEN : 연결 대기 상태(3-way handshake에서 1번 SYN 세그먼트를 대기하는 상태)

연결 수립 과정

SYN-SENT : 액티브 오픈 호스트가 SYN 세그먼트를 보낸 뒤, 그에 대한 응답인 SYN + ACK 세그먼트를 기다리는 상태(연결 요청 전송)

SYN-RECEIVED : 패시브 오픈 호스트가 SYN + ACK 세그먼트를 보낸 뒤, 그에 대한 ACK 세그먼트를 기다리는 상태(연결 요청 수신)

ESTABLISHED : 3-way-handshake가 끝난 뒤 데이터를 송수신할 수 있는 상태(연결 수립)

연결 종료 과정

FIN-WAIT-1 : 액티브 클로즈 호스트가 FIN 세그먼트로 연결 종료 요청을 보낸 상태

CLOSE-WAIT : FIN 세그먼트를 받은 패시브 클로즈 호스트가 그에 대한 응답으로 ACK 세그먼트를 보낸 후 대기하는 상태(연결 종료 요청 승인)

FIN-WAIT-2 : FIN-WAIT-1 상태에서 ACK 세그먼트를 받은 상태

LAST-ACK : CLOSE-WAIT 상태에서 FIN 세그먼트를 전송한 뒤 대기하는 상태

TIME-WAIT : 액티브 클로즈 호스트가 마지막 ACK 세그먼트를 전송한 상태

패시브 클로즈 호스트가 마지막 ACK 세그먼트를 수신하면 CLOSE 상태가 되는 반면, TIME-WAIT 상태에 접어든 액티브 클로즈 호스트는 일정 시간을 기다린 뒤 CLOSED 상태가 됨

이는 마지막 ACK 세그먼트가 올바르게 전송되지 않았을 때 재전송하기 위함

CLOSING : 서로가 FIN 세그먼트를 보내고 받은 뒤 각자 그에 대한 ACK 세그먼트를 보냈지만 아직 자신의 FIN 세그먼트에 대한 ACK 세그먼트를 받지 못한 상태

네트워크의 기본 구조

노드 : 네트워크 기기

네트워크 topology

네트워크 상에서 노드와 노드 사이의 연결 구조

망형, 트리형, 링형 등의 유형으로 나뉨

호스트

네트워크의 가장자리에 위치하여 네트워크를 통해 주고받는 정보를 최초로 송신하고 최종 수신하는 노드

예를 들어 노트북으로 구글 홈페이지에 접속했다면 노트북과 구글 서버 컴퓨터가 각각 호스트로서 정보를 주고 받은 것

클라이언트

노트북처럼 요청(Request)을 보내는 호스트

서버

구글의 서버 컴퓨터처럼 응답(Response)을 보내는 호스트

네트워크를 그래프로 간주했을 때 중간 노드는 호스트가 주고받는 정보를 원하는 수신지까지 안정적으로 전송하는 역할

스위치, 라우터, 공유기 등이 중간 노드 역할을 함

LAN과 WAN

LAN(Local Area Network)

가정이나 기업처럼 가까운 거리를 연결하는 한정된 공간에서의 네트워크

WAN(Wide Area Network)

LAN 간 통신으로, WAN이 인터넷을 가능하게 만드는 네트워크

일반적으로 ISP(Internet Service Provider)가 구축하고 관리

패킷 교환 네트워크

패킷(packet)

송수신 되는 데이터의 단위

패킷 단위로 주고받는 정보를 쪼개서 송수신하고 수신지에서 재조립하여 패킷을 주고받음

payload(패킷에서 송수신하고자 하는 데이터)와 헤더(+ 트레일러(패킷에 추가되는 부가 정보))로 구성됨

주소의 개념과 전송 방식

주소

호스트를 특정할 수 있는 정보

패킷의 헤더에 명시되며 대표적으로 IP 주소와 MAC 주소가 있음

유니캐스트

송신지와 수신지가 일대일로 패킷을 주고받는 전송 방식

브로드캐스트

네트워크상의 모든 호스트에게 메시지를 전송하는 방식

브로드캐스트 도메인

브로드캐스트가 전송되는 범위

호스트가 같은 브로드캐스트 도메인에 속해 있는 경우에 같은 LAN이라고 간주

멀티캐스트

네트워크 내의 동일 그룹에 속한 호스트에게만 전송하는 방식

애니캐스트

네트워크 내의 동일 그룹에 속한 호스트 중 가장 가까운 호스트에게 전송하는 방식

두 호스트가 패킷을 주고받는 과정

프로토콜

네트워크에서 통신을 주고받는 노드 간의 합의된 규칙이나 방법

호스트나 네트워크 장비들이 패킷을 이해하려면 같은 프로토콜을 이해해야 하고, 같은 프로토콜로 통신해야 함

네트워크 상에서 여러 프로토콜을 함께 사용할 수 있고 개발자가 기본적으로 알아야 할 프로토콜의 종류가 정해져 있음(IP, TCP, UDP 등)

프로토콜마다 목적과 특징이 다르므로 상황에 적합한 프로토콜을 사용해야 함

프로토콜마다 패킷의 내용이 달라질 수 있음

네트워크 참조 모델

통신이 이루어지는 단계를 계층적으로 표현한 것

패킷을 송신하는 쪽에서는 상위 계층에서 하위 계층으로 정보를 보내고, 패킷을 수신하는 쪽에서는 하위 계층에서 상위 계층으로 정보를 받아들임

OSI 모델

ISO(국제 표준화 기구)에서 만든 네트워크 참조 모델로, 통신 단계를 7개의 계층으로 나눔

물리 계층(Physical Layer)

비트 신호를 주고 받는 계층

유무선 통신 매체를 통해 운반

데이터 링크 계층 (Data Link Layer)

같은 LAN에 속한 호스트끼리 올바르게 정보를 주고받기 위한 계층

같은 네트워크에 속한 호스트를 식별할 수 있는 MAC 주소를 사용

물리 계층을 통해 주고받는 정보에 오류가 없는지 확인

네트워크 계층 (Network Layer)

네트워크 간 통신을 가능하게 하는 계층

네트워크 간 통신 과정에서 호스트를 식별할 수 있는 IP 주소가 필요하고 IP 프로토콜이 사용됨

전송 계층 (Transport Layer)

정확한 패킷을 전송하게 하는 계층

포트라는 정보를 통해 특정 응용 프로그램과 연결 다리 역할을 수행

대표적인 프로토콜에는 TCP, UDP

세션 계층 (Session Layer)

응용 프로그램 간의 연결 상태를 의미하는 세션을 관리하기 위한 계층

세션 연결 상태를 유지하거나 새롭게 생성하고, 연결을 끊는 역할

표현 계층 (Presentation Layer)

인코딩, 압축, 암호화 수행

응용 계층 (Application Layer)

사용자가 네트워크에 접근할 수 있도록 인터페이스를 제공

중요한 프로토콜(HTTP 등)이 다수 포함됨

TCP/IP 모델

구현과 프로토콜에 중점을 둔 네트워크 참조 모델

네트워크 액세스 계층(링크/네트워크 인터페이스 계층으로도 불림)

OSI 모델의 데이터 링크 계층과 유사

인터넷 계층

OSI 모델의 네트워크 계층과 유사

전송 계층

OSI 모델의 전송 계층과 유사

응용 계층

OSI 모델의 세션 계층, 표현 계층, 응용 계층을 합친 것과 유사

캡슐화와 역캡슐화

캡슐화

송신 과정에서 상위 계층의 패킷이 하위 계층의 페이로드로 간주되고 헤더 및 트레일러를 추가해 나가는 과정

역캡슐화

캡슐화 과정에서 붙인 헤더 및 트레일러를 각 계층에서 확인 후 제거하는 과정

각 계층마다 패킷을 지칭하는 이름이 다름

물리 계층 : 심볼/비트

데이터 링크 계층 : 프레임

네트워크 계층 : 패킷/데이터그램

전송 계층 : 세그먼트(TCP), 데이터그램(UDP)

그 이상의 계층 : 데이터/메시지

HTTP Request를 포함한 이더넷 프레임의 프로토콜 헤더 순서

MAC(데이터링크 계층) -> IP(네트워크 계층) -> TCP(전송 계층) -> HTTP(응용 계층)

다음 두 코드는 모두 정수형 리스트 arr을 인자로 전달받아 같은 작업을 수행하는 함수입니다. 두 코드 중 더 효율적이라고 판단하는 코드를 고르고, 이유를 설명

void first(vector<int>& arr)
{
	const int arrSize = arr.size();

	for (int arrFirstIndex = 0; arrFirstIndex < arrSize - 1; ++arrFirstIndex)
	{
		for (int arrSecondIndex = 0; arrSecondIndex < arrSize - arrFirstIndex - 1; ++arrSecondIndex)
		{
			if (arr[arrSecondIndex + 1] < arr[arrSecondIndex])
				swap(arr[arrSecondIndex], arr[arrSecondIndex + 1]);
		}
	}
}

void second(vector<int>& arr)
{
	const int arrSize = arr.size();

	for (int arrFirstIndex = 0; arrFirstIndex < arrSize; ++arrFirstIndex)
	{
		for (int arrSecondIndex = arrFirstIndex + 1; arrSecondIndex < arrSize; ++arrSecondIndex)
		{
			for (int arrThirdIndex = arrSecondIndex + 1; arrThirdIndex < arrSize; ++arrThirdIndex)
			{
				if (arr[arrSecondIndex] < arr[arrFirstIndex])
					swap(arr[arrFirstIndex], arr[arrSecondIndex]);

				if (arr[arrThirdIndex] < arr[arrSecondIndex])
					swap(arr[arrSecondIndex], arr[arrThirdIndex]);

				if (arr[arrSecondIndex] < arr[arrFirstIndex])
					swap(arr[arrFirstIndex], arr[arrSecondIndex]);
			}
		}
	}
}

• first 함수는 최대 n번의 연산이 필요한 반복문이 2개이므로 시간 복잡도는 O(n^2)입니다.
  그리고 second 함수는 최대 n번의 연산이 필요한 반복문이 3개이므로 시간 복잡도는 O(n^3)입니다.
  따라서 first의 코드가 더 효율적으로 실행됩니다.

시간 복잡도와 빅 오 표기법

• 시간복잡도는 입력의 크기에 따른 프로그램의 실행 관계를 나타냅니다. 실행 시간은 연산 횟수에 비례하므로 입력의 크기에 따른 프로그램의 연산 횟수로 간주되기도 합니다.
  빅 오 표기법은 함수의 점근적 상한을 나타내는데, 시간 복잡도를 표현하기 위해 자주 사용됩니다.
  시간 복잡도를 표현하기 위해 빅 오 표기법이 사용된다면 입력에 따른 실행 시간의 점근적 상한을 의미하는 것입니다.

인코딩된 값과 해시 값의 차이

• 인코딩은 데이터를 다른 방식으로 표현하기 위해 변환하는 것으로, 인코딩된 값은 디코딩을 거쳐 다시 변환될 수 있습니다.
  예를 들어 base64와 아스키 인코딩은 모두 컴퓨터가 이해하는 코드의 형식으로 변환될 수 있고, 그렇게 변환된 코드는 사람이 이해할 수 있는 데이터의 형태로 다시 디코딩될 수 있습니다.
  반면, 해시 값은 해시 함수를 사용하여 고정 길이인 임의의 값으로 데이터를 변환한 결과를 말합니다.
  해시 함수는 인코딩과는 달리 단방향 함수이기 때문에 다시 변환할 수 없습니다.
  또한 임의의 길이의 데이터를 입력받아 고정된 길이의 해시 값을 출력하고, 입력값이 조금이라도 달라지면 해시 값도 완전히 다른 값으로 변경됩니다.
  따라서 인코딩된 값은 주로 데이터를 다양하게 표현하기 위해 사용하고, 해시 값은 주로 데이터의 무결성을 검증하거나 데이터를 빠르게 검색하기 위해 사용됩니다.

스택을 배열로 구현(push와 pop을 반드시 구현)

template<typename T, size_t size>
class myStack
{
public:
	bool isEmpty()
	{
		return topIndex == -1;
	}

	void push(const T& element);
	T pop();

private:
	T elementArray[size];
	int topIndex = -1;
};

template<typename T, size_t size>
void myStack<T, size>::push(const T& element)
{
	if (topIndex == size)
		return;

	++topIndex;
	elementArray[topIndex] = element;
}

template<typename T, size_t size>
T myStack<T, size>::pop()
{
	if (isEmpty())
		return T();

	T element = elementArray[topIndex];
	--topIndex;

	return element;
}

큐를 배열로 구현(인큐와 디큐를 반드시 구현)

class myQueue
{
public:
	bool isEmpty()
	{
		return elementVector.empty();
	}

	int front()
	{
		return *elementVector.begin();
	}

	void enqueue(int element)
	{
		elementVector.push_back(element);
	}

	int dequeue();


private:
	vector<int> elementVector;
};

int myQueue::dequeue()
{
	if (isEmpty())
		return invalid;

	int element = front();
	elementVector.erase(elementVector.begin());

	return element;
}

다음 그림의 자료구조가 무엇인지 설명하고 간단한 코드로 구현

• 트리와 그래프 모두 해당하지만 트리라고 가정하겠습니다.
  이진 트리에 해당하며 각각의 노드가 최대 2개의 자식을 가질 수 있는 트리의 일종입니다.
  따라서 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 표현하는 트리 노드를 구현할 수 있습니다.

class TreeNode
{
public:
	TreeNode(int value) : _value(value) {}

	void setLeftChild(TreeNode* leftChild)
	{
		_leftChild = leftChild;
	}

	void setRightChild(TreeNode* rightChild)
	{
		_rightChild = rightChild;
	}

private:
	TreeNode* _leftChild = nullptr;
	TreeNode* _rightChild = nullptr;

	int _value = 0;
};

int main()
{
	unique_ptr<TreeNode> root = make_unique<TreeNode>(new TreeNode(0));
	root->setLeftChild(new TreeNode(1));
	root->setRightChild(new TreeNode(2));
}

위에서 구현한 자료구조의 모든 노드를 중위 순회하는 코드를 구현, 어떤 순서로 방문하는지 설명

• 중위 순회는 왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리의 순으로 모든 트리 노드를 방문하는 것을 의미합니다. 따라서 b -> a -> c 순으로 순회합니다.

void inorderTraversal(TreeNode* node)
{
	if (node == nullptr)
		return;

	inorderTraversal(node->getLeftChild());

	cout << node->getValue();

	inorderTraversal(node->getRightChild());
}

해시 충돌이 무엇이며, 어떻게 해시 충돌을 해결할 수 있는지 설명

• 해시 충돌이란 서로 다른 키에 대해 같은 해시 값이 대응되는 상황으로, 체이닝과 개방 주소법 등으로 해결할 수 있습니다.
  체이닝은 충돌이 발생한 데이터를 연결리스트로 추가하는 충돌 해결 방식이고,
  개방 주소법은 충돌이 발생한 공간이 아닌 다른 공간을 조사하여 데이터를 저장하는 충돌 해결 방식입니다.

해시 테이블의 장점과 단점

• 해시 테이블의 장점은 데이터 검색 성능이 빠릅니다. 해시 테이블에 대한 키가 주어졌다면 해시 테이블의 검색 성능은 O(1)로 매우 빠릅니다.
  그러나 데이터가 저장될 공간을 미리 확보해 두어야 하므로 메모리 공간이 많이 소요된다는 단점이 있습니다.

배열 대신 연결 리스트를 사용하는 것이 프로그램의 성능에 유리한 경우가 있나요? 만약 그렇다면 그 이유는 무엇인가요?

• 배열과는 달리 연결 리스트를 구성하는 모든 노드는 반드시 메모리 내에 순차적으로 저장되어 있을 필요가 없습니다.
  따라서 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용하게 사용할 수 있고, 배열에 비해 나머지 노드들의 이동이 필요 없어 삽입 및 삭제 연산에서 높은 성능을 보입니다.

우선순위 큐를 구현할 수 있는 방법

• 우선순위 큐는 힙 자료구조로 구현됩니다. 힙은 주로 최댓값과 최솟값을 빠르게 찾는 용도로 사용되는 완전 이진 트리의 일종입니다.
  우선순위 큐는 우선순위가 높은 데이터 순으로 처리하기 때문에 우선순위가 가장 높은 노드를 루트 노드로 삼는 힙으로 구현하기에 용이합니다.

깊이 우선 탐색과 너비 우선 탐색의 차이

• 깊이 우선 탐색과 너비 우선 탐색은 그래프를 탐색하는 기본적인 방법입니다.
  깊이 우선 탐색은 그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊은 자식 노드까지 탐색하기를 반복하는 방법이고,
  너비 우선 탐색은 인접한 모든 정점들을 방문하고, 방문한 정점들과 연결된 모든 정점들을 방문하기를 반복하는 탐색 방법입니다.

RB 트리란 무엇이며, 왜 RB 트리를 사용하는지 설명

• RB 트리는 이진 탐색 트리의 편향을 방지하기 위해 사용하는 자가 균형 이진 트리의 일종입니다.
  이진 탐색 트리는 연산의 순서에 따라 편향된 트리가 될 수 있는데, 편향이 발생할 경우 탐색 속도가 O(n)으로 저하됩니다.
  RB 트리는 이를 방지하기 위해 모든 노드를 빨간색 혹은 검은색으로 간주하고 노드에 색을 칠하는 규칙과 노드에 칠해진 색을 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 높이 균형을 맞춥니다.

B 트리란 무엇이며 왜 B 트리를 사용하는지 설명

• B 트리는 여러 자식 노드를 가질 수 있는 다진 탐색 트리의 일종으로, 파일 시스템이나 데이터베이스와 같은 대용량 입출력 작업이 필요한 상황에서 주로 사용

다음 그림의 자료구조가 무엇인지, 어떻게 구현이 가능한지 설명

• 정점과 그 정점들을 연결하는 간선으로 이루어진 그래프 자료구조입니다. 이는 이차원 행렬이나 연결리스트를 기반으로 구현이 가능합니다.