개발자 모드

이전 글에서 그리디 알고리즘에 대한 개념과 그에 대한 대표적인 예시를 다뤘습니다. 오늘은 그에 이어서 허프만 압축에 대해서 다뤄보겠습니다. 허프만 압축 우리는 파일을 작성한 후에 저장하거나 전송할 때 크기를 압축하고, 필요할 떄 원래의 파일로 변환할 수 있으면 메모리 공간을 효율적으로 사용할 수 있으며 파일 전송 시간을 단축할 수 있을 것입니다. 이러한 파일의 크기를 줄이는 방법을 파일 압축이라고 하며 파일 압축의 방법 중 한 가지인 허프만 압축을 소개합니다. 허프만 압축은 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 방식으로 진행됩니다. 허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성이 존재합니다. 더보기 접두부 특성이란..

오늘은 분할 정복 알고리즘의 대표적인 문제 중 하나인 최근접 점의 쌍 찾기에 대해서 알아보겠습니다. 최근접 점의 쌍 찾기 위와 같은 점들이 있다고 합시다. 여기서 가장 가까운 점의 쌍은 어떤 점일까요?? 물론 이 그림에서는 직관적으로 보일 수 있지만, 이러한 점이 많거나 직관적으로 확인하기 어려울 때 말이죠. 우리는 이러한 문제를 알고리즘으로 해결하기 위해서 분할 정복을 사용합니다. 간단한 방법 사실 간단한 방법으로는 모든 점의 쌍에 대한 거리를 구한 후에, 가장 작은 거리를 구하면 됩니다. 하지만 그렇게 되면 시간 복잡도가 O(n^2)이 되어서, 그렇게 좋은 알고리즘 같아 보이진 않습니다. 그래서 우리는 분할 정복을 이용해 시간 복잡도를 낮춰보겠습니다. 분할 정복을 이용한 알고리즘 가장 먼저는 n개의 ..

오늘은 Address Binding에 대해서 알아봅시다. Address Binding Address Binding이란 logical 주소를 physical 주소로 변환하는 과정을 말합니다. 여기서 physical address는 실제 메모리 상의 주소를 의미하고, logical address는 CPU가 프로세스를 바라볼 때의 주소를 의미합니다. 가상 주소라고도 불립니다. 이러한 Address Binding에 있어서의 3가지 방식이 존재합니다. 이번 글에서는 이 3가지 방법에 대해서 다뤄봅시다. Address Binding at Compile time 첫 번째 방법은 컴파일 시점에 physical Address를 정하는 것입니다. 컴파일 시점에 Address Binding을 진행하게 되면, Logical ..

오늘은 메모리 관리에 대해서 알아봅시다. 메모리 관리 메모리 관리는 크게 메모리 할당, 메모리 보호로 나뉩니다. 메모리 할당은 프로세스에게 메모리 공간을 부여하고 해당 공간에 프로세스에 대한 정보(context)를 삽입하는 과정을 말합니다. 메모리 보호는 허용되는 메모리 공간에만 접근되도록 감시하는 것을 말합니다. Memory Partitioning 메모리의 크기는 한정되어 있습니다. 따라서 우리는 이러한 메모리를 효율적으로 프로세스에게 배정하고 관리해야합니다. 따라서 메모리를 효율적으로 배정하기 위한 방법들이 제시되었습니다. 우리는 그 중에서 Fixed Partitioning, Dynamic Partitioning, Buddy System에 대해서 알아봅시다. Fixed Partitioning Fixe..

RAID에 대해서 알아봅시다. RAID RAID는 Redundanct Array of Inexpensive Disks의 줄임말로, 저렴한 디스크를 여러개 사용하여 용량이 크고 성능이 우수한 디스크처럼 작동하게 하는 디스크 구성 방식을 의미합니다. RAID의 방식에는 여러가지 기법이 있습니다. 차근차근 하나씩 알아가봅시다. RAID 0 (non-redundant) RAID 0은 데이터를 하나의 디스크가 아닌 여러 개의 디스크에 나눠놓는 기법을 말합니다. 이 기법은 데이터를 부분적으로 잃었을 때, 손실되지 않은 데이터로 일부 복원이 가능한 기법을 말합니다. 이 그림에서 strip은 일반적으로 데이터의 저장 단위를 의미합니다. OS에서는 block을 의미하겠죠. RAID 1 (mirrored) RAID 1은 ..

문제 도커라이징한 mysql 컨테이너가 실행되지 않고 아래 에러를 뱉으며 계속 종료되었다. --initialize specified but the data directory has files in it. Aborting. The designated data directory /var/lib/mysql/ is unusable. You can remove all files that the server added to it. Aborting 해결 여러가지 해결 책이 있어 도전해보았지만, 나는 하단의 링크에서 제시한 방법으로 해결하였다. 아마 캐시 데이터가 너무 많아서 실행이 안됐나...?? 싶었다. docker system prune --volumes 해당 코드로 약 36GB(ㄷㄷ..)가 정리되고 정상 실행됐..

오늘은 디스크 스케쥴링에 대해서 다뤄봅니다. 디스크 디스크는 우리가 생각하는 기본적인 cd도 디스크가 될 수 있지만 통상적으로는 hard disk에 쓰이는 disk들을 디스크라고 부릅니다. cd는 한쪽 면만을 사용해서 데이터를 저장하는 방식이라면 hard disk의 저장장치는 양면을 모두 저장공간으로 사용하죠. 우선 디스크의 구조에 대해서 알아봅시다. 디스크는 우측과 같은 구조로 이루어져있습니다. 하나의 띠가 track을 의미합니다. track은 바깥에서 안쪽으로 갈수록 idx가 증가합니다. 섹터는 디스크 제조사에서 설정한 데이터의 최소 저장 단위입니다. 섹터가 모여 track을 구성합니다. 하나의 disk당 20~1500개의 track을 가지게 됩니다. 디스크들이 모여 이러한 층을 통상 이룹니다. 실제..

이번에는 운영체제가 device driver를 통해서 장치를 제어하는 방식에 대해서 다뤄보겠습니다. I/O 제어 방법 운영체제가 I/O 장치를 제어하는 방식은 크게 3가지로 나눌 수 있습니다. Polling, Interrupt-driven I/O, DMA가 있습니다. 이 세가지에 대해서 다뤄보겠습니다. 그 전에, Interrupt가 발생하면 어떠한 수행과정을 통해서 동작이 수행되는지를 다시 한번 상기해봅시다. 1. 디바이스는 Status Register, Control Register, Data-in Register, Data-out Register로 구성되어 있습니다. 또한 device는 command-ready, busy, error의 상태를 갖습니다. 2. 가장 먼저 device driver가 de..

오늘은 운영체제가 인터럽트를 처리하기 위한 방법을 알아보도록 하겠습니다. 인터럽트를 처리하기 전에 우리는 잠깐 mode change의 내용을 떠올려봅시다. 2023.09.23 - [Computer Science/운영체제] - [운영체제] 3-3. 프로세스 스위치 mode change를 통해서 user mode에서 kernel 모드로 진입하게 되는데, 이러한 kernel mode entry pointsms 총 3가지가 있습니다. Interrupt, Trap, System call. 우리는 Interrupt를 처리하는 과정을 다루면서 동시에 Trap와 System call을 어떻게 처리하는지 알아봅시다. Interrupt 우선 간략하게 Interrupt에 대해서 다시 알아봅시다. Interrupt는 비동기 ..

오늘은 입출력 장치에 대해서 알아봅시다. 입출력 장치 입출력 장치는 mechanical part와 electronic part로 이루어져 있습니다. 이 중에서 electric part를 우리는 Controller라고 부르기도 합니다. Controller에는 Control Register, Status Register, internal buffer 등으로 이루어져 있습니다. Control Register는 해당 레지스터의 비트를 1로 만듦으로써 정해진 연산 또는 동작을 수행하게 하는 역할을 합니다. Status Register는 해당 디바이스의 상태를 나타냅니다. I/O가 잘 수행되었는지, 에러가 있는지 등을 Status Register의 특정 비트를 확인함으로써 알 수 있습니다. Internal Buff..