yongmin

1. Thread
2. Lock
3. Condition Variable
4. Semaphore
5. Common Concurrency Problems

1. Thread

- 개념

• 독립된 객체로 프로그램 내에서 독립적으로 생성, 실행되어 프로그램 대신 작업 수행
• 하나의 프로세스 안에 thread들은 주소공간을 공유하여 동일한 값에 접근 가능
• 각 thread는 자신의 상태를 나타내는 PC, 레지스터들을 가지고 있으며 문맥교환시 이를 TCB에 저장
• 프로세스와 달리 쓰레드 간의 문맥 교환시 주소 공간을 그대로 사용
• 쓰레드마다 스택이 할당된다

- 쓰레드 장점

1. parallelism : 여러 cpu에 각각 쓰레드를 동작하게 함으로써 프로그램의 성능 향상
2. 멀티 쓰레드를 통해 하나의 프로그램 안에서 I/O 작업과 다른 작업이 중첩되어 프로세스가 blocked 되는 것을 방지

- 멀티쓰레드 문제점

• 쓰레드는 호출자와 별개로 실행되므로 특정한 실행 순서를 가지고 있지 않아서 race condition에서 indeterminate result 발생

- 해결방안

• race condition이 존재하는 critical section에서 하드웨어와 OS의 지원을 통해 synchronization primitive를 구현하여 쓰레드간 mutual exclusion을 보장해야 한다
• 이를 위한 쓰레드 간 시그널 교환 메커니즘을 위해 condition variable를 사용
• lock 기법을 통해 mutual exclusion 구현 가능

2. Lock

- 개념

• 소스 코드의 critical section을 lock으로 설정하여 해당 critical section이 마치 single atomic instruction인 것처럼 실행되도록하는 기법
• lock을 통해 mutual exclusion이 구현되므로 lock을 mutex라고도 부른다
• mutual exclusion : 한 쓰레드가 critical section 내에 있으면 이 쓰레드가 lock을 release 할때까지 다른 쓰레드가 해당 critical section에 들어 올수 없도록 제한 하는 것

- lock 평가 기준

1. mutual exclusion
2. fairness : 모든 쓰레드들이 락 획득에 대해 공정한 기회가 주어지지 않으면 계속 lock을 획득하지 못하는 starvation 발생
3. performance

3. Conditional Variable

- 개념

• 쓰레드간 시그널 교환 메커니즘 구현을 위해 사용된는 일종의 큐 자료구조
• 쓰레드가 계속 진행하기 전에 어떤 조건이 참인지 검사 하는 경우 lock만으로는 병행 프로그램을 제대로 구현할 수 없으므로 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐를 생성
• 다른 쓰레드가 조건을 만족시키고 시그널을 보내면 대기중이던 쓰레드는 깨어나서 작업 진행

4. Semaphore

- 개념

• 정수 값을 갖는 객체
• 세마포어를 락과 컨디션 변수로 모두 사용함으로써 동기화 관련 문제를 한번에 해결
• 세마포어는 초기 값에 의해 락 또는 컨디션 변수로의 동작이 결정됨

5. Common Concurrency Problems

1. Atomicity-Violation Bugs
   • 해결방법 : 락을 추가
2. Order-Violation Bugs
   • 해결방법 : 컨디션  변수를 추가하여 쓰레드의 순서를 지정
3. DeadLock Bug
   • deadlock dependency graph에서 dependency cycle이 존재하는 deadlock 발생 가능성 존재
   • deadlock 발생 조건
     1. circular wait : 각 쓰레드가 다음 쓰레드가 요청한 락을 갖으면서 순환고리 형성
        • 해결방법 : 락 획득의 전체 순서를 정하여 순환대기가 발생하지 않도록 한다
     2. hold-and-wait
        • 해결방법 : 원자적으로 모든 락을 단번에 획득하도록 한다
     3. no preemption
        • 해결방법 : trylock을 이용하여 락 획득 실패시 다시 시도한다
     4. mutual exclusion
        • 상호배제를 없애고 하드웨어 명령어를 사용하여 wait-free 자료구조 구현

1. Address Space
2.  Base-and-Bound
3. Segmentation
4. Paging
5. 물리메모리 크기 극복

1. Address Space

- 정의

• 실행중인 프로세스가 가정하는 선형적인 메모리의 모습. 실제로는 임의의 물리주소에 산재되어 탑재되어 있다
• address space는 실행 프로그램의 모든 메모리 상태를 갖는다 : code, stack, heap

- virtualizing memory, VM, 메모리 가상화

• 프로세스로 하여금 자신이 특정주소의 메모리에 탑재되고 자신만의 address space를 가지고 있다는 환상을 만드는 것
• VM의 목표 1 : transparency -> 프로그램은 메모리가 가상화되었다는 사실을 인지해서는 안된다
• VM의 목표 2 : efficiency -> OS는 가상화가 시간과 공간 측면에서 효율적이도록 해야 한다
• VM의 목표 3 : protection -> OS는 다른 프로세스로부터 프로세스 및 자신을 보호해야한다. 이를 위해 프로세스들을 서로 고립, isolation 시켜야 한다

- address translation, 주소 변환

• "효율적"이고 "유연성"있는 메모리가상화를 구현하기 위한 기법
• 하드웨어는 명령어 반입, 탑재, 저장등의 가상주소정보를 정보가 실제로 존재하는 물리 주소로 변환
• OS는 메모리의 빈 공간과 사용중인 공간을 항상 알고, 메모리 사용을 제어 및 관리
• 주소변환을 통해 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만든다

2. Base-and-Bound ( = dynamic relocation )

- 정의

• address translation 기법을 구현하기 위해 사용되는 기술
• 각 cpu마다 "base register"와 "bound register"라고 불리는 2개의 하드웨어 레지스터를 이용
• OS가 프로그램이 탑재될 물리 메모리 위치를 결정하고 base register를 그 주소로 지정한다. 그러면 프로세스 실행시 프로세스에 의해 생성되는 모든 주소가 프로세서에 의해 다음과 같이 변환 : physical address = virtual address + base
• 프로세스가 생성하는 메모리 참조는 모두 가상주소 이며 하드웨어는 베이스 레지스터의 값을 이 주소에 더하여 물리 주소를 생성한다
• 가상주소에서 물리주소의 변환을 address translation이라고 하며 이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 address space를 이동할 수 있기 때문에 dynamic relocatoin이라고 한다
• 베이스와 바운드 레지스터는 cpu칩 상에 존재하는 하드웨어 구조처럼 주소변환에 도움을 주는 프로세서의 일부를 MMU (메모리 관리 장치)라고 부른다

- H/W support

1. 하드웨어는 processor status word 레지스터의 한 비트로 cpu의 현재 실행 모드 ( kernel mode or user mode)를 나타낸다
2. 하드웨어는 base register와 bound register를 자체적으로 제공하며 프로세스가 생성한 가상주소에 base register값을 더하여 주소를 변환, bound register와 cpu 내부 일부 회로를 사용하여 주소가 유효한지 검사한다
3. 하드웨어는 base register와 bound register 값을 변경하는 명령어를 제공한다
4. cpu는 user program이 bound를 벗어난 주소로 불법적인 메모리 접근을 시도하는 상황에서 예외를 발생시킨다. 

- OS issue

1. 프로세스가 생성될 때, OS는 새로운 주소 공간 할당에 필요한 영역을 찾기위해 free list 자료구조를 검색
2. 프로세스가 종료할 때, OS는 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있도록 한다
3. 운영체제는 프로세스 전환시 base와 bound쌍을 저장/복원해야 하므로 OS가 process를 중단하기로 결정하면 메모리에 존재하는 프로세스 별 자료구조 안에 base register와 bound register 값을 저장한다
4. OS는 예외핸들러 또는 호출될 함수를 제공해야 한다

- base-and-bound 문제점

• address space 전체를 physical memory에 올리는 base-and-bound 방식은 스택과 힙 사이의 빈공간도 physical memory를 차지하므로 메모리 낭비가 심하다.
• address space가 physical memory 보다 큰 경우 프로세스 실행이 불가능하므로 유연성이 없다

3. Segmentation

- 정의

• base-and-bound 문제를 해결하기 위해 고안된 기법
• 주소 공간의 논리적인 segment (코드, 스택, 힙) 마다 base와 bound 쌍이 각각 존재함으로써, OS는 각 segment를 physical memory의 각기 다른 위치에 배치할 수 있다. 

- address translation

• offset : 주소가 참조하는 바이트가 세그먼트 안에서 세그먼트 시작으로부터 몇번째 바이트인지 나타내는 값
• 하드웨어는 가상주소에서 offset을 구하고 여기에 base register값을 더함으로써 실제 physical address를 구한다.
   

- code sharing 

• protection bit : 세그먼트마다 protection bit를 추가하여 세그먼트를 읽기 전용으로 설정할 수 있도록 한다
• 코드세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유함으로써 메모리를 절약할 수 있다
• 각 프로세스는 자신의 전용 코드세그먼트를 사용하고 있다고 생각하지만 OS는 변경 불가능한 메모리 영역을 비밀리에 공유시킴으로써 환상 구현

- external fragmentation, 외부 단편화 문제

• 정의 : 물리메모리에 임의의 위치에 세그먼트들이 할당됨으로써 중간중간에 작은 크기의 free space들이 남게 되고 이는 새로 생성된 세그먼트를 할당하기에 너무 작아 메모리 낭비 발생
• 해결책 1 compact : OS는 현재 실행중인 프로세스를 모두 중단하고 세그먼트들을 물리메모리상에 연속적으로 재배치 하여 하나의 큰 빈공간을 확보 -> 압축비용이 많이 든다
• 해결책 2 free list : free space들을 리스트 형태로 관리하여 메모리할당시 외부단편화를 최소화 하도록 한다

- free list management

• 분할 : 메모리할당 요청이 free space보다 작은 경우 free space를 분할하여 할당한다
• 병합 : 메모리해제된 free space가 다른 free space와 인접하면 하나의 큰 free space로 병합
• free space 마다 그 크기와 다음 free space의 주소값을 가지고 있는 헤더블럭을 유지함으로써 free list 자료구조를 구현

- free space allocation strategies

1. best fit : 요청 크기와 가장 비슷한 메모리를 가지는 free space를 free list에서 검색하여 할당
2. worst fit : free list에서 가장 큰 크기의 free space를 찾아 요청된 크기만큼 할당하여 최대한 큰 free space를 유지
3. first fit : 요청 크기보다 큰 첫번째 free space를 free list에서 찾아 할당하여 빠르게 할당
4. next fit : 마지막으로 할당된 free space 다음부터 요청크기보다 큰 free space를 검색하여 free list의 앞부분에서만 external fragmenation이 발생하는 것을 방지

4. Paging

- 정의

• 메모리를 동일크기의 조각으로 분할하여 공간관리하는 방법
• 프로세스의 주소공간을 논리 세그먼트로 나누는 것이 아니라, 고정크기의 단위로 나눈다. 고정크기단위로 나눈 가상메모리 블럭을 "Page"라고 하고, 같은 단위로 나눈 물리메모리 블럭을 "Page frame"이라고 한다
• address space의 각 가상 page에 대한 물리메모리 위치를 기록하기 위해 OS는 프로세스마다 "Page Table"이라는 자료구조를 유지하고 여기에 address translation 정보를 저장한다. 다른 프로세스를 실행해야 한다면 OS는 해당 프로세스를 위해 또 다른 Page Table이 필요하다.
• 프로세스가 생성한 virtual address의 변환을 위해서는 먼저 가상주소를 VPN (가상페이지번호)과 offset 2개의 구성요소로 분할한다.

- 장점

• 유연성 : paging은 프로세스의 address space가 어떻게 사용되는 지에 상관없이 효율적으로 주소 공간 개념지원 가능
• free space 관리의 단순함 : OS는 물리메모리의 비어있는 page의 free list를 유지하고 프로세스 실행시 리스트의 첫부분에서 부터 해당 크기의 page frame만 선택하면 된다.

- page table

• 정의 : VPN (가상페이지번호)를 PFN (물리페이지번호)으로 mapping 하는데 사용되는 자료구조이다
• 가장 간단한 page table은 linear page table로 vpn을 index로 하는 배열이다
• OS는 vpn으로 배열항목에 접근하여 PTE ( page table entry) 를 검색. PTE에는 PFN 뿐만 아니라 다른 정보를 담고 있는 비트들(valid bit, protection bit, present bit, dirty bit, reference bit)도 존재

- 문제점

1. 성능 저하 : 페이지에 접근하기 위해 페이지 테이블에 먼저 접근 // TLB로 해결
2. 메모리 낭비 : 페이지테이블의 크기가 크면 물리메모리상의 공간 낭비  // multi-level page table로 해결

- TLB, translation-lookaside buffer

• paging의 속도저하 문제 해결을 위해 MMU의 일부인 TLB를 도입
• TLB는 자주 참조되는 가상주소-실주소 변환 정보를 저장하는 "하드웨어 캐시"이다.
• 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 TLB에 있다면 페이지테이블을 참조하지 않고 변환을 빠르게 실행
• TLB는 VPN, PFN, 다른 비트들(valid bit, protection bit, dirty bit, address-space identifier등)로 구성되어 있다
• TLB 히트율은 spatial locality와 temporal locality에 영향을 받는다

- TLB algorithm

1. 가상주소에서 VPN을 추출
2. 해당 VPN이 TLB에 존재하는지 검사
3. 존재하는 경우 : TLB 히트
   1. 해당 페이지에 대한 접근 권한 검사
   2. 접근권한이 있는 경우, 그 정보를 오프셋과 합쳐서 물리주소 구성
   3. 메모리접근
4. 존재하지 않는 경우 : TLB 미스
   1. 하드웨어는 변환정보를 찾기위해 페이지테이블에 접근
   2. 가상메모리가 유효하고 접근 가능한지 검사
   3. 해당 변환정보를 TLB로 읽어들임
   4. TLB가 갱신되면 다시 TLB 검색
   5. TLB 히트

 - Multi-level Page Table

• paging의 메모리낭비 문제 해결을 위해 사용되는 기법
• 페이지테이블을 페이지 크기의 단위로 나눈 다음, 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면 해당 페이지를 할당하지 않는다.
• PDE (page directory entry)로 구성된 page directory는 valid bit(페이지테이블의 각 페이지 할당 여부 정보)와 PFN 정보를 갖고 있다.
• PDI ( page directory index)를 이용하여 PDE address를 알수 있다 : PDE address = PageDIrBase + (PDI * sizeof(PDE))
• PTI (page table index)를 이용하여 PTE address를 알 수 있다 : PTE address = PDE.PFN + (PTI * sizeof(PTE))
• 페이지 디렉토리가 너무 크면, 트리의 단계를 증가하여 메모리공간을 효율적으로 사용할 수 있지만 메모리주소를 구하는 작업비용이 증가한다

- Multi-level Page Table 장단점

• 장점1 : 멀티레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당되므로 메모리를 효율적으로 사용
• 장점2 : 페이지테이블을 페이지 크기로 분할함으로써, 메모리 관리가 용이하고 페이지 테이블을 위한 공간 할당이 유연하다
• 단점1 : 주소변환을 위해 두 번이상의 메모리 로드가 발생( 페이지 디렉터리 접근 + PTE접근)하므로 작업비용 증가
• 단점2 : 페이지 테이블 검색이 복잡해진다

5. 물리메모리 크기 극복

- 물리메모리 한계

• 주소공간이 물리메모리에 탑재되지 못하는 경우 큰 주소공간을 지원하기 위해 OS는 주소 공간중에 현재 필요하지 않는 일부를 보관해 둘 "공간"이 필요.
• 보조기억장치 ( HDD, SSD 등)에서 "공간"을 확보하고 이 공간을 "swap space"라고 한다

- swap space

• 정의 : 디스크에 페이지를 저장할 수 있는 공간
• swap space 의 입출력 단위는 페이지 크기
• OS는 swap psace에 있는 모든 페이지들의 디스크 주소를 기억
• swap spce를 이용하면 시스템에 실제 물리메모리 공간보다 더 많은 공간이 존재하는 것처럼 가정
• swap은 swap space에서 뿐만 아니라 물리페이지에서도 가능

-present bit

• 하드웨어 기반 TLB를 사용하는 시스템은 page swap을 위해 하드웨어는 present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는 표현한다
• 메모리 참조 알고리즘
  1. 프로세스가 가상 메모리 참조
  2. 하드웨어가 가상주소를 물리주소로 변환하기위해 가상주소에서 VPN 추출, TLB에 변환정보가 있는지 검색
  3. TLB 히트
     1.  물리주소를 얻은 후 메모리로 가져옴
  4. TLB 미스
     1. 페이지 테이블의 메모리 주소 파악
     2. PTE항목 추출
     3. PTE가 유효하고(valid bit = 1) 물리메모리에 존재 (present bit = 1)
        
        1. PFN 정보를 추출하고 TLB에 저장
        2. TLB 갱신되면 TLB 재검색
        3. TLB 히트
     4. PTE가 유효하지만(valid bit =1) 물리메모리에 존재 하지 않음 ( present bit = 0)
        1. page fault (물리메모리에 존재하지 않는 페이지 접근) 발생
        2. OS에게 제어권이 넘어가고 OS는 page-fault handler 실행
        3. OS는 디스크에 있는 페이지를 물리메모리로 swap-in 한다
        4. 물리메모리에 공간이 없는 경우, 물리메모리에 있는 페이지중 swap-out될 페이지는 replacement policy에 의해 결정된다
        5. 디스크 I/O가 완료되면 OS는 해당 PTE의 PFN값을 탑재된 페이지의 메모리 위치로 갱신하고 page fault를 발생시킨 명령어를 재실행
        6. TLB 히트

- swap-out이 일어나는 시기

• 물리메모리의 여유공간이 고갈된 후에 교체 알고리즘이 작동하는 것은 비효율적이므로 OS는 항상 일정한 수준의 여유공간을 유지한다
• OS는 HW (high watermark)와 LW ( low watermark)를 설정
• swap demon 이라고 불리는 백그라운드 쓰레드가 여유공간의 크기가 LW보다 작으면 HW에 이를 때까지 페이지 제거 수행하고 완료후 슬립모드로 전환

- replacement policy

• evict될 page는 OS의 replacement policy에 의해 결정됨
• replacement policy 목표1 : 디스크로부터 swap-in 횟수 최소화
• replacement policy 목표2 : 접근할 페이지가 이미 메모리에 존재하는 횟수 최대화
• Optimal replacement policy : 가장 나중에 접근될 페이지를 evcit -> 가장 최적이며 가장적은 미스 발생하지만 미래의 정보는 알수 없으므로 구현 불가능
• Least Recently Used : 가장 오래전에 접근된 페이지를 evict -> 과거의 정보를 활용하므로 구현 가능

- Approximating LRU

• LRU 알고리즘은 구현은 가능하지만 과거의 메모리 참조 정보를 모두 기록하고 시간정보배여을 순차탐색해야 하므로 매우 큰 작업비용을 가진다
• 몇몇 비트(use bit, dirty bit)를 추가하는 하드웨어 지원으로 LRU에 근사하는 저비용 알고리즘 구현 가능
• Clock Algorithm
  • use bit를 추가, 페이지가 참조될 때마다 H/W는 use bit를 1로 설정
  • 페이지들을 노드로 하는 circular list를 구성
  • 페이지 교체시 OS는 현재 clock hand가 가리키는 페이지의 use bit를 검사
  • use bit가 1이면 해당 페이지는 최근에 참조된 페이지 이므로 물리메모리에 그대로 두고( temporal locality) OS가 use bit를 0으로 재설정
  • 다음 페이지를 검사하여 use bit가 0인 페이지를 찾으면 해당 페이지를 evict
• Corbato Algorithm
  • 주기적으로 use bit를 지우고, 교체 페이지를 선택하기 위해 use bit가 1인지 0인지 검사
  • use bit가 0인 페이지를 찾으면 evict
• Enhanced Clock Algorithm
  • dirty bit를 추가하여 페이지의 변경 여부 정보를 저장
  • 교체할 페이지 선택시 use bit와 dirty bit 둘다 고려
  • 페이지가 최근에 수정되어 dirty bit = 1 이면 그 페이지를 swap-out할 때 디스크에 있는 원본 페이지에 수정된 내용을 기록해야 하므로 추가비용 발생, dirty bit = 0 인 페이지는 추가적인 I/O 비용 없음
  • use bit = 0, dirty bit = 0 인 페이지를 먼저 찾고 evict 하고 이를 만족하는 페이지가 없으면 use bit = 0, dirty bit = 1인 페이지를 evict

- Thrashing

• 발생과정
  1. 물리메모리가 요구를 감당할 수 없을만큼 많은 프로세스 실행중이면 많은 페이지폴트 발생
  2. CPU 사용률 감소 
  3. OS는 CPU 사용율 증가를 위해 더 많은 페이지를 물리메모리에 탑재
  4. 페이지폴트가 계속 발생하면서 page-in, page-out 반복
  5. cpu 사용률이 급감하는 thrashing 문제 발생
• 해결방법
  1. admission control : 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지
  2. out-of-memory killer : 과다한 메모리 요청시, 메모리를 요구하는 프로세스를 kill

1. Process
2. Virtualizing CPU
3. Limited Direct Execution
4. Scheduling

1. Process 

- 정의

: 실행 중인 프로그램

- 프로세스 API

: OS가 제공하는 API

a) create : 프로세스 생성

b) destroy : 프로세스 제거

c) wait : 프로세스를 대기 시킴

d) miscellaneous control : 프로세스 재개와 같은 프로세스 제거, 대기 이외의 기능 

e) status : 프로세스 상태 정보를 알아냄

- 프로세스 상태

a) running : 프로세서에서 프로세스 실행중

b) ready : 프로세스는 실행할 준비가 되어 있지만 다른 프로세스가 실행중이므로 대기

c) blocked ; 프로세스의 수행이 중단

2. Virtualizing CPU

-  정의

: time-sharing 기법을 이용하여 하나의 CPU 또는 소규모 CPU 집합을 무한개의 CPU가 존재하는 것처럼 변환하여 동시에 많은 수의 프로그램을 실행시키는 것.

- Direct Execution

: 프로그램을 CPU상에서 직접 실행시키는 것

- Direct Execution의 문제점

a) 제한된 연산 : 프로그램이 운영체제가 원치않는 일을 하지 않는다는 것을 보장할수 없다

b) 프로세스 간 전환 : 프로세스 실행 시, 운영체제는 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환 시킬 수 있는가

3. Limited Direct Execution

- Direct Execution의 2가지 문제 해결

a) kernel mode : 제한된 연산 문제 해결

b) Non-Cooperative Approach : 프로세스 간 전환 문제 해결

- kernel-mode 

• 접근 권한에 따라 user mode 와 kernel mode로 나누어 user mode에서 실행되는 코드를 제한시킨다.
• 사용자 프로세스는 입출력요청을 하는경우 하드웨어가 제공하는 시스템 콜을 호출하고 이를 위해 trap instruction을 실행
• 하드웨어는 프로세스의 레지스터를 커널 스택에 저장하고 kernel mode로 진입
• OS는 사용자 프로세스가 요청한 작업을 처리한다. 작업이 완료되면 return-from-trap instructoin을 실행
• 하드웨어는 커널 스택으로부터 레지스터를 복원하고 kernel mode에서 user mode로 다시 하향 조정
• 사용자 프로그램으로 다시 리턴

- Non-Cooperative Approach

• 수밀리 초마다 timer interrupt를 발생시켜 프로세스를 중단
• 하드웨어는 프로세스의 레지스터를 프로세스 커널스택에 저장하고 부팅시에 미리 구성된 OS의 interrupt handler를 실행
• OS가 제어권을 다시 획득하면 현재 실행중인 프로세스를 계속 실행할 것인지 아니면 다른 프로세스로 전환할 것인지 OS의 Scheduler가 결정
• 프로세스 전환하기로 결정되면 OS는 context switch코드 실행하여 프로세스의 레지스터, PC, 커널 스택포인터 를 해당 프로세스의 구조체에 저장
• 다음 실행될 프로세스의 구조체에서 레지스터, PC, 커널 스택포인터를 복원하고 다음 프로세스의 커널스택으로 전환
• 하드웨어는 전환된 프로세스의 커널스택에서 레지스터 복원 하고 user mode로 하향조정 및 PC로 분기

4. Scheduling

- FIFO, First In First Out

• 먼저 도착한 순서대로 job을 스케쥴링
• convoy effect : 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로스세의 종료를 기다림

- SJF, Shortest Job First

• 동시에 도착한 작업들중 job이 짧은 순서대로 스케쥴링
• convoy effect 발생

- STCF, Shortest Time-To-Completion First

• 새로운 job이 시스템에 도착하면 스케쥴러는 남아 있는 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행시간을 가진 작업을 스케쥴링
• convoy effect 해결
• response time 측면에서는 효과적이지 못함

- Round-Robin

• time slice동안 실행한 후 실행 큐의 다음 작업으로 전환
• time slice는 timer-interrupt의 N배수
• time slice가 짧을수록 response time 측면에서 성능은 좋아지지만 context-switch 비용이 증가

- Overlap

• 프로세스가 입출력 작업을 요청하는 경우 입출력이 완료될때까지 cpu를 사용하지 않으며 blocked 상태가 된다
• 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄링하여 연산을 overlap, 중첩 시킨다

- MLFQ, multi-level feedback queue

• rule 1 : priority (A) > priority(B) 이면 프로세스 A 실행
• rule 2 : priority (A) = priority(B) 이면 프로세스 A와 B는 Round-Robin 방식으로 실행
• rule 3 : 작업이 시스템에 들어가면 최상위 큐에 배치
• rule 4 : cpu 양도 횟수에 상관없이 time slice를 전부 소진하면 priority 강등 -> cpu를 독점하는 악성 프로세스 방지
• rule 5 : 일정 주기가 지나면, 시스템의 모든 작업을 최상위 큐로 이동 -> starvation 문제 방지

1. System Software
2. Operating System

1. System Software

- 정의

: 시스템 전체를 작동시키는 프로그램, 프로그램을 주기억장치에 적재시키거나 인터럽트 관리, 언어 번역 등의 기능 수행한다. 운영체지는 대표적인 시스템 프로그램.

- 시스템 소프트웨어 구성

a) control program, 제어 프로그램

: 시스템 전체의 작동 상태 감시, 작업의 순서 지정, 작업에 사용되는 데이터 및 자원 관리등의 기능 수행

b) processing program, 처리 프로그램

: 제어 프로그램의 지시를 받아 사용자가 요구한 문제를 해결하기 위한 프로그램

2. Operating System

- 정의

: 사용자와 하드웨어간 인터페이스로써 시스템을 사용하기 편리하고 정확하고 올바른 동작을 실행시킬 수 있도록 환경을 제공하는 시스템 소프트웨어.

- 운영체제 기능

a) 가상화 지원 -> 효율적 자원 관리

b) 병행성 지원 -> 작업 처리능력 향상

c) 영속성 지원 -> 파일 및 정보를 디스크에 안전하고 효율적으로 저장