이누의 개발성장기

쓰레드의 개요 fork()를 사용하면 사용자 공간 상 text 영역은 부모프로세스와 공유하고, data,bss,heap,stack 영역은 복사되어 별도로 할당된다. 이렇게 생성된 프로세스가 전통적 프로세스이며, heavy weight process이다. 이러한 heavy weight process는 data영역이 별도로 할당되기 때문에 프로세스간의 공유변수를 갖기 어렵다. (운영체제가 제공하는 특수 구조체나 공유파일(pipe, shared mem., signal, socket 등)을 사용해야 공유가 가능해진다.) 또한 영역을 복사하는 과정이 시간적 오버헤드와 메모리 낭비를 초래할 수 있다. 반면 light weight process인 쓰레드는 text와 data 모두를 공유하고 stack만 따로 갖는 형..

본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다. 따라서 완벽하지 않은 부분이 있을 수 있습니다. 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다. String Matching 특정 문자열에서 특정 문자열을 찾는 것 ex) abababcabcabcdabccbaabdabcabcdabcd 에서 abcabcd를 찾는 방법 응용 : 워드 / 염기서열 분석 Naive, DFA, KMP 방법 Navie 알고리즘 int naivematch(char T[], int n, char P[], int m, int output[]) { int i, j, k; for (i=1; i

프로세스의 생성 생성상태란 PCB와 주소공간이 마련된 상태를 의미한다. 프로세스는 보통 fork 시스템 콜을 통해 생성된다. 이 때 생성한 주체인 프로세스를 부모프로세스, 피 생성된 프로세스를 자식프로세스라고 한다. 부모와 자식은 1:N 관계가 될 수 있다. 그에 따라 전체적으로 프로세스 구조는 tree형태를 나타낼 것이다. fork()의 수행은 부모 프로세스에서 일어나지만, fork()로부터의 리턴은 부모, 자식 모두에게 일어난다. 단, 부모 프로세스의 리턴값은 자식 프로세스의 고유번호(PID)이고 자식 프로세스의 리턴값은 0이다. 이렇게 리턴값을 다르게 설정한 이유는, fork()의 리턴값을 받아 이를 조건문에 활용해 다른 작업을 수행할 수 있도록 하기 위해서이다. 자식프로세스가 생성되면 사용자 문맥..

배열의 성능분석 같은 배열이라도 값이 모여있을 수 있고 흩어져 있을 수 있다. 또 값들이 순서대로 정렬되어 있을 수 있고 그렇지 않을 수 있다. 이런 특성은 배열의 성능을 결정짓는데에 크게 기여한다. 이를 Packed vs UnPacked (빈 자리를 한 쪽으로 모으느냐? 흩어져 있을 수 있느냐?) Sorted vs UnSorted (아이템들이 정렬된 상태를 유지하느냐? 그렇지 않느냐?) 라고 말할 수 있는데, 이를 기반으로 배열을 총 네가지 분류로 나누고 성능을 분석해보겠다. Packed, UnSorted 가장 간단한 방법 아이템의 개수를 표시하는 변수가 따로 필요하다 Search : O(N) Insert : [Search, O(N)], O(1) (넣기만 하면됨) Delete : [Search, O(N..

상태 천이 (State Transition) 실제로 프로세스는 단순히 중단, 실행의 상태만 있는 것이 아니라 더 다양한 상태가 존재한다. (이는 운영체제의 종류에 따라 다양하지만 대표적인 5가지 상태인 생성,준비, 실행, 대기, 종료에 대해서만 알아보도록 하겠다.) 이러한 프로세스의 상태가 바뀌는 것을 '프로세스 상태 천이'라고 한다. 각각의 상태는 모두 연관되어 있다. 이러한 상태 천이는 상태천이도로서 설명된다. (참고 : https://sungjk.github.io/2016/05/20/Scheduling.html) 생성(new) , 종료(terminated) : 프로세스가 생성 중일 땐 생성(new) 상태가 되고, 프로세스 실행이 종료하면 종료(terminated) 상태가 된다. 준비(ready) :..

합병정렬 int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b, h); sort(b+h, n-h); // Merge two halves in b to a return 0; } 정렬된 두 가지 배열을 정렬되도록 합치는 것이 Merge(합병)이다. 배열을 가장 작게 쪼갠 뒤, 이들을 계속해서 Merge하면 최종적인 배열이 정렬될 것이다. 반복문으로도 구현할 수 있지만, 조금 복잡해져서 재귀를 활용했다. copy와 merge 코드 구현부는 제외하고 서술했다. 시간복잡도 O(N*logN) 합병정렬의 증명 입력 집합 a[0],a[1],...,a[n-1] 의 정수 집합에 대해 Sorting이 완료된 집합은 b[0],b[1],..

선택 정렬 int sort(int a[], int n) { int i,j,m,t; for (i=0;i k - 1 라면 a[x] > a[k-1] 가 성립한다. 4. Prove Invariant by induction Base : 'k = 0 일 경우 invariant가 성립한다.' -> invariant(1) null condition으로 true / invariant(2) null condition으로 true Step : 'k번째 루프가 끝났을 때 invariant가 성립한다면 k+1번째 루프가 끝났을 때도 invariant가 성립한다' -> k번째 루프가 끝났을 때 'a[0] k - 1 라면 a[x] > a[k-1]'가 성립한다고 가정하자. 그 후..

프로세스 정의 프로세스 : 실행 중인 프로그램. 어떤 프로그램이 임의 시점에서 실행되고 있다면 그를 프로세스라고 한다. 프로그램은 저장장치(하드디스크)에 존재한다. 프로그램이 CPU가 이를 다룰 수 있도록 메인 메모리에 탑재되면 프로세스가 된다. 이들은 시스템 콜을 통해서 커널의 통제하에 시스템의 자원을 경쟁하는 주체들이다. 시분할 시스템에서는 임의의 시점에 여러 프로세스가 동시에 수행하는 경우도 있다. 이를 멀티태스킹(혹은 멀티 프로세싱, 태스킹과 프로세싱은 같은 용어라고 봐도 무방)이라고 한다. 프로세스는 그 주체에 따라 두가지로 나뉜다. 응용 프로그램이 실행되면 이는 사용자 프로세스라고 하고, 운영체제가 필요에 의해 생성하는 프로세스는 시스템 프로세스라고 한다. 문맥과 문맥교환 프로세스의 문맥(co..

이중모드와 모드비트 '보호'라는 것은 기본적으로 커널의 모든 데이터가 응용 프로그램 등의 영향에 의해 손상되지 않도록 하는 것을 의미한다. 하지만 커널의 구성요소는 다양하다. 이 모든 것에 대해 하나하나 보호 방법을 강구하는 것을 매우 소모적이다. 따라서 보다 근본적이고 연쇄적으로 작용할 수 있는 해결법을 찾는 것이 중요하다. 이중모드 : 커널 모드와 사용자 모드 모두를 분리하는 방식이다. 메인 메모리를 사용자 공간과 커널 공간으로 나누고 CPU가 사용자 공간 프로그램을 수행할 때는 사용자 모드로, 커널 공간 프로그램을 수행할 때는 커널 모드로 동작하도록 한다. 즉, 어떤 응용 프로그램에서 커널이나 다른 프로그램의 오동작을 야기 시킬 수 있는 함수(코드)를 사용해야 할 때 커널 모드로 전환하여 이를 수행..

- 본격적인 자료구조에 대해 배우기 전에 자료구조를 익히기 위한 사전 지식을 배워보자. - 여러 부분을 다뤄야해서 다소 광범위한 느낌이 있다. - 모든 코드는 C++이 기준이다. 변수 int a = 129; 변수는 기본적으로 위와 같이 선언한다. 변수는 a와 같은 이름과 위 코드에서는 보이지 않지만 해당 값이 저장된 메모리 상의 주소, int와 같은 자료의 타입으로 구성된다고 할 수 있다. 이 중 특히 타입은 해당 값의 '크기'와 '해석 방법'을 정의하기 때문에 중요하다. (int는 4바이트의 크기를 가지고 숫자로 해석되지만, char는 1바이트의 크기를 가지고 아스키 코드를 통해 문자로 해석된다.) 포인터 int a, x; int *p, *r; int **q; x = a + *p; // 가능 q = p..