해나의 컴공생존기

수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. base: p(1) 이 참이다. step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을 알아내는 것이다. 그런데 step 에서 p(n-1) -..

변수는 정보를 담아주는 박스같은 존재이다. 변수는 이름, 주소, type으로 구성되어있다. 이름: 사람들을 위한 속성, 변수들을 구별할 수 있도록한다 주소: CPU 와 메모리를 위한 속성, 변수들을 구별할 수 있도록 한다. Type: 몇바이트의 크기를 갖고 어떤 bit들를 어떤 의미로 읽을 것인가를 결정 (문자형, 정수형) 변수를 선언 할 때 Type 이름 = 변수값 ex) int a =8 이런식으로 선언한다. 이렇게되면 우리는 이름과 타입은 알 수 있지만 주소는 알 수 없다. 우리는 다음과 같은 이유로 주소를 알아야한다. - 모든 변수를 다 만들어 둘 수가 없음 - 메모리를 얼마나 쓸지 미리 알 수 없음 -> 메모리 할당 필요 Type이 주소인 변수를 우리는 포인터 변수라고 한다. 포인터 변수는 int..

자료구조를 공부하기 전에 컴퓨터의 기본적인 구조와 컴퓨터가 어떤 방법으로 실행되는지부터 보겠다. 메모리 안에는 무수한 바아트, 비트들이 있다. - 비트 : 0과 1을 표시할 수 있는 전자회로적인 도구 - 바이트 : 8개의 비트 이러한 메모리는 어떤 방식으로 저장하고 동작할까? 이를 알아보기 위해 간단한 코드와 이가 동작하는 방법을 설명해보겠다. int main() { int a,b,c; c= a+b; } //a:300 b:600 C:900 주소에 저장된다고 가정 int a,b,c 가 실행 되면 a,b,c는 memory 어딘가에 저장이 될 것이다. 메모리에는 0번부터 차례대로 번호가 매겨져 있으며 int a,b,c는 빈 자리에 가서 각 4바이트의 연속된 데이터를 차지하고 있을 것이다. 다음으로 c=a+b ..

1. I/O Devices interface : 시스템 소프트웨어가 작동을 제어할 수 있도록한다. 모든 장치에는 지정된 인터페이스와 프로토콜이 있다. internal : 장치가 시스템에 제공하는 추상적인 명령을 구현하기 위해 구현되어있다. While (STATUS == BUSY) ; // 바쁘니까 이따 와라 Write data to DATA register Write command to COMMAND register (Doing so starts the device and executes the command) While (STATUS == BUSY) ; // wait until device is done with your request 비효율성 및 불편함 1. Polling : Busy 면 계속 기다려..

1. Non-deadlock bugs 1.1 Atomicity-violation bugs 코드 영역은 원자성이지만 실행 중에는 원자성이 적용되지 않을 수도 있다. = race conditon -> mutex 로 해결 가능 1.2 Order-violation bugs 원하는대로 스레드가 실행되지 않아 오류가 생길 수 있다. -> mutex랑 cond를 이용하여 해결 가능 2. Deadlock bugs 2.1 Conditions for Deadlock - Mutual exclusion : 스레드가 lock 되어있어야 함 - Hold-and-wait : lock을 갖고 다른 lock을 갖는다 - No preemption : lock을 강제로 뺏지 못한다 - Circular wait : 각 스레드가 다른 스레드..

Semaphores를 이용하면 lock과 conditon variable을 동시에 사용할 수 있다. 이런 Semaphores는 여러가지 용도로 사용할 수 있다. int sem_init(sem_t *s, int pshared, unsigned int value) // 가운데 인자에는 공유한는 프로세스개수, 마지막인자에는 초기값을 넣어 초기화하는 함수이다 int sem_wait(sem_t *s) // s 를 1 감소시키고 s가 음수가 되면 재우는 함수 int sem_post(sem_t *s) // s 를 1 증가시키고 큐에 자는애가 있으면 깨우는 함수 /*사용예시*/ sem_t m; sem_init(&m, 0, 1); sem_wait(&m); // critical section here sem_post(&m..

조건이 성립하기 전까지 기다리는 것은 스레스에서 굉장히 유용하다. 하지만 이는 CPU 사이클이 낭비된다. 이를 해결할 수 있는 것은 Condition Variables이다. Condition Variables는 큐이다. 스레드가 조건에 성립하지 않아 실행되지 않을 때 큐에 배치된다. 다른 스레드가 상태를 바꾸고 큐에 대기중인 스레드를 깨워 계속 진행할 수 있다. pthread_cond_wait(); // 스레드가 잠들 때 사용 pthread_cond_signal(); // 자는 애를 깨움 함수는 위와같으며 인자로는 mutex가 들어간다. int done = 0; pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t c = PTHREAD_COND_I..

1. Counters typedef struct __counter_t { int value; pthread_mutex_t lock; } counter_t; void init(counter_t *c) { c->value = 0; pthread_mutex_init(&c->lock, NULL); } void increment(counter_t *c) { pthread_mutex_lock(&c->lock); c->value++; pthread_mutex_unlock(&c->lock); } void decrement(counter_t *c) { pthread_mutex_lock(&c->lock); c->value--; pthread_mutex_unlock(&c->lock); } int get(counter_t *..

1. Evaluating locks critical sectiond에 여러 스레드기 들어가지 않도록 조심해야한다. lock이 풀리면 모든 스레드가 그것을 얻을 공평한 기회를 얻어야한다. 즉 굶는 스레스다 있으면 안된다. 또, lock으로 인해 over head가 일어나서도 안된다. 이 방법은 lock 하면 interrupt를 막고 unlock 하면 interrupt를 받아드리는 방법이다. 이 방법은 단점이 많다. - interrupt를 막고 받고 하려면 권한이 있어야한다 - 멀티 프로세스 환경에서는 통하지 않는다. (interrupt) 2. Spin locks typedef struct __lock_t { int flag; } lock_t; //구조체 선언 void init(lock_t *mutex) {..

1. Multi-threaded program 단일 스레스는 프로세스와 비슷하게 각 스레스 자체 PC와 레지스터, 스레드만의 스택을 가지고 있다. 하지만 멀티 스레드는 프로세스와 다르다. - 동일한 주소공간을 공유하여 같은 데이터에 접근할 수 있음 - 동일한 주소공간을 갖고 있어 페이지 테이블을 전환할 필요 없음 (context switch 필요 없음) * context switch는 프로세스가 바뀔 때만 일어남 스레드는 TCB(Thread Control Block)으로 관리된다. 스레드는 Heap 영역과 Program Code(read only) 부분은 공유하고 stack 영역은 스레드별로 가지고 있다. 1.1 스레드의 장점 1) 병렬성을 증가시킬 수 있다 - CPU의 개수가 계속 늘어나고 있는데 이때..