Operating Systems & Networks v4

90 pt · 45 OS / 45 Net · 90 min reported · 1 side A4
rule/method → visible state/substitution → intermediate + unit → boxed result → invariant★ SS23/highest evidence · ◇ slide/worksheet safety net, still IN

★ Architecture · Q1 + Sheets 1–2

VN: shared instruction/data path bottleneck; Harvard splits paths (often split L1 I/D). cycle:
fetch→decode→operands→execute
→write/PC.

near CPU=faster, smaller, costlier/bit; storage=large+persistent. Tcycle=1/f; DDR base=data-rate/2; row miss≈(tRP+tRCD+CL)/fRAM.

5.7GHz→.175ns; DDR5-5600 base2.8GHz; 112cy→40ns; ≈228×

◇ OS evolution · VM

batch groups jobs; spooling disk-queues slow I/O; multiprogramming runs another job during I/O; timesharing adds interactive preemptive quanta.

Type1 hypervisor directly on hardware; Type2 as host-OS app. VM: matching CPU image→vCPU/RAM/disk→attach ISO→install/eject→verify uname -m; lsb_release -a.

★ Privilege, calls, interrupts · Q1

user=restricted/isolation; kernel=privileged hardware+all memory. syscall: wrapper+args→trap→validate/dispatch
→result→return.

interrupt: device/timer→save→top-half ACK→defer bottom-half→restore/schedule. mode switch ≠ necessarily process switch.

context: regs PC/SP, page tables/address space, FDs, sched/credentials.

◇ Process state · IPC · sync

created→ready⇄running→terminated; running→blocked→ready

create boot/fork/user/job; end normal/error/fatal/killed. signal=small async event; pipe=1-way byte stream; shared memory=fast local + must sync; socket=local/remote endpoint.

race=result depends on interleaving; guard critical section with mutex/semaphore; write invariant “≤1 writer”.

★ Scheduling · Q4 + Sheet 4

FCFS earliest nonpreemptive. SPN shortest ready burst nonpreemptive. SRTN preempts for smaller remaining. RR run min(q,rem); arrivals enter; unfinished→tail.

priority lecture: larger=higher; equal RR; starvation→aging. CFS chooses smallest weighted virtual runtime.

RRq2 A0-2 B2-4 C4-6 A6-8 D8-10 B10-11 C11-13 A13-14 D14-16 C16-18 D18-20 C20-22

trace time|run|ready|remaining; check Σbursts=busy time.

★ Shell/script · Q2 + Sheets 3/8

date -d 'next Monday' '+…%d.%m.%Y %H:%M:%S…'; export STUDENT_ID=…; exit 0 success; nonzero error; read $? immediately.

curl -sL URL | grep -o 'Frankenstein' | wc -l. parse→expand→redirect→execute. Function args $1…; quote "$1".

if ((n<=…)); then … elif …; fi; for i in {1..10}; do …; done; while equivalent; ((sum+=n)).

★ Files/permissions · Q2 + Sheet 5

absolute iff leading /. everything-file = FD + open/read/write interface, e.g. /dev/null. r4 w2 x1; choose ONE u/g/o triad.

dir r=list, x=traverse, w+x=create/delete. mkfile nonstandard. sudo echo x >f redirects as shell; use echo x|sudo tee f.

sed 's/sucks/rocks/g' linux.txt. package: sudo apt update; sudo apt install vim htop.

◇ Links · users/groups · mount

hard link=same inode, same FS, survives deletion of one name; symlink=own inode storing path, cross-FS, may dangle.

format creates FS metadata; mount grafts FS root at directory. shared directory often chgrp G d; chmod 2770 d (setgid inherits group). verify id; getent group G; ls -ld.

globbing expands patterns; alias substitutes command text.

◇ Filesystem/storage · Sheet 6

dir entry name→inode; inode=attrs+block pointers; superblock=FS-wide metadata/root. cold path SB→root inode→dir blocks/inodes→target inode.

contiguous fast/random but growth+external frag; linked easy growth/slow random; indexed random access+pointer cost. free list simple; bitmap 1bit/block+run search. LBA=linear logical block id.

blocks=ceil(size/block); waste=blocks·block−size
HDD=Σ(seek+rotation)+bytes/rate
SSD=#requests·latency+bytes/rate

bitmap: number bits+owner row; allocate lowest 0s; delete owner bits only. journaling log-before-commit→recovery, not zero loss.

★ Memory · Q3 + Sheets 7–8

EAT=t1+Pm1(t2+Pm2(t3+…)); conditional miss rates multiply. fit: first restart; next cursor; best smallest; worst largest; update remainder.

SS23 holes 7,23,12,8; P15,4,5,3,8→B,A,B,A,C; left0,3,4,8

valid iff 0≤VA<limit; PA=base+VA. 4KiB→12-bit/3-hex offset; check present then permission; PA=frame||offset.

FIFO oldest load; LRU oldest last-use; NFU stale; aging c=(c>>1)|(R<<MSB); OPT farthest future; clock clear R=1/evict first R=0.

seq0172327103, 4 frames: FIFO 6 faults; LRU 7

EAT branches mutually exclusive Σp=1; 1ms=10⁶ns. TLB miss ≠ page fault.

◇ Relocation · address-space layout

static relocation fixes at load; dynamic MMU base+limit per access. paging pages→frames; TLB cache; valid nonresident page→fault.

low: text|data|BSS|heap↑ … mapped/shared … stack↓ :high

heap dynamic objects; stack calls/params/locals/return state.

◇ Network types/devices

PAN person; LAN site; MAN city; WAN region. repeater L1 regenerate; hub L1 floods bits; bridge/switch L2 MAC frames; router L3 IP between subnets.

draw hosts inside subnet clouds, switch inside one subnet, router between clouds. loss=(sent−delivered)/sent; KPI: low delay/loss/jitter, high throughput.

◇ Switching · Sheets 9–10

circuit dedicated capacity/setup/predictable; packet shares link/stat mux/bursty but queues. multiplexing combines flows.

250MB@100Mbit/s=20s; circuit whole-file starts 0,T,2T; shared 3-flow RR kth mean finish=(3k−1)tpacket

dprop=d/v; dtrans=L/B; RTT=2·one-way
BDP=B·RTT (NEVER ×2); complete pkts=floor(B·RTT/Lbits)
TP=D/(RTT+D/B); jitter_course=Σ|xi−x̄|/n

SS23 RTT4.5ms; 50MB=400Mbit; T=.4045s; TP=988.9Mbit/s

bandwidth gain vanishes if RTT≫D/B; “any case”→worst RTT. VoIP prefer predictable low jitter then mean.

★ Graph/topology · Q5 + Sheet 11

degree=#incident; density=2E/[n(n−1)]; diameter=max shortest path; connectivity=min removals.

star center/failure; ring degree2; clique E=n(n−1)/2 robust+costly; tree hierarchical/scalable+upper failure. assess path, reliability, cost, scale.

fat tree V20 E32 diam4 conn2 nonregular; C(n)=30000+5400n
3×3 torus n9 degree4 diam2 conn4 regular

Internet: access→regional/tier2→tier1 autonomous systems; transit/peering/backbone.

★ Service models · OSI · Q7

one-way; request↔response; notification push. client/server centralized service; P2P peers request+serve. connection-oriented=setup/state/close; reliable=ACK/order/retransmit/correct.

7 App user proto ·6 Pres format/crypto ·5 Sess dialog ·4 Trans ports/reliability ·3 Net IP/route ·2 Link frame/MAC ·1 Phys signal

TCP/IP: App=OSI5–7; Transport4; Internet3; Link1–2. LLC multiplexes upper protocols; MAC medium access/address. data→TCP/UDP→IP→Ethernet→signal.

flow control protects receiver/window; congestion control protects network.

◇ Physical/link · Sheet 12

sync=shared bit timing; duplex=both directions; full duplex simultaneous. differential cancels common noise: (S+n)−(S̄+n)=S−S̄.

00101111: NRZ L L H L H H H H; Manchester lecture 0=LH,1=HL; 4B/5B 0010→10100,1111→11101.

PAM encodes amplitudes. Ethernet II: preamble/SFD | dst MAC | src MAC | EtherType | payload | FCS. MAC OUI=first 24 bits.

★ IPv4/subnet · Q8 + Sheet 13

h=32−p; usable=2^h−2; block=256−mask_octet
net=floor(IP/block)·block; bcast=net+block−1

caps /28 14 /27 30 /26 62 /25 126 /24 254 /23 510 /22 1022 /21 2046 /20 4094.

VLSM largest first; smallest h with 2^h−2≥need; next=prev bcast+1 aligned. DF forbid fragmentation; MF more follows. no-options IPv4 hdr20B; payload=MTU−20; Proto ICMP1/TCP6/UDP17.

172.16.145.78/22→net .144.0, bcast .147.255

★ Routing/ICMP/NAT · Q8 + Sheet 14

LPM: list matches (IP&mask)==net; largest / wins; /0 fallback. direct nets belong in table. traceroute TTL=1,2,…; expired router→ICMP Time Exceeded.

32.20/16→207.10.100.9; 32/8→.8; 48/8→128.1.0.10; /0→128.1.0.11

reverse-binary /22 rev10 offsets 0,512,256,768,128,640,384; then smallest fitting prefix.

PMTUD DF too-big→drop+ICMP Frag Needed→shrink. NAT table privateIP:port↔publicIP:port; breaks simple inbound/end-to-end.

◇ IPv6

V4|TC8|Flow20|PayloadLen16
|Next8|Hop8
Src128|Dst128; fixed40B
Next bits[48,55]

remove IHL/header-check/router fragmentation; options→extensions; TTL→Hop; Protocol→Next; addresses32→128.

★ Header-field method · Q8

start=Σ earlier widths; [start,start+w−1]. Answer field = name + width/location + purpose.

IPv4: V/IHL/DS/Len/ID/flags+frag/TTL/proto/check/src/dst. ICMP: type/code/check. UDP: sport/dport/len/check. TCP: ports/seq/ack/off/flags/win/check/urgent. DHCP: op/xid/flags/ci/yi/si/gi/chaddr/options.

TCP flags104..111: C E U A P R S F ⇒ SYN110

★ UDP/TCP/window · Q8

UDP connectionless message datagrams; no builtin order/reliability/flow/congestion. TCP connected reliable ordered byte stream + flow/congestion.

SYN x→SYN+ACK y,ack x+1→ACK ack y+1

ACK=next byte expected; SYN/FIN consume1. window left=ACK; right=left+rwnd−1; usable=rwnd−inflight; cumulative ACK.

FIN x→ACK x+1; peer FIN y→ACK y+1; active closer TIME_WAIT.

★ DNS/DHCP/apps

FQDN host/subdomain.second-level.TLD.root. records: A v4; AAAA v6; CNAME alias; MX mail; NS authority; PTR reverse.

IPv4 reverse: reverse octets + in-addr.arpa. resolver miss→root→TLD→authoritative→cache TTL; resolver recursive to client, upstream referrals iterative.

DHCP DORA Discover→Offer→Request→Ack; xid/chaddr correlate; ACK options lease/mask/router/DNS. socket=software endpoint IP+port.

fx-991CW + final checks

HOME→Base-N (starts Dec; cycle Dec/Hex/Bin/Oct). HOME→Statistics→1-Variable→1-Var Results gives x̄; course MAD hand-calc abs deviations.

  • all subpart labels?
  • rule + state/substitution + intermediate?
  • bytes×8; ms×10⁻³; probability Σ=1?
  • queue only arrived unfinished?
  • network aligned; LPM not first match?
  • box value+unit; state assumption/check?