랄뚜기의 코딩일기

Condition Variables There are many cases where a thread wishes to check whether a condition is true before continuing its execution. Example: A parent thread might wish to check whether a child thread has completed. This is often called a join(). How to wait for a condition Condition variable Queue of threads Waiting on the condition An explicit queue that threads can put themselves on when some..

Lock-based Concurrent Data structure Adding locks to a data structure makes the structure thread safe. How locks are added determine both the correctness and performance of the data structure. 여기서 알아두면 좋은 것은 correctness와 performance가 trade off 관계에 있다는 것이다. Example : Concurrent Counters without Locks typedef struct __counter_t{ int value; pthread_lock_t lock; } counter_t; void init(counter_t *c){..

Locks : The Basic Idea Ensure that any critical section executes as if it were a single atomic instruction. Add some code around the critical section lock_t mutex; // some globally-allocated lock 'mutex' ... lock(&mutex); balance=balance+1; unlock(&mutex); Lock variable holds the state of the lock available (or unlocked or free) No therad holds the lock acquired (or locked or held) Exactly one t..

thread : Used to interact with this thread. attr : Used to specify any attributes this thread might have. Stack size, Scheduling priority,... start_routine : the function this thread start running in arg : the argument to be passed to the function (start routine) a void pointer allows us to pass in any type of argument 만약 start_routine 대신에 다른 type argument가 필요하다면 declaration은 위와 같을 것이다. thread :..

Thread란 single running process를 위한 새로운 abstraction이다. Multi-threaded program Multi-threaded program은 한 개 이상의 execution을 가진다. Multiple PCs (Program Counter) Thread들끼리 같은 address space를 공유한다. 각각의 thread들은 고유의 PC(Program Counter)와 register들을 가지고 있다. 여러개의 TCB(thread control block)이 각각의 thread의 상태를 저장하기 위해 필요하다. 만약 T1에서 T2로 switching된다면 T1의 register state는 저장이되고 T2의 register state가 restore될 것이다. addr..

Implementing LRU Algorithm Counter implementation 모든 page table에는 counter가 있다 page는 entry를 통해서 참조 되고, counter에 clock을 복사한다. clock은 memory에 참조가 일어날 때마다 증가한다. page가 replace 되야할 때, counter를 확인하여 어떤 page가 replace 될 지 결정한다. Stack implementation doubly linked list 형식으로 page number를 stack으로 만든다. page가 참조 될 때마다 해당 page number를 stack의 top에 올려놓는다. 즉, top이 most recently used가 되고 bottom이 LRU가 된다. update하는데 ..

Cache Management의 목표는 cache miss의 수를 최소화 하는 것이다. 그렇다면 어떤 기준으로 cache를 설정하면 될까? 이것이 Tracing the Optimal Policy이지만 현실적으로 미래를 알 수 없으므로 불가능하다. FIFO 방식으로하면 Hit rate이 36.4%로 급격히 낮아진다. 0이 계속 들어올 것이지만 제거해버렸기 때문이다. 당연히 cache가 커지면 hit rate가 오를 것이라고 생각하겠지만 FIFO에서는 오히려 줄어들 수 도 있다. ex) 3->4 차라리 Random하게 cache에 저장하는 것이 오히려 효율적 일 수 있다.(약 45%) 때때로는 Random이 optimal처럼 좋을 수도 있다. 위 두 개의 history( recency, frequency )..

Os는 현재 크게 필요하지 않는 주소 공간을 버릴 필요가 있다. 현대 Os system에서는 아래의 규칙을 hard disk drive에 사용한다. Swap Space DRAM에 주소를 담을 공간이 부족하다면, SSD의 Swap Space에 page-sized unit 만큼 저장해 놓아야 하므로, OS는 swap space를 기억할 수 있어야 한다. 따라서 Present Bit를 사용해서 page가 physical memory에 있는지 disk에 있는지 확인한다. Page fault physical memory에 있지 않은, 즉, Swap space에 있는 page에 accessing하는 것을 의미한다. page가 swapped disk에 있다면 OS는 해당 page를 다시 memory로 올려놓아야 한다..

Paging : Linear Tables 32-bit address를 space를 사용하고 4KB의 page table을 사용한다면 Page table의 크기는 2^32/2^12*32=4MByte의 크기를 차지하게 된다. 이 page table의 크기는 너무 크다. Page size의 크기를 늘린다면 어떻게 될까? page table은 1MB로 줄어들게 되지만 page frame 안에서의 공간이 남아돌기 때문에 internel fragmentation이 발생한다. 또 각각의 page table이 linear하기 때문에, 언제 사용될지 모르는 낭비되는 공간이 발생하게 된다. Hybrid Approach : Paging and Segment Page Table에서 저렇게 남는 공간이 있는 걸 어떻게 해결 할..

페이지 테이블을 이용하게 되면 메모리를 flexble하게 사용할 수 있으므로 메모리 효율이 올라간다. 하지만 logical address를 physical address로 변환시키기 위해서 page table에 접근하고 page table에 있는 physical address를 확인 후에 다시 physcial address로 접근해야 한다. 따라서 2번의 메모리 접근이 일어나기 때문에 성능이 내려가게 된다. 이를 해결하기 위해서 MMU에 TLB(Translation Lookaside Buffer)를 넣어서 만약 TLB에 cache되있어 hit가 일어난다면 바로 physical address에 접근할 수 있게 한다. TLB는 하드웨어의 cache라고 생각하면 된다. 32-bit address를 4KB의 p..