UNIVERSITY OF CALIFORNIACollege of EngineeringDepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 162 Prof. Alan J. SmithApproximate Lecture ScheduleThis outline is approximate,astocoverage and timing.Lecture Topics1introduction, processes, multiprogramming.2EIT,scheduler,CPU scheduling system model, CPU scheduling, goals.3CPU scheduling, metrics, constraints, open vs. closed systems, user characteristics, jobcharacteristics, FIFO, round robin, little’sformula, CPU Scheduling: SJF,SPT,SRPT,FB,MLFB, Exponential queue,4CPU scheduling: fair share scheduler,countermeasures. Discrete ev e nt simulation. Coop-erating processes, atomic operations, critical sections, too much milk problem. Synchro-nization with semaphores.5Synchronization: producers and consumers, readers and writers, dining philosophers.6Threads. Synchronization with Condition Variables. Unix implementation. Monitors.Semaphore implementation, disabling interrupts.7Deadlock, deadlock prevention. deadlock avoidance, banker’salgorithm, recovery,roll-back. Unix file locking.8Linkers and loaders. Dynamic storage allocation: stacks, heaps, fragmention, (exter-nal/internal)first fit, best fit, next fit, bit map, reference counts, garbage collection, buddysystem.9Memory management - flat memory,relocation (static, dynamic), base and bounds, swap-ping.10 Multiple variable length segments, address translation, processes vs. threads, managingsegments, paging (intro)11 Paging: translation, PTBR, pros/cons, page tables, page table implementation, wired downpages, paging and segmentation combined, sharing, paging vs. segmentation.-2-12 Paging: copyonwrite, address space communication, I/O in paging system, sharing, 370implementation, VAX implementation, TLB, principle of locality,translator.13 Demand paging, principle of locality,page faults. paging fetch algorithms, page replace-ment algorithms (RAND, FIFO, LRU, MIN/OPT), real vs. virtual time.14 Evaluation of paging algorithms, stack algorithms. implementing LRU, clock algorithm,local vs. global replacement.15 Thrashing, working sets. page fault frequency, page size, I/O and paging, trace drivensim-ulation, modifying code to minimize paging, algorithm comparison.16 I/O device characteristics and device management.17 I/O device characteristics and device management.18 File and I/O systems - disk management, file allocation, contiguous allocation, linked files,multilevelindexedfile, simple indexedfile, dynamic optimized allocation (Demos), freeblock list.19 I/O optimization: block size, disk arm sked (fcfs, sstf, scan, cscan), rotational scheduling,skip sector allocation, track offset for head switching, file placement, disk caching,prefetching, data replication, ALIS, RAID.20 File descriptor,tree structured directories, links, symbolic links, root, tree structured direc-tories, working directory,operations on files, file backup and recovery.21 Networks and communications protocols, examples, hardware, topologies, performanceparameters, protocols, ISO, wide area nets, broadcast nets, ethernet.22 Networks: ring networks, circuit switching, packet switching, names vs. routes, communi-cation problems, datagrams, TCP/IP,NFS.23 Protection and security: problems, levels of info protection, design principles, authentica-tion, authorization determination, access lists, capabilities, Multics protection, accessenforcement, common problems.24 Protection: examples of penetration, countermeasures, inference controls, confinementproblem, viruses.25 Encryption: substitution, transposition, codes, cryptanalysis, key distribution, DES, publickeyencryption, safe mail, digital signatures, Clipper Chip.26 Virtual Machines, VMM, emulators, implementation, memory mapping, I/O, VM perfor-mance. Real Time Systems - deadlines.-3-27 Performance evaluation: measurement, hardware monitoring, software monitoring, mul-tics, GTF,workload characterization, analytic modeling, queueing networks, simulation,back-of-the-envelope calculations. Hints for OS designers. Current research in
View Full Document