1、Advanced Operating Systems Lecture notes,Dr. Clifford NeumanUniversity of Southern California Information Sciences Institute,CSci555: Advanced Operating Systems Lecture 1 August 26, 2011,Dr. Clifford NeumanUniversity of Southern California Information Sciences Institute,Administration,Instructors Dr
2、. Clifford Neuman csci555f11clifford.neuman.name Office hours SAL 212 Friday 12:55 PM 1:55 PM TA Nam Ma Namma at usc dot edu Office Hours TBD Class details http:/gost.isi.edu/555,Administration,Class Home Page http:/gost.isi.edu/555/ Announcements Syllabus Lecture Slides Reading listClass e-mail: cs
3、ci555usc.edu,Administrative Information,Reading list 65 papers and 20 book chapters Concentrated toward the first halfText Principles of Computer System Design By Saltzer and Kaashoek Also using second volume online,Administrative Information,Assignments 4 Reports, Due 11 p.m. Wednesday nights Resea
4、rch Paper Due: last class Exams Mid-Term: Friday, in October Final Exam: Friday, December 9,Administrative Information,DEN site - Blackboard Lecture webcast Class forum on DEN GradesLecture notes to be posted before lecture Academic Integrity READ IT It applies to you,Academic Integrity,I take Acade
5、mic Integrity Seriously Every year I have too many cases of cheating Last year I assigned multiple Fs for the class Occasionally students leave USC What is and is not OK I encourage you to work with others to learn the material Do not to turn in the work of others Do not give others your work to use
6、 as their own Do not plagiarize from others (published or not) Do not try to deceive the instructors See section on web site and assignments More guidelines on academic integrity Links to university resources Dont just assume you know what is acceptable.,Administration,Grading 20%: Reading Reports 2
7、0%: Midterm 20%: Final 30%: Research Paper 10%: Class Participation & Quizes Class forum participation In class participation,How to survive?,Read the survival guide How to read papers Read the papers in advance Be critical At least skim through Build your own notes Study group,What you should learn
8、 in this course,You will gain a basic understanding of distributed system concepts. You will develop intuition for which approaches work, and which dont. You will develop the ability to sense where bottlenecks lie in system design. You will remember where to look for more information when you are fa
9、ced with a distributed system problem. Above all, you will learn how to be critical of what you are told by system designers.,Some things an operating system does (review),Memory Management Scheduling / Resource management Communication Protection and Security File Management - I/O Naming Synchroniz
10、ation User Interface,Progression of Operating Systems,Primary goal of a distributed system: Sharing Progression over past years Dedicated machines Batch Processing Time Sharing Workstations and PCs Distributed Systems Devices,Structure of Distributed Systems,Kernel Basic functionality and protection
11、 Application Level Does the real work Servers Service and support functions needed by applications Many functions that used to be in Kernel are now in servers.,Structure of Distributed Systems,Network vs. OS Layering (No direct mapping, colors to stimulate discussion),Transport Layer,Physical,Link L
12、ayer,Network Layer,Application Layer,Presentation Layer,Session Layer,Characteristics of a Distributed System,Basic characteristics: Multiple Computers Interconnections Shared State,Why Distributed Systems are Hard,Scale: Numeric Geographic Administrative Loss of control over parts of the system Unr
13、eliability of Messages Parts of the system down or inaccessible Lamport: You know you have a distributed system when the crash of a computer you have never heard of stops you from getting any work done.,End-to-End Argument,QUESTION: Where to place distributed systems functions? Layered system design
14、: Different levels of abstraction for simplicity. Lower layer provides service to upper layer. Very well defined interfaces.,E2E Argument (continued),E2E paper argues that functions should be moved closer to the application that uses them.,E2E Argument (continued),Rationale: Some functions can only
15、be completely and correctly implemented with applications knowledge. Example: Reliable message delivery, security Encrypted e-mail Streaming media vs. Banking Applications that do not need certain functions should not have to pay for them.,E2E Counter-Argument,Performance Example: File transfer Reli
16、ability checks at lower layers detect problems earlier. Abort transfer and re-try without having to wait till whole file is transmitted. Abstraction Less repetition across apps Bottom line: “spread” functionality across layers.,Lecture Transition,This concludes the slides for lecture1. The following
17、 slides are for lecture 2.,CSci555: Advanced Operating Systems Lecture 2 September 2, 2011 Communication Models,Dr. Clifford NeumanUniversity of Southern California Information Sciences Institute,Outline: Communications Models,Communication Models: General concepts. Message passing. Distributed shar
18、ed memory (DSM). Remote procedure call (RPC) Birrel et al. Light-weight RPC Bershad et al. DSM case studies IVY Li et al. Linda Carriero et al.,COVERED LAST LECTURE,Communication Models,Support for processes to communicate among themselves. Traditional (centralized) OSs: Provide local (within single
19、 machine) communication support. Distributed OSs: must provide support for communication across machine boundaries. Over LAN or WAN.,COVERED LAST LECTURE,Communication Paradigms,2 paradigms Message Passing (MP) Distributed Shared Memory (DSM) Message Passing Processes communicate by sending messages
20、. Distributed Shared Memory Communication through a “virtual shared memory”.,COVERED LAST LECTURE,Message Passing,Basic communication primitives: Send message.Receive message.Modes of communication: Synchronous versus asynchronous. Semantics: Reliable versus unreliable.,.,Send,Sending Q,.,Receiving
21、Q,Receive,COVERED LAST LECTURE,Synchronous Communication,Blocking send Blocks until message is transmitted Blocks until message acknowledged Blocking receive Waits for message to be received Process synchronization.,COVERED LAST LECTURE,Asynchronous Communication,Non-blocking send: sending process c
22、ontinues as soon message is queued. Blocking or non-blocking receive: Blocking: Timeout. Threads. Non-blocking: proceeds while waiting for message. Message is queued upon arrival. Process needs to poll or be interrupted.,COVERED LAST LECTURE,Reliability of Communication,Unreliable communication: “be
23、st effort” - send and hope for the best No ACKs or retransmissions. Application must provide its own reliability. Example: User Datagram Protocol (UDP) Applications using UDP either dont need reliability or build their own (e.g., UNIX NFS and DNS (both UDP and TCP), some audio or video applications)
24、,COVERED LAST LECTURE,Reliability of Communication,Reliable communication: Different degrees of reliability. Processes have some guarantee that messages will be delivered. Example: Transmission Control Protocol (TCP) Reliability mechanisms: Positive acknowledgments (ACKs). Negative Acknowledgments (
25、NACKs). Possible to build reliability atop unreliable service (E2E argument).,COVERED LAST LECTURE,Distributed Shared Memory,Motivated by development of shared-memory multiprocessors which do share memory. Abstraction used for sharing data among processes running on machines that do not share memory
26、. Processes think they read from and write to a “virtual shared memory”.,COVERED LAST LECTURE,DSM 2,Primitives: read and write. OS ensures that all processes see all updates. Happens transparently to processes.,COVERED LAST LECTURE,DSM and MP,DSM is an abstraction! Gives programmers the flavor of a
27、centralized memory system, which is a well-known programming environment. No need to worry about communication and synchronization. But, it is implemented atop MP. No physically shared memory. OS takes care of required communication.,COVERED LAST LECTURE,Caching in DSM,For performance, DSM caches da
28、ta locally. More efficient access (locality). But, must keep caches consistent. Caching of pages for of page-based DSM. Issues: Page size. Consistency mechanism.,COVERED LAST LECTURE,Approaches to DSM,Hardware-based: Multi-processor architectures with processor-memory modules connected by high-speed
29、 LAN (E.g., Stanfords DASH). Specialized hardware to handle reads and writes and perform required consistency mechanisms.,COVERED LAST LECTURE,Approaches to DSM,Page-based: Example: IVY. DSM implemented as region of processors virtual memory; occupies same address space range for every participating
30、 process. OS keeps DSM data consistency as part of page fault handling.,COVERED LAST LECTURE,Approaches to DSM,Library-based: Or language-based. Example: Linda. Language or language extensions. Compiler inserts appropriate library calls whenever processes access DSM items. Library calls access local
31、 data and communicate when necessary.,COVERED LAST LECTURE,DSM Case Studies: IVY,Environment:”loosely coupled” multiprocessor. Memory is physically distributed. Memory mapping managers (OS kernel): Map local memories to shared virtual space. Local memory as cache of shared virtual space. Memory refe
32、rence may cause page fault; page retrieved and consistency handled.,COVERED LAST LECTURE,IVY,Issues: Read-only versus writable data. Locality of reference. Granularity (1 Kbyte page size). Bigger pages versus smaller pages.,COVERED LAST LECTURE,IVY,Memory coherence strategies: Page synchronization I
33、nvalidation Write broadcast Page ownership Fixed: page always owned by same processor Dynamic,COVERED LAST LECTURE,IVY Page Synchronization,Invalidation: On write fault, invalidate all copies; give faulting process write access; gets copy of page if not already there. Problem: must update page on re
34、ads. Write broadcast: On write fault, fault handler writes to all copies. Expensive!,IVY Memory Coherence,Paper discusses approaches to memory coherence in page-based DSM. Centralized: single manager residing on a single processor managing all pages. Distributed: multiple managers on multiple proces
35、sors managing subset of pages.,Linda,DSM: tuple space. Basic operations: out (data): data added to tuple space. in (data): removes matching data from TS; destructive. read (data): same as “in”, but tuple remains in TS (non-destructive).,Linda Primitives: Examples,out (“P”, 5, false) : tuple (“P”, 5,
36、 false) added to TS. “P” : name Other components are data values. Implementation reported on the paper: every node stores complete copy of TS. out (data) causes data to be broadcast to every node.,Linda Primitives: Examples,in (“P”, int I, bool b): tuple (“P”, 5, false) removed from TS. If matching
37、tuple found locally, local kernel tries to delete tuple on all nodes.,Remote Procedure Call,Builds on MP. Main idea: extend traditional (local) procedure call to perform transfer of control and data across network. Easy to use: analogous to local calls. But, procedure is executed by a different proc
38、ess, probably on a different machine. Fits very well with client-server model.,RPC Mechanism,1. Invoke RPC. 2. Calling process suspends. 3. Parameters passed across network to target machine. 4. Procedure executed remotely. 5. When done, results passed back to caller. 6. Caller resumes execution. Is
39、 this synchronous or asynchronous?,RPC Advantages,Easy to use. Well-known mechanism. Abstract data type Client-server model. Server as collection of exported procedures on some shared resource. Example: file server. Reliable.,MP Reliability of Communication,Unreliable communication: “best effort” -
40、send and hope for the best No ACKs or retransmissions. Application must provide its own reliability. Example: User Datagram Protocol (UDP) Applications using UDP either dont need reliability or build their own (e.g., UNIX NFS and DNS (both UDP and TCP), some audio or video applications),RPC Semantic
41、s 1,Delivery guarantees. “Maybe call”: Clients cannot tell for sure whether remote procedure was executed or not due to message loss, server crash, etc. Usually not acceptable.,RPC Semantics 2,“At-least-once” call: Remote procedure executed at least once, but maybe more than once. Retransmissions bu
42、t no duplicate filtering. Idempotent operations OK; e.g., reading data that is read-only.,RPC Semantics 3,“At-most-once” call Most appropriate for non-idempotent operations. Remote procedure executed 0 or 1 time, ie, exactly once or not at all. Use of retransmissions and duplicate filtering. Example
43、: Birrel et al. implementation. Use of probes to check if server crashed.,RPC Implementation (Birrel et al.),work,Caller,Callee,Call packet,Result,User,User stub,RPC runtime,RPC runtime,Server stub,Server,call,pck args,xmit,rcv,unpk,call,return,pck result,xmit,rcv,unpk result,return,RPC Implementati
44、on 2,RPC runtime mechanism responsible for retransmissions, acknowledgments. Stubs responsible for data packaging and un-packaging; AKA marshalling and un-marshalling: putting data in form suitable for transmission. Example: Suns XDR.,Binding,How to determine where server is? Which procedure to call
45、? “Resource discovery” problem Name service: advertises servers and services. Example: Birrel et al. uses Grapevine. Early versus late binding. Early: server address and procedure name hard-coded in client. Late: go to name service.,Synchronous & Asynchronous RPC,Synchronous Asynchronous,Client Serv
46、er,Client Server,RPC Performance,Sources of overhead data copying scheduling and context switch. Light-Weight RPC Shows that most invocations took place on a single machine. LW-RPC: improve RPC performance for local case. Optimizes data copying and thread scheduling for local case.,LW-RPC 1,Argument
47、 copying RPC: 4 times copying between kernel and user space.LW-RPC: common data area (A-stack) shared by client and server and used to pass parameters and results; access by client or server, one at a time.,LW-RPC 2,A-stack avoids copying between kernel and user spaces. Client and server share the s
48、ame thread: less context switch (like regular calls).,A,client,user,kernel,server,1. copy args,2. traps,3. upcall,4. executes & returns,Lecture Transition,This concludes the slides for lecture2. The following slides are for lecture 3.,CSci555: Advanced Operating Systems Lecture 3 Distributed Concurr
49、ency, Transactions, Deadlock 9 September 2011,Dr. Clifford Neuman University of Southern California Information Sciences Institute (lecture slides written by Dr. Katia Obraczka),Concurrency Control and Synchronization,How to control and synchronize possibly conflicting operations on shared data by concurrent processes? First, some terminology. Processes. Light-weight processes. Threads. Tasks.,COVERED LAST LECTURE,Processes,Text book: Processing activity associated with an execution environment, ie, address space and resources (such as communication and synchronization resources).,
