중간고사 정리

Cache Design

• Direct Mapped
  • tag 하나당 하나의 Block만 들어갈 수 있다.
  • 자주 사용하는 여러 Line이 같은 위치로 mapping 된다면 계속 miss가 발생하면서 Block이 교체되고 이는 miss rate의 증가를 일으켜 성능을 떨어뜨린다.
• 2-way Set associative
  • 2개의 Block을 묶어서 하나의 Set으로 구성.
  • cache에서 데이터를 찾을 때 tag를 따라 간 후 2개의 Block 모두 확인해야 한다. 비교기를 2개 두어서 parallel 하게 비교하여 cache 저장할 때 속도가 느려지지 않고 편리하지만 값을 찾을 때 비용이 늘어난다.
• associativity가 증가할수록 구현하는데 돈이 더 많이 들고 빠르게 만들기 어려워짐.
  • mapping 함수가 flexible 할수록, 주어진 block이 cache 안에 있는지 확인하는데 필요한 회로를 만들기 더 복잡해짐.
• cache size
  • 커질수록 hit rate도 증가.
  • 하지만 큰 메모리를 빠르게 작동하게 만들기 어려워짐.
• block size
  • 처음에는 증가할수록 hit ratio도 증가.
  • block size가 커진다고 성능이 무조건 좋아지는 건 아님.
• C = Set * Assoc * Block

---

Cache Write

Only Write

• Target 주소에 해당하는 cache만 update한다.
• Memory access를 하지 않으므로 속도가 빠르다.
• 하지만, memory와 cache 사이에서 inconsistency가 발생한다는 치명적인 단점이 있다.

Write-Through

• Cache와 원본인 memory를 동시에 update해 동시성(consistency)을 보장한다.
• 하지만, memory에 access를 해야하므로 속도가 느려진다는 단점이 있다.
• Write buffer 방법을 사용하면 보완 가능하다!
  • Cache와 memory와 독립적으로 운용되는 buffer를 외부에 둔다.
  • Cache를 update한 뒤, memory에 access 하지 말고 buffer에 주소와 데이터를 저장해둔다.
  • CPU는 그 이후로는 전혀 신경쓰지않고 계속 연산을 수행한다. Buffer는 독자적으로 움직이며 느린 속도로 memory를 update해서 consistency를 보장한다.
• 하지만 Write buffer 방법도 연속해서 같은 주소를 참조하는 연산이 있는 경우에는 consistency를 보장할 수 없다는 단점이 있다.

Write-Back

• Cache를 update하고, valid (dirty) bit를 1로 만들어서 “이 데이터는 memory랑 다름”을 표시한다.
• 이후, 해당 cache 영역을 다른 데이터로 교체할 때 해당 bit를 확인해서 enable 여부에 따라 memory를 update 해준다.

---

I/O

IO Controller

• CPU와 IO device를 이어주는 interface 역할.
• data, status, command 3가지의 register, IO port 라고도 함.

IO Address Space

• IO device와 통신하기 위한 주소.
• Port mapped
  • memory와 완전 별도의 공간을 가져 메모리 공간을 아낄 수 있다는 장점.
  • 별도의 instruction을 필요로 하는 단점 (x86에서 in, out).
• Memory mapped
  • memory와 같은 공간을 사용하는 단점.
  • 별도의 instruction 없이 (load, store 같은 메모리 instruction 그대로 사용) 구현 가능한 장점.

Programmed(Polling) IO and Interrupt-Driven IO

DMA

• HDD 같이 block 단위로 큰 데이터를 업데이트 하는 경우 CPU를 우회하고 데이터를 IO와 memory 사이에서 직접적으로 전달함.
• DMA controller가 IO controller에 통합돼있는 경우도 있음.
• 순서
  1. CPU가 DMA에게 command block을 게시.
  2. HDD가 DMA controller를 통해 memory에 데이터 전달.
  3. DMA controller가 데이터를 카운팅 하다가 0이 되면 CPU에게 interrupt 하여 report.

---

Symmetric Multiprocessors

• 2개 이상의 비슷한 processor들이 memory와 IO 기능을 공유하고 bus로 서로 연결된 형태를 띔.
• IO devices를 공유하고 같은 기능을 함.

Advanced PIC

• 외부 인터럽트 컨트롤러.
  • interrupt signal을 interrupt vector로 바꿔줌.
• SMP에서 APIC을 적용하기 위해 Local APIC 필요.
  • APIC이 CPU를 선택.
  • 그에 상응하는 local APIC에 signal 전달.

---

OS의 역할

• 컴퓨터와 유저의 인터페이스
  • 프로그래머에게 시스템을 사용하는데 편리한 인터페이스를 제공.
  • 응용프로그램 실행 제어.
  • 프로그램 생성 보조, 파일 관리, IO 장치 제어.
• 시스템 자원 관리자

---

OS의 진화하는 능력

• 새로운 하드웨어, 서비스의 등장, 문제점 수정.
• 원래 OS 기능이었던 것이 하드웨어로 기능 이전.

Serial Processing

• 사람이 수동으로 job card를 load하고 프로그램을 실행함.
• 사람이 OS 역할을 함.
• 모든 활동이 순서대로 일어남.
• 프로그래머가 컴퓨터 하드웨어와 직접적으로 상호작용.
• 문제점
  1. 비싼 자원의 비효율적인 사용.
  2. 다른 job으로 변경하는데 시간이 많이 걸림 (긴 setup time).

Simple Batch System

• CPU utilization을 높이고자 (setup time 줄이기) 비슷한 job끼리 묶어서 처리.
• 자동 job sequencing.
• Batch Monitor: 첫 Batch OS, 메인 메모리에 상주.
• 필요한 기능의 등장:
  • 메모리 보호: Monitor(OS) 영역 보호.
  • I/O 보호: OS를 통해서만 I/O 접근.
  • 커널/유저 모드 분리: OS 메모리 영역 보호.
  • CPU 독점 방지: 시스템 타이머 사용.
  • Interrupt: Busy waiting 문제 해결.
• 문제점: 느린 I/O 때문에 CPU가 idle한 시간이 여전히 김.

Multiprogrammed Batch System

• CPU 사용을 늘리고 여러 job들을 동시에 올려서 실행 (scheduling).
• multi-programming degree: 동시에 실행하는 job의 개수.
• 필요한 기능: relocation, memory protection, MMU.

Time Sharing

• 컴퓨터는 싸지고 인간은 비싸지면서, 인간의 생산성을 늘릴 필요 생김. 따라서 response time을 최소화 해야할 필요 생김.

---

Process & System Call

Process

• 어떤 job이 다른 job에 의해 preemption 되면 다음에 다시 실행할 때 현재의 정보를 다시 불러와야 작업 가능.
• 이때 저장되는 process 정보를 execution context라고 함.
• process는 다음 3가지 요소로 구성됨:
  1. Program
  2. Associated data
  3. Execution context

Synchronization

• Race Condition 문제 생김.
• DeadLock 문제 생김.

Resource Protection

• UNIX에서는 dual mode를 통해서 해결.
• kernel 모드: 모든 op code 실행 가능.
• user 모드: privileged instruction 실행 불가.
• user program은 system call하여 privileged instruction 실행.
• system call을 직접 사용하기보다는 잘 정의된 library(API) 사용 (POSIX, Win32, Java…).

SystemCall의 목적

• 시스템 자원 보호.
• 안정적인 프로그램 동작 보장.
• 보안 (malware로부터 시스템 보호).

OS에 parameter를 넘기는 방법

• register로 넘기기.
• Parameter 블록의 주소를 register에 저장하는 방식.
• stack에 push하고 OS가 pop하는 방식.

---

Process란

• 실행중인 program.
• processor에 할당되고 실행될 수 있는 entity.
• 일련의 instruction의 실행, 현재 상태, 그리고 시스템 자원이라는 특징을 갖는 활동의 단위.
• task는 자원 할당의 단위, thread는 실행 단위로 구분하기도 함.

Execution Sequence & Stack

• call stack: procedure call과 parameter를 추적하기 위해 사용되는 stack.
• Stack pointer: 현재 stack top 가리킴.
• Stack frame: 함수가 호출될 때 생성되는 공간. 지역 변수, 매개변수 저장.

PCB (Process Control Block)

• OS에 의해서 제어되고 관리되는 정보들의 집합.
• Process 1개당 1개씩 존재.
• 목적: 현재 실행중인 프로세스를 인터럽트하고 나중에 재개할 때 다시 이전 상태를 복구하고 실행하기 위해 필요.
• PC, Processor register, PID, condition code, PSW 등.

Process Image

1. Program
2. Data (bss and initialized)
3. Stack (procedure 단위)
4. PCB

Process Switch는 언제 발생?

• timer interrupt(time out), system call, io request, exception 발생 시.
• mode switch가 process switch 보다 더 빈번하게 발생.

State Model

• 2 state model 문제점: io를 wait 하고 있으면 run 상태를 줘도 실행이 불가능하므로 blocked 상태 필요.
• 7 state model: process를 memory에서 disk의 swap area로 swap. lower priority의 process를 suspend.

Kernel Stack

• process가 kernel mode일 때 procedure call, return을 관리하기 위해 사용됨.
• 그래서 process는 user stack과 kernel stack 2개 필요.

Process Creation

• cloning(fork)
  • call once, return twice.
  • code, data, stack, pcb를 복사하고 pid만 바꾸어 child process clone.
  • fork() 시 child는 0, parent는 child의 pid를 return.
  • code는 공유하지만, pcb, stack, data는 별도로 존재.
• Copy On Write(COW)
  • 효율적인 프로세스 생성을 위해 fork 후 child process를 위한 데이터들을 바로 copy하는게 아니라 memory에 write할 때 copy를 함.
• fork-exec
  • process의 변신, pid는 안바뀜, code만 바뀜.
  • call once, never return.
  • 새 code와 data를 load.
• Zombie and Reaping
  • process 종료 시 부모가 자식의 exit code를 reap해야 비로소 종료됨.
  • reap 하기 전까지의 child process 상태를 zombie라고 함.
  • zombie가 누적되면 memory leak 발생.
• orphan
  • 부모가 먼저 종료되면 orphaned child는 init process가 reap함.

---

Scheduling

Scheduling Criteria

• System
  • Throughput: 단위 시간당 완료된 프로세스 수
  • Processor utilization: 프로세서가 busy한 시간의 비율
  • Fairness: process들이 공평하게 다뤄지는지
• User
  • Turnaround time: complete time - arrived time
  • Response time: begin time - arrived time
  • Deadline: Real-time에서 중요.

VRR

• RR은 여전히 Long process에 유리하니 short process에 advantage를 주자.
• IO 때문에 다 쓰지 못한 time quantum을 마저 쓸 수 있게 Aux queue를 둬서 ready queue보다 우선순위를 높게 두자.

Multi-level Feedback Q

• process가 queue 간에 이동할 수 있게 한다.
• CPU burst 길이에 따라 process들을 나눔.
• 우선순위 높은 queue 부터 실행.
• time slice 다 쓰면 lower priority queue로 demote.
• waiting time 늘어나면 다시 promote.

---

기타 Q&A

인터럽트 처리 과정 설명

1. 프로세스 실행 중 인터럽트 발생.
2. 현재 프로세스의 실행 중단.
3. 현재 수행 중이었던 프로세스의 상태를 해당 프로세스의 PCB에 저장.
4. 발생한 인터럽트의 번호를 IDT에서 확인하여 해당하는 함수를 호출.
5. 실행이 중단되었던 프로세스의 PCB를 불러와 CPU 레지스터에 초기화하여 프로세스를 다시 수행.

인터럽트를 처리하는 동안 인터럽트를 금지시키는 방법의 문제점과 해결 방법

• 우선순위가 더 높은 인터럽트를 처리하지 못한다. 인터럽트를 실행 중이라도 우선순위가 더 높은 인터럽트가 발생한다면 중첩하여 처리할 수 있도록 한다.

멀티 프로세서 스케줄링 중 Multi-Q 방식의 장점과 문제점, 해결 방법

• IO-bound의 short CPU burst process를 우대하는 queue에 두어 system utilization이 좋다. 하지만 long CPU burst process가 starvation을 겪을 수도 있다는 문제가 있는데, 이를 해결하기 위해 waiting time이 긴 process를 promote하여 해결할 수 있다.