운영체제 DB C++ 알고리즘 자료구조 다 섞임...
CPP 관련
Push_back이랑 emplace_back 차이
Push_back은 함수 외부에서 임시 객체를 먼저 만들고, 그걸 복사해 옮긴 다음 임시 겍체를 파괴하는 과정을 거치지만, emplace_back은 생성자의 인자들만 전달받아 벡터가 할당해둔 메모리 공간 내부에서 객체를 직접 생성하기 때문에 복사할당비용이 더 적게들어 성능 최적화에 유리
Emplace_back은 가변 템플릿이랑, forward를 사용하기 때문에 벡터 내부 메모리에 있는 생성자한테 그대로 전달할수있어서 직접생성이 가능하흐다
String은 힙메모리에 문자열을 저장함. 동적메모리이다!
객체지향 관련
컴파일러가 자동으로 생성하는 6가지 함수 : 기본생성자, 소멸자, 복사생성, 복사대입, 이동생성, 이동대입 연산자.. 이렇게 총 6개!!
기본생성자 – 클래스 내 어떠한 생성자도 명시적으로 선언하지 않았을 때.. 컴파일러가 알아서 만들어. 이때 인자가 들어가는 생성자를만들면, 컴파일러는 그 즉시 손을 뗌. 즉 기본 생성자는 아예 안만들어주므로…. 기본생성자가 필요하면 명시해줘야함.
소멸자 – 개발자가 명시적으로 선언하지 않으면 자동으로 생성됨
복사생성 A(const& A other)
복사대입(할당) A& operator=(const A& other)
이동생성 A(A&& other)
이동대입(할당) A& operator=(A&& other)
그전에....
깊복/얕복 관련
얕은복사(shallow copy)
객체를 복사할때 변수 안에있는.. 메모리 주소만 쓱 복사하는 방식.
컴파일러가 만들어주는 기본 복사 생성자는 얕은복사로 동작
동적할당포인터를 가진 객체가.. 얕복을 한다고 할때...
원본 객체가 자기 메모리를 delete함 -> 복사본 객체는 여전히 그 메모리 주소를 가짐-> 나중에 그 복사본 개체 자신도 delete를 하려고하면?
없다!! dangling pointer발생?->아무튼. 크래시 발생... 이중 해제 하려고 하기에... 크래시~~
깊은복사(Deep copy)
객체를 복사할때... 아예 새로운 메모리를 할당 하고, 거기에 원본이 가리키던 실제 데이터를 싹~~~다 사그리싻ㄲ쌌 복사해 넣는 방식임...
이게 rule of three(five)가 탄생한 배경이라는...
복사생성 – 객체를 새로 만들 때.. 복사를 이용해 만든다. 깊은 복사 이용.
Ex) A(const& A other)이 있을 때.. A a; , A b = a; 이때
A b = a; 이게 복사 생성….!!!!!
복사대입(할당) A& operator=(const& A other)
이미 객체가 존재할 때… 복사해서 대입할 때!
이미 존재하는 a에 대해, b의 내용을 복사하는 것…
이미 존재하는 s3가 있으면… 원래있떤 s3!!에… s1이라는 애를 복사..
일단 자원 먼저 해제해주고. (release사용)
그다음 다시 make_unique() 사용해서 새 메모리 할당한뒤, memcpy사용해서 복사
복사는... 무조건 새로운 메모리를 할당. 이때 깊은 복사를 사용한다..!
이동은 새 메모리 할당 안함.. 소유권만 이전시키고, 원래 거는 없애버리는거임!!
이때 복사와 이동의 차이는
복사 – 새 메모리 할당, 내용 전체 복사
이동 – 상대가 들고있던 포인터 가져옴, 상대는 nullptr같은 상태로 비운다..(복사 안하고 들고오는 것)
A&& 는 rvalue reference
-> 이 객체의 자원을 가져가도 된다. 라는 의미..
일단 먼저.. lvalue 와 rvalue가 뭐냐면,
lvalue(좌측값) : 메모리에 명확한 주소가 있고, 이름이 있어서 오래 살아남는 데이터... (대입 연산자에서 주로 =의 왼쪽에 온다)
rvalue(우측값) : 연산이 끝나면 메모리에서 곧바로 사라질 임시 데이터.. (주로 = 의 오른쪽에 옴)
그래서 A&&가 뭐냐면
이동이란건.. 새 객체가, 다른 애꺼 자원 훔쳐서 만든다고 생각하면됨
이동생성 A(A&& other)
Release로 반환한 자원을 잽싸게 reset을 사용해서 가져옴.
Other.p는 이때 지워져있어야한다… (소유권을 이전한다 생각하면됨), 복사보다 훨 빠름
이동대입 A& operator=(A&& other)
기존 객체에… rvalue를 대입할 때
얘 역시 마찬가지로 이미 존재하는 애한테, 다른애의 자원을 뺏어와서 대입시킬 때 사용!!
이동생성/대입은..
3가지 요건을 만족할 때 만들어짐.
1. 복사연산자(쌩성/대입)을 안만들었을 때
2. 개발자가 이동연산자를 선언하지 않았을 때…
3. 개발자가 소멸자를 선언하지 않았을 때… (이건 왜?)
소멸자는 왜?
이유는..
cpp에서.. Rule of Three/Five
복사생성, 복사대입, 소멸자 중 하나라도 직접 만들었다면 나머지 도 다 만들어줘야한다ㅡ는 법칙..
C++11이후.. 이동연산이 추가되면서 FIVE로 바뀐거임
가상 소멸자..
-> 다형성을 위해..
이때 다형성이란? 객체 지향 프로그래밍에서.. 모습은 같은데, 형태는 다른 것! 그러니까.. 이름이 동일한 함수여도, 다르게 동작할 수 있는..?
Virtual void 식으로 가상함수식으로 사용함..
Animal()이라는 부모 클래스에서 virtual void yar() override;가 있을 때, Animal을 상속받는 Cat은 야옹하고 울고, Dog는 멍멍하고 울게 만드는게.. 다형성임! Polymorphism
네트워크관련
TCP vs UDP
TCP (Transmission Control Protocol)
패킷의 순서를 보장, 유실되면 재전송하기에 신뢰성이 높음.
TCP는 결제나, 로그인, 중요 아이템 획득 등.. 누락되거나 순서가 바뀌면 안되는 데이터에 사용
UDP (User Datagram Protocol)
은 연결절차가 없고, 목적지를 향해 패킷을 막 던진다. 순서 보장이 이뤄지지 않아 신뢰성이 없다.. 그러나 속도는 빠름.
UDP는 MMORPG에서의 캐릭터 이동좌표, FPS의 에임 이동 등에 사용할수 있다
소켓 프로그래밍의 흐름
서버에서의 흐름은
socket() : 소켓 생성
-> bind() : 생성된 소켓에 서버의 IP주소와 포트번호를 부여 ( 이 포트로 들어오는 데이터는 내가 받겠다라는 뜻)\
-> listen() : 클라이언트의 접속 요청 상태를 기다리는 대기 상태로 전환
-> accept() : 클라이언트의 연결요청이 오면 수락하고, 해당 클라와 통신할 새로운 전용 소켓을 반환함
-> recv()/send() 데이터 송수신
클라에서는
socket()
-> connect() : 이대 TCP-3way Handshake 발생
-> send() / recv() 데이터 송수신
HTTP 프로토콜
- 클라가 요청하면, 서버가 응답함.
- 무상태성, 비연결성 (단방향 통신)
- 서버는 응답 주자마자 ㄱ걍 뚝 끊어버림... 클라가 다시 요청 보내도? 서버는 너 누구얌? 하면서 처음 보는 사람 취급...
그래서 쿠키나 토큰같은걸 같이 보내야함.
- 실시간이 필요없는 데이터에 쓰인다.. 로그인이나, 상점 결제, 우편함 열기, 랭킹 조회, 턴제 게임 등..
소켓 통신
파이프 통로라고 생각
한번 파이프를 연결해두면, 어느 한쪽이 끊기 전까지는 연결이 계속 유지됨.
HTTP는... 무조건 클라가 먼저! 질문을 해야 서버가 대답할수있지만...
소켓은 통로가 있으니 클라가 가만히 있어도, 서버가 먼저 데이터를 보낼 수 있음 ! -> 양방향 통신
- 게임에서는 실시간 동기화에 쓰임. MMORPG에서 캐릭터 이동이나.. FPS게임의 총알 피격 등...
REST API 규칙
- HTTP를 가장 깔끔하고 규칙적으로 쓰는 방법론에 관한 것..
빅엔디언 리틀엔디언
4바이트 정수 0x12345678이 있을 때...맨앞 12가 가장 큰값 , 78이 가장 작은 갓!
빅엔디언이 사람이 읽는순서...
가장 큰 바이트부터, 낮은 메모리주소에 차곡차곡 넣음.
리눅스는 epoll사용
윈도우는 iocp 사용해서 네트워크 io를 처리함.
서버 관련
서버 아키텍처
클라-서버 구조 (중앙 집중형)
클라 : 유저한테 그래픽 보여주고, 입력받아서 서버한테 요청하는 역할
- 클라는 믿으면 안되는 존재.
- 유저가 클라를 해킹하며 조작할 수 있기에.. 클라는 계산 결과가 아닌, 뭔가를 했다는 행동만 서버한테 보내야함.
서버 : 클라의 요청을 받아서 그 로직을 계산하고, 검증한 뒤 결과를 알려주는 역할
- 실제로 권한을 가지는 존재. 모든 요청이나 로직에 대한 계산을 결정하고, 그 계산을 다시 클라한테 보냄.
- 모든 데이터를 서버가 관리함. 보안성이 높음!
- MMORPG이런거에 유리
P2P(Peer to Peer) 구조
플레이어가 직접 연결되어 통신하는 구조. 서버가 필요없음
각 클라가 직접 통신, 서버 없이 데이터 교환! 서로 동등하다..
버그에 취약, 동기화가 어렵다... 플레이어 수 많아지면 복잡!
- 1ㄷ1 게임에 유
하이브리드 구조
클라이언트-서버와 P2P구조를 결합한 구조, 상황에 따라 유연하게 대처함
중요 데이터는 서버가 관리, 실시간 데이터는 p2p로 전송..
각 장점을 살릴수 있지만.. 구현이 어렵다!
서버 아키텍처 3계층
1. 프레젠테이션 계층
- 클ㄹ이언트 그 자체
- 게임에선.. 플레이어가 보는 화면, UI, 입력 처리 등을 의미
2. 애플리케이션 계층
- 게임의 핵심 로직이 작동하는 게임 서버
- 게임에선.. 클라 요청을 받아 연산하고, 다음 계층과 통신하며 게임 상태를 실시간으로 제어함
3. 데이터 계층
- 게임의 정보를 영구적으로 저장하고 관리하는 데이터베이스
- 게임에선 캐시(Redis)나 mySQL등을 활용해 유저 데이터를 안전히 보존/읽어옴
고성능 게임서버에서는..
메모리 DB 및 캐싱 사용(Redis)
- 유저가 만약 몬스터를 잡을 때마다 그걸 db에 기록?(근데 이건 느린 작업임.. 디스크에 쓰는거라)
그러면.. 서버가 멈춘다..
그러니까 모든 인게임 변화를 초고속 메모리(Redis)에서 먼저 처리 후, 나중에 백그라운드에서 주기적으로 디스크 DB에 저장하는..
패킷 프로토콜
TCP - 아이템 거래, 로그인, 강화 등 유실되면 안되는 데이터를 주고 받을 때 사용
UDP - 캐릭터 이동, 전투 액션 등 속도가 중요하고 약간의 유실은 ㄱㅊ은 콘텐츠에 사용 (이때는 데드래커닝 사용..)
데드 래커닝이란? 서버에서 데이터가 안오는 동안엔 클라가 알잘딱 계산해서 예측하는거..
데이터베이스 관련(SQL)
쿼리
데이터베이스한테 보내는 질문이나 명령어
SQL이란.. 데이터베이스가 알아들수 있는 전용 언어
조회 쿼리
SELECT gold FROM users WHERE name = '띵띵띵';
(유저네임이 띵띵띵인 애 한테서 골드 몇갠지 찾아)
삽입 쿼리
INSERT INTO users (name, level, gold) VALUES('댕댕', 1, 30);
수정 쿼리
UPDATE users SET gold = 50 WHERE name = '띵띵띵';
(유저네임이 띵띵띵인 애 골드 50으로 바꿔)
삭제 쿼리
DELETE FROM users WHERE level = 0
WHERE - 조건식
ORDER BY - 정렬
DESC - 내림차순
ASC - 오름차순
JOIN - 테이블 합치기
COUNT(*) - 조건에 맞는 데이터(행)이 몇갠지 세는
ex..
유저 정보는 users 테이블에, 유저가 가진 아이템은 items 테이블에 저장되어있을 때..
A유저가 가진! 무기이름!을 찾을땐 JOIN 사용
INNER JOIN (교집합) : 두 테이블 모두에 겹치는 데이터만 가져와
ex..
아이템을 최소 1개 이상 가지고 있는 유저들만 보여줘
SELECT users.name, items.item_name
FROM users
INNER JOIN items ON users.id = items.owners_id;
DB 실제 작동 순서
1. FROM (어디서? 어디테이블에서 꺼낼지..)
2. WHERE (조건..필터링)
3. GROUP BY (그룹 별 묶기)
4. HAVING (그룹 필터링)
5. SELECT (꺼내기)
6. ORDER BY (정렬)
7. LIMIT (자르기)
GROUPBY의 규칙..
GROUP BY를 사용했다면, SELECT에는 딱 2가지만 적을 수 있음.
그룹을 계산하는 집계함수는 (COUNT, SUM, AVG, MAX, MIN)
트랜잭션의 4가지 속성(ACID)
트랜잭션이란? 여러개의 쿼리를.. 하나의 논리적 작업 단위로 묶은 것. (하나의 작업 단위)
A (Atomicity, 원자성) : All or Nothing.. 이체 과정 중 에러가 나면 전부 롤백 되거나, 완벽히 성공해서 커밋 되어야 한다는 것. 중간만 실행될 수는 없다.
C (Consistency, 일관성) : 트랜잭션 전 후에 DB의 제약조건은 항상 지켜져야한다.
I (Isolation, 고립성) : 둘 이상의 트랜잭션이 동시에 실행될 때, 서로의 작업에 끼어들지 못하게 격리(lock)해야 한다.
D (Durability, 영속성) : 커밋 완료된 데이터는 서버 전원이 뽑혀도 DB에 영구적으로 기록되어야한다.
트랜잭션의 격리 수준(isolation level)
a랑 b가 동시에 같은 DB테이블을 건드릴때, 얼마나 엄격히 lock을 걸어 보호할 것인가에 대한 4단계..
아래로 갈수록
안전성 ↑ ↑ ↑ ↑ , 성능 ↓ ↓ ↓ ↓ ↓ ..
1. Read Uncommitted (커밋되지 않은 읽기) : A가 데이터를 수정 중인데.. 아직 커밋을 안함. 근데 B가 그 수정중인 임시 데이터를 읽어버릴수 있음.
문제점!! dirty read 발생. a가 갑자기 에러나서 롤백해버리면... b는 세상에 존재하지도 않는 유령 데이터 읽고 로직 처리한 꼴이됨.
2. Read Committed (커밋된 읽기) : 커밋이 완료된 진짜 데이터를 읽는 것.
문제점!! Non-Repeatable Read 발생. B가 조회 쿼리를 두번날림. 근데 그 두번 사이에 A가 데이터를 수정하고 커밋을 해버림.
B는 첫번째 조회때 읽은 데이터와 두번째읽은 데이터가 달라서.. 결과가 달라지는 현상이 발생.
쿼리는 동일한데, 결과가 다름
3. Repeatable Read (반복가능한 읽기) : B가 트랜잭션을 시작할때의 데이터 스냅샷을 찍어둠. A가 중간에 뭘 수정하든, B는 자기 트랜잭션이 끝날때까지 항상 똑같은 결과를 보장받음.
문제점!! Phantom Read 발생. A가 기존 데이터를 수정하는게 아닌, 새로운 행을 insert하면... B의 두번째 조회에선 아까는 없던 유령 데이터가 튀어나옴.
4. Serializable (직렬화) : 가장 엄격.. 그냥 트랜잭션들을 한줄로 세워서 하나씩 순서대로 처리함..
문제점!! 완벽하지만, 속도가 미친듯이 느려서 실무에서는 거의 안쓴다.. 데드락 위험 상승.
인덱스 Index
책읽을때.. 색인이랑 같은 개념!!
DB전체를 뒤지는대신, B tree라는 자료구조를 만들어서 검색 속도를 빛의 속도로 끌어올린다.
단점은.. 조회가 빨라지는 대신, 새로운 데이터가 추가되거나(insert)나 수정되거나(update), 삭제(delete)되면 트리구조를 재정렬해야해서
쓰기속도가 오히려 느려진다.. 무작정 인덱스를 많이 쓴다고 좋은게 아니다!!
RDB(Relational Database) ex) MySQL, PostgreSQL 같은..
- 데이터를 행과 열로 구성된 2차원 테이블로 관리. 데이터 간의 관계를 외래키로 연결, 엄격한 스키마를 가진다
- 장점은 데이터 중복이 없고, 완벽한 ACID를 가져서 신뢰성이 높당
- 확장성에 한계가 있음.. 여러대의 컴퓨터로 서버를 쪼개는게 어렵..
- 유저의 계정정보나, 결제 데이터, 보유 자산 등.. 절대 하나의 오차도 있으면 안되는 무결성 데이터를 다룰 때 사용함.
NoSQL(NotOnlySQL) ex) Redis, MongoDB등
- 고정된 테이블 구조가 없어서.. (스키마가 엄격하지 않다)...
- 자유로운 형태로 데이터를 저장. 테이블간의 관계가 없다
- 장점은 관계를 따지지 않고 데이터를 통째로 들고있기에 읽기/쓰기가 빠름. 서버 분산에 유리
- 단점은 동일한 데이터가 여러곳에 중복 저장될 수 있음
- 주로 랭킹 시스템이나, 행동 로그 기록 등... 무결성 보다는! 순간적인 대용량 트래픽 처리와 속도가 생명인 데이터를 다룰 때 사용함.
정규화(Normalization)
- 데이터의 중복을 최소화 하고 테이블 내 종속관계로 인해 발생하는 이상 현상을 방지하기 위해 테이블을 무결한 형태로 쪼개 나가는 과정
제 1정규형(1NF) : 테이블의 모든 컬럼이 원자값만 가져가야함
제 2정규형(2NF) : 1NF를 만족하되, 부분함수의 종속성을 제거해야함. (완전함수종속으로 만드는것)
제 3정규형(3NF) : 2NF를 만족하되, 이행적함수종속성을 제거하는 것.
트랜잭션 ACID 속성
A 원자성 - 모두 실행되거나, 전부 실행되지 않아야함
C 일관성 - 하나의 트랜잭션 사이 DB의 제약조건을 항상 만족해야함
I 고립성 - 동시에 실행되는 트랜잭션들이 서로의 연산에 끼어들 수 없음
D 영속성 - 한번 저장된 트랜젹선은 영구적으로 보존되는 것
캐싱전략
Redis
- NoSQL 데이터 베이스가 맞긴 하지만, 속도가 빨라서 캐시용도로 쓴다고함
- Redis는 메모리에서 바로 꺼내서 속도가 개빠름, 그러나 휘발성이 높아서 서버 꺼지면 그 데이터 내용도 같이 날라감.
- 자주 찾는데 날아가도 괜찮은 데이터는 Redis에 올려두고 사용하는것
- Cache Hit (캐시 적중)
: 유저가 랭킹을 보여달라고 함-> Redis(캐시)를 뒤짐 -> 아까 올려놨기에 DB까지 가지 않고 빠르게 유저한테 정보 제공
- Cache Miss(캐시 미스)
: 서버가 Redis를 뒤짐 -> 데이터가 없으면? DB까지 가서 데이터 긁어옴 -> 유저한테 주면서.. 다음 번을 위해 Redis에 올려둔당..
로드 밸런스와 부하분산
왜 부하 분산이 필요?
수천~수만명의 유저가 동시에 몰려도.. 서버가 터지지 않고 안정적으로 작동해야하니까!
게임서버의 로드 밸런싱 방식
L4 vs L7
L4 로드 밸런싱
: IP주소랑 포트번호만 보고 유저를 여러 서버로 균등히 찢어줌
: 패킷 내부 안보기에 속도 빠르고, 데이터 처리 오버헤드가 적음.. 실시간 TCP/UDP 소켓 ㅕㅇㄴ결에 쓴다
L7 로드 밸런싱
: 패킷 내부까지 보고 분산, 특정 기능별 API 요청을 목적지에 맞게 잘 분류가ㄴㅇ
3가지 부하 분산 전략
1. 세션 기반 분산
- LOL, 배그, 옵치 등..
- 유저들이 룸이나 매치 단위로 모여서 게임을 진행! 좀 여유가 있는 게임 세션 서버에.. 새로운 방을 개설, 유저들 진입시킴
- 게임이 끝나면 연결이 끊기므로 분산이 쉽다
2. 대규모 월드 분산
- 주로 MMORPG에서..
- 모든 유저가 같은 공간에 있음, 서버 자체를 쪼갠다
- 분산 방식은...
- 채널 분산 : 1채널, 2채널 등..으로 복제해서 유저를 나눔
- 심리스 존 분산 : 맵을 격자로 나눠서.. 동쪽, 서쪽 서버같은 형식으로 나누고 유저가 이동하면? 서버를 이관시킴
3. 고정 연결 (스티키 세션)
- 한번 특정 서버에 접속한 유저는 연결 끊을 때 까지 그 서버로만 패킷을 보내도록 고정시키는 것...
OS/멀티스레드 관련
프로세스(process) vs 스레드(thread)
프로세스는.. 실행중인 프로그램 그 자체.
- os에서 실행중인 독립적인 프로그램
os로 부터 각각 독립된 메모리 공간을 할당받음. ( CODE , DATA, HEAP, STACK )
잠만.. 메모리공간 복습좀..
메모리 구조 (ram..안에 존재!) (위에 있을 수록 낮은 주소에 존재)
CODE - 실제 코드 내용. 실행할 프로그램의 코드!!
DATA - 전역변수, 정적 변수
HEAP - 동적할당, 런 타임때 크기가 결정됨, FIFO구조가짐 (메모리의 낮은 주소에서.. 높은 주소 방향으로 할당)
STACK - 지역변수, 매개변수, 포인터, 컴파일 때 크기가 결정, LIFO 구조 가짐(메모리의 높은 주소에서 낮은 주소 방향으로 할당)
그럼 컴파일이랑 런타임때랑 뭐가다름?
컴파일
- 코드를 기계어로 번역하는 시간..
- 아직 프로그램이 실행된게 아님. 이때 code, data, stack의 크기가 결정! 됨.
- 이때 크기가 이미 정해진 애들!의 메모리 자리를 잡아둠.
런타임
- 실제 유저가 .exe파일을 더블 클릭해 프로그램이 램에 올라가 돌아가는 시간
- 접속자가 10명일지 10000명일지 모를때.. 실시간으로 몬스터를 생성하고 (new) 메모리를 받아옴
- 이때 실행 도중 유동적으로 크기가 결정되고 할당되는 공간이 HEAP 임..
그럼 왜 힙은 위로자라고(높은 주소로), 스택은 아래로자라는거지(낮은 주소로)??
둘다 같은 방향으로 자라게 하면... 언젠가는 조금이라도 겹칠수있음..
(ex 힙, 스택 순서로 있을 때 힙이 너무 갑자기 커지면 스택 자리 침범 금방해버림
그럴바엔 그냥 서로 양쪽끝에서 출발시키자..!
이러면.. 가운데 빈 공간을 향해 서로 마주보며 자라니까.. 최대한 공간을 많이 쓸 수 있다!
스택 오버 플로우(또는 힙 오버 플로우)
스택이 힙을 침범해버리거나, 힙이 스택을 침범하는걸 오버플로우라고함.
스레드는.. 프로그램 안에서.. 일하는 작업자들이라고 생각하면됨.
- 프로세스 내 실행 흐름의 단위
한 프로세스 내의 스레드들은.. STACK만 따로 가지고 나머지는 공유함! -> 이게 data race 이유
메모리를 공유해서 서로 통신하기는 빠르나, 한 스레드에서라도 메모리 에러를 내면.. 전체 프로세스가 터져버림
경쟁상태 (Race Condition) / 임계영역
경쟁상태란.. 여러 스레드가 공유 메모리에 있는.. heap이나, data에 있는 변수들 동시에 건들어서 값을 수정해버리면?! 데이터가 망가져버림..이걸 경쟁상태라고 한다.. 한 변수에 대해 여러 메모리가 접근하려하는 것
임계영역(Critical Section) : 여러 스레드가 동시에 접근하면 터지니까... 접근 못하게 lock 같은걸로 막아둔 영역!
즉 여러 스레드가 동시에 접근핳면 안되는 부분!! 보호해야 하는 곳!!
이걸 어떻게 막느냐..? (동기화 방법)
1. mutex 사용 : lock을 사용하는 것.. 딱 자물쇠 걸고 들어가서 걔만 작업실행하다가,.. 작업 다 끝날때까지 다른 애들은 기다리고, unlock할때까지.. 기다리는 것.. std::lock_guard<std::mutex> 써서 예외 발생해도 안전하게 락 풀리게 설계하는게 좋음!
lock_guard가 뭐엿더라면
내기억엔 락을 자동으로 풀어주는애
lock() unlock()내가 수동으로 해줘도?되지만?
만약 하나라도 안하면???? 터짐..
그래서 lock_guard를 사용하면... 자동으로 락을 걸고 풀어준당..(소멸자 성질을 이용함)
-> 데드락이나, 컨텍스트 스위치 오버헤드 발생
또는 스핀락 발생 가능..
무작정 반복적으로.. lock이 반환됐는지 계속~~ 확인하는 것! 무한루프 도는거 ㅇㅇ
스핀락 장점은 문맥교환비용x , 락 획득 빠름 -> 임계영역 짧을 수록 유리
단점은? 임계영역 길면..? -> 기아상태 발생.. (특정 스레드가 한 공유자원 오래 점유한다면, 다른 스레드들이 계속.. 기다려야하는것)
그 락이 반환될때 까지 오래걸린다면..?-> 비지 웨이팅 발생.. (쓸데없이 계속 무한루프 돌면서 cpu를 사용하는것)
2. semaphore 세마포어 사용 :
세마포어란.. 얘는 일단 소유권이 없음.
wait()랑 signal() 사용
wait() - 자원을 획득하는 과정
signal() - 자원을 반납, 이벤트를 알리는 과정
wait랑 signal을 호출하는 스레드가 서로 달라도 무방.. -> 근데 이러면 남이 락을 풀어버리면 망하는 것.. 또 우선순위 역전이 발생할 수 있음
카운터를 줄이고 늘리는 방식으로 동작함.
아근데 세마포어랑.. 뮤텍스 차이는?
세마포어 - 공유자원이 하나 이상일때 사용.. 동기화 대상이 하나 이상!
뮤텍스- 공유자원이 하나일때.. 동기화 대상이 하나!
그럼 각각 언제쓰느냐
mutex - 데이터 보호할때.. 공유자원 값 수정하거나 이래야할때!
semaphore - 자원 풀 관리.. 또는 순서 동기화 할때... 신호 기반으로!
3. 원자적 연산 atomic한 연산하기!
이 연산은 절대 중간에 쪼개 지지 않고 한방에 실행됨을 보장해준다~! 는 것. lock free 기법...
Dead Lock 교착상태 - 여러 프로세스가 서로 자원을 기다리며 무한 대기에 빠지는 현상
데드락 발생 4가지 조건!! 하나라도 깨지면 데드락 발생 안함... 4가지 전부 만족해야 데드락 발생한
1. 상호 배제 - 공유자원은 한번에 한 프로세스만이 사용 가능함.
2. 점유 대기 - 프로세스가 할당된 자원을 가진 상태에서, 다른 프로세스가 그 자원을 사용하려고 기다리고 있어야함
3. 비선점 - 다른 프로세스에 할당된 자원은 뺏을수 없음
4. 순환 대기 - 자원을 요구한는 프로세스 간 사이클이 형성되어야함..(꼬리물기..)
데드락을 예방하려면?!
크게..
1 예방, 회피
2 탐지, 복구
3 무시
존재
예방
순환 대기 예방 - 모든 스레드가 정해진 순서대로 자원을 획득하게끔 강제한다
점유 대기 예방 - 스레드가 작업을 시작하기전, 자기가 필요한 자원에 다 락을 걸고 시작하게 함
비선점 예방 - 어떤 자원을 원하는데, 이미 다른 스레드가 쥐고있다면.. 자기가 갖고있는 락을 일단 다 풀어 양보하고 다시 줄서게함
회피
겨착상태 예상 후, 안전할때만 자원 요청하기..
은행원 알고리즘 같은거.. (안전한 상태가 유지될때만 자원을 할당)
자료구조/알고리즘
퀵 정렬 O(NlogN), 최악은 O(N^2)
: pivot 기준 잡고 나보다 작은애들 왼쪽, 큰애들 오른쪽으로 정렬..
만약 pivot으 ㅣ기준이 너무 작거나 크다면? 매우 비효율적
또는 이미 정렬된 배열을 퀵 정렬로 돌리면 속도가 O(N^2)으로...
병합 정렬 (항상 O(NlogN).. 최악의 경우에도 속도 보장)
: 데이터를 반씩 쪼개다가.. 나중에 다시 합치는것..
우선순위 큐
: 내부적으로 힙이라는 트리구조 사용
일단 큐는.. 데이터가 먼저 들어오면 먼저 들어온 순서대로 나가는 FIFO 형식의 자료구조임.
우선 순위큐는?? 들어오는 순위에 상관없이, 우선순위가 높은!! 애들먼저 나가는 자료구조임.
힙을 이용해서 구현하는게 제일 좋당
데이터 삽입 O(logN)
데이터 삭제 O(logN)
힙이란??
완전이진트리 형태의 자료구조
이때 완전 이진트리란...... 마지막 레벨을 제외한 모든 레벨이 모두 ! 채워져있고!
그 마지막 레벨은! 왼쪽부터 잘 채워져있어야함..
최대힙 - 부모 노드의 키값이 자식 노드의 키값보다 큰 것..
최소힙 - 부모 노드의 키값이 자식 노드의 키값보다 작은 것..
STACK 스택
- LIFO 후입선출
가장 늦게 들어온게 제일 먼저 나감. 프링글스 생각하면됨
- DFS(깊이 우선 탐색)ㅇ서 활용. 미로찾기할때.. 막히면 가장 최근에 갈라졌던 교차로로 간당. 로직 구현할때 사용
- 실행 취소나.. UI창 관리(창 연순서대로.. 다시 끄는거)
DFS vs BFS
둘다 그래프를 탐색하는 방법.
그래프를 탐색한다? -> 하나의 정점으로부터 차례대로 모든 정점을 방문하는것을 말함.
DFS (Depth-Frist Search 깊이 우선 탐색)
미로가 있다고 가정할때...
미로에서 한쪽 길을 선택해서 갈 수 있을때 까지 직진하는 것..
만약 더이상 갈 수 없다면? 최근에 갈라졌던 교차로로 다시 돌아감!! 그리고 또 거기서 쭉 들어감.
주로 스택이나, 재귀함수를 사용
- 현 경로의 노드만 기억하면 돼서... BFS에 비해 메모리 공간 덜 차지.
- 단점은.. 현재 경로가 최단경로가 아닐 수 있음. 시간 허비 가능..
BFS (Breadth-First Search 너비 우선 탐색)
얇고 넓게 파는 방식..
시작점에서 가까운곳부터 점진적으로 범위를 넓히며 탐색함.
미로의 시작점에서 1보 가까운 애들먼저 확인후, 그 다음 2보, 3보에 있는 칸들을 순차적으로 확인함.
주로 큐를 사용. 먼저 발견한 노드와 연결된 노드를 먼저 탐색해야 하므로.. FIFO 구조가 필요함!
- 장점은... 시작점부터 무조건 가까운 곳부터 탐색하므로, 목표 노드를 발견했을 때 그 경로가 최단경로임을 보장.
- 단점은.. 탐색해야 할 노드가 많아질수록 큐에 저장해야하는 데이터가 기하급수적으로 늘어나서 메모리 많이 차지...
'허공' 카테고리의 다른 글
| 언리얼에서 vrm파일사용 (0) | 2025.10.16 |
|---|---|
| ㄹㄹㄹ (0) | 2025.03.25 |