OPERATING SYSTEMS CSC 4103
Popular in Course
Popular in ComputerScienence
This 254 page Class Notes was uploaded by Miss Emery VonRueden on Tuesday October 13, 2015. The Class Notes belongs to CSC 4103 at Louisiana State University taught by Staff in Fall. Since its upload, it has received 49 views. For similar materials see /class/222870/csc-4103-louisiana-state-university in ComputerScienence at Louisiana State University.
Reviews for OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/13/15
Protection and Security l Protection controls the access of users and their processes and programs to a system for various resources 1 Files memory segments CPU l Security ensures the authentication of system users to protect the information stored as well as the physical resources I Chapters to be covered 4 Protection Chapter 14 4 Security Chapter15 080 4108 Operating System 14391 B B Karki LSU Protection Source Operating System Concepts by Silberschatz Galvin and Gagne 080 4108 Operating System 142 B B Karki LSU Topics l Goals and Principles l Protection Domain l Access Matrix and Its Implementation l Access Control I Revocation of Access Rights l Languagebased protection Java 080 4108 Operating System 143 B B Karki LSU Goals of Protection l Protect integrity of modern computer systems Increase reliability l Prevent mischievous intentional violation of an access by an user I Ensure that each program uses system resources in appropriate way I Provide a mechanism for enforcement of policies governing resource use 080 4108 Operating System 144 B B Karki LSU Principles of Protection l A key timetested guiding principle for protection is the principle of least privilege Programs users and systems should be given just enough privileges to perform their tasks 4v Example Creating a separate account for each user with just the privileges that the user needs I To make sure that the failure or compromise of a component does the minimum damage and allows the minimum damage to be done 080 4108 Operating System 145 B B Karki LSU Domain of Protection l Operating system consists of a collection of processes and objects 4 Hardware objects m Software objects I Each object has a unique name and can be accessed through welldefined and meaningful operations I Protection problem 7 Ensure that each object is accessed correctly and only by those processes that are allowed to do so Use the needtoknow principles 080 4108 Operating System 146 B B Karki LSU Domain Structure l A process operates within a protection domain I Accessright ltobjectname rightssetgt rightssetis a subset of all valid operations that can be performed on the object I Domain 2 a set of accessrights l Static or dynamic association between process and domain D Dz Da lt 03 read write gt lt 01 read write gt lt 01 execute gt lt 02 execute gt lt 03 read gt lt 02 write gt lt 04 print gt 0804106 Operating System 4 7 B B Karim LSU UNIX Example l Domain associated with each user I Domain switch corresponds to changing the user identification temporarily l Switching accomplished via file system 4b Each file userid and setuid bit 9 When setuid on the userid is set to that of the file s owner and the file actually will run under the owner s id a When setuid off the user id is set to that of the other user who is executing the file 080 4108 Operating System 148 B B Karki LSU MULTICS Example l Protection domains in a hierarchical ring structure 4r Let D and Djbe any two domain rings ifjlt igt D is a subset of D A process executing in D0 has the most privileges l Domain switch occurs when a process crosses from one ring to another by calling a procedure in a different ring 1quot Define an access bracket b1b2 for ring ifor its process to make a call for a procedure or segment ring 1 ring N t 080 4103 Operating System B B Karki LSU Access Matrix I View protection as a matrix access matrix I Rows represent domains I Columns represent objects I Accessi j is the set of operations that a process executing in Domain Di can invoke on Object oj 080 4108 Operating System 1410 B B Karki LSU Access Matrix object I F1 F2 F3 printer domain D1 read read 02 print D3 read execute read read D4 write write 080 4103 Operating System 1411 B B Karki LSU Use of Access Matrix Cont l Access matrix design separates mechanism from policy a Mechanism J Implementation operating system provides access matrix rules J The matrix is only manipulated by authorized agents and that rules are strictly enforced 5 Policy J User dictates policy J Who can access what object and in what domain 080 4108 Operating System 1412 B B Karki LSU Use of Access Matrix I If a process in domain Di tries to do op on object oj then op must be in the access matrix I Can be expanded to dynamic protection it Operations to add delete access rights at Special access rights transfer switch from domain D1 to Dj Jcopy op from O1 to Oj Jowner of O1 Jcontrol Di can modify Dj access rights 080 4108 Operating System 1413 B B Karki LSU Access Matrix with Domains as Objects object F1 F2 F3 laser D1 D2 03 D4 domain pnmer D1 read read switch 02 print switch switch 03 read execute D4 read read switch write write 0504106 Operating System 1414 B B Karki LSU Access Matrix with Copy Rights 080 4103 Operating System object F1 F2 F3 domain D1 execute write D2 execute read execute 0 execute 6 object F1 F2 F3 domain D1 execute write 02 execute read execute 0 execute read b 1415 B B Karki LSU Access Matrix With Owner Rights 080 4108 Operating System object F1 F2 F3 domain D owner 1 execute wme D 51 2 owner write 0 execute 8 object F1 F2 F3 domain 0 owner 1 execute wme owner readw 0 readquot owner write write 133 write write bi 1416 B B Karki LSU Access Matrix with Control Right ob39ect J F1 F2 F3 laser D1 D2 03 D4 domain Printer D1 read read switch switch Dz print SWItch control 03 read execute D4 write write switch 080 4106 Operating Sjslem 1417 B B Karki LSU Implementation of Access Matrix CSC 4108 Operating System Global Table A set of ordered triples lt domain object rightsez gt Access lists for objects 7 Each column 2 accesscontrol list for one object Defines who can perform what operation Domain 1 2 Read Write Domain 2 2 Read Domain 3 2 Read Capability lists for domains 7 Each row 2 capability List For each domain what operations allowed on what objects Object 1 Read Object 4 Read Write Execute Object 5 Read Write Delete Copy Lockkey mechanism Each object has a lock and each domain has a key Combined approach First the access list is searched and then a capability is created and attached to the process 1418 B B Karki LSU Access Control I Protection can be applied to nonfile resources I Solaris 10 provides rolebased access control to implement least privilege it Privilege is right to execute system call or use an option within a system call 1 Can be assigned to processes Users assigned roles granting access to privileges and programs 080 4108 Operating System 1419 user 1 role 1 executes with role 1 privileges B B Karki LSU Revocation of Access Rights l Access List Delete access rights from access list 4 Immediate vs delayed 41 Selective vs general Partial vs total 4 Temporary vs permanent I Capability List Locate capability in the system before capability can be revoked at Reacquisition Backpointers Indirection Keys 080 4108 Operating System 1420 B B Karki LSU LanguageBased Protection Java V l Provide highlevel description of policies for the allocation and use of resources I Protection is handled by the Java Virtual Machine JVM l A class is assigned a protection domain when it is loaded by the JVM l The protection domain indicates what operations the class can and cannot perform I If a library method is invoked that performs a privileged operation the stack is inspected to ensure the operation can be performed by the library 080 4108 Operating System 1421 B B Karki LSU Stack Inspection protection main cket class untrusted so permission applet URL loader networking none ucentcom80 connect any gui getURL u openAddr a getUH oola rivileged oneckPermission openaddr open proxyucentcom80 a connect ltrequest u from proxygt connect a 080 4108 Operatmg System 14 22 B B Karkt LSU Summary Objects hardware or software need to be protected from misuse Define protection domain Aset of access rights Processes execute in domains I Access matrix v Model of protection matrix elements define different access rights Separation of policy and mechanism tr Implementation as access lists or capability lists I Languagebased protection 439 JVM runs several threads each in a different protection class 080 4108 Operating System 1423 B B Karki LSU CPU Scheduling Source Operating System Concepts by by Silberschatz Galvin and Gagne 080 4103 Operating System 51 BB Karki LSU CPU Scheduling l CPU scheduling is fundamental to multiprogramming OS 4 Deals with problem of deciding which of processes in the ready queue is to be allocated the CPU I What we cover a Basic concepts w Scheduling criteria Scheduling algorithms Multipleprocessor scheduling Thread scheduling Realtime scheduling Algorithm evaluation OS examples 4h 399 4 080 4103 Operating System 52 BB Karki LSU CPUlO Burst Cycle l Process execution consists of a cycle of CPU execution and Ho wait I Process alternates between these two states I Process always begins and ends with a CPU burst 080 4108 Operating System load store add store read from file wait for 0 store increment index write to file wait for 0 load store add store read from file wait for IO CPU burst O burst CPU burst O burst CPU burst O burst Histogram of CPUBurst Times l Durations of CPU bursts have a typical frequency curve exponential or hyperexponential 9 many short bursts an lO bound program 1 a few long bursts a CPU bound program frequency l l l l l O 8 16 24 32 40 080 4108 Operating burst duration milliseconds BB Karkiy LSU CPU Scheduler l CPU scheduler also called shortterm scheduler selects from among the processes in ready queue and allocates the CPU to one of them CPU scheduling decision may take place when a process Switches from running to waiting state Switches from running to ready state Switches from waiting to ready Terminates Scheduling under 1 and 4 is nonpreemptive r Once the CPU is allocated to a process the process keeps the CPU until it switches to waiting state or terminates All other scheduling is preemptive 7 Incurs a cost 080 4103 Operating System 55 BB Karki LSU Dispatcher l Dispatcher gives control of the CPU to the scheduled process This involves as switching context a switching to user mode is jumping to the proper location in the user program to restart that program I Dispatch latency time the dispatcher takes to stop one process and start another running 080 4103 Operating System 56 BB Karki LSU Scheduling Criteria Criteria for comparing CPUscheduling algorithms l CPU utilization keep the CPU as busy as possible 0 to 100 efficiency l Throughput of processes that complete their execution per time unit I Turnaround time amount of time to execute a particular process Ir waiting for memory ready queue execution O l Waiting time amount of time a process waits in the ready queue l Response time amount of time it takes from when a request was submitted until the first response is produced 080 4103 Operating System 57 BB Karki LSU Optimization Criteria v I Max CPU utilization l Max throughput l Min turnaround time I Min waiting time I Min response time I Optimize the max or min values or average measure or vanance 080 4103 Operating System 58 BB Karki LSU FirstCome FirstServed FCFS Scheduling l FCFS is the simplest CPUscheduling algorithm 4 The process that requests the CPU first is allocated the CPU first I Implemented with a FIFO queue av PCB of a new process is linked onto the tail of the ready queue w Process at the head of the queue gets CPU first I Average waiting time varies a lot and is quite long I FCFS is nonpreemptive CSC 4103 Operating System 59 BB Karki LSU FCFS Scheduling Cont Process Burst Time ms P1 24 P2 3 P3 3 l Suppose that the processes arrive in the order P1 P2 P3 The Gantt Chart for the schedule is P1 P2 P3 l Average waiting time 0 24 273 17 milliseconds l Average turnaround time 080 4103 Operating System 510 BB Karki LSU FCFS Scheduling Cont Suppose that the processes arrive in the order 1 P2 P3 P1 l The Gantt chart for the schedule is P2 P3 P1 l Average waiting time 6 O 33 3 ms l Much better than previous case I Convoy effect short process behind long process 080 4103 Operating System 511 BB Karki LSU ShortestJobFirst SJF Scheduling l Associate with each process the length of Process Burst Time Its next CPU burst Use these lengths to schedule the process with the shortest P1 6 time first p2 8 P3 7 l SJF IS optimal gives minimum average waiting time for a given set of processes P4 3 Average waiting time is 3169O4 7ms But with FCFS scheme 0 3 9 15 24 average waiting time would be 1025 ms 080 4103 Operating System 512 BB Karki LSU Determining Length of Next CPU Burst l Challenge is to know the length of the next CPU request I Approximate prediction of the length of next CPU burst 0 from the lengths of previous CPU bursts by using exponential averaging it running average of each burst for each process 1 tn actual observed length of n hCPU burst 2 In predicted value for the next CPU burst 3 or O s or 51 4 Define Tn1 O In 1 001quot 080 4103 Operating System 518 BB Karki LSU Examples of Exponential Averaging 0 0 Tn1 In Recent history does not count a 1 Tn1 In Only the actual last CPU burst counts If we expand the formula we get 17n1 or Z n 1 or or I m 1 orocl nj 1 0cquot1r0 Since both a and 1 a are less than or equal to 1 each successive term has less weight than its predecessor 080 4103 Operating System 514 BB Karki LSU Prediction of the Length of the Next CPU Burst 080 4103 Operating System 515 BB Karki LSU SJF Scheduling Cont l Two schemes 1 nonpreemptive once CPU given to the process it cannot be preempted until completes its CPU burst 43 preemptive if a new process arrives with CPU burst length less than remaining time of current executing process preempt This scheme is known as the ShortestRemainingTime First SRTF l Preemptive improves average waiting time CSC 4103 Operating System 516 BB Karki LSU Example of NonPreemptive SJF Process Arrival Time Burst Time P1 0 7 P2 2 4 P3 4 1 P 5 4 A l SJF nonpreemptive P1 P3 P2 P4 O 3 7 8 12 16 l Average waiting time O 6 3 74 4 ms 080 4103 Operating System 517 BB Karki LSU Example of Preemptive SJF Process Arrival Time Burst Time P O P P P l A L LPV 2 4 5 A U 0 l P3 P2 P4 P1 I I O 2 4 5 7 11 16 l Average waiting time 9 1 O 24 3 ms l Preemptive SJF suffers from starvation l Highest response ratio next HRRN scheduling R w ee at As time elapses the ratio increases so that a longer process will eventually get past competing shorter processes 080 4103 Operating System 518 BB Karki LSU Priority Scheduling l A priority is associated with eaCh process and the CPU is Process Burst Time Priority allocated to the process With the highest priority P1 10 3 4 smallest integer 5 highest priority P2 1 l SJF is a priority scheduling P3 2 4 where priority is the inverse of P 1 5 the predicted next CPU burst 4 time P5 5 2 Average waiting time is 82 ms 080 4103 Operating System 519 BB Karki LSU Priority Scheduling l Priorities can be defined internally or externally l Priority scheduling can be preemptive or nonpreemptive l Problem 5 Starvation Low priority processes may never be executed eg a lowpriority process submitted in 1967 never ran until the shutdown of IBM 7094 at MIT in 1973 l Solution 5 Aging As time progresses increase the priority of the process 080 4103 Operating System 520 BB Karki LSU Round Robin RR l Each process gets a small unit of CPU time time quantum are Usually 10100 milliseconds at After this time has elapsed the process is preempted and added to the end of the ready queue Ready queue treated as a circular queue I If there are n processes in the ready queue and the time quantum is q then each process gets 1n of the CPU time in chunks of at most q time units at once No process waits more than n 1qtime units l Performance 399 q large 2 FIFO q small gt q must be large with respect to context switch otherwise overhead is too high 080 4103 Operating System 521 BB Karki LSU Example of RR with Time Quantum 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 l The Gantt chart is P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 O 20 37 57 77 97 117 121 134 154162 I Typically higher average turnaround than SJF but better response 4 Useful in time sharing systems 080 4103 Operating System BB Karki LSU Time Quantum and Context Switch Time process Time quantum needs to be large enough with respect to the context switch time Context switch increases the waiting and turnaround time 080 4103 Operating Syaem 5 23 BE Karim LSU Turnaround Time Varies With The Time Quantum process time P1 6 132 3 P3 1 P4 7 S C 3 2 U C E g 100 S g 95 90 time quantum 080 4108 Operating Sys1em 524 BB Karki LSU Multilevel Queue l Ready queue is partitioned into separate queues at foreground interactive are background batch l Each queue has its own scheduling algorithm are foreground RR are background FCFS l Scheduling must be done between the queues are Fixed priority scheduling ie serve all from foreground then from background Possibility of starvation Time slice each queue gets a certain amount of CPU time which it can schedule amongst its processes I 80 to foreground in RR and 20 to background in FCFS 080 4103 Operating System BB Karki LSU Multilevel Queue Scheduling batch student processes Each queue has absolute priority over lowerpriority queues 080 4103 Operating Sy em 526 BB Kalki LSU Multilevel Feedback Queue l A process can move between the various queues a Move a process to a lower priority queue if it uses too much CPU time a Move a process to a higher priority queue if it waits too long aging can be implemented this way I Multilevelfeedbackqueue scheduler defined by the following parameters av number of queues 4p scheduling algorithm for each queue a method used to determine when to upgrade a process to a higherpriority queue as method used to determine when to demote a process to a lowerpriority queue is method used to determine which queue a process will enter when that process needs service 080 4103 Operating System 527 BB Karki LSU Example of Multilevel Feedback Queue l Three queues o 00 time quantum 8 milliseconds 4 01 time quantum 16 milliseconds 02 FCFS quantum 8 I quantum 16 050 4103 Operating System 528 BB Karki LSU MultipleProcessor Scheduling l CPU scheduling more complex when multiple CPUs are available I Homogeneous identical processors within a multiprocessor system I Asymmetric multiprocessing one single processor called master server does all scheduling including lO processing e Other processors execute only user codes I Symmetric multiprocessing SMP Each processor is self scheduling ee Provide a separate queue for each processor 4 Use a common ready queue it Two issues Processor affinity and load balancing 080 4103 Operating System 529 BB Karki LSU Symmetric Multithreading l Symmetric multithreading SMT runs several threads at a time by providing multiple logical rather than physical processors 9 Also known as hyperthreading technology on Intel processors l Each logical processor has its own architecture state registers interrupt handling supported in hardware level To create multiple logical processors on the same physical processor I Figure illustrates that tour processors are available for work on this system from 08 s perspective logical logical logical logical CPU CPU CPU CPU physical physical CPU CPU csc 41 03 Dnsrmi system bus BB Karki LSU Thread Scheduling l Lightweight process LWP maps an userlevel thread to an v associated kernel level thread I Contention scope competition among threads at two level as Processcontention scope PCS schedules userlevel threads to run on an available LWP 7 Systemcontention scope SCS schedules kernellevel threads on a physical CPU l Pthread scheduling POSIX Pthread AIP supports PCS and 808 scheduling with PTHREADSCOPEPROCESS r PTHREADSCOPESYSTEM 080 4103 Operating System 531 BB Karki LSU RealTime Scheduling l Hard realtime systems required to complete a critical task within a guaranteed amount of time 4 Scheduling should admit or not the process by examining the process requirements a Deadline scheduling l Soft realtime computing uses priority scheduling a Critical processes receive priority over less fortunate ones a Priority should not degrade with time at Minimize latency interrupt and dispatch 1 Make kernel preemptive 080 4103 Operating System 532 BB Karki LSU Algorithm Evaluation l Many scheduling algorithms 4 FCFS SJF RR Priority Multilevel queue l Define the selection criteria 4 Relative importance of CPU utilization throughput or response time 4 Maximize CPU utilization under constraint that the maximum response time is 1 second 4 Maximize throughput such that turnaround time is on average linearly proportional to total execution time I Different methods 4 Deterministic modeling a Queuing models 4 Simulations 4 Implementation 080 4103 Operating System 538 BB Karki LSU Deterministic Modeling l Analytical evaluation of an algorithm 9 Takes a particular predetermined workload r Produces a formula or number to define the performance of the algorithm for that workload l Process Burst Time P 1 0 P2 29 P3 3 P4 7 P5 1 2 I Consider FCFS SJF and RR quantum 10 ms Which algorithm would give the minimum average waiting time 080 4103 Operating System 584 BB Karki LSU Queuing Algorithm l Queuing models 390 CPU burst distribution v Arrival time distribution l Little s formula average queue length average arrival rate X average waiting time in the queue 4L Compute one variable if you know the other two I Knowing arrival rates and service rates one can compute utilization average queue length average wait time 080 4103 Operating System 535 BB Karki LSU Simulations l A more accurate evaluation 4 Program a model of the computer system A Simulator l OSP operating system project it A collection of JavaC modules that together implement an OS I As the simulation executes statistics that indicate algorithm performance are gathered and printed I Data to drive simulation l Randomnumber generator a Trace tapes recorded sequence of actual events 080 4103 Operating System 536 BB Karki LSU Implementation l Most accurate evaluation 4 Code the algorithm put in the real 08 and see how it works I Too frequent implementation is inconvenient 080 4103 Operating System 537 BB Karki LSU Operating System Examples l Solaris Scheduling l Windows XP Scheduling l Linux Scheduling 080 4103 Operating System 538 BB Karki LSU Solaris Scheduling global scheduling scheduler run priority priorities classes queue highest lirst real lime nel threads of Prioritybased O ealilme scheduling Al orithm 9 0 Inverse relationship swam kernel servrce between priorities 0 threads and time quanta 0 interactive amp kernel time sharing 0 threads of interactive amp limesharing O 0504108 Operating System lowest last Solaris Dispatch Table Interactive and time sharing scheduling use 60 priority levels CSC 4103 Operating System time return time quantum from priority quantum expired sleep 0 200 O 50 5 200 O 50 10 160 O 51 15 160 5 51 20 120 10 52 25 120 15 52 30 80 2O 53 35 80 25 54 4O 4O 30 55 45 4o 35 56 5O 4O 40 58 55 4O 45 58 59 2O 49 59 540 BB Karki LSU Windows XP Scheduling real high above normal below idle I Ime normal normal priority timecritical 31 15 15 15 15 15 highest 26 15 12 1O 8 above normal 25 14 11 9 7 5 normal 24 13 1O 8 6 4 below normal 23 12 9 7 5 3 lowest 22 11 8 6 4 2 idle 16 1 1 1 1 1 Prioritybased preemptive scheduling algorithm Dispatcher scheduler uses a 32level priority scheme Variable class 1 to 15 and realtime class 16 to 31 Relationship between Windows XP and Win32 API 030 4103 Operating System 541 BE Karkr LSU Linux Scheduling l Preemptive prioritybased scheduling algorithm with two separate priority ranges it A realtime range from O to 99 and a nice value ranging from 100 to 140 l Global priority scheme Numerically lower values indicate higher priorities 6 Priority is proportional to time quantum slice numeric relative time priority priority quantum 0 highest 200 ms realtime tasks 99 1 00 Z other tasks 050 4103 Operating 1 40 owest 1 0 ms BB Karki LSU Tasks Indexed According to Priorities l A runqueue data structure contains two priority arrays 4 Active array tasks with time remaining in their time slices 9 Expired array all expired tasks 9 Once active array is done the expired array is changed to the active array l Dynamic priorities Recalculate a task s priority whenever the task moves to the expired array 9 Realtime tasks are assigned static priorities active expired array array priority task lists priority task lists 0 0 0 0 0 0 0 1 0 0 0 1 O 050 4103 Operating 1 40 O 1 40 0 0 BB Karki LSU Summary 080 4103 Operating System CPU scheduling selects a process from the ready queue and the dispatcher allocates the CPU to the selected process FCFS scheduling is the simplest approach but it can hurt short processes SJF scheduling is optimal providing the shortest average waiting time It suffers from problems of predicting the length of the next CPU burst and starvation SJF can be preemptive or nonpreemptive Priorityscheduling algorithm allocates the CPU to the highestpriority process RR allocates the CPU to all processes in time slice so it is appropriate for timesharing system RR is always preemptive Multilevel queue algorithms allow different algorithms in different queues interactive and background and also allow processes to move from one queue to another Multiprocessor and realtime scheduling are more challenging Four ways of evaluating scheduling algorithms Deterministic modeling queuing models simulations and implementation Real operating systems use a combination of different algorithms 544 BB Karki LSU Exercises on CPU Scheduling 080 4103 Operating System 545 BB Karki LSU Exercises l 51 Why is it important for the scheduler to distinguish lO bound programs from CPUbound programs I 53 Consider the exponential average formula used to predict the length of the next CPU burst What are the implications of assigning the following values to the parameters used by the algorithm ad0and 1302100 ms b or 099 and 10 10 ms l 55 Which of the following scheduling algorithms could result in starvation is a Firstcome firstserved is b Shortest job first is c Round robin 080 4103 Operating System 546 BB Karki LSU Exercises Cont l 57 Consider a system running ten Obound tasks and one CPUbound task Assume that the Obound tasks issue an O operation once for every millisecond of CPU computing and that each O operation takes 10 milliseconds to complete Also assume that the context switching overhead is 01 millisecond and that all processes are longrunning tasks What is the CPU utilization for a roundrobin scheduler when 4k a The time quantum is 1 millisecond 4 b The time quantum is 10 milliseconds 080 4103 Operating System 547 BB Karki LSU Exercises Cont l 59 Consider a preemptive priority scheduling algorithm based on dynamically changing priorities Larger priority numbers imply higher priority When a process is waiting for the CPU in the ready queue but not running its priority changes at a rate or when it is running its priority changes at a rate 3 All processes are given a priority of 0 when they enter the ready queue The parameters or and 3 can be set to give many different scheduling algorithms a What is the algorithm that results from 3 gt or gt O 4 b What is the algorithm that results from or lt 3 lt O 080 4103 Operating System 548 BB Karki LSU Exercises Cont l 512 Consider the scheduling algorithm in the Solaris operating system for time sharing threads at a What is the time quantum in milliseconds for a thread with priority 10 With priority 55 at b Assume a thread with priority 35 has used its entire time quantum without blocking What new priority will the scheduler assign this thread l c Assume a thread with priority 35 blocks for lO before its time quantum has expired What new priority will the scheduler assign this thread 080 4103 Operating System 549 BB Karki LSU Exercises Cont l 513 The traditional UNIX scheduler enforces an inverse relationship between priority numbers and priorities The higher the number the lower the priority The scheduler recalculates process priorities once per second using the following function Priority Recent CPU usage 2 Base where base 60 and recent CPU usage refers to a value indicating how often a process has used the CPU since priorities were last recalculated Assume that recent CPU usage for process P1 is 40 process P2 is 18 and process P3 is 10 What will be the new priorities for these three processes when priorities are recalculated 7 Based on this information does the traditional UNIX scheduler raise or lower the relative priority of a CPUbound process 080 4103 Operating System 550 BB Karki LSU 080 4103 Operating Systems Y Spring 2009 Bijaya B Karki Tuesday and Thursday 140 PM to 300 PM 215 Tureaud Hall Office Hours l Instructor Bijaya B Karki 439 100 PM to 300 PM Monday and Wednesday or it Any time by appointment 7 283 Coates Hall it karkicscsuedu l Teaching Assistant Qing Huang Any time by appointment 080 4108 Operating Systems 02 B B Karki LSU Reading Materials amp Resources l Textbooks Required av A Silberschatz PB Galvin and G Gagne Operating System Concepts 7th Edition Wiley ISBN 0471694665 or 8th Edition or A Silberschatz PB Galvin and G Gagne Operating System Concepts with JAVA 7th Edition Wiley ISBN 9780471769071 40 M Kiefer and SA Smolka Introduction to Operating System Design and Implementation The OSP 2 Approach 2007 Java version or M Kiefer and SA Smolka OSP An Environment for Operating System Projects AddisonWesley 1991 C version I Lecture Notes Posted regularly online preferably the moodle site httpmoodlelsuedu httpwwwcscIsuedukarki l Resources 1 Will be provided with an UNIX accountin classes to work in project 080 4108 Operating Systems 03 B B Karki LSU Grading Policy l Grading Scale r A 90 or more B 78 to 89 r C 65 to 77 D 50 to 64 F below 50 l Grading Items Pop Quiz 10 Homework 10 Programming 20 Midterm Exam 30 Final Exam 3O o 080 4108 Operating Systems 04 B B Karki LSU RulesRecommendation V l Late submission of homeworkprogramming assignments will be penalized I No books lecture notes laptops and other materials will be allowed in quizzes and exams I Use of laptops during the class time is not recommended I Academic dishonesty will be treated seriously 080 4108 Operating Systems 05 B B Karki LSU Homework Assignments l 1O of total grading l Assigned at the rate of approximately 3 weeks I Also useful in preparation for the midterm and final exams 080 4108 Operating Systems 06 B B Karki LSU Programming Assignments l 20 of total grading l OSP Operating System Project Distributed during the first month of the class 4 Working on Unix machine 4 Implementation and exploration of some key features and algorithms of 08 4r OSP manual and textbook l Other programming at Implementation outside OSP 080 4108 Operating Systems 07 B B Karki LSU Topics To Be Covered Overview 5 5 tquot 0 oar 70 8 00 0 30 06 J lt0 lbs f 000 QV 080 4108 Operating Systems 08 B B Karki LSU Overview I Introduction I Computer System Structures l Operating System Structures 080 4108 Operating Systems 09 B B Karki LSU Process Management l Processes l Threads l CPU Scheduling l Process Synchronization l Deadlocks 080 4108 Operating Systems 010 B B Karki LSU Storage Management l Memory Management I Virtual Memory l FileSystem Interface l FileSystem Implementation 080 4108 Operating Systems 011 B B Karki LSU InputOutput Systems l O Systems I MassStorage Structure 080 4108 Operating Systems B B Karki LSU Protection and Security l Protection l Security 080 4108 Operating Systems B B Karki LSU Sample Exam Questions l The questions in midterm and final exams will be of three types a Type A True or false statements 4 Type B Short answer descriptive or numerical questions 3 Type C Long answer multipart questions I The list of the sample questions given here is not complete but it will give you an idea about what the exam would look like The number of questions and the order they appear in the actual exams will vary l Closedbook exams 9 Books notes and computers are not allowed at Four quizzes 10 o one midterm 30 and one Final 30 o 080 4108 Operating Systems 014 B B Karki LSU Type A Questions Each 1 Point l Answer True or False to the following statements a Desktop system is mainly concerned with convenience 4 The FCFS scheduling can never be preemptive In a pure demand paging some pages of a process are kept in the main memory prior to the process execution 4 DMA transfers data between devices and memory byte by byte 4 A counting semaphore can be implemented with binary semaphores 439 The Nstep diskscheduling algorithm suffers from starvation 080 4108 Operating Systems 015 B B Karki LSU Type B Questions Each 2 Points Define CPU bound and lO bound processes What would be the problem if all processes were CPU bound Describe how the hardware supports segmentation A singlelane bridge connects the north and south parts of a town The bridge can become deadlocked if both a northbound and a southbound vehicle get on the bridge at the same time The drivers are stubborn and are not willing to back up Using semaphores design an algorithm that prevents the deadlock Consider a 20block long file on a disk If you are currently at the 10th logical block and want to access logical block 15 how many physical blocks must be read from the disk according to the index allocation scheme Justify your answer Assume that the information about the file is already in memory If the average waiting time is 30 ms for the queue of average number of 8 processes calculate the average arrival rate CSC 4108 Operating Systems 016 B B Karki LSU Type C Questions Each 6 Points 1 Consider five processes P1 P2 P3 P4 and P5 with CPU burst times of 10 29 3 7 and 12 milliseconds respectively a a Draw Gantt charts for the FCFS SJF and RR scheduling algorithms time quantum of 10 ms 4r b Find out which of these algorithms would give the minimum average waiting time a c Compare the average turnaround time between SJF and RR scheduling algorithms 2 Consider the following pagereference string 1 2 3 4 2 15 6 2 1 2 3 7 6 3 2 1 2 3 6 How many page faults would occur for the following replacement algorithms assuming four frames which all are initially free is a FIFO replacement a b LRU replacement 7 0 Optimal replacement 080 4108 Operating Systems 017 B B Karki LSU Type C Questions Contd 3 A barbershop consists of 5 chairs for the customers to wait and one barber chair for the haircut If there are no customers to be served the barber goes to sleep If a customer enters the barbershop and all chairs are occupied then the customer leaves the shop lithe barber is busy but chairs are available then the customer sits in one of the free chairs lithe barber is asleep the customer wakes up the barber Use the following semaphores to coordinate the barber and customers semaphore mutex customers barber int waiting Here mutex is initialized to 1 The semaphores customers and barber each of which is initialized to 0 track the availability of customers and barber The variable waiting which is initialized to 0 gives a count of waiting customers r a Explain the meaning of mutex 7 b Determine the type binary or counting of the three semaphores a c Write the structure of a barber process r d Write the structure of a customer process 080 4108 Operating Systems 018 B B Karki LSU FileSystem Implementation Sources Operating System Concepts by Silberschatz Galvin and Gagne 080 4108 Operating Systems 39 BB Karki LSU Topics l Implementation issues I Allocation Methods l FreeSpace Management I Efficiency and Performance l Recovery I NFS 080 4108 Operating Systems BB Karki LSU FileSystem Structure l File definition 4 Logical storage unit 7 Named collection of related information I File system resides on secondary storage 4 Disks are convenient medium J Rewritable J Direct access I Two design problems a How the file system should look to the user 74 How to map the logical file system onto the secondary storage devices 080 4108 Operating Systems 39 BB Karki LSU Layered File System l O control 4 Acts as a translator using device drivers and interrupt handlers I Basic file system Commands device driver to read and write physical blocks l Fileorganization module a Translates logical block addresses to physical block addresses l Logical file system v Manages filesystem structure directory structure protection and security 080 4103 Operating Systems application programs logical file system liileorganization module basic file system O control devices B B Karki LSU Virtual File Systems filesystem interface I Virtual file Systems VFS provide an objectoriented way of implementing multiple file VFS interface systems l VFS allows the j l same system can local file system local file system interface the API remote file system type 1 to be used for different types of file systems 1 network 080 4108 Operating Systems B B Karki LSU OnDisk Structure The ondisk structure for implementation of a file system includes VI Boot control block tr Information about how to boot an OS 4 eg boot block in UFS l Partition control block 4 Partition details such as information about blocks block and file pointers eg superblock in UFS l Directory structure 4 Organization of files I File control block 4 File details eg inode in UFS 080 4108 Operating Systems 39 BB Karki LSU File Control Block FCB file permissions file dates create access write file owner group ACL file size file data blocks or pointers to file data blocks l Storage structure consisting of information about a file 080 4103 Operating Systems 39 B B Karki LSU lnMemory Structure The inmemory structure provides filesystem management and improved performance via caching l nmemory partition table if information about each mounted partition I nmemory directory structure if information about recently accessed directories l Systemwide openfile table 4 copy of the FCB of each open file I Perprocess openfile table a pointer to the entry in the systemwide openfile table 080 4108 Operating Systems 39 BB Karki LSU lnMemory File System Structures l File open Pass the tile name Search the tile in the directory structure Copy FCB into a system wide opentile table I File read Make an entry in a per process opentile table Pointers to other fields current location in the tile access mode I File close Remove perprocess entry and decrement the systemwide entry s open count 080 4103 Operating Systems open file name DE DE directory structure directory structure f39 e control block user space kernel memory a secondary storage read index index systemwide openfile table perprocess openfile table CD D data blocks him filecontrol block user space kernel memory secondary storage B B Karki LSU Directory Implementation V l Linear list of file names with pointer to the data blocks simple to program is timeconsuming to execute l Hash Table linear list with hash data structure decreases directory search time colisions situations where two file names hash to the same location fixed size 080 4108 Operating Systems 1310 BB Karki LSU Allocation Methods Allocation method refers to how disk blocks are allocated to files so that disk space is used effectively and files can be accessed quickly I Three methods Contiguous allocation Linked allocation Indexed allocation 080 4108 Operating Systems 1339 BB Karki LSU Contiguous Allocation I Each file occupies a set of contiguous blocks on the disk I Simple only starting location block and length number of blocks are required I Both sequential and random accesses supported I Wasteful of space dynamic storageallocation problem 1 First fit and best fit strategies can be used 2 Suffers from external fragmentation l Files cannot grow 080 4108 Operating Systems 1312 BB Karki LSU Contiguous Allocation of Disk Space 080 4103 Operating Systems V count 0D 1D 2D 3D 1 4D 5D 61 7E 8D 9D10D11D H 12D13D14D15D 16D17D18D19D mail 20D21D22D23D MDDDZD list 28D29D30D31D directow file start length count 0 tr 14 mail 19 list 28 f 6 2 3 6 4 2 1313 33 Karki LSU ExtentBased Systems l Many file systems use a modified contiguous allocation scheme a Initial continuous chunk of space is Apply extra chunk of contiguous space if needed I Extentbased file systems allocate disk blocks in extents I An extent is a contiguous block of disks Extents are allocated for file allocation A file consists of one or more extents 080 4108 Operating Systems 1314 BB Karki LSU Linked Allocation l Each file is a linked list of disk blocks blocks may be scattered anywhere on the disk block pointer l Simple need only starting address 7 Any isolated free block can be used no external fragmentation at A file can grow as long as free blocks are available I Useful for sequentialaccess files Follow pointers from one block to next starting from the first one I Memory cost for pointers 7 Cluster of multiple blocks to reduce memory overhead and disk head seeks 080 4108 Operating Systems 1315 BB Karki LSU Linked Allocation Contd l The directory contains a pointer to the first and last blocks of the file I A file of five blocks might start at block 9 continue at block 16 then block 1 block 10 and finally block 25 l Each block contains a pointer to the next block 080 4103 Operating Systems 20II2139 2I23I file jeep 9 25 directory start end 24 D25 26 II27II 28 DZQEIBO I31II 1316 33 Karki LSU FileAllocation Table l The table has one entry for each disk block and is indexed by the block number I The entry contains the block number of the next block in the file I Unused blocks are indicated by a 0 table value I Example file consisting of disk blocks 271 618 and 339 080 4103 Operating Systems directory entry 618 no of disk blocks 1 618 339 FAT 1317 BB Karki LSU Indexed Allocation l Brings all pointers block addresses together into the index block 2 Each file has its own index box 4 The F entry points to the if block of the file w The directory contains the address of the index block I Logical view Similar to a paging scheme 080 4103 Operating Systems mDIDZD 28 D29D30 D31 D directow file index block leerJ 19 1318 B B Karki LSU Indexed Allocation Cont Supports random access No external fragmentation Mapping from logical to physical in a file of maximum size of 256K words and block size of 512 words We need only 1 block for index table Mapping from logical to physical in a file of unbounded length block size of 512 words One block is not enough for index table Linked scheme Link blocks of index table no limit on size Multilevel index Combined scheme 1819 080 4108 Operating Systems BB Karki LSU Combined Scheme UNIX mode owners 2 timestamps 3 size block count direct blocks single indirect double indirect triple indirect 080 4103 Operating Systems 1320 B B Karki LSU FreeSpace Management Bit Vector l Maintains a freespace list to keep track of free disk space Records all free disk blocks and allocate that space to new files I Bit vector or bit map n blocks Easy to locate first free block For a disk with free blocks 2 3 4 5 8 9 10 11 12 13 17 18 25 26 and 27 and the rest of the blocks allocated the freespace bit map is 001111001111110001100000011100000 l Block number calculation n1 number of bits per word number of Ovalue words offset of first 1 bit 1 gt bIOCkM free bitl l Bit map requires extra space in main memory block size 212 bytes disk size 230 bytes 1 GB n 230212 218 bits or 256 KB 0 gt blockI occupied 1821 080 4108 Operating Systems BB Karki LSU Linked Free Space List l Link together all the free disk blocks free space list head I Keep a pointer to the first free block on the disk and cache it in memory The first block contains a pointer to the next free disk block and so on Free blocks 2 3 4 5 8 9 1o 11 12 13 17 18 25 26 and 27 28 D29EI30D31 I 0804103 Operating Systems 1322 BB Karki LSU Grouping and Counting Free Blocks l Grouping 4 A linked list of index blocks is kept r Each index block contains addresses of n free blocks and a pointer to the next index block it Provides address of a large number of free blocks quickly I Counting 7 Keeps the address of the first free block and the number n of free contiguous blocks that follow the first block 4 Each entry in the list contains a disk address and a count r Makes overall list shorter 080 4108 Operating Systems 1323 BB Karki LSU Efficiency l Efficiency is dependent on disk allocation and directory algorithms I Some examples 4 UNIX inodes Clustering blocks File s directory entries Pointer sizes Dynamic allocation 080 4108 Operating Systems 1324 BB Karki LSU Performance Using Various Caches 050 4103 Track or disk cache Local memory in disk controller to store tracks at a time w Controller transfers any sector requests from the disk cache to the OS Buffer cache A section of main memory where blocks are kept r Accesses interface with filesystem oriented physical blocks Page cache Pages used to cache file data Accesses interface with virtual memory rather than the file system Unified virtual memory Use page caching to cache both process pages and file data eg Solaris Linux Windows ram disk quot A track V buffer I L J CPU Open39 le table controller disk block buffer main memory Unified Buffer Cache l Uses the same page cache to cache both memorymapped pages and ordinary file system O eg UNIX and Linux 7 Avoids double caching memorymapped lO 0 using read and write I page cache bu ercache A file system 080 4103 Operating Systems 1326 O without a unified buffer cache memorymapped IO lO using read and write bu ercache M V file system B B Karki LSU Recovery vl Files and directories are kept both in main memory and on disk 9 System failure can result in loss of data or in data inconsistency l Consistency checking 9 Compares data in directory structure information in memory cache or in disk with data blocks on disk and tries to fix inconsistencies l Back up and restore 4x Use system programs to back up data from disk to another storage device floppy disk magnetic tape tr Recover lost file or disk by restoring data from backup tr Backup cycle Full back up followed by incremental backups at later times or days 080 4108 Operating Systems 1327 BB Karki LSU Log Structured File Systems l Log structured file systems record each update to the file system as a transaction I All transactions are written to a log A transaction is considered committed once it is written to the log I The transactions in the log are asynchronously written to the file system When the file system is modified the transaction is removed from the log I If the file system crashes all remaining transactions in the log must still be performed 080 4108 Operating Systems 1328 BB Karki LSU Network File System NFS l An implementation and specification of a software system for accessing remote files across LANs or WANs as Integrated with the overall directory structure and interface of the client system I A clientservernetwork file system I Uses TCP or UDPIP protocol for networking l UNIX and PC operating systems support NFS 080 4108 Operating Systems 1329 BB Karki LSU NFS Cont l A set of interconnected workstations is viewed as a set of independent machines with independent file systems Allow sharing among these file systems in a transparent manner I A remote directory is mounted over a local file system directory The mounted directory looks like an integral subtree of the local file system 4 Files in the remote directory can then be accessed in a transparent manner r Subject to accessrights accreditation any file system or directory within a file system can be mounted remotely on top of any local directory 080 4108 Operating Systems 1330 BB Karki LSU NFS Cont l NFS specifications are independent of the media 4 Heterogeneous environment of different machines operating systems and network architectures lt9 Use of RPC primitives built on top of an External Data Representation XDR protocol l NFS specification distinguishes between the services provided by a mount mechanism and the actual remotefileaccess services It Uses two protocols J Mount protocol J NFS protocol 080 4108 Operating Systems 1361 BB Karki LSU Three Independent File Systems S 1 39 S2 LISI usr usr local shared dir2 dir1 l Three independent file systems and machines Only local files can be accessed at each machine 18 82 B B Karki LSU Mounting in NFS l Mounting 81 over U Users can use usrocadir1 on U l Cascading A file system can be mounted over another file system that is remotely mounted not local 030 4103 Operating Systems local Mounts 1333 b Cascading mounts BB Karki LSU NFS Mount Protocol l Establishes initial logical connection between server and client l Mount operation includes name of remote directory to be mounted and name of server machine storing it is Mount request is mapped to corresponding RPC and forwarded to mount server running on server machine Export list specifies local file systems that server exports for mounting along with names of machines that are permitted to mount them I Following a mount request that conforms to its export list the server returns a file handle a key for further accesses is eg a filesystem identifier and an inode number to identifythe mounted directory within the exported file system I The mount operation changes only the user s view and does not affect the server side 080 4108 Operating Systems 1334 BB Karki LSU NFS Protocol l Provides a set of remote procedure calls for remote file operations The procedures support the following operations t searching for a file within a directory iv reading a set of directory entries 47 manipulating links and directories 4r accessing file attributes 4 reading and writing files I NFS servers are stateless each request has to provide a full set of arguments av No openfiles table exists on the server side I Modified data must be committed to the server s disk before results are returned to the client I The NFS protocol does not provide concurrencycontrol mechanisms 080 4108 Operating Systems 1335 BB Karki LSU Three Major Layers of NFS Architecture l v UNIX filesystem interface based on the open read write and close calls and file descriptors l Virtual File System VFS layer distinguishes local files from remote ones and local files are further distinguished according to their filesystem types at The VFS activates filesystemspecific operations to handle local requests according to their filesystem types 4 Calls the NFS protocol procedures for remote requests I NFS service layer bottom layer of the architecture implements the NFS protocol 080 4108 Operating Systems 1336 BB Karki LSU Schematic View of NFS Architecture client server system cals interface VFS interface VFS interface other types of file systems system system UNIXfiIe NFS NFS UNIXfiIe network 080 4103 Operating Systems 1337 BB Kalki LSU Summary File system resides on secondary storage Disk partitions to support multiple file systems which can be mounted onto a logical file system File system structure Layered structure and Virtual file system VFS Disk space can be allocated to files using contiguous linked or indexed allocation methods Free space can be managed using bit vectors linked lists grouping and coun ng NFS network file systems based on clientserver paradigm allows access remotely located file systems Examples of file systems 4 Unix file system UFS as Windows file systems FAT FAT32 NTFS 4s Removable media file systems CDROMs DVD floppydisk 1888 080 4108 Operating Systems BB Karki LSU Example l Given a file of 100 blocks what is the minimum number of disk lO operations needed to insert a block in the middle of the file for the contiguous linked and indexed allocation strategies Assume that the FCB information and the block to be inserted are already in memory 080 4108 Operating Systems 1339 BB Karki LSU Example l Consider a file system on a disk that has both logical and physical block sizes of 512 bytes Assume that the information about each file is already in memory For each of the three allocation strategies contiguous linked and indexed answer these questions at How is the logicaltophysical mapping accomplished in the system For the indexed allocation assume that a file is always less than 512 blocks long at If we are currently at logical block 10 the last block access was block 10 and want to access logical block 4 how many physical blocks must be read from the disk 080 4108 Operating Systems 1340 BB Karki LSU MassStorage Systems Source Operating System Concepts by Silberschatz Galvin and Gagne 030 4103 Operating System 121 B B Karki LSU Topics l Disk Scheduling l Disk Management I RAID Structure l Tertiary Storage Devices 030 4103 Operating System 122 B B Karki LSU Disk Structure l V Disk drives are addressed as large 1dimensional arrays of logical blocks where the logical block is the smallest unit of transfer I The array is mapped into the sectors of the disk sequentially 7 Sector 0 is the first sector of the first track on the outermost cylinder 1 Mapping proceeds in order through that track then the rest of the tracks in that cylinder and then through the rest of the cylinders from outermost to innermost 030 4103 Operating System 123 B B Karki LSU Disk Structure track I rotation arm assembly CSC 4103 Operating System B B Karki LSU Disk Scheduling l 08 is responsible for using hardware efficiently 2 Having a fast access time and disk bandwidth for disk drives 4 Maximize throughput t Minimize mean response time and variance in response time I Access time has two major components 74 Seek time moving the heads to the cylinder containing the desired sector a Rotational latency waiting for the disk to rotate the desired sector to the disk head I Rotational speed Number of revolutions per minute r l Disk bandwidth 439 Total number of bytes transferred divided by the total time between the first request for service and the completion of the last transfer I Total access time seek time rotational latency transfer time I Seek andor rotational optimization based scheduling 030 4103 Operating System 125 B B Karki LSU Disk Scheduling Cont 1 l Several algorithms exist to schedule the servicing of disk lO requests 43gt To improve both the access time and bandwidth I We illustrate them with a request queue 0199 for lO blocks on cylinders in the following order 98 183 37 122 14 124 65 67 Head pointer 53 030 4103 Operating System 126 B B Karki LSU FC FS Firstcome firstserve Illustration shows total head movement of 640 cylinders queue 98 183 37 122 14 124 65 67 head starts at 58 O 14 37 5865 67 98 122124 183199 I I I II I II I I I I cs0 4103 Operating System 11 B B Karki LSU SSTF l SSTF shortestseektime first l Selects the request with the minimum seek time from the current head position I SSTF scheduling is a form of SJF scheduling may cause starvation of some requests I Illustration shows total head movement of 236 cylinders 030 4103 Operating System 128 B B Karki LSU SSTF Cont queue 98 183 37 122 14 124 65 67 head starts at 58 O 14 37 586567 98 122124 183199 030 4108 Operating System 29 B B Karki LSU SCAN l The disk arm starts at one end of the disk and moves toward the other end servicing requests until it gets to the other end of the disk where the head movement is reversed and servicing continues I Sometimes called the elevator algorithm l Illustration shows total head movement of 208 cylinders 030 4103 Operating System 1210 B B Karki LSU SCAN Cont 0 I CSC 4103 Operating System 1 4 queue 98 183 37 122 14 124 65 67 head starts at 53 37 536567 98 122124 I II I II 183199 I I I 1211 B B Karki LSU CSCAN y l Provides a more uniform wait time than SCAN l The head moves from one end of the disk to the other servicing requests as it goes When it reaches the other end however it immediately returns to the beginning of the disk without servicing any requests on the return trip I Treats the cylinders as a circular list that wraps around from the last cylinder to the first one 030 4103 Operating System 1212 B B Karki LSU CSCAN Cont queue 98 183 37 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 1 i 030 4103 Operating Syslem 12 B B Kavki LSU CLOOK l Version of CSCAN l Arm only goes as far as the last request in each direction then reverses direction immediately without first going all the way to the end of the disk I Similar version of SCAN is called LOOK 030 4103 Operating System 1214 B B Karki LSU CLOOK Cont queue 98 18837 122 14 124 65 67 head starts at 53 0 14 37 536567 98 122124 183199 030 4108 Operating System 121 5 B B Karki LSU Other Scheduling Algorithms l Random 4r Useful for analysis and comparison purpose Prioritybased 4 Priority by process I LIFO Last in first out NStepSCAN 4r SCAN of N records at a time I FSCAN 4r NstepSCAN with N queue size at beginning of SCAN cycle 030 4103 Operating System 1216 B B Karki LSU Selecting a DiskScheduling Algorithm l SSTF is common and has a natural appeal I SCAN and CSCAN perform better for systems that place a heavy load on the disk I Performance depends on the number and types of requests I Requests for disk service can be influenced by the file allocation method csc 4103 Operating System 1217 B B Karki LSU Disk Management Lowlevel formatting or physical formatting Dividing a disk into sectors that the disk controller can read and write To use a disk to hold files the operating system still needs to record its own data structures on the disk 4 Partition the disk into one or more groups of cylinders 4 Logical formatting or making a file system Boot block initializes system The bootstrap is stored in ROM Bootstrap loader program Methods such as sector sparing or sector slipping used to handle bad blocks 030 4103 Operating System 1218 B B Karki LSU Booting from a Disk in Windows 2000 partition 1 partition 2 partition 3 partition 4 boot MBR code table partition boot partition 080 4108 Operating System 1219 B B Karki LSU SwapSpace Management l Swapspace Virtual memory uses disk space as an extension of main memory I Swapspace can be carved out of the normal file systemor it can be in a separate disk partition I Swapspace management r 43 BSD allocates swap space when process starts holds text segment the program and data segment 74 Kernel uses swap maps to track swapspace use at Solaris 2 allocates swap space only when a page is forced out of physical memory not when the virtual memory page is first created I Similar use by Linux 030 4103 Operating System 1220 B B Karki LSU Swap Maps l The data structures for swapping on Linux systems i swap area page 39 slot 39 swap partition or swap file swap map 1 O 3 O 1 0804106 Operating System 2 2 B B Kern LSU RAID Structure l RAID redundant arrays of inexpensive or now independent disks l Improvement of reliability via redundancy Mirroring or shadowing keeps duplicate of each disk I Improvement in performance via parallelism a Data stripping bits of each byte or blocks of a file are stripped across multiple disks 439 Use a group of disks as one storage unit I RAID schemes improve performance and reliability of the storage system by storing redundant data 030 4103 Operating System 1222 B B Karki LSU RAID Levels l RAID Levels Schemes to provide high redundancy at low cost by using the idea of stripping combined with parity bits I P parity error indicating bits C a second copy of data 080 41 Operating System Ei j jti a FWD 0 nonredundant striping 3888 b FWD 1 mirrored disks 8 8EiEiEi 0 RAID 2 memorystyie errorcorrecting codes d RAM 3 bitinterieaved parity e FWD 4 biockinterieaved parity Ei i FWD 5 biockinterieaved distributed parity a HAD 6 P O redundanc B Karki LSU stripe mirror mirror mirror mirro 080m Operamgsmem b RAID 1 o with a sinnle disk failure B B Kern LSU 3 Disk Attachment l Disks may be attached one of two ways I Host attached via a local lO port 4 Simple PC bus SCSI FC buses l Network attached via a network connection NFS and CIFS are common protocols 4 Remote host and distributed files system Remoteprocedure calls RPCs 030 4103 Operating System 1225 B B Karki LSU NetworkAttached Storage LANWAN Client client csc 41 03 Operating System 1225 B B Karki LSU StorageArea Network l Common in large storage environments I Multiple hosts attached to multiple storage arrays flexible client server client storage LAN WAN array server client storage SAN array dataprocessing Itape web content IIbrary provider 0504103 Operating System 2 27 B B Kern LSU StableStorage Implementation l Writeahead log scheme requires stable storage I To implement stable storage 4 Replicate information on more than one nonvolatile storage media with independent failure modes J Maintain two physical blocks for each logical block at Update information in a controlled manner to ensure that we can recover the stable data after any failure during data transfer or recovery 030 4103 Operating System 1228 B B Karki LSU Tertiary Storage Devices l Low cost is the defining characteristic of tertiary storage I Generally tertiary storage is built using removable media I Common examples of removable media are floppy disks CDROMs tapes other types are available 030 4103 Operating System 1229 B B Karki LSU Removable Disks l Floppy disk thin flexible disk coated with magnetic material Y enclosed in a protective plastic case 4 Floppies hold about 1 MB 4 Removable magnetic disks can hold more than 1 GB and be nearly as fast as hard disks as Laser heat is used to amplify a large weak magnetic field to record a bit I A magnetooptic disk records data on a rigid platter coated with magnetic material 4 Laser light is used to read data Kerr effect 4 The head flies far from the disk surface which is covered with a protective layer of plastic or glass l Optical disks employ special materials that are altered by laser light to have dark and light spots 030 4103 Operating System 1230 B B Karki LSU WORM Disks I WORM Write Once Read Many Times disks can be written only once I To write a bit the drive uses a laser light to burn a small hole through the aluminum sandwiched between two glass or plastic platters 7 information can be destroyed but not altered r Very durable and reliable I Read Onlydisks such ad CDROM and DVD come from the factory with the data prerecorded l The data on ReadWrite disks can be modified over and over 030 4103 Operating System 1231 B B Karki LSU Tapes y l Compared to a disk a tape is less expensive and holds more data but random access is much slower l Useful for backup copies of disk data holding huge volumes of data I Large tape installations typically use robotic tape changers that move tapes between tape drives and storage slots in a tape library I Room to improve areal density 030 4103 Operating System 1232 B B Karki LSU Operating System Issues V l Two major 08 jobs 4 Manage physical devices 42 Present a virtual machine abstraction to applications I For hard disks the 08 provides two abstraction i Raw device an array of data blocks File system the OS queues and schedules the interleaved requests from several applications I How the 08 does it for removable storage media 030 4103 Operating System 1233 B B Karki LSU Application Interface l 08 handles removable disks like fixed disks 4 A new cartridge is formatted and an empty file system is generated on the disk i Provide basic operations I Read write and seek for disks l Locate read and space for tapes I Tapes are presented as a raw storage medium 4 Application does not not open a file on the tape it opens the whole tape drive as a raw device ir Usually the tape drive is reserved for the exclusive use of that application Since the 08 does not provide file system services the application must decide how to use the array of blocks 030 4103 Operating System 1234 B B Karki LSU File Naming y I How to name files on removal media I Difficulty arises the same removable cartridge will be used in different computers I Contemporary OSs generally leave the name space problem unsolved for removable media and depend on applications and users to figure out how to access and interpret the data I Some kinds of removable media eg CDs are so well standardized that all computers use them the same way csc 4103 Operating System 1235 B B Karki LSU Hierarchical Storage Management HSM I A hierarchical storage system extends the storage hierarchy beyond primary memory and secondary storage to incorporate tertiary storage 4 Usually implemented as a jukebox of tapes or removable disks I Usually incorporate tertiary storage by extending the file system a Small and frequently used files remain on disk at Large old inactive files are archived to the jukebox l HSM is usually found in supercomputing centers and other large installations that have enormous volumes of data 030 4103 Operating System 1236 B B Karki LSU Performance Speed l Two aspects of speed in tertiary storage are bandwidth and latency l Bandwidth is measured in bytes per second 4 Sustained bandwidth average data rate during a large transfer of bytestransfer time Data rate when the data stream is actually flowing as Effective bandwidth average over the entire lO time including seek or locate and cartridge switching Drive s overall data rate I Access latency amount of time needed to locate data w Access time for a disk move the arm to the selected cylinder and wait for the rotational latency lt 35 milliseconds Access on tape requires winding the tape reels until the selected block reaches the tape head tens or hundreds of seconds Generally say that random access within a tape cartridge is about a thousand times slower than random access on disk 030 4103 Operating System 1237 B B Karki LSU Performance Reliability l A fixed disk drive is likely to be more reliable than a removable disk or tape drive I An optical cartridge is likely to be more reliable than a magnetic disk or tape l A head crash in a fixed hard disk generally destroys the data whereas the failure of a tape drive or optical disk drive often leaves the data cartridge unharmed csc 4103 Operating System 1238 B B Karki LSU Performance Cost y l Main memory is much more expensive than disk storage I The cost per megabyte of hard disk storage is competitive with magnetic tape it only one tape is used per drive I The cheapest tape drives and the cheapest disk drives have had about the same storage capacity over the years I Tertiary storage gives a cost savings only when the number of cartridges is considerably larger than the number of drives 030 4103 Operating System 1239 B B Karki LSU Price per Megabyte of DRAM From 1981 to 2004 1280 640 320 160 8O 40 SISMB 20 10 08 128 MB 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 Year 512 MB 080 4103 Operatmg System 1240 B B Karkw LSU Price per Megabyte of Magnetic Hard Disk From 1981 to 2004 MB 05 02 005 002 0004 BOIGB I I I I I I I I 39 39 0001 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 Year 0804105 Operatmg System 2 B B KarkI LSU Price per Megabyte of a Tape Drive From 19842004 MB 72 GB 320 GB 1 84 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 Year 0804106 Operatmg System 1242 B B Karkr LSU Summary l Disk drives are major secondarystorage lO device I Disk scheduling algorithms aim to improve the effective bandwidth throughput the average response time and the variance in response time 339 FCFS SSTF SCAN CSCAN LOOK and CLOOK algorithms l 08 manages the disk blocks and swapspace as Formatting partitioning and creating file systems 4 Allocating swapspace l RAID improves performance and reliability 4 Redundant disks t Different levels of RAID algorithms l Disk attachment using the local lO ports or a network connection I Tertiary storage includes disk and tape drives that use removal media 3 08 provides filesystem interface or raw interface I Performance is dependent on bandwidth latency and reliability 030 4103 Operating System 1243 B B Karki LSU Question 1 l Suppose that a disk drive has 5000 cylinders numbered 0 to 4999 The drive is currently serving a request at cylinder 143 and the previous request was at cylinder 125 The queue of pending requests in FIFO order is 86 1470 913 1774 948 1509 1022 1750 130 Starting from the current head position what is the total distance in cylinders that the disk arm moves to satisfy all pending requests for each of the following diskscheduling algorithms FCFS SSTF SCAN LOOK CSCAN CLOOK 943 030 4103 Operating System 1244 B B Karki LSU Question 2 I From elementary physics we know that when an object is subjected to a constant acceleration a the relationship between distance dand time t is given by d 05 at2 Suppose that during a seek the disk in the question 1 accelerates the disk arm at a constant rate for the first half of the seek then decelerates the disk arm at the same rate for the second half of the seek Assume that the disk can perform a seek to an adjacent cylinder in 1 ms and a fullstroke seek over all 5000 cylinders in 18 ms The distance of a seek is the number of cylinders that the head moves Explain why the seek time is proportional to the square root of the seek distance 1 Write an equation for the seek time as a function of the seek distance The equation should be of the form t X ytL where t is the time in ms and L is the seek distance in cylinders at Calculate the total seek time for each of the schedules in the question 1 Determine which schedule is the fastest has the smallest total seek time 030 4103 Operating System 1245 B B Karki LSU Question 3 l Suppose that the disk in the question 2 rotates at 7200 RPM 7 What is the average rotational latency of this disk drive 4 What seek distance can be covered in the time that you found for the first part 030 4103 Operating System 1246 B B Karki LSU lO Systems Source Operating System Concepts by Silberschatz Galvin and Gagne 080 4108 Operating System BB Karki LSU Overview 080 4108 Operating System Computer does HO and processing 4 IO can be a major job browse web or edit a file a OS manages lO devices and operations Two conflicting trends J A wide variety of HO devices I Standardization of software and hardware interfaces lO Hardware Application lO Interface Kernel lO Subsystem Transforming lO Requests to Hardware Operations Streams Performance BB Karki LSU O Hardware l A variety of HO devices I Common concepts 4 Port a connection point 4 Bus daisy chain J PCI bus 4 Controller Simple controller or a host adapter I lO transfer mechanism at Direct lO instructions at Memorymapped HQ 080 4108 Operating System 39 BB Karki LSU A Typical PC Bus Structure dis monitor processor cache bridgememory controller 3 l Dr l w egge graphics controller SCSI controller expansion bus Interface keyboard serial port parallel pon 080 41 13 Operating System BB Karki LSU lO Port Registers l Status register 4 Read to indicate command completion data availability device error I Control register 139 Write to start a command or to change a device mode I Datain register iv Read to get input I Dataout register 139 Write to send the output 080 4108 Operating System 39 BB Karki LSU Polling l Protocol for interaction between the host and a controller 4 Simple handshaking notion using bits I Determines state of device at busy in commandready 4 error I Busywaiting or polling loop 41gt Reading the status register over and over until the busy bit becomes clear 080 4108 Operating System 39 BB Karki LSU Interrupts l CPU Interrupt request Iine triggered by HG device 4 Interrupt handler receives interrupts l Two interrupt request lines 9 Nonmaskable for events such as unrecoverable memory errors Maskable to ignore or delay some interrupts l Interrupt mechanism 9 Interrupt vector to dispatch interrupt to correct handler Based on priority I Interrupt mechanism also used for Exceptions dividing by zero attempting to execute a privileged instruction from user mode Virtualmemory paging page fault System calls executes a trap Managing flow control eg interrupting a disk read Timers 4 4 a 4 080 4108 Operating System BB Karki LSU InterruptDriven V0 Cycle CPU IO controller 1 device driver initiates lO initiates lO l CPU executing checks lor interrupts between instructions I I I input ready output mplete or error generates interrupt signal CPU receiving interrupt transfers control to interrupt handler interrupt handler processes ata returns from interrupt CPU resumes processing of interrupted task cscmoe Operating By B B Karkr LSU Intel Pentium Processor EventVector Table vector number description 0 divide error 1 debug exception 2 null interrupt 3 breakpoint 4 INTOdetected overflow 5 bound range exception 6 invalid opcode 7 device not available 8 double fault 9 coprocessor segment overrun reserved 10 invalid task state segment 11 segment not present 12 stack fault 13 general protection 14 page fault 15 Intel reserved do not use 16 floatingpoint error 17 alignment check 18 machine check 19 31 Intel reserved do not use 0804108 ope 32 255 maskable interrupts Kerk LSU Direct Memory Access l Programmed lO PIO 4 Watch status bits and feed data into a controller register one byte at a time 4 PIO is not useful for large data movement I Directmemoryaccess DMA controller a A special purpose processor to bypass CPU to transfer data directly between lO device and memory at CPU writes the address of a DMA commandblock into DMA controller which then operates the memory bus directly as Handshaking between the DMA and device controllers occurs using DMArequest and DMAacknowledge wires 4 Cycle stealing preventing CUP from accessing main memory 1810 CSC 4108 Operating System BB Karki LSU DMA Transfer 1 device driver is told to transfer disk data to buffer at address X 5 DMA controller 2 device driver tells transfers bytes to disk controller to buffer X increasing transfer C bytes memory address from disk to buffer and decreasing C at address X until C O DMAbus interrupt controller 6 when G 0 DMA interrupts CPU to signal transfer completion I CPU memogy bus x memory l DP IN 3 disk controller initiates D A transfer lDE disk COHtFOllel 4 disk controller sends each byte to DMA controller cscznoc Operating System B B kam LSU Application lO Interface l lO system calls encapsulate device behaviors in generic classes I Devicedriver layer hides differences among lO controllers from kernel To interface the hardware to OS I Devices vary in many dimensions 4 Characterstream or block Sequential or randomaccess Synchronous or asynchronous Sharable or dedicated Speed of operation readwrite read only or write only kf r 1812 080 4108 Operating System BB Karkl LSU A Kernel lO Structure kernel 9 t5 5 kernel O subsystem 8 SCSI keyboard mouse PCI bus floppy ATAP device device device 0 0 device device device driver driver driver driver driver driver SCSI keyboard mouse PCI bus floppy ATAPl device device device device device device m controller controller controller controller controller controller I E 3 ATAPl SCSI OPPY39 devices devices keyboard mouse PCI bus disk dlsks drives tapes drives How the Orelated portions of the kernel are structured in the software layers 080 4103 Operating System 1313 B B Karki LSU Characteristics of V0 Devices 050 4108 Operating Systen aspect variation example datatransfer mode character terminal block disk sequential modem access method random CDROM transfer schedule SynChronous tape asynchronous keyboard Sharin dedicated tape 9 sharable keyboard device speed latency seek time transfer rate delay between operations read only CDROM lO direction write only graphics controller read write disk 1814 B B Karkl LSU Block and Character Devices l Blockdevice interface transfer blocks of data 4 Disk device Commands read write seek Raw lO or filesystem access Memorymapped file access possible I Characterstream interface transfer byte by byte v Keyboards mice serial ports 4v Commands get put v Libraries layered on top allow lineatatime access 1815 080 4108 Operating System BB Karkl LSU Network Devices l Network lO interface network socket interface Unix and Windows NT Separates network protocol from network operation 41 Includes select functionality to manage a set of sockets l Approaches vary widely pipes FlFOs streams message queues mailboxes 1816 080 4108 Operating System BB Karkl LSU Clocks and Timers l Three basic functions 4 Provide current time Provide elapsed time i Set a timer to trigger an operation at a specified time I Hardware a programmable interval timer I Used fortimings periodic interrupts eg CPU scheduler 080 4108 Operating System 1317 BB Karki LSU Blocking and Nonblocking lO l Blocking process suspended until lO completed 4 Easy to use and understand it Insufficient for some needs I Nonblocking lO call returns as much as available it User interface data copy buffered HO 9 Implemented via multithreading iv Returns quickly with count of bytes read or written I Asynchronous process runs while lO executes Difficult to use at O subsystem signals process when O completed 1818 080 4108 Operating System BB Karkl LSU Kernel lO Subsystem l Kernels provide many services related to lO 4 Built on the hardware and device driver infrastructure l Scheduling 4 Some O request ordering via perdevice queue it Some 085 try fairness l Buffering store data in memory while transferring between devices To cope with device speed mismatch 4 To cope with device transfer size mismatch 4 To maintain copy semantics 1819 080 4108 Operating System BB Karkl LSU Sun Enterprise 6000 DeviceTransfer Rates gigaplane bus SBUS SCSI bus fast ethernet hard disk etherne1 laser printer modem mouse keyboard 1320 080 4108 Operating System 55 Karkl LSU More O Services l Caching fast memory holding copy of data amp Alwaysjusta copy amp Key to performance Spooling hold output for a device 4 If device can serve only one request at a time eg printing l Device reservation provides exclusive access to a device System calls for allocation and deallocation Watch out for deadlock l Error handling 4 OS can recover from disk read device unavailable transient write failures 4 Most return an error number or code when lO request fails 4 System error logs hold problem reports 1821 080 4108 Operating System BB Karki LSU Kernel Data Structures l Kernel keeps state info for lO components including open file tables network connections character device state I Many complex data structures to track buffers memory allocation dirty blocks I Some use objectoriented methods and message passing to implement lO 1822 080 4108 Operating System BB Karkl LSU UNIX V0 Kernel Structure CSCM systemwide openfile table file descriptor perprocess openfile table quot i d filesystem record inode pointer pointer to read and write functions pointer to select function pointer to ioctl function pointer to close function table userprocess memory networking socket record pointer to network into pointer to read and write functions pointer to select function pointer to ioctl function pointer to close function r information table kernel memory lO Requests to Hardware Operations I Consider reading a file from disk for a process Determine device holding tile 43 s Translate name to device representation Physically read data from disk into butter 2 Make data available to requesting process Return control to process 39t The life cycle of an lO request 050 4108 Ope39atiiig System 18 24 usei requesl lO mess lO completed inpuldala Bimllablei or output mmpieleu ssleiii caii ieluin keiriEl can mm iio sulsslem sailsly iequest liaiisiei uala ii appiopnale to process ieiuin co ltleilon ai e i iioni sysleiii caii in i or code send iequesila device uiivei black pioceSs ir Keinel appropiiale iio subsystem neleirnine wnicn iio process request issue 3355 ems campieledi indicate stale dllVEl block will lniellupied mange 0 lO subsystem Mew ieceive interrupt slaie uencarcaiiiioiiei commands mm data in aevmeuiivei uiiiiei ii inpul signal to unblock uewce driver iiileiiiipl rnaniloi dEVlCEi inleirupi wnen io cumpleled device coniiuiiei geneiale interrupt lO compieleu STREAMS STREAM a tullduplex communication channel between a user process and 39a device A STREAM consists of STREAM head inten aces with the user process l driver end interfaces with the device zero or more STREAM modules between them Each module contains a read queue and a write queue Message passing is used to communicate between queues csc 4108 Ope39atlng System user process stream head modules read queue write queue i 1 read queue write queue i i read queue write queue i 1 read queue write queue driver end device Performance character typed l lO a major factor in system performance Demands CPU to execute device driver kernel lO code process scheduling Context switches due to interrupts Data copying Network traffic especially stressful 4 network e lntercomputer communications 050 4108 Ope39atmg System sending System reBEiVing System Improving Performance l Reduce number of context switches l Reduce data copying l Reduce interrupts by using large transfers smart controllers polling I Use DMA l Move processing primitives into hardware device controllers l Balance CPU memory bus and HG performance for highest throughput 1827 080 4108 Operating System BB Karki LSU DeviceFunctionality Progression elderations 080 4103 Operating System cost new algorithm application code kernel code devicedriver code devicecontroller code hardware increased device code hardware 1328 88 Karki LSU Summary I Basic lO hardware elements are buses device controllers and devices I Two ways of data transfer between devices and memory Programmed lO DMA controller I Systemcall interface provides a wide range of functionality I Kernel s lO subsystem provides services such as lO scheduling buffering spooling error handling device reservation and translation I STREAMS allows a fullduplex connection between a device driver and a userlevel process I lO system calls consume CPU time a lot because of the many layers of software between a physical device and the application 1829 080 4108 Operating System BB Karki LSU OperatingSystem Structures Source Operating System Concepts by Silberschatz Galvin and Gagne 080 4108 Operating Systems 21 B B Karki LSU OS Basics CSC 4108 Operating Systems 22 Explore 4 What components OS has 4 What services OS provides rs How they are provided Structuring OS Installation Customization Boot OS Components OS Services User OS Interface System Calls and Their Types System Programs OS Design and Implementation OS Structure Layered approach Microkernels Modules Virtual machines OS Generation System Boot B B Karki LSU Common Operating System Components l OS is large and complex system Consists of different components each with well defined inputs outputs and functions I A modern OS supports the following components Process Management Main Memory Management File Management O System Management SecondaryStorage Management Networking Protection System 080 4108 Operating Systems 23 B B Karki LSU Process Management l A process is a program in execution It is the unit of work in a system It can be running a program or job eg wordprocessing program compiler program sending output to a printer simulation program I System consists of a collection of processes related to OS and user I A process needs resources CPU time memory space files and HG devices to accomplish its task I A process may require input or initialization data I The OS is responsible for all process management activities r process creation and deletion e process suspension and resumption scheduling r mechanisms for J process synchronization J process communication J deadlock handling 080 4108 Operating Systems 24 B B Karki LSU MainMemory Management l Main memory an array of words or bytes each with its own address 7 A repository of quickly accessible data shared by the CPU and HG devices 390 Programs with the data they access must be in main memory for the CPU to execute them l 08 is responsible for all memory management activities it tracking which parts of memory are currently being used and by whom s deciding which processes to load when memory space becomes available 4amp allocating and deallocating memory space as needed 080 4108 Operating Systems 25 B B Karki LSU File Management l Computers can store information in different physical media eg disks tapes l 08 provides a logical an abstract view of information storage ie define a logical storage unit called the file a 08 maps files into physical media and accesses these files via the storage devices such as disk drive I A file is a collection of related information program or data defined by its creator l 08 is responsible for all file management activities a file creation and deletion 6 directory creation and deletion 6 support of primitives for manipulating files and directories 4 mapping files onto secondary storage a file backup on stable nonvolatile storage media 080 4108 Operating Systems 26 B B Karki LSU lO System Management l 08 hides the peculiarities of specific hardware devices from the user by defining an lO subsystem l The lO subsystem consists of 1 buffering caching and spooling r a general devicedriver interface as drivers for specific devices I The lO subsystem interfaces to other system components manages devices transfers data and detects lO completion 080 4108 Operating Systems 27 B B Karki LSU SecondaryStorage Management I The computer system must provide secondary storage to back up main memory 4 Disk used as both the source and destination for processing l 08 is responsible for disk management activities 7 free space management 4 storage allocation 7 disk scheduling 080 4108 Operating Systems 28 B B Karki LSU Networking l Networking is of primary concern in a distributed system which is a collection processors that do not share memory or a clock r Different processors are connected through a communication network I Network design should consider Message routing 4 Connection strategies Security l Communication takes place using a protocol eg FTP NFS http 080 4108 Operating Systems 29 B B Karki LSU Protection System l Protection refers to a mechanism for controlling access by programs processes or users to both system and user resources I The protection mechanism must at distinguish between authorized and unauthorized usage 4 specify the controls to be imposed it provide a means of enforcement 080 4108 Operating Systems 210 B B Karki LSU OS Services Provide certain services to programs and to the users of those programs 080 4108 Operating Systems User interface commandline batch interface and GUI Program execution system capability to load a program into memory and to run it lO operations A running program may require lO which may involve a file or an lO device Filesystem manipulation program capability to read write create and delete files Communications exchange of information between processes executing either on the same computer or on different systems tied together by a network Implemented via shared memory or message passing Error detection ensure correct computing by detecting errors in the CPU and memory hardware in HQ devices or in user programs 211 B B Karki LSU Additional OS Functions Additional functions exist not for helping the user but rather for ensuring efficient system operations 39 Resource allocation allocating resources to multiple users or multiple jobs running at the same time 39 Accounting keep track of and record which users use how much and what kinds of computer resources for account billing or for accumulating usage statistics 39 Protection ensuring that all access to system resources is controlled 080 4108 Operating Systems 212 B B Karki LSU User OS Interface l Two common approaches for users to interface with OS I Command line interface CLI or command interpreter a Shell program that is executed automatically when ajob is initiated or a user logs on a Get and execute the next userspecified command a UNIX l Graphical user interface GUI 4 Mousebased windowandmenu system 0 Icons representing files programs actions etc at Windows I Many systems now include both CLI and GUI interfaces 4 Microsoft Windows is GUI with CLI command shell a Apple Mac OS X as Aqua GUI interface with UNIX kernel underneath and shells available a Solaris is CLI with optional GUI interfaces Java Desktop KDE 080 4108 Operating Systems 213 B B Karki LSU System Calls l System calls provide an interface between a process and the OS I Typically written in a highlevel language C or C l Even simple programs make heavy use of 08 a But users never see this level of detail I Mostly accessed by programs via a highlevel application program interface API rather than direct system call use a Win32 POSIX and Java APIs 080 4108 Operating Systems 214 B B Karki LSU Example of System Calls l System call sequence to copy the contents of one file to another file 08041 source file I l destination file Example System Call Sequence Acquire input file name Write prompt to screen Accept input Acquire output file name Write prompt to screen Accept input Open the input file if file doesn39t exist abort Create output file if file exists abort oop Read from input file Write to output file Until read fails Close output file Write completion message to screen Terminate normally am LSU Example of Standard API l Considerthe ReadFileO function in the Win32 API a function for reading from a file return value EOOL ReadFile C HANDLE file LPVOID buffer bytes To Read bytes Read parameters DW RD function name LPOVERLAPPED ovl l A description of the parameters passed to ReadFileO ex HANDLE file thefile to be read 9 LPVOID buffer a buffer where the data will be read into and written from DWORD bytesToRead the number of bytes to be read into the buffer LPDWORD bytesRead the number of bytes read during the last read LPOVERLAPPED ovI indicates if overlapped IIO is being used 0304103 OperatingSystems s s 75 216 E El Kern LSU System Call Implementation l Typically a number associated with each system call Fr Systemcall interface maintains a table indexed according to these numbers I The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values I The caller need know nothing about how the system call is implemented an Just needs to obey API and understand what 08 will do as a result call if Most details of OS interface hidden from programmer by API J Managed by runtime support library set of functions built into libraries included with compiler 080 4108 Operating Systems 217 B B Karki LSU API System Call OS Relationship user mode mode kernel user application open system call interface 030 4103 Operaung Syaems open Implementation of open system call retu rn E E Kam LSU System Call Parameter Passing l Methods to pass parameters between running program and OS 3 Pass parameters in registers Store parameters in a table or a block in memory and the table address is passed as a parameter in a register Push store parameters onto the stack by the program and pop off the stack by OS e X register X parameters for call use parameters Code for load address X from table X system call 13 system call 13 user program oso 4103 Ope operating system B Karki LSU Five Categories of System Calls l Process control File management I Device management I Information maintenance I Communications 080 4108 Operating Systems 220 B B Karki LSU Process Control end abort load execute create process terminate process get process attributes set process attributes wait time wait event signal event allocate and free memory 080 4108 Operating Systems 221 B B Karki LSU MSDOS Execution free memory I The MSDOS operating system is a single tasking system free memory it The command interpreter is invoked process when the computer is started 4 It loads the program into memory and 90mmand runs it Interpreter command interpreter It does not create a new process kernel kernel 3 b At System Startup Running a Program 050 4103 Operating Systems 222 B B Karki LSU UNIX Running Multiple Programs l FreeBSD is a multitasking system a v a 9 t Shell of the user s choice is run on user s logging on Shell may continue running while another program is executed Shell executes a fork system call to create a new process and the selected program is loaded into memory via an exec system call and then executed Process may run interactively or in the background Exit call once the process is done 080 4103 Operating Systems 223 process D free memory process C interpreter process B kernel B B Karki LSU File Management Common systems calls dealing with files and directories I create file delete file I open close I read write reposition I get file attributes set file attributes 080 4108 Operating Systems 224 B B Karki LSU Device Management Similarity between files and lO devices results in similar device system calls some 08 even merges two into a combined file device structure I request device release device I read write reposition I get device attributes set device attributes I logically attach or detach devices 080 4108 Operating Systems 225 B B Karki LSU Information Maintenance System calls for transferring information between the user program and OS I get time or date set time or date I get system data set system data I get process file or device attributes I set process file or device attributes 080 4108 Operating Systems 226 B B Karki LSU Communication System calls for transferring information between the user program and OS I create delete communication connection I send receive message I transfer status information I attach or detach remote devices 080 4108 Operating Systems 227 B B Karki LSU Communication Models l Message passing model Information is exchanged through inter process communication facility provided by OS I Shared memory model Processes use map memory system calls to gain access to regions of memory owned by other processes process A E7 process A E1 shared memory 2 process B E process B E kernel kernel E Message Passing Shared Memory 080 4103 Operating Systems 228 I B B Karki LSU System Programs l System programs provide a convenient environment for program development and execution They can be divided into 4 File management Manipulate files and directories Status information Date disk space number of users in File modification Text editors a Programming language support Compilers assemblers debuggers etc Program loading and execution Loaders linkage editors 2 Communications Connection messages remote login data transfer I Most users view of the operation system is defined by system programs not the actual system calls The system programs are actually user interfaces to system calls I Application programs or system utilities 4 Web browsers word processors text formatters spreadsheets compilers plotting games 080 4108 Operating Systems 229 B B Karki LSU System Design Goals V l Designing a system requires defining specifications and goals of the system I Specifications choice of hardware and type of system I Goals user and system level I No unique solution to the problem of defining the requirements for an OS 1 Different requirements can result in a large variety of solutions for different systems 080 4108 Operating Systems 230 B B Karki LSU Mechanisms and Policies l Mechanisms determine how to do something I Policies decide what will be done I The separation of policy from mechanism allows maximum flexibility a Policy decisions can be changed later at Microkernelbased OS implements a basic set of primitive building blocks which are almost policy free I Policy decisions must be made for all resourceallocation and scheduling problems 080 4108 Operating Systems 231 B B Karki LSU System Implementation I Once an OS is designed it must be implemented l Traditionally written in assembly language 08 can now be written in higherlevel languages such as C or C 44 MSDOS in Intel 8088 assembly language 9 Linux in C I An 08 is easier to port move to some other hardware if it is written in a highlevel language 080 4108 Operating Systems 232 B B Karki LSU OS Structures l Organization of OS components to specify the privilege with which each component executes l Four structures as Monolithic All components contained in the kernel 4 Layered Topdown approach to separate the functionality and features into components at Microkernel Only essential components included in the kernel 7 Modules Objectoriented structure I Virtual Machines Run on the top of any OS 9 VMware and the Java Virtual machine 080 4108 Operating Systems 233 B B Karki LSU MS DOS System Structure I written to app ca on program provide the most functionality in the least space Notdivided into modules Although MSDOS has some structure its interfaces and levels of functionality are not well separated resident system program 080 4103 Operating Systems 234 B B Karki LSU UNIX System Structure 080 4103 CF I UNIX 08 consists of two separable parts Systems programs it Kernel is everything between the systemcall interface and physical hardware and has a large amount of functionality Kernel the users shells and commands compilers and interpreters system libraries systemcall interface to the kernel signals terminal handling character lO system terminal drivers file system swapping block lO system disk and tape drivers CPU scheduling page replacement demand paging virtual memory kernel interface to the hardware terminal controllers device controllers terminals memory controllers disks and tapes physical memory 235 B B Karki LSU Layered Approach l 08 is divided into a number of layers levels each built on top of lower layers The bottom layer layer 0 is the hardware the highest layer N is the user interface I With modularity layers are selected such that each uses functions operations and services of only lowerlevel layers I Design and implementation of 08 get simplified in the layered approach layer N r user interface gt El layer M 39 A new layer 1 operations layer 0 gt hidden layer M 1 hardware operations V existing 39 operations I 082 Layer Structure application application application I applicationprogramming interface I API extension I system kernel memory management task dispatching device management l I an I w I device driver device driver device driver i E39 device driver EA i l A descendant of MS DOS with multitasking and dualmode operation 050 4103 Operating Systems 237 B B Karki LSU Microkernel Structure l Moves as much from the kernel into user space a Result is a smaller kernel I Microkernel provides communication facility and minimal process and memory management 7 Communication between user modules or services using message passing l Benefits Easier to extend 08 as new services are added to user space it Easier to port 08 to new architectures due to smaller kernel as More reliable and secure less code is running in kernel mode 080 4108 Operating Systems 238 B B Karki LSU Windows NT ClientServer Structure Win32 39 032 39 POSIX application application application POSIXH application l Various applications Win32 082 and POSIX run in user space I Server for each application runs in user space I Message passing between client application programs and application servers runs in kernel space 080 4103 Operating Systems 239 B B Karki LSU Modules l Most modern operating systems implement kernel modules Uses objectoriented approach 9 Each core component is separate v Each talks to the others over known interfaces 1 Each is loadable as needed within the kernel I Overall similar to layers but with more flexible schedang device and Classes bus drivers miscellaneous modules Solaris Modular Approach core Solaris ernel loadable system calls STREAMS modules executable formats 080 4108 Operating System Mac OS X Structure application environments and common services A A V V kernel BSD environment Mach l Uses a hybrid structure I Below top layers is the kernel environment Mach microkernel and BSD kernel 080 4108 Operating Systems 241 B B Karki LSU Virtual Machines l A virtual machine a Treats hardware and OS kernel as though they were all hardware Application programs view everything under them as though the latter were a part of the machine itself z processes I A virtual machine provides an interface identical to the a underlying bare kernel hardware hardware OS creates the illusion of multiple processes a programming interface processes processes processes v v v kernel kernel kernel VM1 VM2 VM3 virtualmachine implementation hardware b each executing on its own processor with its own virtual memory 080 4103 Operating Systems Nonvirtual Machine Virtual Machine B B Karki LSU AdvantagesDisadvantages of VMs Provides complete protection of system resources since each virtual machine is isolated from all others Allows system development without disrupting normal system operation ls becoming popular as a means of solving system compatibility problems Sun Microsystems includes a virtual Intel machine built on the top of its native processor to run Windows OS and applications 7 Intel instructions need to be translated into native instruction Difficult to implement due to the effort required to provide an exact duplicate to the underlying machine r Virtual user and virtual monitor modes 080 4108 Operating Systems 243 B B Karki LSU VMware l VM Architecture Abstracts Intel 80X86 hardware into isolated virtual machines to run several guest operating systems as independently application application application application guest operating guest operating guest operating system system system free BSD Windows NT Windows XP virtual CPU virtual CPU virtual CPU virtual memory virtual memory virtual memory virtual devices virtual devices virtual devices virtualization layer l host operating system hardware 030 410 CPU memory lO devices Ka39kiy LSU Java Virtual Machine l Compiled Java programs are platformneutral bytecodes executed by a Java Virtual Machine JVM v JAVA runs on a virtual machine Java program Java API l JVM consists of gt Class loader Cass files a class loader a class verifier Java a runtime interpreter i host system Windows Linux etc l JustlnTime JIT compilers increase performance 6 Transforms the architectureneutral bytecodes into the host machine language 080 4103 Operating Systems 245 B B Karki LSU System Generation SYSGEN l Operating systems are designed to run on any class of machines 4 The system must be configured for each specific computer type a process called SYSGEN system generation I SYSGEN program obtains information on specific configuration of the hardware system and specific 08 options a CPU memory devices or The OS is adopted with recompilation linkinglibraries or executables l Booting starting a computer by loading the kernel 7 Bootstrap program code stored in ROM that is able to locate the kernel load it into memory and start its execution 080 4108 Operating Systems 246 B B Karki LSU System Boot l Operating system must be made available to hardware so hardware can start it I Small piece of code bootstrap loader locates the kernel loads it into memory and starts it I Sometimes twostep process where boot block at fixed location loads bootstrap loader I When power initialized on system execution starts at a fixed memory location I Firmware used to hold initial boot code 080 4108 Operating Systems 247 B B Karki LSU Summary 080 4108 Operating Systems 08 provides a number of services in Lowest level system calls allow a running program to make direct requests from 08 Higher level command interpreter or shell provides a mechanism to issue a request without writing a program System calls provide basic functions such as process control lO requests status control communication Design becomes flexible with separation of policy and mechanism 08 is now written in a higherlevel language A layered approach or microkernel results in modularity Virtualmachine concept treats both the OS kernel and hardware as though they were all hardware w JVM provides an architecturalneutral interface SYMGEN creates an OS for a particular machine configuration 248 B B Karki LSU
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'