전체보기
[OS] Process Scheduling
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이 글은 process scheduler를 설명한다. CPU Scheduler CPU scheduler는 ready queue에 있는 process 중 하나를 선택해 CPU에 할당한다. 이 때 강제로 다른 process의 가져올 수 있는지 또는 해당 process가 끝난 이후에 scheduling을 진행하는지에 따라 크게 2종류로 나뉜다. preemptive : 필요 시 process로부터 CPU를 강제로 회수하는 방법. non preemptive : process의 동작이 종료되거나 process가 자발적으로 중지할 때까지 해당 process의 실행을 보장하는 방법. 용어 task : 사용자의 request l..
[OS] Multiprocessor Synchronization & Deadlock
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 지난 포스팅에서 lock 등을 사용해 synchronization을 사용하는 방법을 알아보았다. 그러나 이 방법은 lock을 사용하기 때문에 multi processor에서는 효율이 나쁘다. 이 글에서는 어떻게 이를 해결하는지, 그리고 resource의 요청이 꼬였을 때 발생하는 deadlock에 대해 알아본다. Multiprocessor Synchronization multi processor 환경에서 많은 thread를 가진 프로그램은 효율이 좋지 않다. lock contention : 한 번에 단 하나의 thread만 lock을 가질 수 있기 때문이다. cache ping : lock에 의해 보호받는 sha..
[OS] Implementing Synchronization
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이전 포스팅에서 Lock, Condition Variable, Semaphore를 살펴봤었다. 이 글에서는 어떻게 이들을 구현하는시 살펴본다. Sychronization 구현 synchronization을 구현하는 방법에는 크게 3가지가 있다. atomic한 memory load/store instruction. (note와 while문을 사용하는 peterson 알고리즘) 그러나 이 방법은 너무 복잡하고 thread 개수가 많아지면 구현하기 어렵기에 좋은 방법이 아니다. 특정 코드에 대해 interrupt를 차단하는 방법. 이 방법은 간단하지만 interrupt가 발생했을 때 해당 코드를 모두 실행한 후 int..
[OS] Synchronization - Lock, Condition Variable, Semaphore
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이 글에서는 synchronization의 개념에 대해 살펴본다. 딱 하나의 thread만 있는 경우 모든 instruction이 deterministric하기 때문에 아무런 문제가 없다. 그러나 multi thread 환경으로 concurrent 환경을 만들었을 경우, shared data에 대한 concurrent access가 race condition을 발생시키고, data inconsistency가 발생할 수 있다. 이 장에서는 이러한 현상을 어떻게 막을 수 있는지를 살핀다. Atomic Operation Race Condition race condition은 shared data에 동시에 접근할 때, ..
[OS] Concurrency & Thread
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이 글은 OS의 concurrency와 thread를 다룬다. 한 프로그램은 여러 개의 이벤트를 동시에 처리해야 할 수 있어야 한다. 앞에서 살펴본 내용으로는 process가 concurrency를 지원하기 때문에 여러 개의 process를 사용하면 concurrency를 처리할 수 있을 것이다. 그러나 process의 생성 cost가 클 뿐아니라 process끼리는 독립된 자원을 사용하기 때문에 상호작용도 어렵다. 이를 해결하기 위해 나온 것이 thread이다. Thread 위에서 문제삼은 내용을 해결하기 위해 process를 thread와 address space 2개로 나눈다. thread : process..
[OS] Process
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이 글은 process에 대해 살펴본다. Process process는 program의 instance이다. Program program은 disk에 있는 instruction들의 집합이다. 소스코드 .c 파일은 컴파일을 거쳐 .s 파일이 되고, 어셈블러를 거쳐 .o 파일이 되고, linker가 이들을 모아 executable file인 .out 파일이 된다. 이 .out 파일이 program이다. Instance program을 실행하면 해당 파일 내에 있는 instruction과 data를 메모리에 올리며, 이렇게 메모리에 올라가 실행 중인 프로그램이 하나의 instance, 즉 process이다. 메모리에 ..
[OS] Operating System Overview
이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다. 이 글에서는 Operating System의 대략적인 그림을 살펴본다. OS를 위한 하드웨어 기술 Bootstrapping bootstrap은 OS의 실행 준비를 뜻하며 아래 4가지 과정을 거친다. power on : physical memory의 defined address로 jump (ROM의 bootstrap code - BIOS -로 간다.) disk 내의 bootloader를 physical memory로 복사한다. disk 내의 kernel을 bootloader가 physical memory로 복사한다. 이후에는 OS가 각 app을 찾아 memory에 load한다. 이 과정은 disk에서 app을 찾고..
[컴퓨터 SW] Dynamic Memory Allocation
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 dynamic memory allocation에 대해 알아본다. (java의 object나 C의 malloc, C++의 new 등 heap에 data 할당하는 것들) Dynamic Memory Allocation C의 mmap과 같이 직접 메모리를 할당할 수 있지만 이 경우 메모리의 할당 주소를 직접 지정해 주고 잊지않고 할당한 메모리를 해제하는 등의 작업이 필요하다. 이를 해결한 것이 dynamic memory allocation이다. dynamic memory allocatior는 heap에 필요한 만큼 메모리를 자동으로 할당해 준다. 또한 모든 프로그램의 data structure는 r..
[컴퓨터 SW] Virtual Memory
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 virtual memory에 대해 알아본다. disk size는 memory size보다 훨씬 크고 memory size는 꽤 작기 때문에 실제로 한 번에 실행할 수 있는 process의 개수가 한정된다. 그러나 virtual memory를 통해 하나의 process에 격리된 하나의 private linear address space를 제공할 수 있게 된다. 이외에도 locality에 의해 memory를 효율적으로 사용할 수 있게 되고, memory 관리를 단순화하며, address space를 격리할 수 있는 장점이 있다. Virtual Memory Virtual Memory Concept..
[컴퓨터 SW] System Level I/O
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글은 Linux에서 system level I/O를 살펴본다. Unix I/O Linux에서 file은 m개 byte의 나열, B$_0$, B$_1$, B$_2$, ... , B$_{m-1}$이며, 모든 I/O device는 file로 간주하며 current file position을 조정해 해당 위치에 있는 byte를 읽는다. File Type file type은 아래 3가지가 있다. Regular File : 임의의 데이터를 포함하는 file Directory : 관련있는 파일 그룹의 index. link들의 배열로 이루어져 있으며 각 link는 file과 filename을 매핑한다. Socket..
[컴퓨터 SW] Exceptional Control Flow & Process
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 exceptional control flow에 대해 알아본다. Exceptional Control Flow processor가 시작된 순간부터 끝나는 순간까지 CPU는 연속된 instruction으로부터 한 번에 하나의 instruction을 읽고 실행한다. 이러한 순서를 CPU의 control flow라고 부른다. control flow가 바뀌는 경우는 크게 3가지가 있는데, 그 중 2가지는 앞에서 배운 call과 return / jump와 branch이고 나머지 하나가 exceptional control flow이다. call and return 또는 jump and branch의 경우 ..
[컴퓨터 SW] Static Linking
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 Linking에 대해 알아본다. Linking Linking은 프로그램 코드와 데이터를 합쳐 실행할 수 있는 파일을 만드는 과정이고, Linker는 Linking을 수행하는 프로그램이다. Linking의 장점 Linking의 개념이 등장하기 이전에는 모든 소스코드를 한 번에 컴파일해 실행가능한 프로그램을 만들었는데, 이 방식의 경우 소스코드가 조금만 바뀌어도 프로그램 전체를 재컴파일해야하는 비효율적인 방식이다. 그러나 Linker의 등장으로 프로그램을 작은 소스파일의 단위로 모듈화했고, 소스코드가 수정된 부분의 모듈만 재컴파일해 기존 모듈들과 Linking을 할 수 있게 되었다. 즉슨 기존에..
[컴퓨터 SW] Cache와 Locality
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글은 cache에 대해 다룬다. Locality locality는 프로그램이 최근에 참조한 주소와 그 근처의 주소에 반복적으로 참조하는 경향이다. temporal locality와 spatial locality 2종류가 있다. temporal locality : 최근에 참조된 주소를 반복적으로 참조하는 것을 의미한다. spatial locality : 최근에 참조한 주소 근처의 주소를 참조하는 것을 의미한다. int sum = 0; for(int i = 0; i 4라 가정하자. 제일 첫 접근 : ijk for(int i =0; i
[컴퓨터 SW] Storage - RAM & Disk
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 Storage저장매체 중 RAM과 disk에 대해 간단히 살핀다. Random-Access Memory, RAM RAM은 자유롭게 내용을 읽고 쓸 수 있는 저장장치이다. 최소단위는 cell이며 하나의 cell에 하나의 bit가 저장된다. 이 cell들이 모여 chip을 이루고, chip들이 모여 memory가 된다. 크게 SRAM과 DRAM으로 나뉜다. 특징으로는 전원이 꺼지면 정보를 잃어버리는 volatile휘발성 메모리이다. Static RAM 각 cell이 4개 또는 6개의 트랜지스터를 가지고 있으며 내부 루프를 통해 값을 계속 유지시키기 때문에 전원이 유지되는 한 값이 유지되며, ce..
[컴퓨터 SW] Buffer Overflow
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 buffer overflow에 대해 알아본다. Buffer Overflow 정의 Calling Convention 게시글에서 어떤 procedure P가 procedure Q를 호출할 때 return address를 stack에 push한다고 했다. 그러나 입력 범위보다 더 큰 값이 입력되는 등 특정한 상황에서 return address가 다른 값으로 변경될 수 있다. return address가 위치해 있는 assembly는 무조건 실행되기 때문에 segmentation fault가 나거나, 또는 사용자가 원하는 instruction을 실행시킬 수도 있다. 이처럼 데이터의 크기가 할당된 범..
[컴퓨터 SW] Array/Structure/Union의 할당과 접근
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 array와 structure가 선언되었을 때 메모리에 어떻게 저장하고 어떻게 접근하는지 알아본다. Array Allocation TYPE ARRAY[LENGTH]; 와 같이 선언된 경우, TYPE이 총 LENGTH개 있는 배열을 선언한 것이다. 이 때 메모리에는 LENGTH * sizeof(TYPE)만큼의 공간이 할당되며, ARRAY 안에 있는 값들은 연속되어 저장된다. Access 값들이 연속되어 저장된다는 점을 이용해 array의 시작 주소를 이용해 array의 특정 element에 접근할 수 있다. 위 예시에서, ARRAY[i]의 주소값은 [시작 주소값] + sizeof(TYPE) *..
[컴퓨터 SW] Calling Convention
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 calling convention에 대해 알아본다. calling convention은 함수가 호출되었을 때 어떻게 parameter를 처리하고 결과를 return할지에 대한 규약이다. Stack의 구조 C언어나 Java 등을 배우면서 '메모리는 code, stack, heap 등으로 나뉘어져 있어요~'라는 내용을 한 번쯤은 들어봤을 것이다. stack에는 local variable과 parameter 등이 저장되며, 이 값들이 저장되고 반환되는 방식이 calling convention이다. intel 계열 중 하나인 x86에서는 stack memory가 더 작을수록 top에 위치한다. 즉 ..
[컴퓨터 SW] Byte Ordering
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 byte ordering에 대해 살펴본다. * LSB : Least Significant Byte, 제일 작은 byte를 의미한다. Byte Ordering 모든 컴퓨터는 word라는 단위로 메모리에 접근한다. 32-bit 컴퓨터의 경우 4 byte, 64-bit 컴퓨터의 경우 8 byte이다. byte ordering이란 컴퓨터가 메모리에 값을 저장하는 방식이다. 크게 Big Endian과 Little Endian으로 나뉜다. 주소값은 0부터 시작하며, 값이 커질수록 higher address이다. Big Endian LSB가 high address에 저장되는 방식이다. Sun, PPC M..
[Troubleshooting] 쿼리 최적화 : Subquery -> JOIN
문제상황 개발 환경은 eGovFramework에서 ibatis XML을 사용해 query를 날리고, DB는 CUBRID이다. 기존 쿼리는 아래와 같고, 시간은 약 200초로 응답이 너무 오래 걸려 기능 개선 요청이 들어온 상황이다. table명, column명은 맥락과 비슷하게 조금 수정했지만 전체 query의 구조는 동일하게 작성했다. 분석 일단 코드를 보면 개판이다. 학과 종류에 따라 subject에서 무슨 값을 가져올지가 다른데, 이 로직 하나 때문에 나머지 subquery 전체가 복사+붙여넣기이다. 따라서, 이 부분을 해결할 수 있는 방법을 고민하는 것이 첫 번째 문제이다. 두 번째로, 실행계획이다. 이 query를 아주 간단하게 표현하면 아래와 같으며, WHERE EXISTS문 subquery가..
[컴퓨터 SW] Bit를 이용한 컴퓨터의 정보 표현
이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다. 이 글에서는 컴퓨터가 정보를 표현하는 방식인 bit와 연산에 대해 알아본다. Bit와 Bytes 컴퓨터는 모든 정보를 0과 1로 표현하며, 표현의 최소 단위를 하나의 bit라고 정의한다. byte는 8개의 bit로 구성되어 있으며 0과 1로 이루어진 수가 8자리로 이루어져 있으므로, 2진수로 숫자를 표현한다. 1byte == 8bit 1byte는 $00000000_2$부터 $11111111_2$까지 표현 가능하며, 10진수로는 0~255, 16진수로는 00$_{16}$부터 FF$_{16}$까지 표현할 수 있다. 일반적인 수들의 byte 개수는 다음과 같다. Data Type 32bit 64bit char..
23.06.06. 7월까지 당분간 할 일들 - 끝!
전역 전에 끝내고 싶은 것들 알고리즘 (코테 - 리트코드 1문제씩) 면접준비 (CS) 상세계획 6월에 마프/OS를 끝내고, 7월에 네트워크/DB를 끝내보자. 8월달은 그때가서 생각하자. 밤시간에 조금 여유 가져도 되는 것들 Naver2Tistory 리팩토링 (리팩토링, 클린 아키텍처 책 참고, 클래스 구조도 한 번 그려보기) 상세계획 - 끝! 군에서 한 일들 간단히 포스팅으로 정리 - 끝! SQL optimization - 끝! vertical partitioning? extract superclass? 아무튼. 토이프로젝트 만들고 포스팅하기 - 리팩토링 포스팅으로 퉁쳤다. - 23.09.05. 끝! large one query vs small two query 실험해 보기 - 23.09.06. 끝! e..
키보드 디자인 프로그램
생각하게 된 계기 커스텀 스플릿 키보드를 하나 만들려 생각중이다. 그런데 신경써야 하는 것들과 알아야 하는 것들이 너무 많다. 1. PCB 핸드와이어링을 사용하는 경우 스위치와 와이어를 납땜한다. 따라서 스위치와 하우징을 바꾸기 위해서는 납땜을 풀어줘야 하는데.. 이는 미관상 그닥일 뿐만 아니라 스위치 하나 바꾸자고 와이어링을 다시 하는 것은 아닌 것 같다. 따라서, 가능하다면 PCB 기반에 핫스왑 소켓을 사용하는 편이 좋다. 그럴려면 PCB 기판을 설계할 수 있어야 한다. 그러나 기본 지식 없이 PCB 기판 설계를 위해서는 PCB의 기본에 대해 알고 있어야 한다. 회로는 어떻게 짜는지, 풋프린트(외관)은 어떻게 하는지, 하우징과 체결은 어떤 부분에 할 것인지, 칩 위치는 어디에 배치할 것인지, 내가 짠..
23.05.09. 풀었던 문제들
Leetcode 54. Spiral Matrix 첫 접근 (wrong) 처음에는 위 그림처럼 풀려 했다. 결국 spiral로 풀기 때문에 겉면만 벗겨가면서 풀면 된다고 생각했기 때문이고, 가능하면 모든 변을 동일하게 접근하는 게 구현에서 쉬울 거라 생각했다. 일단 벗기는 회수는 row size를 m, col size를 n이라 했을 때 min((m+1)/2, (n+1)/2)이다. 이건 뭐 간단하게 나오는 답. 그러나 복잡한 경우는 matrix가 3 by 3라서 제일 겉면을 벗겼는데, 안에 딱 1개의 element만 남는 경우이다. [시작점]부터 [끝점-1]까지만 접근하기 때문에 이런 경우를 처리할 수 없다. 올바른 접근 (correct) 결국 한 번은 전부 다에 접근해야 한다. 구현의 편의를 위해 row ..
23.05.07. 풀었던 문제들
Leetcode 1964. Find the Longest Valid Obstacle Course at Each Position 일단 이 문제는 i까지 진행하면서 모든 obstacles에 대해 longest course length를 저장하면 될 것 같은 문제이다. 이 때, 각 course는 obstacles[i]부터 i = 0까지 내림차순으로 진행되어야 하며 i는 꼭 포함되어야 한다. 어디서 많이 본 접근 아닌가? 바로 LIS이다. 예전에 작성했던 DP + LIS 포스팅, lower bound & upper bound 포스팅 그대로 풀면 될 것이다. 단, 대신, 기존 LIS는 strictly increasing인 반면 이 문제는 monotinic increasing이다. 이를 고려해서 문제를 풀어야 한다..
23.05.06. 풀었던 문제들
Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition 일단 이 문제를 brute-force로 푼다면, length n인 것들에 대해 모든 subset을 봐야 하므로 $2^n$ 개수를 보아야 한다. 그러나 n이 100,000이기 때문에 시간 초과가 무조건 난다. 다른 방법을 풀어야 한다. 이 문제는 two-pointer로 푸는 문제이다. 만약 array가 정렬된 상태에서 어떤 subarray를 골랐다고 치자. 정렬된 상태이므로 subarray의 첫 번째 index, 마지막 index element만 가져와서 target의 값과 비교하면 된다. 그 합이 target보다 작다면 해당 subarray의 모든 subset은 문제 조건..
23.05.04. 풀었던 문제들
Leetcode 649. Dota2 Senate Greedy + Queue를 사용하는 문제. 2개의 종류 R, D가 있을 때 이 문제는 앞에서부터 선택권을 가지기 때문에, 자신보다 뒤에 있는 다른 종류의 char를 없애는 것이 제일 optimal한 선택이다. 예를 들어 RD가 있다고 하자. 만약 D의 차례에서 자신보다 앞에 있는 R의 char를 없애는 것을 optimal이라 하자. 그러나 순서는 R부터이기 때문에 R은 D를 지울 수 있다. 따라서 이건 optimal이 아니므로 - 자신보다 뒤에 있는 다른 종류의 char를 지우는 것이 제일 optimal이다. (greedy) 자신보다 뒤에 있는 다른 type의 char를 없애는 것을 반복한다면 다시 처음부터 시작하게 되는데, 결국 환형을 이루게 된다. -..
23.05.02. 풀었던 문제들
Leetcode 1822. Sign of the Product of an Array nums의 모든 element 곱이 양수인지 음수인지 0인지 리턴하는 문제. 당연히 전부 다 곱하면 overflow 나니까 0이 있으면 return 0, 아니면 음수 개수가 짝순지 홀순지 판별하면 되는 문제이다. // Runtime 7 ms Beats 57.19% // Memory 10.2 MB Beats 45.94% class Solution { public: int arraySign(vector& nums) { int isNegative = 1; for(int n : nums){ if(n == 0) return 0; if(n < 0) isNegative *= -1; } return isNegative; } }; 시간복..
23.05.01. 풀었던 문제들
Leetcode 1491. Average Salary Excluding the Minimum and Maximum Salary 주어진 배열에서 max값, min값을 뺀 값들의 평균을 구하는 문제. 전체를 sort하고 min, max값만 빼고 평균 구해도 되지만 그러면 시간복잡도가 O(nlogn)이다. 그냥 한 번 순회하면서 min, max값, sum 구하고 구하는 게 나을 거라 생각했다. // Runtime 0 ms Beats 100% // Memory 7 MB Beats 98.74% typedef long long ll; class Solution { public: double average(vector& salary) { ll sum = 0, minValue = INT_MAX, maxValue = I..
23.04.30. 풀었던 문제들
Leetcode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable 어제 문제를 풀었다면 접근을 조금 쉽게 할 수 있는 문제. 문제 힌트에도 대놓고 [graph를 완성한 후 비교하는 것이 아니라, 거꾸로 생각해라] => [0부터 build해나가는 식으로 만들어라] => 즉, union-find를 이용해 graph를 이어나가면 된다. A와 B 각각의 edge를 union-find를 이용해 graph를 만들어가는 방법을 생각했다. 단 주의해야 할 부분으로 A, B로만 edge를 만들고 common edge 중 없앨 수 있는 edge만 없앨지 common edge로 기본 graph를 만들고, A, B edge 중 사용해야 하는 것만 사용하고 나머..
23.04.29. 풀었던 문제들
1697. Checking Existence of Edge Length Limited Paths edge 간 weight가 있는 어떤 graph와 [vertex 1, vertex 2, limit]으로 주어지는 query list가 있을 때 각 query의 vertex 1부터 vertex 2까지 path 중 max값이 limit보다 작으면 true를, 아니면 false를 계산하는 문제. vertex 개수를 V, edge 개수를 E, query 개수를 Q라고 했을 때 0