적으려고 하다보니 쓰레드 관련 내용이 하도 많아서 쓰레드부분만 분리하려고 새 글 팠음...

아래 내용은 'Windows via C/C++'을 기반으로 하고 있습니다.

* 틀린거 많으니 교차검증 꼭 하세요 *

[1] 스레드

1. 스레드 이론
   1. 스레드란? : '작업 흐름', 코드를 수행하는 흐름 단위. 프로세스의 주소 공간내에 있는 코드를 수행하고 데이터를 이용함.
   2. 스레드에는 '스레드 커널 오브젝트' (운영체제가 관리하기 위한 커널 오브젝트) / '스레드 스택' (코드 수행시 필요한 데이터를 담아두는 스택)이 포함
   3. 하나의 프로세스 내에 둘 이상의 스레드가 존재 할 수 있음. 이때 스레드들은 단일 주소 공간을 공유하며 동일한 코드를 수행할 수도 있으며 동일 데이터를 조작할수도 있음.
   4. 커널 오브젝트 핸들 테이블은 스레드별이 아닌 프로세스별로 존재함으로 동일 프로세스 내의 스레드들은 커널 오브젝트 핸들도 공유하게 됨
   5. 프로세스는 스레드보다 더 많은 리소스를 사용하기 때문에 프로세스를 생성하는 대신 추가적인 스레드를 생성하여 사용하는편이 좋음. 하지만 때때로는 추가적인 프로세스를 생성하는것이 더 좋을 수 있음.
      (ex : 구글 크롬의 경우 멀티프로세스를 생성하여 작동시키는 방법을 사용함)
2. 스레드 이론 2
   1. 스레드 생성이 필요한 경우 : 스레드 별 우선순위를 설정하여 일부 작업을 백그라운드로 밀어 작업을 수행하게 하거나 입력 / 출력등의 중요한 업무를 분리시켜 작업할 수 있음.
   2. 스레드 생성을 하지 않아야 하는 경우 : 다중 스레드로 인해 동일 파일에 입출력이 동시에 적용되는경우 (프린트 되는 문서에 직접 수정가하는 등), 사용자 인터페이스 같은 단일화가 필요한 작업은 멀티 스레드를 사용하지 않는것이 좋음
   3. 멀티스레드보다 멀티 프로세스를 사용하는 경우 : 애플리케이션 내부의 실행단위를 독립적으로 수행하는 경우. (메모리를 공유하지 않고 독립적으로 사용하는 경우) 구글 크롬의 경우 각 탭별로 다른 프로세스를 할당하여 타 탭이 꺼지더라도 앱 전체가 꺼지지 않음.

[2] 스레드 스케쥴링

1. 스케쥴링 기본 :
   1. 스레드는 정지(Suspended), 대기(Wait), 실행 (Run) 상태를 가짐. 정지된 스레드는 스케쥴링될 수 없음.
   2. 'Suspended thread' 명령 수행시, 커널모드에서 수행중인 코드는 비동기적으로 수행을 완료하나, 유저모드에서 수행중인 코드는 즉시 정지됨. (메모리 잠금이 일어날 수 있음)
      따라서, 해당 명령은 정지시키고자 하는 스레드가 어떤 작업을 수행중인지, 정지시 생길 수 있는 문제점과 해결책을 명확하게 파악한 후 사용해야함.
   3. 특정 프로세스 내 스레드를 전부 순회하며 정지를 시키면 프로세스를 정지시킨것과 유사한 효과를 낼 수는 있음. 하지만 자주 쓰이지는 않음.
   4. 스레드는 sleep() 함수를 호출하여 일정시간동안 스케쥴링 대상이 되지 않도록 명령을 내릴 수 있음. sleep 호출시 스레드는 자신에게 남은 Time slice (할당시간)을 포기함.
      함수의 인자로 ms 단위의 시간을 제공할 수 있으며, 0을 입력할 수 있음.
2. 스레드 우선순위 :
   1.  

[3] 스레드 동기화

1. 유저모드 동기화 :
   
   1. 동기화란? : 다수의 스레드가 공유 리소스에 접근해야 하며, 리소스가 손상되지 않아야 하는 경우, 특정 스레드가 타 스레드에게 작업이 완료되었음을 알려야 하는 경우에 이루어지는 행동. 이 경우 각 스레드들은 상호 통신을 수행함. 
      동기화가 수행되지 않으면 데이터 오염 및 경쟁-교착상태(Race Condition)에 빠질 수 있음
   2. '원자적 접근' (Atomic) : Atomic은 일반적으로 'Instruction 단위' (명령어 수행 단위)를 의미함. 특정 리소스에 Instruction 단위로 수행중일 때, 타 스레드는 동일 시간에 동일 리소스로 접근해서는 안됨.
   3. 인터락 : 명령 수행중 인터럽트 되지 않고 값을 원자적으로 조작할 수 있음. 인터락 함수를 사용 시 값의 변화를 보장 할 수 있으나, 인터락 함수의 대상인 리소스는 타 함수 (인터락이 아닌 함수)가 호출해서는 안됨.
      인터락 함수는 유저모드/커널모드 전환을 일으키지 않으며 속도가 매우 빠름.
      인터락 함수로 전달되는 값은 반드시 메모리 상에 정렬되어 있어야 함. (아니면 호출 실패)
   4. 스핀 락 : 공유 리소스 사용시 리소스 사용여부를 지속적으로 검사하는 방식. (Busy Wait)
      스핀락은 CPU 시간을 많이 낭비할 수 있으며, 스핀락을 사용하는 모든 스레드가 동일한 우선순위에 놓여 있어야만 함.
      또한, 스핀락 변수와 락을 걸고자 하는 데이터는 서로 다른 캐시 라인에 있는것이 좋음. 동일 캐시 라인이라면 리소스 사용중인 CPU는 동일 리소스에 접근하고자 하는 타 CPU와 경쟁하게 될 것.
      단일 코어 프로세서에서는 스핀락을 사용하지 않는것이 좋음. (CPU 시간 낭비)
   5. 크리티컬 섹션 : 공유 리소스에 대해 배타적으로 접근해야 하는 코드 집합. 공유 리소스를 다루는 여러줄의 코드를 "원자적으로 수행"하기 위한 방법.
      여기서 원자적이란, 위에 적힌것과 같이 현재 스레드가 리소스에 접근중일때는 다른 스레드가 동일 리소스에 접근 할 수 없음을 의미.
      크리티컬 섹션 사용시에는 Enter -> Leave 순으로 함수를 호출해야하며, Enter시 타 스레드가 크리티컬 섹션의 데이터를 사용 시 진입 불가, 미 사용시에는 진입이 가능하여 사용 할 수 있다.
      크리티컬 섹션 사용시, 데이터를 사용완료하고 나면 반드시 Leave를 호출해주어야 한다. (그렇지 않으면 나머지 모든 스레드가 해당 자원을 사용하지 못하게 됨)
   6. 크리티컬 섹션 2 : 크리티컬 섹션에 진입한 스레드가 매우 빠르게 자원을 리턴하여, 이후 스케쥴링 타임까지 시간이 낭비되는 등의 경우를 방지하기 위해 크리티컬 섹션 사용시 스핀락 메커니즘을 투입하여, 리소스 획득을 반복적으로 검사하게 할 수 있음. 
      크리티컬 섹션에 스핀락 메커니즘을 사용시, 일정 시간동안 스핀락을 수행하며 공유 리소스의 자원획득을 시도하고 실패시 스레드를 대기시키기 위해 커널모드로의 전환을 시도 함.
   7. SRWLock (Slim Reader-Writer Lock) : 크리티컬 섹션과 유사하나 값을 읽는 Reader와 값을 쓰는 Writer가 분리되어 있음. 공유 리소스에 동시에 Read를 실시하는것은 공유 리소스 값을 손상시키지 않기 때문에 동시에 다수의 수행이 일어나더라도 상관없음. 단, Writer가 리소스를 수정하는 동안에는 어떠한 Reader/Writer도 추가적으로 접근 해서는 안됨
   8. 조건변수
2. 커널모드 동기화 :
   1. 개요 : 정확히는 커널 오브젝트를 이용한 스레드 동기화. 스레드를 동기화 하기 위해 커널 오브젝트 등을 어떻게 사용할것인가 에 대한 설명을 적을 예정.
   2. 시그널 / 논 시그널 : 시그널 상태 - 사용 가능 상태, 논 시그널 - 대기 상태 (사용중인 상태)
   3. 대기함수 : 대기함수 호출시 인자로 전달된 커널 오브젝트가 시그널 상태가 될때까지 '대기함수를 호출한 스레드'를 대기상태로 유지시킴.
      대기함수 호출시 커널 오브젝트가 시그널 상태면 대기상태로 전환되지 않음.
   4. 대기 함수 사용시 'dwMilliseconds'와 같은 대기시간 인자에 'INFINITE'를 전달 할 수 있음. 이때에는 스레드가 영원히 블로킹 되지 않도록 주의가 필요.
   5. '성공적인 호출', '성공적인 대기의 부가적인 영향' : 성공적인 호출을 통해 오브젝트의 상태가 변경 시 '성공적인 대기의 부가적인 영향' 이라고 칭함. (책에선 그러더라구요)
      '성공적인 호출'은 매개변수로 전달된 커널 오브젝트가 정상적으로 시그널 상태가 된 것을 의미.
3. 커널 오브젝트 리스트 :
   1. 이벤트 커널 오브젝트 (이벤트 기반 동기화) : 이벤트 = '작업이 완료되었음을 알림'. 수동 리셋 이벤트 / 자동 리셋 이벤트가 존재.
      수동 리셋 이벤트 : 시그널 상태 시 대기중인 모든 스레드는 동시에 스케줄 가능한 상태가 됨
      자동 리셋 이벤트 : 시그널 상태 시 대기중인 오브젝트 중 하나만이 스케쥴 가능한 상태가 됨
   2. 대기 타이머 커널 오브젝트 (Waitable Timer) : 특정 시간 / 일정 시간 간격을 두고 시그널 상태가 되는 커널 오브젝트.
      특정 시간 / 간격에 맞춰서 작업을 수행해야하는 경우 사용.
      대기 타이머는 항상 논 시그널 상태로 생성됨.
      유저 타이머 (SetTimer를 사용)와의 차이점 - 대기 타이머는 커널 오브젝트임으로 다수의 스레드에서 공유될 수 있고 좀 더 보안에 안정적임.
   3. 세마포어 커널 오브젝트 : 리소스의 개수를 고려해야 하는 상황에서 주로 사용됨.
      최대 리소스 카운트, 현재 리소스 카운트를 저장하고 사용함.
      대기함수가 세마포어를 전달받을 시 현재 리소스 카운트 값을 확인하고 0보다 크면 값을 1 감소시키고 대기함수를 호출한 스레드를 스케줄 가능상태로 만듬. 
      현재 리소스 카운트가 0이면 (=세마포어가 논 시그널이면) 호출한 스레드를 대기상태로 유지시킴.
      
      작동 규칙 : 
      1. 현재 리소스 카운트가 0보다 크면 시그널
      2. 현재 리소스 카운트가 0이면 논시그널
      3. 현재 리소스 카운트는 0 미만이 될 수 없음
      4. 현재 리소스 카운트는 최대 리소스 카운트보다 커질 수 없음
   4. 뮤텍스 커널 오브젝트 (Mutual Exclusion ; 상호배제) : 크리티컬 섹션과 유사.
      
      작동 규칙 :
      
      1. 스레드 ID가 0 (유효하지 않은 스레드 ID)일 시 : 시그널 상태 ; 어떠한 스레드도 뮤텍스를 소지하지 않음
      2. 스레드 ID가 0이 아닌 경우 : 논 시그널 상태 ; 특정 스레드에 의해 소지중 
      3. (그 외 특수한 경우 규칙 위반 가능)
         
         1. 논시그널 상태에서도 스레드가 뮤텍스를 다시 소지가능
         2. 뮤텍스를 소지한 스레드가 소유권을 해지하지 않고 종료되는 경우, '버림' 처리 되어 소유권을 강제로 해제시킴

그냥 혼자 책읽고 하기에는 내용을 자꾸 빼먹는거 같아서 필기도 할겸...

아래 내용은 'Windows via C/C++'을 기반으로 하고 있습니다.

* 틀린거 많으니 교차검증 꼭 하세요 *

1. 커널 오브젝트 이론
   1. 커널 오브젝트는 OS가 제공/사용하는 커널레벨의 기능을 추상화 시킨 오브젝트 타입이다.
      커널에 의해 할당된 메모리 블럭들로, 이 메모리 블럭들은 커널 오브젝트에 대한 세부 정보드를 저장하고 있으며 커널에 의해서만 접근이 가능한 구조체로 구성되어 있다.
   2. 커널 오브젝트의 데이터 구조체는 커널에서 접근이 가능하기 때문에 애플리케이션 레벨 (유저레벨)에서 해당 정보를 직접 변경하는것은 불가능. 
   3. 커널 오브젝트 사용은 각각의 호출 함수를 통해 핸들 (HANDLE 타입 변수들)을 얻어 조작이 가능하다.
   4. 커널 오브젝트는 프로세스에서 소유하는것이 아닌 커널에서 소유함. 즉, 특정 프로세스에서 커널 오브젝트 생성을 지시하였어도 해당 프로세스가 소멸시 커널 오브젝트도 같이 소멸한다는 보장은 할 수 없음.

#define _CRTDBG_MAP_ALLOC
#include <cstdlib>
#include <crtdbg.h>

그리고 메인 함수에 _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 넣어줄것.

p.s : 특정 메모리 위치 찍어내기 : _CrtSetBreakAlloc(번호) 

뭔가 했더니 C++/CX 문법이라고 한다...

https://docs.microsoft.com/ko-kr/cpp/cppcx/visual-c-language-reference-c-cx?view=msvc-160 

이해를 똑바로 한게 맞다면... 저 Hat은...

포인터의 레퍼런스 카운터와 연관되어있는 (카운터를 올리거나 내리는) 기호인듯... 합니다.

https://devblogs.microsoft.com/cppblog/ccx-part-2-of-n-types-that-wear-hats/

git에 특정 조건을 걸어서 메시지등을 출력하는 hook이라는 기능이 있다.

(더 상세한 내용은 이 블로그 말고 다른곳을 검색해보기 바란다)

훅을 처음 써보면서, shell script도 제대로 쓸줄몰라 엄청 해멨으나 일단 원하는걸 하나 구현해놨기에 기록해둔다.

원하는건 코드 컨벤션을 맞추기 위해 설정한 문구 중

모든 코드 스타일을

void foo()
{
codes;
}

  방식으로 픽스하기 위한 조건이었다.

그걸 위해, 검색해서 pre-commit 을 수정해보려고 하니... 에러가 뜬다.

error: cannot spawn .git/hooks/pre-commit: No such file or directory

대충 이런 문구다.

요약하면 pre-commit이라는 hook이 없다는 얘긴데...

정확한 이유는 파악하지 못했으나, git 용 hook에 필수적으로 포함되어야 하는 문구들이 있는 모양이었다.

해서, 검색을 통해 어떤 문구가 있어야하는지 파악을 해두고, 문구 적용을 시켜보도록 했다.

#단순히 ") {" 스타일이 들어오면 밴 먹임

disallowed="){"


git diff --cached --name-status | while read x file; do
	if ["$x" == 'D']; then continue; fi #뭔 의미지? 'D'가 뭐지?
	
	if grep ')\s{' $file ; then
    echo "ERROR: 코드 스타일 에러입니다."
    exit 1
	fi	
	
	for word in "$disallowed"
	do
	    if egrep $word $file ; then
        echo "ERROR: Disallowed expression \"${word}\" in file: ${file}"
        exit 1
    fi
    done
		
done || exit $?

완성된건 이런 스타일인데, 정리하면 다음과 같다.

1. disalowed에 "없어야 될 문자열"을 기록한다.

2. git에서 수정된 사항을 읽는다.

3 (은 이해를 못했습니다...)

4. 파일을 전체 검색하며, 조건에 맞는 문자열이 있는지 검사후, 조건에 만족하면 echo  메시지를 띄운 후 에러를 리턴한다.

5. 정상 통과 하면 while문을 종료시키고 끝낸다.

의 구조이다.

웃긴점은, 이를 좀 "있어보이게" / "다른 사용자들이 큰 수정할 필요없이" 적용을 시키기 위해 core.hooksPath를 수정해줬더니 저 hook 조차 에러를 검사하여 리턴해버리는게 아닌가...

해서, 이런 경우에는 hookspath를 임의로 수정해준 뒤, 커밋 갱신을 해줘야 하는 소소한 불편함(?)이 발생하고 있다.

해당 문서를 위해

woowabros.github.io/tools/2017/07/12/git_hook.html

singun.github.io/2019/03/16/git-hook-pre-commit/

두 문서를 참고하였습니다. 감사합니다.

작업중, 파일을 불러올때 마지막 줄이 계속 오염이 일어나서 프로그램이 깨지는 현상을 목격함.

뭔가 했더니 값 읽어오는 >>포인터<< 변수가 데이터 로드 블럭 나가면서 데이터를 오염시켜서 생긴 문제였음.

코드 블럭 나가자마자 nullptr 찍어주는거로 해결.

원인 찾는건 조금 걸렸지만 아무튼 간단하게 해결

공부를 하다보니 하도 헷깔려서 정리 할 겸 작성함.

(물론 다른 언어들에게도 존재하지만) C 계열 언어에는 const라는 키워드가 존재한다.

간단히, '상수화 키워드' 로 알려져 있는 이 키워드는, 말 그대로 해당 키워드가 붙는 모든것을 상수화 (고정값 화) 시켜버린다.

여기서 알아두어야 할 것이, 모든 것이라는 점인데, 단순히 변수는 물론이고, 함수 삽입값(파라미터), 함수 리턴값, 심지어는 클래스/객체에도 사용이 가능하다.

근데 이게 어디 붙여도 다 상수화.... 되는건 맞는거 같은데, 좀 헷깔리는 감이 없잖아 있어서 정리를 좀 해보고자 한다.

일단 알아두어야 할 점은, const 키워드는 const 키워드 바로 다음에 오는것을 상수화 시킨다.

1. 변수의 상수화

const int A = 10;

int 형의 A 라는 이름을 가진 변수에 10을 넣고, 이를 상수화 시켜 사용하겠다는 의미이다.

이렇게 사용 시, A는 10이라는 값으로 고정되어 버리고, 어떤 방식으로든 수정이 불가능해진다. (상수 값이 되었으니..)

근데 이런 경우에, 만일 같은 이름 같은 타입의 변수를 다시 상수가 아닌 변수로 쓰고 싶다고 하면...

그냥 새로 선언해주면 끝이다.

+ 특이 케이스 :

만일 const 멤버 상수에 레퍼런스를 붙인다고 하면, 레퍼런스 변수 또한 const로 선언해주어야 한다.

이유는 레퍼런스 접근을 통한 데이터 수정 방지.

애초에 굳이 const 선언해둔걸 억지로 애써서 수정할 필요가...?

2. 함수의 상수화 A

const int foo ();

함수의 리턴 타입에 상수 키워드가 붙는 경우이다.

이 경우는 사실 하나하나 따져보면 이해하기 쉬운게, "리턴 타입" 에 "상수 키워드", 즉 "리턴 값이 상수화" 된다는 의미와 동일하다.

즉, 함수가 실행되고 나온 결과값이 상수값이 되어 수정이 불가능한 값으로 얻어진다는 의미다.

어디다 써멱냐 싶지만, 생각보다 자주 보인다. 특히 문자열쪽이라던가.

그럼 대입은 어떻게 하느냐?

그냥 쓰면 된다.

단지 가지고 있는 값이 현재 상수화 되어 보호되어 있다는것이지, 값을 누군가 대입받은 이후에는 그걸 어떻게 쓰던지 까지는 통제하지 않는다.

그냥 리턴값이 상수라는것만 기억하면 딱히 겁 먹을 필요 없음.

3. 함수의 상수화 B ; Const 멤버 함수

int foo() const;

이 케이스는 좀 특이 케이스인데, 함수 정의부가 상수화되어버린다.

무슨 얘기나면, 함수 내부에서는 값 변경이 불가능해진다 라는 의미이다.

더 정확히는, 함수 내부에서는 '지역변수를 제외한 모든 값에 대해 상수성을 보장한다' 라는 의미에 더 가까운데, 예를들어 함수 내에 값을 임시로 저장하기 위해 사용하는 temp 변수 등과 같은 케이스를 제외한 모든 경우에, 외부에서 진입된 값을 변할 수 없다는 의미이다.

이런 형태를 쓰는 케이스는 다양한 경우가 있는데, 가장 주의해야하는 케이스가 바로 포인터/레퍼런스 타입을 인자로 받는 경우이다. 

값을 복사하지 않고 원본을 사용하기 위해 가져 왔는데, 이를 시스템상에서 보장을 하기 위해 내부를 상수화 시켜버리는 것이다.

정리하면

1) Const 멤버 함수를 호출할 경우 멤버들의 값 변경을 허용하지 않음.

2) 하지만, Const 멤버 함수의 지역 변수는 값 변경이 가능함.

3) Const 멤버 함수를 일반 멤버 함수에서 호출하는것은 문제가 없으나 역은 불가능함. (상수성 파괴 위험)

* 여기서 3번은 테스트가 좀 필요해 보인다. 실제로 저런 케이스를 접해본적이 없고 테스트를 어떻게 해봐야할지 감이 잘 안잡히기도 하고...

4. 객체의 상수화

여러가지 케이스가 있는데 여기선 1번과 유사한 경우로 설명한다.

리턴값이 객체거나, 혹은 객체를 멤버로 가지는 클래스 / 자료구조에 대한 경우, 혹은 객체를 보호하고 싶은 경우에 객체 앞에 const를 붙여서 값을 리턴시킨다.

당연하겠지만 값을 사용하는것엔 문제가 없으나... 값 자체를 수정하려는 경우 (ex : 리턴 된 값이 객체인 경우)에는 수정이 불가능함에 유의.

위의 경우는 실제로 겪은 케이스인데, map / set 등과 같이 자동 정렬이 되는 자료구조 등을 사용할 경우, 구조상으로 정렬 상태를 외부에서 깨트리지 않게 하기 위해 내부 자료를 const 형으로 리턴해서 돌려준다.

즉, 리턴된 객체 전체가 const로 이루어져서 레퍼런스 접근임에도 불구하고 데이터 읽기만 가능하고 쓰기/수정이 전혀 불가능해지는 문제 아닌 문제가 발생한다.

5. const_cast

왠만하면 쓰지말자

객체/상수화 변수의 상수성을 깨트리는 역할을 한다.

4번의 경우와 유사하게, 내부 규칙을 깨트리진 않으나 값을 수정하려고 할때 const로 리턴받아질때 (문자열을 받는다거나 등) 상수성을 깨트리고 값을 사용하게 해주는 C++ 캐스트인데...

굳이 상수화 시킨 이유를 생각해보며 왠만하면 피해보도록 하자.

(진짜루)

(전부 다 를 다루는것이 아닌, "아마 회사 입사 테스트에서 봤던거 같은" 애들 위주로 정리합니다.)

1. 자료구조

1) 분류

(1) 선형 구조 : 선형 리스트(=배열), 연결리스트, 스택, 큐, 덱

(2) 비선형 구조 : 트리 (및 트리를 기반으로 한 자료구조), 그래프

2) 요약

(1) 연결리스트 : 각 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조.

(2) 스택 : 리스트의 한쪽 끝에서만 Input/Output이 가능. "LIFO" 구조의 자료형

(3) 큐 : 선형 리스트의 한쪽에선 Input, 다른 쪽에선 Output만 진행. "FIFO"구조의 자료형

(4) 덱 (Deque) : Input, Output이 양쪽에서 발생가능. 단 입/출력이 모두 양쪽에서 발생하진 않음.

(5) 트리 : Node (정점)과 가지 (Branch)를 이용하여 사이클을 이루지 않게 구현된 그래프.

Root Node에서 시작.

트리의 깊이 (Depth) : 트리 노드의 최대 길이.

트리의 차수 (Degree) : 각 노드에서 뻗어나온 가지의 수

단말 노드 (Terminal Node, Leaf Node) : 자식이 하나도 없는 (= Degree Zero) 노드

3) 이진 트리 운행

(1) Pre order (전위) : Root -> Left -> Right 순으로 진입.

(2) In Order (중위) : Left -> Root -> Right 순으로 진입.

(3) Post Order (후위) : Left -> Right -> Root 순으로 진입.

2. 정렬 / 탐색 알고리즘 기본

1) 기본

(1) 오름차순 : 다음 차수로 갈수록 값이 올라감. 1,2,3,4,5...

(2) 내림차순 : 다음 차수로 갈수록 값이 내려감. 5,4,3,2,1...

2) 종류 1 (오름 차순 기준)

(1) 삽입 정렬 : i값과 i+1 값을 비교 후, i > i+1 일 시 i+1을 i 이전에 삽입. 앞 부터 정렬됨

(2) 버블 정렬 : i값과 i+1 값을 비교 후, i > i+1 일 시 서로 맞바꿈. 뒤 부터 정렬됨

(3) 선택 정렬 : i값과 i+a 값을 비교, i > i+a 일 시 위치를 바꿔줌. i 값을 점진적으로 증가시킴 (i+a<=N)

3) 종류 2

(1) 이진 탐색 : 전체 리스트를 2개의 서브 리스트로 분리하여 탐색함.

찾고자 하는 값을 값의 중간값과 비교하며 검색.

중간 레코드 값은 ((첫번째 레코드 번호 + 마지막 레코드 번호)/2) 로 계산

(2) 해싱 : 해시 함수를 이용하여 리스트에 대한 Hash Table의 위치를 계산후 값을 저장하거나 검색함.

3. 파일 처리 / 파일 구조

1) 순차 파일 처리 : 입력되는 데이터를 논리적인 순서에 따라 물리적 연속공간에 저장.

기록 속도는 빠르나 삽입 / 수정 / 삭제, 검색은 매우 느림.

2) 색인 순차 파일 : 순차 & 랜덤 처리가 가능하도록 레코드를 정렬시켜 기록, 키 항목만을 모은 색인을 구성.

4. 논리 게이트 (시나공 2017 요약본 참조)

5. 기초 표현

1) 2진법 / 8진법 / 16진법

(1) 2진법 : 0,1로만 값을 표현. 2의 배수 만큼 올라감

(2) 8진법 : 0~7까지의 값으로 표현, 2진법으로 변환 시 값 3개를 묶음 (000~111)

(3) 16진법 : 0~9,A~F (10~15) 까지의 16개 값으로 표현, 2진법으로 변환 시 값 4개를 묶음 (0000~1111)

2) 보수 (2진법 한정)

(1) 1의 보수 : 0과 1의 값을 뒤집음.

(2) 2의 보수 : 0과 1의 값을 뒤집고 1의 자리에 +1

3) 부동 소수점 표현 1 (float)

0bit : 부호

1~7 bit : 지수부

8~31 bit : 가수부

4) 자료 표현 코드

(1) BCD 코드 : 10진수 1자리를 2진수 4bit로 표현

(2) Excess-3 (3초과 코드) : BCD +3

(3) Gray 코드 : BCD 인접 코드를 XOR 연산을 이용하여 만듬

(4) 패리티 검사 코드 : 데이터 비트에 1bit의 패리티 비트 추가 (Odd : 1 Bit의 수가 홀수 / Even : 1Bit의 수가 짝수)

6. 컴퓨터 구조

1) CPU

(1) 제어 장치 : 장치들의 동작을 지시 / 제어. 주기억 장치에서 읽어들인 명령어를 해독, 제어 신호를 보냄

(2) 연산 장치 : 산술, 논리, 관계, Shift 연산 등을 수행. (ALU 등)

(3) 레지스터 : CPU 내부의 임시 기억 장소

2) BUS

: CPU, 메모리, I/O 장치 등과 상호 필요한 정보를 교환하기 위한 공동 전송선.

(CPU 연산 처리 체제에도 영향을 많이 받음 (32bit / 64bit 등))

3) CPU 상태

Fetch, Indirect, Execute, Interrupt의 4가지.

(1) Fecth : 명령어를 주기억 장치에서 CPU의 명령 레지스터로 가져와 해독

(2) Indirect : Fetch 단계에서 해석된 명령의 주소부가 간접 주소인 경우. 명령의 유효주소를 계산.

(3) Execute : 명령어를 수행하는 단계

(4) Interrupt : 문제 (Interrupt)가 발생할 시 복귀 주소 (Program Counter ; PC)를 저장시키고, 제어 순서를 인터럽트 처리의 첫번째 명령으로 이동.

인터럽트 이후 정상적인 과정에서는 Fatch로 복귀함.

4) 하드디스크

(2) Access Time

= Seek Time + Latency Time + Transmission Time

(Seek Time = 탐색 시간 : Head 이동 시간) / (Latency Time = Search Time = 회전 지연 시간, 특정 섹터 데이터가 Head까지 가는 시간) / (TransMission Time = 전송 시간 : Head Access Data 와 주기억 장치간의 데이터가 전달되는 시간)

5) Cache Memory

(L1, L2 캐시라고 불리던 그거)

CPU와 메모리 간의 속도차이를 줄이기 위해 사용하는 Buffer Memory.

Cache Hit Percent (캐시 적중률) = 적중 횟수 / 총 접근 횟수

6) 가상 메모리

(1) 이론 : MMU (Memory Management Unit)을 이용, CPU의 연산 비트수에 매치되는 메모리 사이즈를 실제 존재하는것처럼 인지시켜 컨트롤 시키는 공간.

각 프로세스는 자신만의 가상 주소 공간을 가지고 있으며, 프로그램에서 메모리 주소에 접근시 'logical memory' 주소에 접근하도록 유도한다.

실제로는 모든 프로세스가 자신만의 가상 주소 공간을 가지고 있어, 물리적인 메모리 주소로만 접근시 충돌이 일어날 수 있기에 프로세스의 logical memory 와 physcial memory를 분리시키기 위해 만들어진 구조이다.

(2) 'Page' : 가상 메모리를 사용하는 최소 크기 단위. 

(3) Demending Page : 실제로 필요한 Page를 물리 메모리로 로드하는 단계.

(4) Page Fault : 필요한 Page가 물리 메모리에 존재하지 않는 경우. 이 경우 원하는 Page를 물리 메모리로 로드하는 과정이 일어난다.

7) 기억장치 배치 전략

(1) First Fit : 프로그램 / 데이터가 들어갈 수 있는 첫번째 공간에 삽입

(2) Best Fit : 프로그램 / 데이터가 들어갈 수 있는 가장 작은 공간에 삽입

(3) Worst Fit : 프로그램 / 데이터가 들어갈 수 있는 가장 큰 공간에 삽입

8) 단편화

(1) 내부 단편화 : 내부 분할 영역이 할당될 프로그램의 크기보다 큼으로써, 할당 후 사용되지 않고 남은 공간.

(2) 외부 단편화 : 내부 분할 영역이 할당될 프로그램의 크기보다 작음으로써 할당될 수 없이 남아있는 공간.

7. 운영체제

2) 프로세스 : 프로세서 (CPU 등)에 의해 처리되는 사용자 프로그램이나 시스템 프로그램을 의미.

3) 스레드 : 하나의 프로세스 내에서 작동하는 스케쥴링의 최소 단위. 서로 독립적인 다중 수행 가능.

(1) 사용자 수준 스레드 : 사용자측 라이브러리를 이용하여 스레드 운용.

(2) 커널 수준 스레드 : 운영체제 커널에서 스레드 운용. 

4) 상호 배제 :

(1) 임계 구역 : 공유 데이터 및 자원. 특정 시점에는 단 한개의 프로세스만 자원을 차지할수 있도록 지정된 공유 자원.

(2) 상호 배제 (Mutual Exclusion) : 특정 프로세스가 공유 자원 사용시 타 프로세스가 사용할 수 없도록 제어.

(3) 세마포어 : 각 프로세스에 제어 신호를 전달, 순서대로 작업을 수행. 프로세스간 동기화 유지 및 상호 배제 보장.

(4) 교착 상태 (Deadlock) : 자원 무한정 대기 상태

교착 상태의 필요 충분 조건

 - 1 : 상호 배제 : 한번에 한개의 프로세스만이 공유 자원 사용

 - 2 : 점유/대기 (Hold & Wait) : 최소 하나의 자원을 점유중에 타 자원을 추가 점유하려고 대기중인 프로세스 존재

 - 3 : 비선점 : 다른 프로세스에 할당된 자원은 끝날때까지 뺏을수 없음

 - 4 : 환형 대기 (Circular Wait) : 프로세스대기가 원형으로 구성되어 자신에게 할당된 자원을 점유하며 앞/뒤의 프로세스 자원을 요구

교착상태 해결 기법

 - 1 : 회피 기법 : 교착상태가 발생시 피해나감.

 - 2 : 발견 기법 : 시스템에 교착상태가 발생했는지 점검.

 - 3 : 회복 기법 : 교착상태 프로세스를 종료하거나 자원 선점하여 프로세스 혹은 자원 회복

8. 프로세서 스케줄링

(1) 정의 : 시스템의 여러 자원을 필요한 프로세스에게 할당하는 작업

(2) Context Switching (문맥 교환) : A 프로세스에서 B 프로세스로 CPU가 할당되는 과정에서 발생하는 일련의 작업.

현재 CPU가 할당된 프로세스의 상태 정보를 저장 -> 새로운 프로세스의 상태 정보 설정 -> CPU 할당

CPU Overhead의 주 요인중 하나

(3) 비 선점형 스케줄링 : 이미 할당된 CPU를 뺏어갈 수 없음, 할당받을시 완료시까지 CPU 사용

1) FCFS (=FIFO) : 도착한 순서에 따라 차례로 CPU를 할당함

2) SJF (Shortest Job First) : 실행시간이 가장 짧은 프로세스부터 CPU 할당

3) HRN (Hightest Response-ratio Next) : SJF 보완, 우선순위에 따른 CPU 할당

우선순위 계산 공식 = (프로세스 대기시간 + 서비스 시간)/서비스 시간

결과값이 높을수록 우선순위가 빨리 부여됨.

(4) 선점형 스케줄링 : 준비상태 큐의 프로세스 중에 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당.

1) SRT (Shortest Remaining Time) : SJF의 선점형, 가장 짧은 시간이 남은 프로세스부터 CPU 할당

2) RR (Round Robin) : 시분할 시스템을 위해 고완, FIFO를 선점형태로 변형.

FIFO 기반이나, '할당 시간' 만큼 CPU를 사용 후, 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘기고 준비상태 큐의 가장 뒤로 배치됨. 

할당 시간이 클수록 FIFO와의 차이가 사라지고, 할당 시간이 작을수록 Context Switching과 Overhead 가 자주 일어남.

9. 네트워크

1) 경로 제어 (라우팅 기법)

(1) IGP - RIP : 최대 홉 수를 15로 제한. 특정 시간단위로 라우팅 정보 갱신

(2) IGP - OSPF : 홉 수에 제한이 없음. 라우팅 정보가 갱신될 때 변화정보만 모든 라우터에 알림

(3) EGP : 게이트웨이 간의 라우팅

(4) BGP : EGP의 단점 보완. 처음에는 RIP처럼 전체 경로 제어표 교환, 이후에는 OSPF처럼 변화정보만 교환.

2) 망 구조

(1) 성형 (Star) : 중앙 집중형

(2) 순환형(Ring) : 단말기들을 이웃하는것끼리 Point To Point 연결시킨 형태.

(3) 버스형(Bus) : 한개의 통신회선에 여러 단말기가 연결됨.

(4) 계층형(Tree) : 분산처리 구성 방식. 

(5) 망형(Mesh) : 모든 지점의 컴퓨터와 단말기를 서로 연결.

필요 회선 수 = (n(n-1))/2

3) 인터넷 주소 체계

(1) IP Class :

Class A : 국가 / 대형 통신망 (2^24)

Class B : 중대형 통신망 (2^16)

Class C : 소규모 통신망 (2^8)

Class D : 멀티 캐스트용

Class E : 실험용 (예비)

(2) 서브넷 마스크 : 4바이트의 IP주소 중 네트워크 주소와 호스트 주소를 구분하기 위한 비트

(3) IPv6 : 16비트씩 8부분으로 구성됨

(4) 도메인 네임 : IP주소와 매치되는, 문자로 구성된 주소

(5) DNS : 도메인 네임과 IP 주소를 상호변환해주는 시스템/서버

4) OSI 참조 모델

(7) 응용 계층 : 사용자 (응용 프로그램)이 OSI 환경에 접근할 수 있도록 서비스 제공.

(6) 표현 계층 : 응용계층 <> 세션계층 간 데이터 변환. 코드 변환, 데이터 암호화, 구문검색, 문맥관리 등

(5) 세션 계층 : 송 수신측 관련선 유지, 대화 제어

(4) 전송 계층 : 종단 시스템간 데이터 전송을 가능하게 함, 전송 연결 설정, 데이터 전송, 흐름제어 등 <TCP/UDP>

(3) 네트워크 계층 : 개방 시스템간의 네트워크 연결관리, 데이터의 교환 및 중계, 경로설정, 트래픽 제어 등 <IP>

(2) 데이터 링크 계층 : 두개의 인접한 개방 시스템간의 신뢰성 있는 정보전송을 위함. 흐름제어, 오류제어 등 <LLC>

(1) 물리 계층 : 장치간 실제 접속관 절단 등에 필요한 기계적, 전기적, 기능적, 절차적 특성 <RS-232C>

5) TCP/IP 계층 모델

(4) 응용 계층

(3) 전송 계층 

(2) 인터넷 (=네트워크) 계층

(1) 네트워크 엑세스 계층 : 실제 데이터 송/수신

6) 주요 프로토콜

(1) TCP : 전송계층, 신뢰성 있는 연결형 서비스 제공. FTP, SMTP (메일), HTTP 등

(2) UDP : 전송계층, 빠른 비연결형 서비스 제공, 동시에 여러 사용자에게 데이터 전달할 경우. 실시간 전송에 유리.

(3) IP : 네트워크 계층, 데이터그램을 기반으로 한 비연결형 서비스 제공. 패킷 분해/조립, 주소 지정, 경로 선택 등

(4) ICMP : IP와 조합, 통신중에 발생하는 오류 처리, 전송 경로 변경 등을 위한 제어메시지 관리

(5) ARP : IP주소에서 물리주소 (MAC Address) 로 변환

(6) RARP : 물리주소에서 IP주소로 변환

10. 보안

1) 암호화 기법

(1) 비밀키 시스템 : 동일한 키로 데이터 암호/복호화. 대칭 암호화 기법

(2) 공개키 시스템 : 서로 다른 키로 데이터 암호화 / 해독하는 비대칭 암호화 방식. 키의 분배 용이.