"right thing" vs. "worse is better" -simplicity -simplicity above all else -correctness -works on slower systems -consistency -lowers expectations -completeness -encourages integration of small systems (can't build large ones) complexity: origins: -many components -many interconnections -irregularity: non-repetitive arrangements ("lack of methodical description") -communication among a team of engineers problems arising: -emergent properties: arise during integration -propagation of effects: one change requires other changes throughout a system -incommensurate scaling: one part scales better/faster than another part tools for complexity control: -modularity: smaller pieces -abstraction: hide unnecessary details in a module "functional modularity" is modularity with abstraction (robustness principle: tolerant on inputs, strict on outputs) -hierarchy: assemble modules into larger modules -layering: conceptual abstraction -iteration: simple system -> complex system in steps therac-25: -system was not designed well -design iteration was botched -code reuse: removed hardware interlocks from previous versions, but used the same code -no quality testing of software independant of the system -complex interactions between various components -multiple race conditions in poorly designed code -bureaucracy got in the way of solving serious flaws in the system -focused on specific bugs, should have redesigned instead -documentation was poor or nonexistant -error messages were useless -operator interface was misleading Enforcing modularity Why need modularity? 1. Simplicity 2. Fault-tolerant 3. Flexibility Models of enforced modularity 1. Client/server model -Client sends requests to server as messages. -No global data sharing, each cannot corrupt its data. -Client shield against server failures by having timeouts on waiting for server responses. -One server can work for multiple clients. -One client can use several servers. -This request/response style of communication between client/server is called RPCs (Remote Procedure Calls). -Some systems have stub programs to make RPC programming easy. An RPC looks just like an ordinary procedure call. On the client, the stub program does the marshalling of the call, and the unmarshalling of the reply. -Some systems don't use RPCs at all. In the X Window systems, for example, the clients sends messages in a stream, some without expecting a reply from the server. Example: X-Windows System -It is device-independent display API. -X server runs where the display and keyboard devices are. -X client runs on (potentially remote) machines that are doing some computation and sends the display results to the server. -Messages between client and server are sent in a stream rather RPC. -because network round trip time is high. Don't want to wait for reply to every call, esp. for interactive apps. 2. Virtual Memory -If programs have unlimited access to all physical memory, it's very easy for them to corrupt each other's data. -To prevent corruption, give each program the illusion of its own physical memory, a virtual memory. -A virtual memory manager sits between the processor and the physical memory. The VMM translates each virtual memory address in a physical memory address. -The physical and virtual memory is usually divided into fixed-size blocks. -A virtual mem address consist of the page number and a offset within that block. -To translate VA to PA, the VMM maps the page number to the physical block number, and concatenates the physical block number with the offset within the block. -Each program has its own virtual address space, and can only access memory with this space. -Two programs can share the same physical block by mapping their VPN to the same physical block. Go over solution to last year's quiz 1 question on virtual memory. [Questions 5-10] Solution can be obtained from the 6.033 2002 site. 3. Threads Enforces modularity for the processor. -Each module has its own virtual processor. -A thread encapsulates the state of a running program. -A thread can be stopped and resumed later. -Use thread switching to share the physical processor. Thread switching. -To give each module a fair share of the processor. -When a thread cannot proceed (is waiting for an event). -Preemptive Vs non preemptive scheduling. Thread Sequence Coordination -Threads wait for some conditions to be true due to actions by other threads. -Rather than checking if the conditions are met, create a mechanisms for; (i)Threads to declare their interests. (ii)Enabling a thread to tell interested parties that something has interesting happened. E.g. eventcount type eventcount input_byte_count -wait( input_byte_count, processed_byte_count) -notify(input_byte_count) Polling Vs interrupts -To over come the effects due to scheduling (infrequent Vs frequent scheduling) -To process an action within a given deadline Threads and address space -One address space-many threads. --All the threads in an address space share fate. --User-level threads Vs Kernel threads. -One address space- one thread. --process --Threads do not share fate Coordinating References to Writable Variables -Mutual exclusion; -Use locks. -acquire(lock) and release(lock). -Only one thread can acquire the lock at a given time. -- acquire(lock) -- temp = next_thread +1; | -- temp = temp %2; | execute atomically -- next_thread = temp; | -- release(lock) Avoiding dead-lock -Possible dead lock scenario:- --Thread A Thread B --acquire(L1); acquire(L2) --acquire(L2); acquire(L1) -To avoid dead-lock, number the locks and; (a)Acquire locks in the ascending order (or) (b)Acquire in any order, do not wait for locks with smaller numbers than currently held (release the larger one before acquiring the larger one). Sample questions - Refer question III of the Spring 2002 Quiz1 solutions. - Refer question 13 and 14 of Spring 2001 Quiz1 solutions. Sharing Resources ----------------- Performance under load -If presented load > capacity , resource is overloaded -If overload persists; --Shed load --Reduce load Measuring response -Turn-around time -Response time -Waiting time Scheduling schemes -First come first served. --Favors big jobs. -Shortest first. --Can lead to starvation. -Round robin. --Enforces modularity (preemptive). --Can cause large turn-around times. -Priority scheduler. --Multiple priority queues (priority can be dynamic). -Real-time scheduler. -Time critical applications Sample question - Refer to question 19 of the class readings. Unix ---- Features: -Hierarchical file system -Compatible file, device and interprocess I/O (using file descriptors) -Ability to initiate asynchronous processes Directories Vs ordinary files -Directory entries provide level of indirection -Filename -> i-number -i-node contains: --Link count. --User and group Ids. --Protection bits --Addresses of the file blocks. -- (and more file specific info.) Processes -Fork() to create a process -Child and parent: --Independent copies of the original memory --Open file descriptors are inherited by the child. --Pipes for interprocess communication. Shell -Command execution. -Pipes and file redirection. -Multitasking (creating background processes). Cache ----- Stable interface -> transparently expand functionality Virtual memories - LOAD-STORE interface -> expand virtual memory size in address spaces beyond physical memory - mechanism: page fault, page manager, page-replacement alg. Multi-level memories: primary -> secondary fast -> slow small -> large CPU registers -> L1 -> L2 -> DRAM -> disk Locality of reference - reference string - working set - thrashing ( working set > cache ) Replacement policy - FIFO, LRU, MRU, OPT - demand-paging vs prefetching/prepaging - clock (approx LRU) Write semantics - write-through, write-behind, write-on-close Problems: 3.1, 3.3 (skipped these) Flash ----- Web server - RPC: request( URL ) -> response( contents of file corresponding to URL ) - Overall flow (simple method) read a request from the network process req ( unmarshall URL, translate URL -> filename ) read file from disk send file to network - can add a cache to avoid some disk reads - problem: can only handle one req at a time, disk underutilized MP: like simple, but N identical processes - good: can handle up to N reqs - bad: cache is split among processes, overhead due to context switching MT: like MP, but N threads sharing one address space - good: can fully utilize cache - bad: complex and expensive cache sync using locks; doesn't work on all OSes SPED: one process, event loop, non-blocking syscalls - good: high cache perf. (no splitting or locking) - bad: disk files don't have non-blocking reads, so disk performance suffers AMPED: like SPED, but uses helper processes to do disk reads (helper blocks, but master and other helpers don't) - good: perf. good in both cache-bound and disk-bound cases - bad: very complex! Networks -------- forms of multiplexing - isochronous (frames, hard-edged, connections) - asynchronous (packets, soft-edged but nonuniform data rate, connectionless) Receive-and-forward, routing - transit time: propagation, processing, transmission, queueing delays - segmented messages Buffer overflow possibilities - plan for the worst case --- harder than it seems - plan for the average case and push back with "quench" messages - makes congestion works and may cause deadlock - plan for the average case and discard packets: "datagram" "best-effort" Timing diagrams - dropped packets - retransmission after timeout - possibility of duplicated packets - reordered delivery Dealing with duplicated packets - duplicate suppression: nonce, response resending, duplicate responses - idempotent operations