Programmer's Digest

*목적  Race Condition방지, data corruption 방지 *Race condition  특정 접근 순서에 따라서 실행결과가 달라지는 경우 *silient corruption  data corruption을 운이좋게 피해간 경우 *Non-preemptive kernel  no race condition. 평균 대기시간 증가 *Critical Section  process들이 공유변수들을 수정할수 있는 코드의 영역 *Critical Section Problem  critical section에는 오직 한 process만 실행되도록 하는 문제 Requirement :  1) mutual exclusion : critical section에는 오직 한 process만이 실행될수 있다. 2) progress : 어떤 process가 임계영역에 들어가려 할때, 무기한 연기가 되어서는 안된다. 3) Bounded Waiting : 어떤 process가 임계영역에 들어가기 위해 대기하는 시간은 유한해야한다. 구현방법: Static Alternation  progress requirement를 만족하지 않음. 한 프로세스가 실행되고나서 다른 process가 실행되기 전까지는 무기한 연기됨. Peterson’s algorithm  progress, Bounded waiting 모두 만족 Special H/W instruction  atomic operation을 코드로 구현하는 것이 아니라, 하나의 instruction으로 구현. Mutex Locks   critical section 문제를 해결하기 위한 SW tool 문제점 : busy waiting이 발생함 bush waiting이란 instruction을 수행하면서 기다림(CPU cycle 낭비) 해결책 :  1) process를 semaphore의 waiting queue에 넣고 wait state...

모든 Proceess가 다른 process에 의해 야기될수 있는 event를 기다리고 있을때 발생 *필수조건 1) Mutual Exclusion : 최소 하나의 자원이 비공유 모드로 지원되어야 함 2) hold and wait : process는 최소하나의 자원을 점유한 상태로, 다른 process에 의해 점유된 자원을 얻기 위해 대기해야함 3) No preemption : 자원들은 선점이 될 수 없고, 자발적으로만 방출될수 있다. 4) circular wait : waiting process들이 순환적 대기를 해야한다. * Solution 1) system이 deadlock state에 들어가지 않도록 하는 protocol이 사용(deadlock prevention, deadlock avoidance) 2) system이 deadlock에 들어가도록 허용하되, detect해서 recover하도록 하는 방법 3) 어차피 자주 발생하지 않으므로 무시하는 방법(most popular) deadlock prevention,avoidance 방법은 비용이 너무 크므로 발생하면 재부팅 *Deadlock Prevention : deeadlock 발생 4가지 조건중 하나라도 안되도록 하는 방법 1) mutual exclusion : resource를 sharable하게 만듬 2) hold and wait : 실행전에 필요한 resource들을 모두 요청하게 한다. 3) No preemption : process가 자원들을 점유하다가 즉시 할당할수 없는 자원을 요청하면 현재 점유되고 있는 자원들이 released 4) circular wait : 모든 자원 타입들에 전체적인 순서를 부여하여 각 process가 열거된 순서대로 자원을 요청하도록 요구. *Deadlock Avoidance : 자원이 어떻게 요청될지에 대한 추가 정보를 요구, 프로세스의 요청과 방출에 대한 완전한 순서를 파악함으로써 교착상태를 피하기 위해서 process의 대기여부 결정 safe state : 시...

다중 프로그래밍 실현을 위해 메모리에 많은 process들을 동시에 유지 *Address Binding Time compile time binding : 만일 process가 memory내에 들어갈 위치를 컴파일 시간에 미리 알수 있다면 컴파일러는 절대코드를 생성가능 load time binding : 이진코드를 재배치 가능 코드로 만듬 execution time binding : process가 실행하는 중간에 memory 내의 한 segment에서 다른 segment로 옮겨질수 있다면 바인딩이 실행시간까지 허용되었다고 함 *Logical vs Physical Address logical address : cpu가 생성하는 주소 physical address: 메모리가 취급하는 주소 compile-time binding과 load-time binding에서는 logical addr = physical addr execution-time binding은 logical addr != physical addr *MMU(Memory Management Unit)  virtual(logical) addr -> physical addr *Dynamic Loading  각 routine이 재배치 가능 상태로 디스크에 대기하다가, 필요할때 적재. 사용되지 않는 routine은 적재 되지 않는다. *Dynamic Llinking linking이 실행시간 까지 미루어짐. 라이브러리를 부르는 곳마다 stub이 생겨서 메모리를 찾는방법과 없을경우 라이브러리 적재방법을 알려준다. *Swapping  일시적으로 process를 main memory에서 disk로 이동시켰다가 다시 memory로  이동시키는것. 목적 : process들을 실행하는데 필요한 공간이 physical memory공간을 초과할때 사용 roll in, roll out : 더 높은 우선순위의 process가 swap-in 되고 더 낮은 우선순위의 procss가 swap-ou...

스레싱은 프로세스의 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정 시점까지는 높아지지만, 다중 프로그래밍의 정도가 더욱 커지면 스레싱이 나타나고, CPU의 이용률은 급격히 감소하게 된다. 방지방법 다중 프로그래밍의 정도를 적정 수준으로 유지한다 페이지 부재 빈도를 조절하여 사용한다 Working Set을 유지한다

비선점 스케줄링 FCFS(First Come First Served) : 도착한 순서에 따라 차례로 CPU를 할당하는 기법 SJF(Shortest Job First) : 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법 선점 스케줄링 RR(Round Robin) : 각 프로세스는 시간 할당량동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치됨 Multi-level Queue : 프로세스 운선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비상태 큐를 상위,중위,하위 단계로 배치한다. 각 준비상태 큐는 독자적인 스케줄링 기법을 사용한다. Multi-level Feedback Queue : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 있음 각 준비상태 큐마다 시간 할당량을 부여하여 그 시간 동안 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동됨.

주소변환 : 가상주소를 물리주소로 변환하는 작업 가상주소 형식 : 페이지 번호, 변위값 물리주소 형식 : 페이지 프레임, 변위값 페이지 맵 테이블 : 디스크 페이지 번호(보조기억 장치 주소), 페이지 프레임 번호, 상태 비트(참조하는 페이지가 주기억장치에 있으면 1, 없으면 0)

가상메모리 : 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법 논리주소(가상주소) : 보조기억장치 상의 주소 물리적주소 : 주기억장치 상의 주소로 물리적 주소 페이징 기법 : OS가 보조기억장치에 있는 프로그램을 동일한 크기의 블록으로 나누어서 관리하는 기법 Demand Paging : 실행 프로그램이 요구할 때 비로소 보조기억장치에서 주기억장치로 적재하는 방법

Paging 을 사용했을때의 장점 Fragmentation을 해결할 수 있다. Swapping 이 용이해진다.(페이지 크기를 디스크 블록 사이즈에 맞춤) Paging 을 사용했을때의 단점 Internal Fragmentation 이 발생하나 효과는 미미함. Segmentation일 때와 마찬가지로 메모리를 접근하기 위해서 실제적으로 2번의 접근이 필요하다 Segmentation과 반대로 페이지 테이블의 크기가 방대해지는 문제가 생긴다. 출처 : http://yimoyimo.tk/Segmentation-and-Paging-1/ Page Table Structure 1. hierarchical paging(계층적 페이징) - 32비트 컴퓨터에선 페이지 테이블은 4MB정도로 크다. - 페이지 테이블을 작은 조각으로 나눈다. 페이지 테이블 자체가 다시 페이지화 되는 것. - 계층이 깊어질수록, 페이지 접근 시간이 늘어나는 치명적인 단점이 있는 방식. - 64비트 컴퓨터의 경우 페이지 크기가 어마어마하게 크다. 너무 많은 메모리 접근을 요구하므로 구현이 불가능하다. 2. hashed page table -주소 공간이 32bit 보다 커지면 사용 - 해시 테이블에 각 항목은 연결리스트를 가지고 있으며, 충돌을 일으켜서 이곳으로 해시되는 원소들이 연결된다. - 각 원소는 가상 페이지번호, 사상되는 페이지 프레임 번호, 연결 리스트 상의 다음 원소 포인터를 가진다. - 알고리즘 : 가상 주소 공간에서 페이지 번호가 오면 그것을 해싱함수에의해 해싱한다 -> 페이지 테이블에서 연결리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교해본다 -> 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리주소를 얻고, 일치하지 않으면 다음 원소로 이동하여 반복. 3. Inverted Page Table - 보통 프로세스 마다 각...

FIFO memory에 올라온 시간이 가장 오래된 page를 victim으로 선정 optimal 하지는 않지만 correctnesss에 영향을 주지는 않음 Belady's anomaly 발생(frame 수는 증가했디만, page fault는 오히려 증가하는 현상) Optimal Page Replacement 가장 오랜기간동안 사용되지 않을 page를 선택 할당된 frame수가 고정일때 가장 낮은 page 부재율을 부장 구현이 어려움(앞으로 process가 메모리를 어떻게 참조할지 알아야 하므로) LRU page Replacement optimal algorithm에 대한 근사 과거를 가까운 미래의 근사치로 본다 가장 오랫동안 사용되지 않은 page를 선택, Belady의 모순현상 없음 단점 : 프로세스가 main memory에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함(오버헤드 발생)

정의 S는 정수값을 가지는 변수이며, 다음과 같이 P와 V라는 명령에 의해서만 접근할 수 있다. (P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다.) P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다. 이때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 다시 말해, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다. 구현하는 방법 방법 1) 최초 제시된 방법은 바쁜 대기(busy waiting)을 이용한 방법이다.  P(S) {      while S <=0; // 아무것도 하지 않음 (반복문)      S--;  }  V(S) {      S++;  } 방법2) 최초 방법의 단점을 보완한 방법으로서 재움 큐를 활용하여 프로세스를 재우는 방식이다.  P(S) {      S--;      if S < 0          // 이 프로세스를 재움 큐에 추가 (잠 듦)  }  V(S) {      S++;      if S <= 0          // 재움 큐로부터 프로세스를 제거 (깨어남)  }

Non-preemptive scheduling :현재 실행중인 프로세스를 다른 프로세스가 선점할 수 없는 cpu 스케줄링 Critical section :process들이 공유변수들을 수정할 수 있는 코드영역

시스템 콜 이란 프로그래밍 언어에서 운영체제(커널)의 서비스를 호출하여 사용하는 것을 말한다.  만약 일반 응용 프로그램이 시스템의 자원을 사용하여 작업을 하려고 한다면 시스템 콜을 사용하여 작업을 한다. 인터럽트 는 프로세서가 프로그램을 실행 도중 하드웨어나 소프트웨어의 문제 때문에 프로그램이 실행되고 있던 순서를 변경하여 좀 더 급한 이벤트를 수행한 후에 원래의 프로그램으로 복귀하여 나머지 프로그램을 수행한다. 인터럽트가 발생하면 현재 위치가 자동으로 인터럽트의 스택에 복귀주소로써 저장되어 인터럽트의 끝에서 복귀 명령을 만나면 다시 복귀주소로 돌아온다.

같은 프로세스 내부에서는 thread들이 code,data,heap 영역을 공유하고 있기 때문에, context switching할때 stack 영역만 교체하면된다 다른 프로세스에 있는 thread들과 context switching 할때는, thread들간에 공유하는 영역이 없기 때문에, 현재 실행중인 process 정보를 메모리에 저장하고 새로운 프로세스를 CPU에 적재하여 실행해야한다.

Paging 가상기억장치를 모두 같은 크기의 페이지 블록으로 편성하여, 각각의 페이지 블록들이 실제 물리 프레임에 맵핑 되도록 구성하는 기법, 논리주소 공간이 한 연속적인 공간에 모여 있어야 하는 제약조건을 없앤다. Paging을 할때 어떻게 실제 메모리 주소에 데이터를 전송하는가? 페이지 번호와 페이지 변위로 구성된 가상주소를 가지고 page table에 접근하여, page 번호와 일치되는 행의 프레임 번호를 찾고 그 위치와 page offset을 더하여 실제 메모리 주소에 접근한다. Page table에 저장되는 항목 page 번호,해당 페이지에 할당된 물리 메모리(프레임)의 시작 주소 Page table이 저장되는 장소  메인메모리 Page table접근 속도 향상시키는 방법 TLB(Transition Look-aside Buffer) 이용 : TLB는 page table entry에 대한 특수한 소형 하드웨어 캐시이다. 만약 페이지 번호가 연관 register TLB에서 찾아지지 않으면 main memory에 있는 page table에서 찾으면 된다. TLB에 저장되는 항목 Page table의 일부를 저장한다

인터럽트 프로그램을 실행하는 도중에 예기치 않은 상황이 발생할 경우, 현재 실행중인 작업을 즉시 중단하고 발생된 상황을 우선 처리한 후 실행중이던 작업으로 복귀하여 계속 처리하는 것 인터럽트의 종류 software interrupt  프로그램내에서 발생, CPU로부터 발생하는 운영오류등을 포함 발생하는 시점이 프로그램의 일정한 지점(동기적) hardware interrupt  하드웨어적으로 프로그램 외부에서 발생, 비동기적(언제 발생할지 모름). CPU외의 다른 장치들에서 발생. 예를들어, 입출력장치, 타이밍장치, 전원 등 외부적인 요인에 의해 발생한다.

logical address(virtual address) CPU가 생성하는 주소, 세그먼트와 세그먼트 offset으로 구성, MMU에 의해서 physical address로 변환됨 Physical address 메모리가 취급하는 주소

정의 : 프로세스 간의 데이터 통신 대표적으로 pipe와 shared memory가 있다.

프로세스와 스레드의 차이점 - 프로세스는 완벽히 독립적이기 때문에 메모리 영역(Code, Data, Heap, Stack)을 다른 프로세스와 공유하지 않는다. -스레드는 해당 스레드를 위한 스택을 생성할 뿐 그 이외의 Code, Data, Heap영역을 공유한다.(stack은 공유하지 않는다) *PCB 프로세스의 현재상태, 프로세스 고유 식별자, 스케줄링 및 프로세스의 우선순위, 주기억장치 관리 정보, 입 출력 상태 정보 등

multithread program 특정 쓰레드에서 에러를 감지할때 다른 쓰레드의 상황을 고려해야 한다 멀티쓰레드의 경우 거기에 다른 쓰레드의 상황또한 테스팅의 요소가 됨 sequential program 시퀀셜의 경우 해당 쓰레드 내의 모든 인풋과 실행경로만 고려

메모리 관리기능을 제대로 수행하는지 test 현재 메모리의 어느 부분이 사용되고, 누가 사용하는 지를 점검하는 기능 test 프로세스에 공간을 할당하고 회수하는 방법이 제대로 돌아가는지 test 프로세스 관리 test 프로세스와 스레드 스케줄링 테스트 프로세스 동기화를 위한 동기화 기법을 제공하는지 test 프로세스 통신을 위한 기법 제공하는지 test deadlock방지 기법제공하는지 test 파일 관리 기능 test 파일 생성과 제거 디렉터리 생성과 삭제 보조기억장치에있는 파일 맵핑 test 기타 시스템 보호, 네트워킹 등을 테스트