본문 바로가기

전체 글155

[CDS] chapter 8 : 트리 1. 트리 기본트리는 한 개 이상의 노드로 이루어진 유한 집합으로, 계층적인 자료를 표현하는데 적합한 자료구조이다. 항목들이 순차적으로 저장되는 선형 자료구조는 각 항목간의 관계를 표현하기 어려워 더이상 적합하지 않게 된다.트리 자료구조와 관련된 용어는 위 그림으로 정리하면 된다. 위 그림에 더하여, 노드의 차수는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다는 것만 추가적으로 정리하자.(더하여, 책에서는 루트의 레벨을 1로 놓고 트리의 높이 등을 계산하고 있다는 점이 위 그림의 표현과 차이점이다)2. 이진트리(1) 정의 이진 트리는 모든 노드가 2개의 서브 트리를 가지고 있는 트리로, 가장 많이 쓰이는 트리라고 한다. 여기서 서브 트리는 공집합일 수 있기 때문에 모든 노드의 차수는 2 이하가 된.. 2025. 3. 5.
[OSTEP] CPU 가상화 : 스케줄링 개요 1. 비교를 위한 전제(1) 워크로드에 대한 가정워크로드(workload)란 시스템에서 처리해야 할 전체 작업의 양을 말한다. 여기서는 스케줄링 정책 논의의 복잡도를 줄이기 위해 워크로드를 '일련의 프로세스들이 실행하는 상황'으로 단순하게 정의하기로 하자. 그리고 이 워크로드에 대해 다음 다섯가지의 비현실적인 가정을 도입하고 점진적으로 완화시켜나가면서 현실적인 스케줄링 정책을 도출해보기로 한다.모든 작업은 같은 시간 동안 실행된다.모든 작업은 동시에 도착한다.각 작업은 시작되면 완료될 때까지 실행된다.모든 작업은 CPU만 사용하고 입출력을 수행하지 않는다.각 작업의 실행 시간은 사전에 알려져 있다.(2) 스케줄링 평가 항목스케줄링에는 다양한 평가 기준이 존재하는데, 성능 측면에서의 평가기준인 '반환 시간.. 2025. 3. 4.
[OSTEP] CPU 가상화 : 제한적 직접 실행 원리 1. 직접 실행 프로토콜과 문제점프로그램을 CPU상에서 직접 실행시키면 CPU의 빠른 연산속도에 의해 프로그램을 빠르게 실행할 수 있을 것이다. 아무런 제한이 없는 직접 실행 프로토콜은 다음과 같이 이루어진다.그러나 이러한 직접 실행 기법에서는 다음과 같은 문제점이 자연스럽게 대두된다.프로그램에게 제한된 연산은 어떻게 수행하는가시분할 기법의 구현은 어떻게 하는가2. 제한된 연산의 수행방법(1) 커널 모드와 시스템 콜프로세스가 시스템 자원에 영향을 주는 특수한 연산(디스크 입출력 요청, 추가 메모리 할당 등)을 수행하길 원하는 경우, 이를 방치한다면 여러 문제가 발생할 수 있다. 악성 프로그램이 디스크 전체를 읽을 수 도 있고, 메모리를 무한정으로 할당하여 시스템을 다운시킬 수 도 있을 것이다. 이를 방지.. 2025. 3. 2.
[KNK] chapter 17 : 포인터 고급 1. 동적 메모리 할당(1) 기본지금까지 살펴본 C의 자료구조는 고정된 크기를 갖고 있었다. 일반 배열의 경우 프로그램이 컴파일되면 원소의 개수가 고정이 되고, C99의 가변 크기 배열 VLA의 경우에는 런타임에 배열의 크기가 동적으로 결정되지만 그 이후로는 크기가 고정된다. 프로그램 실행 중에 필요한 메모리 크기를 알 수 없는 경우가 많기 때문에, 이러한 자료구조만으로는 유연한 메모리 관리가 불가능하고 메모리 효율성도 낮을 수 밖에 없다. 때문에 C언어에서는 동적 메모리 할당이 존재한다. 말 그대로 동적으로 메모리를 할당하는 개념이기에, 런타임에 메모리를 할당하거나 해제할 수 있어 필요에 따라 자료구조의 크기를 늘리거나 줄이는 것이 가능해진다.(2) 동적 메모리 할당 함수동적 메모리 할당에서는 stdl.. 2025. 3. 2.
고추잡채 태어나서 처음으로 먹어본 음식 2탄은 '고추잡채'이다. 일단 기본적으로 나는 잡채를 엄청 좋아하지는 않는다. 잡채에 대한 개인적인 한줄평은 '의외로 묘하게 느끼함'이다. 군대에 갔을때 잡채가 나름 상위권의 인기메뉴여서 놀랐던 기억도 있다.  고추잡채는 잡채에 약간 변화구를 준 음식으로 생각하기 쉽다. 하지만 고추잡채는 잡채와 생각보다 거리가 있는 음식이었다. 마치 개미와 흰개미의 관계와 비슷하달까? 개미가 하얘진다고 흰개미가 되는게 아닌 것처럼, 잡채에 고추를 넣는다고 고추잡채가 되는 것이 아니었다. 결정적으로 고추잡채에는 잡채의 아이덴티티인 당면이 없다. 고추잡채에 대한 개인적인 한줄평은 '잡채보다는 맛있으나 양장피가 낫다'이다. 또다시 중국집에 가게 된다면 고추잡채를 선택하기 보다는 새로운 도전을 해.. 2025. 2. 28.
[OSTEP] CPU 가상화 : 프로세스 1. 프로세스 기본개념운영체제는 적은 수의 CPU임에도 마치 매우 많은 CPU가 있는 듯한 환상을 만들어 내는데, 이를 CPU 가상화라고 한다는 것을 앞서 살펴보았다. 이 환상은 하나의 프로세스를 실행시킨 뒤 중단시키고 다른 프로세스를 실행하는 작업을 반복하는 과정을 통해 만들어지는 것이다. 이 시분할 기법(time sharing)으로 인해 원하는 수 만큼의 프로세스를 동시에 실행할 수 있게 된다. 프로세스를 간단하게 정의하면 실행중인 프로그램이라고 할 수 있다. 디스크에 저장되어 있는 프로그램을 실행하기 위해 운영체제는 새로운 프로세스를 생성하고 프로세스가 실행될 메모리 공간을 할당하여 실행 파일을 메모리로 로드한다. 이때, CPU는 프로세스를 실행하기 위해 필요한 레지스터를 초기화한다. 이제 CPU가.. 2025. 2. 28.
[OSTEP] Intro : 운영체제 개요 0. 개요운영체제는 쉽게 표현하면 컴퓨터 시스템의 자원을 효율적으로 관리하는 소프트웨어라고 할 수 있다. 이를 위해 운영체제는 CPU, 메모리, 디스크와 같은 물리 자원을 가상화 하고, 병행성과 관련된 복잡한 문제를 처리하며, 파일을 영속적으로 저장하여 안전한 상태에 있게 한다. 이하에서 가상화부터 살펴보자.1. 가상화가상화(virtualization) 기법은 시스템의 물리적 자원을 활용하여 사용이 편리한 가상 형태의 자원을 생성하는 것을 의미한다. 가상화를 공부하면서 캐치해야 할 핵심적인 질문은 '운영체제가 어떻게 자원을 가상화하는가'이다. (1) CPU 가상화CPU 가상화란 하나 또는 소규모 CPU 집합을 무한개의 CPU가 존재하는 것처럼 변환하는 것을 말한다. 이를 통해 동시에 많은 수의 프로그램을.. 2025. 2. 27.

티스토리툴바