CS 414 ReviewOperating System: DefinitionWhat is in an OS?Crossing Protection BoundariesWhat is a process?Process State TransitionsContext SwitchThreads and ProcessesSchedulersCPU SchedulingRace conditionsThe Fundamental Issue: AtomicityCritical Section ProblemSolution StructureSolution RequirementsSemaphoresSemaphore TypesMutexes and SynchronizationMonitorsSynchronization Using MonitorsTypes of MonitorsDeadlocksFour Conditions for DeadlockDealing with DeadlocksSafe StateBanker’s AlgorithmBasic AlgorithmNetwork Stack: LayeringEnd-to-End ArgumentPacket vs. Circuit SwitchingLink level IssuesRepeaters and BridgesNetwork LayerTwo connection modelsDNS name serversPurpose of Transport layerUDPUDP FunctionalityTCPTCP SummaryRemote Procedure CallMemory Management IssuesScheme 1: Load-time LinkingScheme 2: Execution-time LinkingSegmentationMapping SegmentsFragmentationPagingMapping PagesPaging + SegmentationWhat is virtual memory?Virtual MemoryPage FaultsPage Replacement AlgorithmsThrashingApproach 1: Working SetWorking SetsApproach 2: Page Fault FrequencyAllocation and deallocationMemory AllocatorWhat happens on free?Design featuresMalloc & OS memory managementWhat does the disk look like?Disk overheadsDisk SchedulingRAID LevelsStable Storage AlgoFile System LayoutImplementing FilesLinked List AllocationUsing an in-memory tableI-nodesImplementing DirectoriesSlide 75Managing Free Disk SpaceBackup StrategiesFile System ConsistencyFS PerformanceBlock Cache ReplacementLFS Basic IdeaLFS CleaningFS ExamplesSecurity in Computer SystemsCryptography OverviewSecret-Key CryptographyPublic Key CryptographyDigital SignaturesAuthenticationSalting ExampleOne time passwordsSecurity Attacks & DefensesMobile Code ProtectionEncoding SecurityProtecting CapabilitiesSlide 96Slide 97Capability RevocationCS 414 Review2Operating System: DefinitionDefinitionAn Operating System (OS) provides a virtual machine on top of the real hardware, whose interface is more convenient than the raw hardware interface.HardwareApplicationsOperating SystemOS interfacePhysical machine interfaceAdvantagesEasy to use, simpler to code, more reliable, more secure, …You can say: “I want to write XYZ into file ABC”3What is in an OS?Operating System ServicesInterrupts, Cache, Physical Memory, TLB, Hardware DevicesGeneric I/O File SystemMemory ManagementProcess ManagementVirtual MemoryNetworkingNamingAccess ControlWindowing & graphicsWindowing & GfxApplicationsOS InterfacePhysical m/c IntfDevice DriversShellsSystem UtilsQuake Sql ServerLogical OS Structure4Crossing Protection Boundaries•User calls OS procedure for “privileged” operations•Calling a kernel mode service from user mode program:–Using System Calls–System Calls switches execution to kernel modeUser process System CallTrapMode bit = 0Save Caller’s state Execute system call Restore stateReturnMode bit = 1Resume processUser ModeMode bit = 1Kernel ModeMode bit = 05What is a process?•The unit of execution•The unit of scheduling•Thread of execution + address space•Is a program in execution–Sequential, instruction-at-a-time execution of a program.The same as “job” or “task” or “sequential process”6Process State TransitionsNewReady RunningExitWaitingadmittedinterruptI/O or event waitI/O or event completiondispatchdoneProcesses hop across states as a result of:• Actions they perform, e.g. system calls• Actions performed by OS, e.g. rescheduling• External actions, e.g. I/O7Context Switch•For a running process–All registers are loaded in CPU and modified•E.g. Program Counter, Stack Pointer, General Purpose Registers•When process relinquishes the CPU, the OS–Saves register values to the PCB of that process•To execute another process, the OS–Loads register values from PCB of that processContext SwitchProcess of switching CPU from one process to anotherVery machine dependent for types of registers8Threads and Processes•Most operating systems therefore support two entities:–the process, •which defines the address space and general process attributes–the thread, •which defines a sequential execution stream within a process•A thread is bound to a single process. –For each process, however, there may be many threads.•Threads are the unit of scheduling •Processes are containers in which threads execute9Schedulers•Process migrates among several queues–Device queue, job queue, ready queue•Scheduler selects a process to run from these queues•Long-term scheduler: –load a job in memory–Runs infrequently•Short-term scheduler:–Select ready process to run on CPU–Should be fast•Middle-term scheduler–Reduce multiprogramming or memory consumption10CPU Scheduling•FCFS•LIFO•SJF•SRTF•Priority Scheduling•Round Robin•Multi-level Queue•Multi-level Feedback QueueRace conditions•Definition: timing dependent error involving shared state –Whether it happens depends on how threads scheduled•Hard to detect:–All possible schedules have to be safe •Number of possible schedule permutations is huge•Some bad schedules? Some that will work sometimes?–they are intermittent•Timing dependent = small changes can hide bug12The Fundamental Issue: Atomicity•Our atomic operation is not done atomically by machine–Atomic Unit: instruction sequence guaranteed to execute indivisibly–Also called “critical section” (CS)When 2 processes want to execute their Critical Section,–One process finishes its CS before other is allowed to enter13Critical Section Problem•Problem: Design a protocol for processes to cooperate, such that only one process is in its critical section–How to make multiple instructions seem like one?Processes progress with non-zero speed, no assumption on clock speedUsed extensively in operating systems:Queues, shared variables, interrupt handlers, etc.Process 1Process 2CS1Time CS214Solution StructureShared vars: Initialization:Process:. . . . . . Entry SectionCritical SectionExit SectionAdded to solve the CS problem15Solution Requirements•Mutual Exclusion–Only one process can be in the critical section at any time•Progress–Decision on who enters CS cannot be indefinitely postponed•No deadlock•Bounded Waiting–Bound on #times others can enter CS, while I am waiting•No livelock•Also efficient (no extra resources), fair, simple, …16Semaphores•Non-negative integer with atomic increment and decrement•Integer ‘S’ that (besides init)
View Full Document
Unlocking...