컴퓨터 과학 도장깨기

계기

학교 C++ 수업 담당 선생님께서, 여름방학 숙제를 내주셨다.
숙제의 내용이 해당 카테고리들에 대한 것들에 대해 학습하고 정리하는 것이다!

이를 정리와 더불어, 블로그로 적어두어 언제 어디서든 CS 지식이 필요할 때
다시 볼 수 있도록 만들면 좋을 것 같다는 생각을 해서 적게 된 글이다.
먼저, 프로세스와 스레드에 대해 알아보자!

프로세스와 스레드

이는 운영체제에서 다루어지는 매우 중요하고 기본적인 지식이다.
프로세스와 스레드가 각각 무엇인지, 어떤 관계인지에 대해 알아보자.

프로세스가 뭐야?

프로세스는 컴퓨터에서 실행되는 컴퓨터 프로그램을 뜻한다.
그럼 컴퓨터 프로그램은 무엇이냐? 생각보다 간단하다.
컴퓨터 프로그램은 어떤 작업을 위해 실행할 수 있는 파일이다.

프로세스는 운영체제로부터 시스템 자원을 할당받는다.
대표적으로 CPU 시간과 필요한 주소 공간, 메모리 영역 등을 할당받게 된다.
생각보다 간단하다. 그런데 우리는 프로세스와 관련된 글을 읽다 보면,
모든 글에서 나타나는 한 가지의 공통된 문장을 볼 수 있다.

기본적으로 프로세스는 최소 1개의 스레드를 가지고 있다.

이 문장을 통해 스레드가 무엇인지 몰라도 어떤 점을 추측할 수 있을까?
프로세스가 더 큰 범위, 즉 스레드를 품는 부모 역할이고, 스레드가 자식 역할이라는
정도를 알 수 있다.

그렇다면, 이 배경지식으로 스레드에 대해서 알아보자.

스레드는 뭐야?

스레드는 프로세스가 할당받은 자원을 이용하는 실행의 단위이다.
스레드는 메모리상 스택 영역만 따로 할당을 받고, 코드와 데이터, 힙 영역은
다른 스레드들과 공유를 한다.

하지만 프로세스들은 다른 프로세스와 공유할 수 없다는 차이점이 있다.

마치 회사와 회사원 같은 느낌이네!

난 이들의 관계를 예를 든다면 프로세스는 회사, 스레드는 회사원이라고 생각한다.

회사원은 회사의 여러 자료들을 공유하며 업무를 처리하지만,
회사들은 서로의 자료들을 공유하거나 영역을 침범하지 않기 때문이다.

마무리

프로세스와 스레드에 대해 알아보았다. 운영체제와 관련해 제일 기본이 되는 개념이며,
현재 내가 글을 쓰고 있는 작업과 청자가 글을 읽는 작업도 모두 프로세스와 스레드 개념으로
작업이 진행된다. 이에 대해서 잘 이해하는 개발자가 되도록 하자.
이제, 네임 맹글링에 대해 알아보자.

네임 맹글링 ( 네임 데코레이션 )

네임 맹글링은 프로그램에서 함수나 변수를 선언했을 때,
사용했던 이름을 컴파일러가 컴파일 단계에서 자신만의 규칙으로 바꾸는 작업을 뜻한다.

네임 스페이스나 지역, 전역 변수들을 기준으로도 이름을 바꾸기도 하며,
함수호출 거리와 콜링 컨벤션에 따라서도 네임 맹글링 기법이 변형된다.

컴파일 단계에서 링커가 이를 구분하기 위해 컴파일러가 함수, 변수 명을 다시 변형해준
다는 점이 정말 신기한 것 같다.

궁금해졌는데, 처음부터 네임 맹글링을 사용해서 함수와 변수명을 선언하면
컴파일러가 변환을 하지 않아도 되니 속도가 빨라질까?
나중에 이에 대해서 한번 알아보아야겠다.

네임 맹글링 형식은 잘 정리해둔 블로그가 있으니 이를 참고하면 좋을 것 같다.
샤라웃 투 네온아이님 갱갱
링크

그렇다면 이제 페이징에 대해 알아보자.

페이징 기법

페이징은 가상 메모리를 블럭으로 쪼개어 나누는 기법을 말한다.
가상 메모리를 더욱 효율적이게 관리하는 기법 중 하나이다.

가상 메모리에서는 프로세스의 모든 데이터를 적재하는 것이 아니라,
나누어진 프레임을 할당 받아야만 물리 공간으로 데이터가 이동되는 기법이다.

사진처럼, 큰 메모리를 작은 단위의 블록으로 만들어서 관리하는 방법이다.
이를 페이징 기법이라 하며, 이 블록들을 한 페이지라고 표현한다.

페이지의 특징

페이지는 모두 같은 크기를 가진다는 특징이 있으며,
크기는 2의 제곱수를 사용한다. 일반적으로는 4KB 정도로 할당한다고 한다.

페이지의 친구, 프레임

페이지와 비슷한 프레임이라는 친구가 있는데, 이 친구와의 차이점은 다음과 같다.
프레임 : 물리 메모리를 일정한 크기로 나눈 블록이다.
페이지 : 가상 메모리를 일정한 크기로 나눈 블록이다.

페이지는 가상 메모리 기법이며, 페이지가 하나의 프레임을 할당 받는 형식으로
작업이 진행되고, 할당받은 페이지는 물리 메모리에 위치하게 된다.

페이지의 크기는 누가 정할까?

페이지의 크기는 하드웨어에 의해 정의된다.
컴퓨터의 구조에 따라서 작게는 512바이트에서, 많게는 16MB정도 된다고 한다.

페이징을 왜 사용할까?

앞서 말했듯이, 가상 메모리를 효율적으로 관리하는 기법이기 때문이다.
이에 더불어, 외부 단편화를 해결해주지만, 내부 단편화는 아쉽게도 해결해주지 못한다.
근데 외부 단편화와 내부 단편화가 뭘까?

외부 단편화와 내부 단편화

짧게 알아보자.

먼저 내부 단편화는 다음과 같이, 빈 공간보다 작은 블록이 들어갔을 경우 일어난다.

들어가면 20MB가 남을 것인데, 이 남은 공간이 너무 좁아 다른 작업이 들어오기도
애매하고 근데 공간은 아까운 섭섭한 상황이 발생하는 것이 내부 단편화이다.

외부 단편화는 다음 사진과 같다.

작업은 너무 큰데 하나의 빈 공간이 작업만큼 크지 않아 비는 공간은 작업의 크기보다
넓은데도 불구하고 작업이 들어가지 못하는 섭섭한 상황이다.

페이징을 이용하면, 페이지라는 블록으로 나누어 작업을 할당해주기 때문에,
이런 위와 같은 외부 단편화를 해결할 수 있다.

마무리

계속 공부하면서 느낀건, 생각보다 CS에 대해 너무 방어적인 태세를 갖추고 있지
않았나 싶은 생각이 든다. 두 세개의 글이나 자료를 읽어보니, 해당 기술들이
어떤 역할을 하는 기술들인지에 대해 거의 다 이해가 갔다.

조금 기가 빨린다고 해야하나..? 그런 느낌이 없지않아 있긴 하지만,
흥미가 있는 것들이기에 계속 꾸준히 하루에 30분씩이라도 관련 공부를 해보아야겠다.

사담이 조금 길어졌다. 다음으로 넘어가자.

세그멘테이션

세그멘테이션은 방금 소개한 페이징과는 반대로, 내부 단편화는 해결할 수 있으나
외부 단편화는 해결하지 못하는 기법이다.

이는 위에서 설명한 것을 토대로 간단하게 설명할 수 있다.

페이징 기법은 모두 같은 단위로 페이지를 나누어 처리를 하지만,
세그멘테이션은 이와 다르게 메모리에 맞게 크기를 다르게 분할해 할당한다.

프로세스가 필요한 만큼 메모리를 할당해주기 때문에, 공간보다 더 작은
내부 단편화는 일어나지 않는다.

하지만, 프로세스가 중간에 메모리를 해제하면 틈이 생기기 때문에,
외부 단편화는 해결해주지 못한다.

다음은, 커널과 힙 알고리즘에 대해 알아보자.

커널

커널은 컴퓨터 운영 체제의 핵심이 되는 컴퓨터 프로그램이다.
컴퓨터의 모든 요소들을 제어할 수 있다.

아까 프로세스가 운영체제로부터 시스템 자원을 할당받는다고 했는데,
이처럼 프로세스에게 자원을 할당해주는 친구가 바로 커널이다.

커널은 한정된 시스템 자원을 효율적으로 관리해주며, 아까 말한 것처럼
프로세스에게 자원을 할당해주는 역할을 스케줄링이라고 한다.

그런데, 커널은 힙 정렬 알고리즘을 사용한다.
이유는 리눅스 커널의 헤더 노트에서 확인할 수 있는데,
힙 정렬은 구조체 배열같은 사용자가 정의한 데이터들도 정렬을 할 수 있기
때문이라고 한다.

그럼 힙 정렬이 무엇인지에 대해 알아보자.

힙 정렬 알고리즘

힙은 트리를 구성해 정렬을 진행하는 알고리즘이다.
크게 두 가지로 나뉘는데, 최소힙과 최대힙 트리이다.

최대힙은 트리의 루트가 제일 큰 값으로 정렬되며,
최소힙은 반대로 루트가 제일 작은 값으로 정렬되는 알고리즘이다.

내림차순 정렬을 위해서는 최대 힙을 구성하고,
오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

먼저 인덱스 순으로 새로운 노드를 삽입한 다음,
삽입한 상태에서 형제 노드와 부모 노드와 값을 비교하여
만약 자신이 더 크다면 현재 자신의 위치와 더 작은 노드의 값을 바꾸며
정렬을 하는 알고리즘이다.

이제 벡터에 대해서 알아보자.

벡터

먼저, C++의 기준으로 벡터를 설명해보겠다.

벡터란?

벡터는 C++의 표준라이브러리에 있는 컨테이너로,
사용자가 사용하기 편하게 정의된 class를 벡터라고 한다.

속도적인 측면에서는 배열에 비해서 성능이 떨어진다. 하지만,
메모리를 효율적으로 관리할 수 있고 예외처리까지 쉽다는 장점이 있어 많이 사용된다.

사용법

코드	의미
vector<자료형> 변수명	백터 생성
vector<자료형> 변수명(숫자)	숫자만큼 백터 생성 후 0으로 초기화
vector<자료형> 변수명 = { 변수1, 변수2, 변수3... }	백터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[] = {, }	백터 배열(2차원 백터)선언 및 초기화(열은 고정, 행은 가변)
vector<vector<자료형>> 변수명	2차원 백터 생성(열과 행 모두 가변)
vector<자료형>변수명.assign(범위, 초기화할 값)	백터의 범위 내에서 해당 값으로 초기화

vector<int> v;        // int형 백터 생성

vector<int>v(4);    // int형 백터 생성 후 크기를 4로 할당(모든 백터요소 0으로 초기화)

vector<int>v = { 1, 2, 3 };        // int형 백터 생성 후 1, 2, 3 으로 초기화

vector<int>v[] = {{1, 2}, {3, 4}};        // int형 백터 배열 생성(행은 가변이지만 열은 고정)

vector<vector<int>> v;        // 2차원 백터 생성(행과 열 모두 가변)

vector<int> v = { 1, 2, 3, 4, 5};        // 백터 범위를 5로 지정하고 정수 10으로 초기화

v.assign(5, 10);    // 10 10 10 10 10

벡터의 명령어들

명령어	기능
v.begin()	백터 시작점의 주소 값 반환
v.end()	백터 (끝부분 + 1) 주소값 반환
v.rbegin() (revers begin)	백터의 끝 지점을 시작점으로 반환
v.rend() (revers end)	백터의 (시작 + 1) 지점을 끝 부분으로 반환

그림으로 나타내면 이렇게 생긴 친구라고 한다.
마지막으로 덱에 대해서 알아보자.

덱

덱은 데이터를 앞으로도 뒤로도 입력할 수 있고,
앞으로도 뒤로도 출력이 가능한 큐 혹은 스택 혹은 두 개 모두와 같은 자료형이다.

덱은 큐와 스택을 모두 가진 것처럼, 앞으로 삽입 후 뒤로 뺄 수도, 앞으로 뺄 수도 있다.

친구와 큐 안에 큐를 넣으면 정말 효율적일 것 같다고 이야기를 나누었던 적이 있는데,
큐 안에 큐를 넣은 것이 바로 덱이다. 이미 있었군..

마무리

이렇게 컴퓨터과학 지식에 대해서 짧게 알아보았다. 재미있고 흥미로운 내용들이
많지만, 확실히 뇌가 힘들어하는 느낌을 제대로 받았다.

앞으로도 여러가지 컴퓨터 과학들을 공부하며, 알고리즘 문제들을 풀 때에도 덱 같은
경우에는 이를 적용할 수 있게 노력해보아야겠다.

코드만 작성하는 코더가 아니라, 컴퓨터를 잘 이해하는 진짜 개발자가 되려고 노력하자.