bluebrown

운영체제 시험 노트 배껴서 간단히 올린다. 나중에 혹시라고 검색하고 싶은 거 있는데, 분명 이 노트들 다 버렸을 테고 처음부터 책 뒤져가면서 배우기 귀찮을 때, 여기서 보고 감이라도 잡기를 바라는 마음에서 남기는 것. 혹시라도 다른 사람이 이걸 보고 자신의 기억을 되짚어볼 수 있다면 역시 환영이고. pre를 써서 창 바깥쪽으로 삐져나가 보이지 않는 부분이 많을 테니 그냥 긁어붙이기 해서 메모장에서 보길.

Thread Implementations

one level model: too much system calls
two level model, one kernel thread: if one blocks the kernel, everyone blocks
two level model, multiple kernel threads:
	1) not enough kernel threads: deadlock -> create a new thread, # of active thread < # of processors -> pthread_setconcurrency
	2) too much kernel threads: too much system call for blocking/releasing idle kernel threads

scheduler activation model: no kernel thread at all. assigns processors to user schedulers.
variable weight process: one thread per process, clone/fork

Scheduling

simple batch: FIFO/SJF/SRTN
multiprogrammed batch
time sharing: round robin queue/multi-level feedback queue
partitioned servers: lottery scheduling
real-time: soft/hard, earliest deadline first/rate monotonic scheduling: thread with priority 1/pi

coverage wait time – SJF
throughput: jobs/hour
priority inversion/priority inheritance

Virtual Memory

paging: |page# size a|offset size b|, 2^a page table entries, 2^b page size
segment paging/forward-mapped page tables
translation lookaside buffer (TLB) 
linear page table
hashed page table, inverted page table

fetch policy: prepaging
replacement policy: FIFO, LRU, LFU, clock algorithm
placement policy: 
global collection: 부익부빈익빈
local allocation: thrashing

vfork: do not modify a page, share
fork: lazy evaluation, read-only pages

private map / shared map (mmap)

backing up pages
	read-only pages (e.g. text): do not back up
	modified read-write pages – shared: save to the original file
	modified read-write pages – private: save to the swap space
	anonymous memory (e.g. bbs, stack): save to the swap space

swap policy
	conservative: redundant backing store
	liberal: page out might fail, lazy evaluation

File Systems

hard disk: seek time, rotational delay, transfer time, head skewing, cylinder skewing

FFS
	large block size: seek time & rotational delay decrease, internal fragmentation
	cylinder group: seek time decreases
	interleaving blocks: rotational delay decreases

write-efficient: log-structured file systems
consistency preserving: soft update/journaling(metadata/everything)/shadow paging
striping
large striping unit: high consistency factor, seek & rotational delay decrease
small striping unit: high parallelism, transfer delay decreases

RAID1: pure mirroring
RAID2: error correcting code 10/4
RAID3: parity bits
RAID4: parity blocks: the check disk is a bottleneck, good for expansion, WAFL & ZFS no small writes
RAID5: rotational parity blocks: good for lots of small writes, Ext3 & NTFS
RAIDZ: small writes are handled efficiently; block bounding info is in the metadata

WAFL: shadow paging/log-structured writes/consistency points with non-volatile RAM/snapshots

Security

one-way function
dictionary attack
salt
trusted path (ctrl-alt-delete)
access matrix, access control lists (ACL), protection domain, capability
discretionary & mandatory access control
trap doors/Trojan horses/viruses and worms/buffer overflow attack

Communication Protocols

circuit switching vs. packet switching
ISO OSI ref. model vs. internet architecture
internet address, subnetting, classess internet domain routing
UDP & TCP

initial sequence number (ISN generator, IP spoffing)
1) receive window ||acknowledged data|ok to receive||ignore
2) send window ||sent but unacknowledged data|ok to send||

congestion control, retransmission timeout perioud (RTO)
slow start (exponential), add. increase mult. decrease (AIMD)
fast retransmit and recovery: triple cummulative ack. half congestion window size

Remote Procedure Call Protocols

stab procedure
interface definition language
marshall and unmarshall: an array, a pointer, caller and callee, data structure, aliasing
idempotent / non-idempotent -> transmission ID

Distributed File Systems

data state, attribute state, open-file state
NFS2:
	file protocol:
		file handler, open-file state is not kept in the server
		recovery client: server is stateless, no effect
		recovery server: hard link (clients retry till he gets response) / soft link (timeout error)
	mount protocol:
	network lock manager (NLM) protocol:
		recovery client: request lock
		recovery server: notify, get reclaims during a grace period

opportunistic locking
	client must request only level 1 lock
	server may give level 2 lock instead

Authentication in Distributed Systems

authentication: message, verifier, credentials
symmetric crypto system
	replay -> include time info
	data integrity -> message authentication code (MAC)
	Kerberos: preauthentication, autentication server & ticket granting server
asymmetric crypto system
	plain text attack & men in the middle attack
	secret message: public key write, private key read
	digital signature: public key read, private key write, with time stamp
	certificates: public key distribution CA
hybrid schemes: SSL

Time

UUID
network time protocol
optimistic concurrency control
	last-read, last-write timestamps
	when writing, if its time is less than last-read or last-write, there’s a problem