구름 개발일기장

Caching 한정된 빠른 공간(Cache)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식 program system외에도 cache memory, buffer caching, web caching등 다양한 분야에서 사용하고 있다. 캐쉬 운영의 시간 제약 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에 적용하기가 어렵다. 마지노선 (log N) 빠르게 데이터를 가져오기 위해 사용하는 것인데, 메모리에 올리기위해 공간확보에 시간을 오래쓰게 되면 비효율적이다. Buffer caching & Web caching의 경우 → O(1) ~ O (log N) 정도까지 허용한다. 여기서 LRU, LFU 알고리즘이 사용된다. Paging S..

Demanding Page 실제로 필요할 때, page를 메모리에 올리는 기법으로 아래와 같은 장점이 있다 I/O 양의 감소 Memory 사용량 감소 빠른 응답 시간 더 많은 사용자 수용 Vaild / Invalid bit의 사용 invalid의 의미는? → 사용되지 않는 주소영역인 경우 (참고로 가상 메모리 대부분은 사용하지 않는 공간이다) → Page가 현재 물리적 메모리에 없는 경우 (Swap Area에 있는 경우일 것이다) 처음에는 모든 Page Entry가 invaild로 초기화 되어있다 address translation 시에 invaild bit가 set되어 있으면? → "Page Fault" 즉, 현재 메모리에 올라와 있지 않은 것이므로, swap area에서 메모리에 올려야하는 것이고, ..

Multilevel Paging and Performance Address Space가 더 커지면 다단계 페이지 테이블이 필요하다. 각 단계의 페이지 테이블은 물리 메모리에 page로서 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하게 된다. TLB를 사용함으로서 메모리 접근 시간을 줄일 수 있다. 4단계 페이지 테이블을 사용하는 경우 접근 시간 계산 (메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, TLB hit ratio가 98%인 경우로 가정한다.) 0.98 * (20 + 100)ns + 0.02 * (20 + 400 + 100)ns ⇒ ( 120 * 0.98 + 520 * 0.02 )ns 98%는 TLB 접근시간 20ns와..

Allocation of Physical Memory 메모리는 일반적으로 두 영역으로 나뉘어서 사용된다 OS 상주 영역 interrupt vector와 함께 낮은 주소 영역 사용 사용자 프로세스 영역 높은 주소 영역 사용 사용자 프로세스 영역의 할당방법 Contiguous allocation 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 방법 Fixed partition allocattion Variable partition allocation Noncontiguous allocation 하나의 프로세스가 메모리의 여러 영역에 분산되어 할당하는 방법 현대에 사용하고 있는 방식이다 Paging : 일정한 크기로 물리 메모리 공간을 잘개 쪼갬 Segmentation : 논리적 단위로 물리 메모리..

Logical vs. Physical Address Logical address 프로세스마다 독립적으로 가지는 주소공간. 각 프로세스마다 0번지부터 시작한다. CPU가 보는 주소는 logical address이다. Physical address 메모리에 실제로(물리적 공간) 올라가는 위치 Q. 주소 바인딩이란? A. 주소를 결정하는 것 Symbolic Address -> Logical Address - ... (이때가 언제일까?) ... -> Physical Address symbolic Address란? 함수나 변수값으로 메모리를 사용하는 것을 symbolic address라 한다. 컴파일이 되면 해당 메모리가 프로세스의 논리적 메모리 주소로 변환이 되고, 이를 실제 물리적 메모리 주소로 변환해서 처리..

데드락 (교착 상태) 자신이 가진 자원은 포기하지 않은채 상대방의 자원을 원하는게 맞물린 상태 Deadlock 일련의 프로세스들이 서로가 가진 자원을 기다리면 block된 상태 Resource 하드웨어, 소프트웨어 등을 포함하는 개념 i/o device, cpu cycle, memory space, semaphore 등 프로세스가 자원을 사용하는 절차 : (1)request → (2)allocate → (3)use → (4)release Deadlock 발생 조건 4가지 Mutual exclusion 매 순간 하나의 프로세스만이 자원을 사용할 수 있다 No Preemption 프로세스는 자원을 스스로 내놓을 뿐, 강제로 빼앗을 수 없는 경우 Hold and wait 자원을 가진 프로세스가 다른 자원을 기..

Producer - Consumer Problem Producer 자원 : 비어있는 버퍼 공유 메모리(버퍼)에 접근하여 Empty-Buffer를 확인한다. 공유메모리에 접근할 때마다 빈 버퍼의 개수는 줄고, 데이터는 추가된다. Consumer 자원 : 채워져있는 버퍼 공유 메모리(버퍼)에 접근하여 Full-Buffer를 확인한다. 공유 메모리에 접근할 때마다 빈 버퍼의 개수는 늘고, 데이터는 줄어든다. 동기화를 위한 Semaphore 변수 Producer & Consumer가 존재하고 있는 상황으로 버퍼로의 동시접근을 막기 위해 Binary Semaphore로 lock / unlock 수행을 해줘야 한다. 즉, 버퍼에 생산자든 소비자든 동시에 하나만 접근해서 조작할 수 있다. 생산자/소비자의 자원 개수 ..

Semaphore Cirtical Section에 대한 문제 해결 알고리즘을 추상화 시킨것. Integer 변수: 정수값은 자원의 개수를 의미한다. 아래의 두가지 Atomic 연산으로만 접근이 가능하다. Semaphore 변수 "S" P 연산 /* P 연산 */ P(S): if (S 0, S가 양수가 되면 자원을 획득 */ else S--; /* 자원 획득 */ S가 0이하라면 해당 프로세스를 Block 시킴. S가 1이상이라면 해당 자원을 획득하여 사용함. → 공유 데이터를 획득하는 과정, semaphore S의 값을 획득하는 과정 V 연산 /* V 연산 */ V(S): S++; // 자원 반납 wake_up(); /* block 중인 프로세스 깨움 */ → 자원을 사용하고 나서 반납하는 과정 S의 값..

Critical Section이란? 공유자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역 Critical-Section Problem n개의 프로세스가 공유 데이터를 동시에 접근하려는 경우 프로세스의 code Segment에는 공유 데이터를 접근하는 코드인 Critical-Section이 존재한다. 하나의 프로세스가 Critical Section에 있을 때, 다른 모든 프로세스는 Critical Section에 들어갈 수 없어야 한다. 프로세스의 일반적인 구조 do { entry section; // Critical Section으로 들어감 ~ Critical Section; ~ exit section; // Critical Section에서 나옴 remainder section; } whil..

Process Synchronization Process Synchronization 문제 데이터를 읽고 씀에 있어서 특정 주소 공간에서 값을 가져와서 연산 후 다시 저장을 하는 과정에서 프로세스끼리 충돌이 발생할 수 있다. 공유 데이터의 동시 접근은 데이터의 불일치를 발생할 수 있다. 일관성 유지를 위해 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다 Race Condition이란? A. 두개 이상의 Thread or Process가 공유자원을 병행적으로 읽거나 쓰는 상황을 말한다. Storage(Memory Address Space)를 공유하는 Execution(CPU Process)이 여러개가 있는 경우 Race Condition의 가능성이 있다. Multi-Processor Syste..

Multi-level Queue Ready Queue를 한줄이 아니라 여러줄로 분할한다. (예시) foreground Queue (interative) background Queue (batch - no human interaction) 등등 각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있다. (예시) foreground Queue - RR 스케줄링 background Queue - FCFS 스케줄링 큐에 대한 스케줄링이 필요하다. 두가지 방식이 존재 방법 1) Fixed priority scheduling 무조건 foreground에 먼저 service를 제공하고, 그다음에 가능할 때 background에 제공한다. → 우선순위를 무조건 지키는 형태로 Starvation을 유발할 수 있다. 방법 2)..

FCFS (First come First Service) non-preemptive 방식, 먼저 잡으면 빼앗기지 않고 먼저 처리한다. 만약 첫 프로세스의 소요시간이 매우 길다면 뒤의 프로세스의 소요시간에 상관 없이 기다려야 하므로 매우 비효율적이다. 첫 프로세스의 소요시간에 매우 의존적이다. Convoy effect 가 발생할 수 있다. - short process behind long process 문제 P 프로세스 : burst Time - P1 : 24 - P2 : 3 - P3 : 3 p1 → p2 → p3 순서로 매우 비슷한 시간에 왔다고 가정 Average wating time p1 (0) + p2 (24) + p3 (27) = 51 / 3 == 17 SJF (Shortest Job First)..