File에는 다음의 정보가 저장되어 있다. Inode number Path File descriptor Inode에는 meta data가 저장되어 있다. Hierarchical으로 구성되어 있다. 빈번하게 path를 검색하는 것을 방지하기 위해서 사용된다. 가령 file descriptor는 다음처럼 사용된다. int fd = open(char *path, int flat, mode_t mode) read(int fd, void *buf, size_t nbyte) write(int fd, void *buf, size_t nbyte) close(int fd) Disk Structure Disk는 large array로 구성되어 있다. Data를 이 array에 잘 mapping하는 것이 주요 포인트이다. ..

HW supprot for I/O I/O를 쉽게 하기 위해, 각 HW는 bus에 연결되어 있어 통신이 가능해진다. Canonical HW device HW를 쉽게 관리하기 위해 공통된 protocol을 가지고 있다. Write할 때 발생하는 protocol은 다음과 같다. HW interface가 결국, 동작을 결정하게 된다. 각 친구들의 variants는 다음과 같다. Status Data Control polling interrupts PIO DMA Special instruction Memory-mapped I/O Status Interrupt이 항상 좋은 것은 아니다. Fast device라면 spin하는 것이 더 좋을 수 있다. 또한 interrupt이 계속해서 발생하는 device라면 live..

Conditional variable은 queue에 park하고 unpark를 기다리는 것이었다. 즉, state가 없다. CV에 state를 넣어서 관리하려고 만든 것이 semaphore이다. 동작은 간단하다. Wait sem > 0 이면. semaphore의 값을 1 감소시키고 lock을 acquire한다. sem < 0 이면, 대기한다. post()에 의해 sem 값이 0보다 커지면 깨어날 수 있다. Post: sem의 값을 1 증가시킨다. 그리고 waiter 하나를 깨운다. 위 동작은 atomic하게 구현되어 있다. Conditional variable보다 동작이 간단해진다. Semaphore = Lock + CV Semaphore로 lock이나 CV처럼 사용할 수 있고, lock과 CV가 있으면..

기존 lock은 OS 스케쥴러가 lock으로 인해 무슨 일이 발생하는 지 몰랐다. 이제는 OS 스케쥴러가 이 lock 활동을 직접 관리하여 ready 상태의 thread를 run한다. 구현은 간단하게도 ready queue에서 lock으로 인해 동작 못하는 thread는 제거하는 방식이다. (park(), unpark()) Lock: Block when waiting Lock에 lock과 guard, 그리고 queue가 있다. Guard는 queue를 위한 lock이라고 보면 된다. Acquire lock 과정은 다음과 같다. guard 사용중: spin wait guard 작업 없음: guard 얻음 lock 잡혀있음 queue에 thread 넣고 guard 내리기 park() lock 없음 lock ..

6장 thread에서 이어지는 내용이다. Lock Goal 이미 한번 봤던 내용이지만, lock의 구현 목표는 다음과 같다. Correctness Fairness Performance Mutual exclusion Deadlock-free Starvation-free wait for same amount of time CPU is always used Locking linked lists Linked list에 node를 추가하려고 할 때, race condition에 빠질 수 있다. 이를 위해 lock을 구현해야 한다. 그러기 위해 우선 linked list에 lock을 추가한다. Head 부분의 구조체에 mutex를 추가한다. 그리고 linked list 초기화할 때, lock을 NULL로 설정해 준..

OS마다 구현은 다르겠지만, 본 포스팅에서는 IA32로 stack에 대해 설명한다. IA32에서 사용하는 register는 다음과 같다. %eax 등은 data를 저장하는 데 사용된다. %esp나 %ebp는 stack의 위치를 나타낸다. %eip는 PC라고 생각하면 된다. IA32 stack Stack은 lower address로 grow한다. %ebp가 제일 큰 주소를 가지고 %esp가 감소하는 식으로 stack에 정보를 저장한다. (아래로 큰다. Heap은 위로 큰다.) Push %esp의 주소가 -4되면서 data가 저장된다. 명령어는 pushl이다 Pop %esp의 주소가 +4되면서 가장 밑에 있던 data가 pop된다. Procedure control flow 스택에는 function call과..

코어 수는 증가하는 반면, CPU의 속도는 증가하기 어렵게 되자 concurrency를 위한 수단이 필요해졌다. 많은 코어를 사용할 수 있는 어플리케이션이 필요해진 것이다. 처음에는 그 만큼 프로세스 수를 늘렸다. 쉽고, 보안성도 확실했기 때문이다. 그러나 프로세스 간의 통신은 큰 overhead이며 context switching 비용도 만만치 않다. 이런 배경에서 등장한 것이 thread이다. 프로세스와 비슷하지만, 같은 프로세스에서 나온 thread는 address space를 공유한다. 매우 큰 일을 나눠서 해결하며 shared address space를 통해 communication을 하기 때문에 비용이 적게 든다는 장점이 있다. 이와 같은 장점으로 인해 multi-threaded program..

OS의 목표 중 하나는 physical memory가 부족할 때, 프로세스가 최대한 동작하게 만드는 것이다. 가령 user의 code 영역은 프로세스마다 physical memory에 저장할 필요가 없을 것이다. Virtual memory는 physical memory가 훨씬 더 많은 것처럼 환상을 주는 OS의 핵심 스킬이다. Locality of reference 프로세스 내부에서 얼마나 연속적이거나 근처에서 참조하는지 나타내는 지표를 locality라고 한다. 크게 2가지의 locality가 있다. Spatial: 참조한 address 근처 address를 참조 Temporal: 참조한 address 다시 참조 프로세스는 code의 10%에 90%의 시간을 쓸만큼, locality를 고려해 code를..

Physical memory에 virtual memory를 할당시켜 보려는 노력을 계속했었는데, contiguous한 성질 때문에, fragmentation이라는 한계에 부딛히게 된다. 이를 해결하고자 도입한 것이 paging이다. 아이디어는 간단하다. 메모리를 fixed-sized page로 잘게 나눠버리는 것이다. (보통 4KB) Translation (VA->PA) 방법은 기존과 동일하다. Logical address에서 일정 top bit로 table에 저장되어 있는 내용을 참고해 physical frame number를 찾고, offset만큼 이동해 데이터를 참조하게 된다. 실제 동작은 다음처럼 진행된다. Page Table Mapping 정보가 저장된 table이다. 프로세스마다 1개씩 가지게..