NYSadfW2

1Recall: Process Memory
2Copyright © 2010 Michael Kerrisk.
3Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
4Recall: Single and Multithreaded Processes
5• Threads encapsulate concurrency
6– “Active” component of a process
7• Address spaces encapsulate protection
8– Keeps buggy program from trashing the system
9– “Passive” component of a process
10Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
11Virtualizing Resources
12• Physical Reality:
13Different Processes/Threads share the same hardware
14– Need to multiplex CPU
15– Need to multiplex use of Memory
16– Need to multiplex disk and devices
17• Why worry about memory sharing?
18– The complete working state of a process and/or kernel is
19defined by its data in memory (and registers)
20– Consequently, cannot just let different threads of control
21use the same memory
22» Physics: two different pieces of data cannot occupy the same
23locations in memory
24– Probably don’t want different threads to even have access
25to each other’s memory (protection)
26Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
27Important Aspects of Memory Multiplexing
28• Controlled overlap:
29– Separate state of threads should not collide in physical
30memory. Obviously, unexpected overlap causes chaos!
31– Conversely, would like the ability to overlap when
32desired (for communication)
33• Translation:
34– Ability to translate accesses from one address space
35(virtual) to a different one (physical)
36– When translation exists, processor uses virtual
37addresses, physical memory uses physical addresses
38– Side effects:
39» Can be used to avoid overlap
40» Can be used to give uniform view of memory to programs
41• Protection:
42– Prevent access to private memory of other processes
43» Different pages of memory can be given special behavior
44(Read Only, Invisible to user programs, etc).
45» Kernel data protected from User programs
46» Programs protected from themselves
47Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
48Binding of Instructions and Data to Memory
49• Binding of instructions and data to addresses:
50– Choose addresses for instructions and data from the
51standpoint of the processor
52– Could we place data1, start, and/or checkit at
53different addresses?
54» Yes
55» When? Compile time/Load time/Execution time
56– Related: which physical memory locations hold particular
57instructions or data?
58data1: dw 32
59…
60start: lw r1,0(data1)
61jal checkit
62loop: addi r1, r1, -1
63bnz r1, r0, loop
64…
65checkit: …
660x300 00000020
67… …
680x900 8C2000C0
690x904 0C000340
700x908 2021FFFF
710x90C 1420FFFF
72…
730xD00 …
74Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
75Multi-step Processing of a Program for Execution
76• Preparation of a program for
77execution involves components at:
78– Compile time (i.e. “gcc”)
79– Link/Load time (unix “ld” does link)
80– Execution time (e.g. dynamic libs)
81• Addresses can be bound to final
82values anywhere in this path
83– Depends on hardware support
84– Also depends on operating system
85• Dynamic Libraries
86– Linking postponed until execution
87– Small piece of code, stub, used to
88locate the appropriate memoryresident
89library routine
90– Stub replaces itself with the
91address of the routine, and
92executes routine
93Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
94Recall: Uniprogramming
95• Uniprogramming (no Translation or Protection)
96– Application always runs at same place in physical
97memory since only one application at a time
98– Application can access any physical address
99– Application given illusion of dedicated machine by giving
100it reality of a dedicated machine
101• Of course, this doesn’t help us with multithreading
1020x00000000
1030xFFFFFFFF
104Application
105Operating
106System
107Valid 32-bit
108Addresses
109Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
110Multiprogramming (First Version)
111• Multiprogramming without Translation or Protection
112– Must somehow prevent address overlap between threads
113– Trick: Use Loader/Linker: Adjust addresses while
114program loaded into memory (loads, stores, jumps)
115» Everything adjusted to memory location of program
116» Translation done by a linker-loader
117» Was pretty common in early days
118• With this solution, no protection: bugs in any program
119can cause other programs to crash or even the OS
1200x00000000
1210xFFFFFFFF
122Application1
123Operating
124System
125Application2 0x00020000
126Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
127Multiprogramming (Version with Protection)
128• Can we protect programs from each other without
129translation?
130– Yes: use two special registers Base and Limit to prevent
131user from straying outside designated area
132» If user tries to access an illegal address, cause an error
133– During switch, kernel loads new base/limit from TCB
134» User not allowed to change base/limit registers
1350x00000000
1360xFFFFFFFF
137Application1
138Operating
139System
140Application2 0x00020000 Base=0x20000
141Limit=+0x10000
142Segmentation with Base and Limit registers
143• Can use base & bounds/limit for dynamic address
144translation (Simple form of “segmentation”):
145– Alter every address by adding “base”
146– Generate error if address bigger than limit
147• This gives program the illusion that it is running on its
148own dedicated machine, with memory starting at 0
149– Program gets continuous region of memory
150– Addresses within program do not have to be relocated
151when program placed in different region of DRAM
152DRAM
153>?
154+
155Base
156Limit
157CPU
158Virtual
159Address
160Physical
161Address
162Yes: Error!
163Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
164Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
165Issues with simple segmentation method
166• Fragmentation problem (complex memory allocation)
167– Not every process is the same size
168– Over time, memory space becomes fragmented
169– Really bad if want space to grow dynamically (e.g. heap)
170• Other problems for process maintenance
171– Doesn’t allow heap and stack to grow independently
172– Want to put these as far apart in virtual memory space
173as possible so that they can grow as needed
174• Hard to do inter-process sharing
175– Want to share code segments when possible
176– Want to share memory between processes
177process 6
178process 5
179process 2
180OS
181process 6
182process 5
183OS
184process 6
185process 5
186OS
187process 9
188process 6
189process 5
190process 9
191OS
192process 10
193Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
194Multiprogramming (Translation and Protection version 2)
195• Problem: Run multiple applications in such a way that
196they are protected from one another
197• Goals:
198– Isolate processes and kernel from one another
199– Allow flexible translation that:
200» Doesn’t lead to fragmentation
201» Allows easy sharing between processes
202» Allows only part of process to be resident in physical
203memory
204• (Some of the required) Hardware Mechanisms:
205– General Address Translation
206» Flexible: Can fit physical chunks of memory into arbitrary
207places in users address space
208» Not limited to small number of segments
209» Think of this as providing a large number (thousands) of
210fixed-sized segments (called “pages”)
211– Dual Mode Operation
212» Protection base involving kernel/user distinction
213Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
214Example of General Address Translation
215Prog 1
216Virtual
217Address
218Space 1
219Prog 2
220Virtual
221Address
222Space 2
223Code
224Data
225Heap
226Stack
227Code
228Data
229Heap
230Stack
231Data 2
232Stack 1
233Heap 1
234OS heap &
235Stacks
236Code 1
237Stack 2
238Data 1
239Heap 2
240Code 2
241OS code
242Translation Map 1 OS data Translation Map 2
243Physical Address Space
244Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
245Two Views of Memory
246• Recall: Address Space:
247– All the addresses and state a process can touch
248– Each process and kernel has different address space
249• Consequently: two views of memory:
250– View from the CPU (what program sees, virtual memory)
251– View fom memory (physical memory)
252– Translation box converts between the two views
253• Translation helps to implement protection
254– If task A cannot even gain access to task B’s data, no
255way for A to adversely affect B
256• With translation, every program can be linked/loaded
257into same region of user address space
258– Overlap avoided through translation, not relocation
259Physical
260Addresses CPU MMU
261Virtual
262Addresses
263Untranslated read or write
264Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
265More Flexible Segmentation
266• Logical View: multiple separate segments
267– Typical: Code, Data, Stack
268– Others: memory sharing, etc
269• Each segment is given region of contiguous memory
270– Has a base and limit
271– Can reside anywhere in physical memory
2721
2733
2742
2754
276user view of
277memory space
2781
2794
2802
2813
282physical
283memory space
2841
2852
286Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
287Implementation of Multi-Segment Model
288• Segment map resides in processor
289– Segment number mapped into base/limit pair
290– Base added to offset to generate physical address
291– Error check catches offset out of range
292• As many chunks of physical memory as entries
293– Segment addressed by portion of virtual address
294– However, could be included in instruction instead:
295» x86 Example: mov [es:bx],ax.
296• What is “V/N”?
297– Can mark segments as invalid; requires check as well
298Base0 Limit0 V
299Base1 Limit1 V
300Base2 Limit2 V
301Base3 Limit3 N
302Base4 Limit4 V
303Base5 Limit5 N
304Base6 Limit6 N
305Base7 Limit7 V
306Virtual Seg # Offset
307Address
308Base2 Limit2 V
309+ Physical
310Address
311> Error
312Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
313Example: Four Segments (16 bit addresses)
314Seg ID # Base Limit
3150 (code) 0x4000 0x0800
3161 (data) 0x4800 0x1400
3172 (shared) 0xF000 0x1000
3183 (stack) 0x0000 0x3000
319Seg Offset
32015 14 13 0
3210x4000
3220x0000
3230x8000
3240xC000
325Virtual
326Address Space
327Virtual Address Format
3280x0000
3290x4800
3300x5C00
3310x4000
3320xF000
333Physical
334Address Space
335Space for
336Other Apps
337Shared with
338Other Apps
339Might
340be shared
341Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
342Example of segment translation
343Let’s simulate a bit of this code to see what happens (PC=0x240):
3441. Fetch 0x240. Virtual segment #? 0; Offset? 0x240
345Physical address? Base=0x4000, so physical addr=0x4240
346Fetch instruction at 0x4240. Get “la $a0, varx”
347Move 0x4050 ï‚® $a0, Move PC+4ï‚®PC
3482. Fetch 0x244. Translated to Physical=0x4244. Get “jal strlen”
349Move 0x0248 ï‚® $ra (return address!), Move 0x0360 ï‚® PC
3503. Fetch 0x360. Translated to Physical=0x4360. Get “li $v0,0”
351Move 0x0000 ï‚® $v0, Move PC+4ï‚®PC
3524. Fetch 0x364. Translated to Physical=0x4364. Get “lb $t0,($a0)”
353Since $a0 is 0x4050, try to load byte from 0x4050
354Translate 0x4050. Virtual segment #? 1; Offset? 0x50
355Physical address? Base=0x4800, Physical addr = 0x4850,
356Load Byte from 0x4850ï‚®$t0, Move PC+4ï‚®PC
3570x240 main: la $a0, varx
3580x244 jal strlen
359… …
3600x360 strlen: li $v0, 0 ;count
3610x364 loop: lb $t0, ($a0)
3620x368 beq $r0,$t1, done
363… …
3640x4050 varx dw 0x314159
365Seg ID # Base Limit
3660 (code) 0x4000 0x0800
3671 (data) 0x4800 0x1400
3682 (shared) 0xF000 0x1000
3693 (stack) 0x0000 0x3000
370Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
371Observations about Segmentation
372• Virtual address space has holes
373– Segmentation efficient for sparse address spaces
374– A correct program should never address gaps (except
375as mentioned in moment)
376» If it does, trap to kernel and dump core
377• When it is OK to address outside valid range:
378– This is how the stack and heap are allowed to grow
379– For instance, stack takes fault, system automatically
380increases size of stack
381• Need protection mode in segment table
382– For example, code segment would be read-only
383– Data and stack would be read-write (stores allowed)
384– Shared segment could be read-only or read-write
385• What must be saved/restored on context switch?
386– Segment table stored in CPU, not in memory (small)
387– Might store all of processes memory onto disk when
388switched (called “swapping”)
389Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
390Schematic View of Swapping
391• Extreme form of Context Switch: Swapping
392– In order to make room for next process, some or all
393of the previous process is moved to disk
394» Likely need to send out complete segments
395– This greatly increases the cost of context-switching
396• Desirable alternative?
397– Some way to keep only active portions of a process in
398memory at any one time
399– Need finer granularity control over physical memory
400Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
401Paging: Physical Memory in Fixed Size Chunks
402• Problems with segmentation?
403– Must fit variable-sized chunks into physical memory
404– May move processes multiple times to fit everything
405– Limited options for swapping to disk
406• Fragmentation: wasted space
407– External: free gaps between allocated chunks
408– Internal: don’t need all memory within allocated chunks
409• Solution to fragmentation from segments?
410– Allocate physical memory in fixed size chunks (“pages”)
411– Every chunk of physical memory is equivalent
412» Can use simple vector of bits to handle allocation:
41300110001110001101 … 110010
414» Each bit represents page of physical memory
4151allocated, 0free
416• Should pages be as big as our previous segments?
417– No: Can lead to lots of internal fragmentation
418» Typically have small pages (1K-16K)
419– Consequently: need multiple pages/segment
420Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
421Physical Address
422Offset
423How to Implement Paging?
424• Page Table (One per process)
425– Resides in physical memory
426– Contains physical page and permission for each virtual page
427» Permissions include: Valid bits, Read, Write, etc
428• Virtual address mapping
429– Offset from Virtual address copied to Physical Address
430» Example: 10 bit offset  1024-byte pages
431– Virtual page # is all remaining bits
432» Example for 32-bits: 32-10 = 22 bits, i.e. 4 million entries
433» Physical page # copied from table into physical address
434– Check Page Table bounds and permissions
435Offset Virtual Virtual Address: Page #
436Access
437Error
438PageTableSize >
439PageTablePtr page #0
440page #2
441page #3
442page #4
443page #5
444V,R
445page #1 V,R
446V,R,W
447V,R,W
448N
449V,R,W
450page #1 V,R
451Check Perm
452Access
453Error
454Physical
455Page #
456Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
457PageTablePtrB page #0
458page #1
459page #2
460page #3
461page #5
462V,R
463N
464V,R,W
465N
466page #4 V,R
467V,R,W
468What about Sharing?
469Offset Virtual
470Page # Virtual Address
471(Process A):
472PageTablePtrA page #0
473page #1
474page #3
475page #4
476page #5
477V,R
478V,R
479page #2 V,R,W
480V,R,W
481N
482V,R,W
483Offset Virtual
484Page # Virtual Address:
485Process B
486Shared
487Page
488This physical page
489appears in address
490space of both processes
491page #2 V,R,W
492Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
493Simple Page Table Discussion
494• What needs to be switched on a context switch?
495– Page table pointer and limit
496• Simple Page Table Analysis
497– Pros
498» Simple memory allocation
499» Easy to Share
500– Con: What if address space is sparse?
501» E.g. on UNIX, code starts at 0, stack starts at (231-1).
502» With 1K pages, need 4 million page table entries!
503– Con: What if table really big?
504» Not all pages used all the time  would be nice to have
505working set of page table in memory
506• How about combining paging and segmentation?
507– Segments with pages inside them?
508– Need some sort of multi-level translation
509Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
510• What about a tree of tables?
511– Lowest level page tablememory still allocated with bitmap
512– Higher levels often segmented
513• Could have any number of levels. Example (top segment):
514• What must be saved/restored on context switch?
515– Contents of top-level segment registers (for this example)
516– Pointer to top-level table (page table)
517Multi-level Translation: Segments + Pages
518page #0
519page #1
520page #3
521page #4
522page #5
523V,R
524V,R
525page #2 V,R,W
526V,R,W
527N
528V,R,W
529Offset
530Physical Address
531Virtual
532Address:
533Offset Virtual
534Page #
535Virtual
536Seg #
537Base0 Limit0 V
538Base1 Limit1 V
539Base2 Limit2 V
540Base3 Limit3 N
541Base4 Limit4 V
542Base5 Limit5 N
543Base6 Limit6 N
544Base7 Limit7 V
545Base2 Limit2 V
546Access > Error
547page #2 V,R,W
548Physical
549Page #
550Check Perm
551Access
552Error
553Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
554What about Sharing (Complete Segment)?
555Process
556A
557Offset Virtual
558Page #
559Virtual
560Seg #
561Base0 Limit0 V
562Base1 Limit1 V
563Base2 Limit2 V
564Base3 Limit3 N
565Base4 Limit4 V
566Base5 Limit5 N
567Base6 Limit6 N
568Base7 Limit7 V
569Base2 Limit2 V
570page #0
571page #1
572page #2
573page #3
574page #4
575page #5
576V,R
577V,R
578V,R,W
579V,R,W
580N
581V,R,W
582Shared Segment
583Process
584B
585Offset Virtual
586Page #
587Virtual
588Seg #
589Base0 Limit0 V
590Base1 Limit1 V
591Base2 Limit2 V
592Base3 Limit3 N
593Base4 Limit4 V
594Base5 Limit5 N
595Base6 Limit6 N
596Base7 Limit7 V
597Base2 Limit2 V
598Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
599Physical
600Address:
601Offset Physical
602Page #
6034KB
604Another common example: two-level page table
60510 bits 10 bits 12 bits
606Virtual
607Address:
608Offset Virtual
609P2 index
610Virtual
611P1 index
6124 bytes
613PageTablePtr
614• Tree of Page Tables
615• Tables fixed size (1024 entries)
616– On context-switch: save single
617PageTablePtr register
618• Valid bits on Page Table Entries
619– Don’t need every 2nd-level table
620– Even when exist, 2nd-level tables
621can reside on disk if not in use 4 bytes
622Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
623Multi-level Translation Analysis
624• Pros:
625– Only need to allocate as many page table entries as we
626need for application
627» In other wards, sparse address spaces are easy
628– Easy memory allocation
629– Easy Sharing
630» Share at segment or page level (need additional reference
631counting)
632• Cons:
633– One pointer per page (typically 4K – 16K pages today)
634– Page tables need to be contiguous
635» However, previous example keeps tables to exactly one
636page in size
637– Two (or more, if >2 levels) lookups per reference
638» Seems very expensive!
639Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
640• With all previous examples (“Forward Page Tables”)
641– Size of page table is at least as large as amount of
642virtual memory allocated to processes
643– Physical memory may be much less
644» Much of process space may be out on disk or not in use
645• Answer: use a hash table
646– Called an “Inverted Page Table”
647– Size is independent of virtual address space
648– Directly related to amount of physical memory
649– Very attractive option for 64-bit address spaces
650• Cons: Complexity of managing hash changes
651– Often in hardware!
652Inverted Page Table
653Offset Virtual
654Page #
655Hash
656Table
657Offset Physical
658Page #
659Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
660Dual-Mode Operation
661• Can Application Modify its own translation tables?
662– If it could, could get access to all of physical memory
663– Has to be restricted somehow
664• To Assist with Protection, Hardware provides at
665least two modes (Dual-Mode Operation):
666– “Kernel” mode (or “supervisor” or “protected”)
667– “User” mode (Normal program mode)
668– Mode set with bits in special control register only
669accessible in kernel-mode
670Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
671For Protection, Lock User-Programs in Asylum
672• Idea: Lock user programs in padded cell
673with no exit or sharp objects
674– Cannot change mode to kernel mode
675– User cannot modify page table mapping
676– Limited access to memory: cannot
677adversely effect other processes
678» Side-effect: Limited access to
679memory-mapped I/O operations
680(I/O that occurs by reading/writing memory locations)
681– Limited access to interrupt controller
682– What else needs to be protected?
683• A couple of issues
684– How to share CPU between kernel and user programs?
685» Kinda like both the inmates and the warden in asylum are
686the same person. How do you manage this???
687– How do programs interact?
688– How does one switch between kernel and user modes?
689» OS  user (kernel  user mode): getting into cell
690» User OS (user  kernel mode): getting out of cell
691Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
692Userï‚®Kernel (System Call)
693• Can’t let inmate (user) get out of padded cell on own
694– Would defeat purpose of protection!
695– So, how does the user program get back into kernel?
696• System call: Voluntary procedure call into kernel
697– Hardware for controlled UserKernel transition
698– Can any kernel routine be called?
699» No! Only specific ones.
700– System call ID encoded into system call instruction
701» Index forces well-defined interface with kernel
702Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
703System Call Continued
704• What are some system calls?
705– I/O: open, close, read, write, lseek
706– Files: delete, mkdir, rmdir, truncate, chown, chgrp, ..
707– Process: fork, exit, wait (like join)
708– Network: socket create, set options
709• Are system calls constant across operating systems?
710– Not entirely, but there are lots of commonalities
711– Also some standardization attempts (POSIX)
712• What happens at beginning of system call?
713» On entry to kernel, sets system to kernel mode
714» Handler address fetched from table/Handler started
715• System Call argument passing:
716– In registers (not very much can be passed)
717– Write into user memory, kernel copies into kernel mem
718» User addresses must be translated!
719» Kernel has different view of memory than user
720– Every Argument must be explicitly checked!
721Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
722Userï‚®Kernel (Exceptions: Traps and Interrupts)
723• A system call instruction causes a synchronous
724exception (or “trap”)
725– In fact, often called a software “trap” instruction
726• Other sources of Synchronous Exceptions:
727– Divide by zero, Illegal instruction, Bus error (bad
728address, e.g. unaligned access)
729– Segmentation Fault (address out of range)
730– Page Fault (for illusion of infinite-sized memory)
731• Interrupts are Asynchronous Exceptions
732– Examples: timer, disk ready, network, etc….
733– Interrupts can be disabled, traps cannot!
734• On system call, exception, or interrupt:
735– Hardware enters kernel mode with interrupts disabled
736– Saves PC, then jumps to appropriate handler in kernel
737– For some processors (x86), processor also saves
738registers, changes stack, etc.
739• Actual handler typically saves registers, other CPU
740state, and switches to kernel stack
741Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
742Closing thought: Protection without Hardware
743• Does protection require hardware support for
744translation and dual-mode behavior?
745– No: Normally use hardware, but anything you can do in
746hardware can also do in software (possibly expensive)
747• Protection via Strong Typing
748– Restrict programming language so that you can’t express
749program that would trash another program
750– Loader needs to make sure that program produced by
751valid compiler or all bets are off
752– Example languages: LISP, Ada, Modula-3 and Java
753• Protection via software fault isolation:
754– Language independent approach: have compiler generate
755object code that provably can’t step out of bounds
756» Compiler puts in checks for every “dangerous” operation
757(loads, stores, etc). Again, need special loader.
758» Alternative, compiler generates “proof” that code cannot
759do certain things (Proof Carrying Code)
760– Or: use virtual machine to guarantee safe behavior
761(loads and stores recompiled on fly to check bounds)
762Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
763Summary (1/2)
764• Memory is a resource that must be shared
765– Controlled Overlap: only shared when appropriate
766– Translation: Change Virtual Addresses into Physical
767Addresses
768– Protection: Prevent unauthorized Sharing of resources
769• Dual-Mode
770– Kernel/User distinction: User restricted
771– UserKernel: System calls, Traps, or Interrupts
772– Inter-process communication: shared memory, or
773through kernel (system calls)
774• Exceptions
775– Synchronous Exceptions: Traps (including system calls)
776– Asynchronous Exceptions: Interrupts
777Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
778Summary (2/2)
779• Segment Mapping
780– Segment registers within processor
781– Segment ID associated with each access
782» Often comes from portion of virtual address
783» Can come from bits in instruction instead (x86)
784– Each segment contains base and limit information
785» Offset (rest of address) adjusted by adding base
786• Page Tables
787– Memory divided into fixed-sized chunks of memory
788– Virtual page number from virtual address mapped
789through page table to physical page number
790– Offset of virtual address same as physical address
791– Large page tables can be placed into virtual memory
792• Multi-Level Tables
793– Virtual address mapped to series of tables
794– Permit sparse population of address space
795• Inverted page table
796– Size of page table related to physical memory size
797Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
798• What about a tree of tables?
799– Lowest level page tablememory still allocated with bitmap
800– Higher levels often segmented
801• Could have any number of levels. Example (top segment):
802• What must be saved/restored on context switch?
803– Contents of top-level segment registers (for this example)
804– Pointer to top-level table (page table)
805Review: Multi-level Translation
806page #0
807page #1
808page #3
809page #4
810page #5
811V,R
812V,R
813page #2 V,R,W
814V,R,W
815N
816V,R,W
817Offset
818Physical Address
819Virtual
820Address:
821Offset Virtual
822Page #
823Virtual
824Seg #
825Base0 Limit0 V
826Base1 Limit1 V
827Base2 Limit2 V
828Base3 Limit3 N
829Base4 Limit4 V
830Base5 Limit5 N
831Base6 Limit6 N
832Base7 Limit7 V
833Base2 Limit2 V
834Access > Error
835page #2 V,R,W
836Physical
837Page #
838Check Perm
839Access
840Error
841Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
842Physical
843Address:
844Offset Physical
845Page #
8464KB
847Review: Two-level page table
84810 bits 10 bits 12 bits
849Virtual
850Address:
851Offset Virtual
852P2 index
853Virtual
854P1 index
8554 bytes
856PageTablePtr
857• Tree of Page Tables
858• Tables fixed size (1024 entries)
859– On context-switch: save single
860PageTablePtr register
861• Sometimes, top-level page tables
862called “directories” (Intel)
863• Each entry called a (surprise!)
864Page Table Entry (PTE) 4 bytes
865Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
866What is in a PTE?
867• What is in a Page Table Entry (or PTE)?
868– Pointer to next-level page table or to actual page
869– Permission bits: valid, read-only, read-write, write-only
870• Example: Intel x86 architecture PTE:
871– Address same format previous slide (10, 10, 12-bit offset)
872– Intermediate page tables called “Directories”
873P: Present (same as “valid” bit in other architectures)
874W: Writeable
875U: User accessible
876PWT: Page write transparent: external cache write-through
877PCD: Page cache disabled (page cannot be cached)
878A: Accessed: page has been accessed recently
879D: Dirty (PTE only): page has been modified recently
880L: L=14MB page (directory only).
881Bottom 22 bits of virtual address serve as offset
882Page Frame Number
883(Physical Page Number)
884Free
885(OS) 0 L D A
886PCD
887PWT
888U WP
88931-12 11-9 8 7 6 5 4 3 2 1 0
890Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
891Examples of how to use a PTE
892• How do we use the PTE?
893– Invalid PTE can imply different things:
894» Region of address space is actually invalid or
895» Page/directory is just somewhere else than memory
896– Validity checked first
897» OS can use other (say) 31 bits for location info
898• Usage Example: Demand Paging
899– Keep only active pages in memory
900– Place others on disk and mark their PTEs invalid
901• Usage Example: Copy on Write
902– UNIX fork gives copy of parent address space to child
903» Address spaces disconnected after child created
904– How to do this cheaply?
905» Make copy of parent’s page tables (point at same memory)
906» Mark entries in both sets of page tables as read-only
907» Page fault on write creates two copies
908• Usage Example: Zero Fill On Demand
909– New data pages must carry no information (say be zeroed)
910– Mark PTEs as invalid; page fault on use gets zeroed page
911– Often, OS creates zeroed pages in background
912Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
913How is the translation accomplished?
914• What, exactly happens inside MMU?
915• One possibility: Hardware Tree Traversal
916– For each virtual address, takes page table base pointer
917and traverses the page table in hardware
918– Generates a “Page Fault” if it encounters invalid PTE
919» Fault handler will decide what to do
920» More on this soon
921– Pros: Relatively fast (but still many memory accesses!)
922– Cons: Inflexible, Complex hardware
923• Another possibility: Software
924– Each traversal done in software
925– Pros: Very flexible
926– Cons: Every translation must invoke Fault!
927• In fact, need way to cache translations for either case!
928CPU MMU
929Virtual
930Addresses
931Physical
932Addresses
933Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
934Caching Concept
935• Cache: a repository for copies that can be accessed
936more quickly than the original
937– Make frequent case fast and infrequent case less dominant
938• Caching underlies many of the techniques that are used
939today to make computers fast
940– Can cache: memory locations, address translations, pages,
941file blocks, file names, network routes, etc…
942• Only good if:
943– Frequent case frequent enough and
944– Infrequent case not too expensive
945• Important measure: Average Access time =
946(Hit Rate x Hit Time) + (Miss Rate x Miss Time)
947Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
948CPU
949µProc
95060%/yr.
951(2X/1.5yr)
952DRAM
9539%/yr.
954(2X/10
955yrs)
956DRAM
9571
95810
959100
9601000
9611980
9621981
9631982
9641983
9651984
9661985
9671986
9681987
9691988
9701989
9711990
9721991
9731992
9741993
9751994
9761995
9771996
9781997
9791998
9801999
9812000
982Processor-Memory
983Performance Gap:
984(grows 50% / year)
985Performance
986Time
987“Moore’s Law”
988(really Joy’s Law)
989Processor-DRAM Memory Gap (latency)
990Why Bother with Caching?
991“Less’ Law?”
992Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
993• Cannot afford to translate on every access
994– At least three DRAM accesses per actual DRAM access
995– Or: perhaps I/O if page table partially on disk!
996• Even worse: What if we are using caching to make
997memory access faster than DRAM access???
998• Solution? Cache translations!
999– Translation Cache: TLB (“Translation Lookaside Buffer”)
1000Another Major Reason to Deal with Caching
1001page #0
1002page #1
1003page #3
1004page #4
1005page #5
1006V,R
1007V,R
1008page #2 V,R,W
1009V,R,W
1010N
1011V,R,W
1012Offset
1013Physical Address
1014Virtual
1015Address:
1016Offset Virtual
1017Page #
1018Virtual
1019Seg #
1020Base0 Limit0 V
1021Base1 Limit1 V
1022Base2 Limit2 V
1023Base3 Limit3 N
1024Base4 Limit4 V
1025Base5 Limit5 N
1026Base6 Limit6 N
1027Base7 Limit7 V Access > Error
1028Physical
1029Page #
1030Check Perm
1031Access
1032Error
1033Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1034Why Does Caching Help? Locality!
1035• Temporal Locality (Locality in Time):
1036– Keep recently accessed data items closer to processor
1037• Spatial Locality (Locality in Space):
1038– Move contiguous blocks to the upper levels
1039Address Space 0 2
1040n
1041- 1
1042Probability
1043of reference
1044Lower Level
1045Upper Level Memory
1046Memory
1047To Processor
1048From Processor
1049Blk X
1050Blk Y
1051Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1052Memory Hierarchy of a Modern Computer System
1053• Take advantage of the principle of locality to:
1054– Present as much memory as in the cheapest technology
1055– Provide access at speed offered by the fastest technology On-Chip Registers Cache
1056Control
1057Datapath
1058Secondary
1059Storage
1060(Disk)
1061Processor
1062Main
1063Memory
1064(DRAM)
1065Second
1066Level
1067Cache
1068(SRAM)
10691s 10,000,000s
1070(10s ms)
1071Speed (ns): 10s-100s 100s
1072Size (bytes): 100s Ks-Ms Ms Gs
1073Tertiary
1074Storage
1075(Tape)
107610,000,000,000s
1077(10s sec)
1078Ts
1079Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1080• Compulsory (cold start or process migration, first
1081reference): first access to a block
1082– “Cold” fact of life: not a whole lot you can do about it
1083– Note: If you are going to run “billions” of instruction,
1084Compulsory Misses are insignificant
1085• Capacity:
1086– Cache cannot contain all blocks access by the program
1087– Solution: increase cache size
1088• Conflict (collision):
1089– Multiple memory locations mapped
1090to the same cache location
1091– Solution 1: increase cache size
1092– Solution 2: increase associativity
1093• Coherence (Invalidation): other process (e.g., I/O)
1094updates memory
1095A Summary on Sources of Cache Misses
1096Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1097• Index Used to Lookup Candidates in Cache
1098– Index identifies the set
1099• Tag used to identify actual copy
1100– If no candidates match, then declare cache miss
1101• Block is minimum quantum of caching
1102– Data select field used to select data within block
1103– Many caching applications don’t have data select field
1104How is a Block found in a Cache?
1105Block
1106offset
1107Block Address
1108Tag Index
1109Set Select
1110Data Select
1111Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1112:
11130x50
1114Valid Bit
1115:
1116Cache Tag
1117Byte 32
11180
11191
11202
11213
1122:
1123Cache Data
1124Byte 31 :
1125Byte 1 Byte 0
1126Byte 63 :
1127Byte 33
1128Byte 1023 :
1129Byte 992 31
1130Direct Mapped Cache
1131• Direct Mapped 2N byte cache:
1132– The uppermost (32 - N) bits are always the Cache Tag
1133– The lowest M bits are the Byte Select (Block Size = 2M)
1134• Example: 1 KB Direct Mapped Cache with 32 B Blocks
1135– Index chooses potential block
1136– Tag checked to verify block
1137– Byte select chooses byte within block
1138Ex: 0x50 Ex: 0x00
1139Cache Index
114031 4 0
1141Cache Tag Byte Select
11429
1143Ex: 0x01
1144Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1145Cache Index
114631 4 0
1147Cache Tag Byte Select
11488
1149Cache Data
1150Cache Block 0
1151Valid Cache Tag
1152: : :
1153Cache Data
1154Cache Block 0
1155Cache Tag Valid
1156: : :
1157Mux 1 0
1158Sel1 Sel0
1159OR
1160Hit
1161Set Associative Cache
1162• N-way set associative: N entries per Cache Index
1163– N direct mapped caches operates in parallel
1164• Example: Two-way set associative cache
1165– Cache Index selects a “set” from the cache
1166– Two tags in the set are compared to input in parallel
1167– Data is selected based on the tag result
1168Compare Compare
1169Cache Block
1170Fully Associative Cache
1171• Fully Associative: Every block can hold any line
1172– Address does not include a cache index
1173– Compare Cache Tags of all Cache Entries in Parallel
1174• Example: Block Size=32B blocks
1175– We need N 27-bit comparators
1176– Still have byte select to choose from within block
1177:
1178Cache Data
1179Byte 31 :
1180Byte 1 Byte 0
1181Byte 63 :
1182Byte 33 Byte 32
1183Valid Bit
1184: :
1185Cache Tag
11864 0
1187Cache Tag (27 bits long) Byte Select
118831
1189=
1190=
1191=
1192=
1193=
1194Ex: 0x01
1195Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1196Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1197• Example: Block 12 placed in 8 block cache
1198Block 0 1 2 3 4 5 6 7
1199no.
1200Direct mapped:
1201block 12 can go
1202only into block 4
1203(12 mod 8)
1204Set associative:
1205block 12 can go
1206anywhere in set 0
1207(12 mod 4)
1208Block 0 1 2 3 4 5 6 7
1209no.
1210Set
12110
1212Set
12131
1214Set
12152
1216Set
12173
1218Fully associative:
1219block 12 can go
1220anywhere
1221Block 0 1 2 3 4 5 6 7
1222no.
12230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
122432-Block Address Space:
1225Block 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
1226no.
1227Where does a Block Get Placed in a Cache?
1228Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1229Caching Applied to Address Translation
1230• Question is one of page locality: does it exist?
1231– Instruction accesses spend a lot of time on the same
1232page (since accesses sequential)
1233– Stack accesses have definite locality of reference
1234– Data accesses have less page locality, but still some…
1235• Can we have a TLB hierarchy?
1236– Sure: multiple levels at different sizes/speeds
1237Data Read or Write
1238(untranslated)
1239CPU Physical
1240Memory
1241TLB
1242Translate
1243(MMU)
1244No
1245Virtual
1246Address Physical
1247Address Yes
1248Cached?
1249Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1250TLB organization: include protection
1251• How big does TLB actually have to be?
1252– Usually small: 128-512 entries
1253– Not very big, can support higher associativity
1254• TLB usually organized as fully-associative cache
1255– Lookup is by Virtual Address
1256– Returns Physical Address + other info
1257• What happens when fully-associative is too slow?
1258– Put a small (4-16 entry) direct-mapped cache in front
1259– Called a “TLB Slice”
1260• Example for MIPS R3000:
12610xFA00 0x0003 Y N Y R/W 34
12620x0040 0x0010 N Y Y R 0
12630x0041 0x0011 N Y Y R 0
1264Virtual Address Physical Address Dirty Ref Valid Access ASID
1265Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1266Caching Summary
1267• The Principle of Locality:
1268– Program likely to access a relatively small portion of the
1269address space at any instant of time.
1270» Temporal Locality: Locality in Time
1271» Spatial Locality: Locality in Space
1272• Three (+1) Major Categories of Cache Misses:
1273– Compulsory Misses: sad facts of life. Example: cold start
1274misses.
1275– Conflict Misses: increase cache size and/or associativity
1276– Capacity Misses: increase cache size
1277– Coherence Misses: Caused by external processors or I/O
1278devices
1279• Cache Organizations:
1280– Direct Mapped: single block per set
1281– Set associative: more than one block per set
1282– Fully associative: all entries equivalent
1283Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1284TLB Summary
1285• PTE: Page Table Entries
1286– Includes physical page number
1287– Control info (valid bit, writeable, dirty, user, etc)
1288• A cache of translations called a “Translation Lookaside
1289Buffer” (TLB)
1290– Relatively small number of entries (< 512)
1291– Fully Associative (Since conflict misses expensive)
1292– TLB entries contain PTE and optional process ID
1293• On TLB miss, page table must be traversed
1294– If located PTE is invalid, cause Page Fault
1295• On context switch/change in page table
1296– TLB entries must be invalidated somehow
1297• TLB is logically in front of cache
1298– Thus, needs to be overlapped with cache access to be
1299really fast
1300
13011
1302Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1303Disk Scheduling
1304• Disk can do only one request at a time; What order do
1305you choose to do queued requests?
1306• FIFO Order
1307– Fair among requesters, but order of arrival may be to
1308random spots on the disk  Very long seeks
1309• SSTF: Shortest seek time first
1310– Pick the request that’s closest on the disk
1311– Although called SSTF, today must include
1312rotational delay in calculation, since
1313rotation can be as long as seek
1314– Con: SSTF good at reducing seeks, but
1315may lead to starvation
1316• SCAN: Implements an Elevator Algorithm: take the
1317closest request in the direction of travel
1318– No starvation, but retains flavor of SSTF
1319• C-SCAN: Circular-Scan: only goes in one direction
1320– Skips any requests on the way back
1321– Fairer than SCAN, not biased towards pages in middle 2,2 5,2 7,2 3,10 2,1 2,3
1322User Head
1323Requests
13241
13254
13262
1327Disk Head
13283
1329Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1330Building a File System
1331• File System: Layer of OS that transforms block
1332interface of disks (or other block devices) into Files,
1333Directories, etc.
1334• File System Components
1335– Disk Management: collecting disk blocks into files
1336– Naming: Interface to find files by name, not by blocks
1337– Protection: Layers to keep data secure
1338– Reliability/Durability: Keeping of files durable despite
1339crashes, media failures, attacks, etc
1340• User vs. System View of a File
1341– User’s view:
1342» Durable Data Structures
1343– System’s view (system call interface):
1344» Collection of Bytes (UNIX)
1345» Doesn’t matter to system what kind of data structures you
1346want to store on disk!
1347– System’s view (inside OS):
1348» Collection of blocks (a block is a logical transfer unit, while
1349a sector is the physical transfer unit)
1350» Block size  sector size; in UNIX, block size is 4KB
13512
1352Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1353Translating from User to System View
1354• What happens if user says: give me bytes 2—12?
1355– Fetch block corresponding to those bytes
1356– Return just the correct portion of the block
1357• What about: write bytes 2—12?
1358– Fetch block
1359– Modify portion
1360– Write out Block
1361• Everything inside File System is in whole size blocks
1362– For example, getc(), putc()  buffers something like
13634096 bytes, even if interface is one byte at a time
1364• From now on, file is a collection of blocks
1365File
1366System
1367Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1368Disk Management Policies
1369• Basic entities on a disk:
1370– File: user-visible group of blocks arranged sequentially in
1371logical space
1372– Directory: user-visible index mapping names to files
1373(next lecture)
1374• Access disk as linear array of sectors. Two Options:
1375– Identify sectors as vectors [cylinder, surface, sector].
1376Sort in cylinder-major order. Not used much anymore.
1377– Logical Block Addressing (LBA). Every sector has integer
1378address from zero up to max number of sectors.
1379– Controller translates from address  physical position
1380» First case: OS/BIOS must deal with bad sectors
1381» Second case: hardware shields OS from structure of disk
1382• Need way to track free disk blocks
1383– Link free blocks together  too slow today
1384– Use bitmap to represent free space on disk
1385• Need way to structure files: File Header
1386– Track which blocks belong at which offsets within the
1387logical file structure
1388– Optimize placement of files’ disk blocks to match access
1389and usage patterns
13903
1391Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1392Designing the File System: Access Patterns
1393• How do users access files?
1394– Need to know type of access patterns user is likely to
1395throw at system
1396• Sequential Access: bytes read in order (“give me the
1397next X bytes, then give me next, etc”)
1398– Almost all file access are of this flavor
1399• Random Access: read/write element out of middle of
1400array (“give me bytes i—j”)
1401– Less frequent, but still important. For example, virtual
1402memory backing file: page of memory stored in file
1403– Want this to be fast – don’t want to have to read all
1404bytes to get to the middle of the file
1405• Content-based Access: (“find me 100 bytes starting
1406with AUERBACH”)
1407– Example: employee records – once you find the bytes,
1408increase my salary by a factor of 2
1409– Many systems don’t provide this; instead, databases are
1410built on top of disk access to index content (requires
1411efficient random access)
1412Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1413Designing the File System: Usage Patterns
1414• Most files are small (for example, .login, .c files)
1415– A few files are big – nachos, core files, etc.; the nachos
1416executable is as big as all of your .class files combined
1417– However, most files are small – .class’s, .o’s, .c’s, etc.
1418• Large files use up most of the disk space and
1419bandwidth to/from disk
1420– May seem contradictory, but a few enormous files are
1421equivalent to an immense # of small files
1422• Although we will use these observations, beware usage
1423patterns:
1424– Good idea to look at usage patterns: beat competitors by
1425optimizing for frequent patterns
1426– Except: changes in performance or cost can alter usage
1427patterns. Maybe UNIX has lots of small files because big
1428files are really inefficient?
1429• Digression, danger of predicting future:
1430– In 1950’s, marketing study by IBM said total worldwide
1431need for computers was 7!
1432– Company (that you haven’t heard of) called “GenRad”
1433invented oscilloscope; thought there was no market, so
1434sold patent to Tektronix (bet you have heard of them!)
14354
1436Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1437How to organize files on disk
1438• Goals:
1439– Maximize sequential performance
1440– Easy random access to file
1441– Easy management of file (growth, truncation, etc)
1442• First Technique: Continuous Allocation
1443– Use continuous range of blocks in logical block space
1444» Analogous to base+bounds in virtual memory
1445» User says in advance how big file will be (disadvantage)
1446– Search bit-map for space using best fit/first fit
1447» What if not enough contiguous space for new file?
1448– File Header Contains:
1449» First block/LBA in file
1450» File size (# of blocks)
1451– Pros: Fast Sequential Access, Easy Random access
1452– Cons: External Fragmentation/Hard to grow files
1453» Free holes get smaller and smaller
1454» Could compact space, but that would be really expensive
1455• Continuous Allocation used by IBM 360
1456– Result of allocation and management cost: People would
1457create a big file, put their file in the middle
1458Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1459Linked List Allocation
1460• Second Technique: Linked List Approach
1461– Each block, pointer to next on disk
1462– Pros: Can grow files dynamically, Free list same as file
1463– Cons: Bad Sequential Access (seek between each block),
1464Unreliable (lose block, lose rest of file)
1465– Serious Con: Bad random access!!!!
1466– Technique originally from Alto (First PC, built at Xerox)
1467» No attempt to allocate contiguous blocks
1468Null
1469File Header
14705
1471Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1472Linked Allocation: File-Allocation Table (FAT)
1473• MSDOS links pages together to create a file
1474– Links not in pages, but in the File Allocation Table (FAT)
1475» FAT contains an entry for each block on the disk
1476» FAT Entries corresponding to blocks of file linked together
1477– Access properties:
1478» Sequential access expensive unless FAT cached in memory
1479» Random access expensive always, but really expensive if
1480FAT not cached in memory
1481Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1482Indexed Allocation
1483• Third Technique: Indexed Files (Nachos, VMS)
1484– System Allocates file header block to hold array of
1485pointers big enough to point to all blocks
1486» User pre-declares max file size;
1487– Pros: Can easily grow up to space allocated for index
1488Random access is fast
1489– Cons: Clumsy to grow file bigger than table size
1490Still lots of seeks: blocks may be spread over disk
14916
1492Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1493Multilevel Indexed Files (UNIX BSD 4.1)
1494• Multilevel Indexed Files: Like multilevel address
1495translation (from UNIX 4.1 BSD)
1496– Key idea: efficient for small files, but still allow big files
1497– File header contains 13 pointers
1498» Fixed size table, pointers not all equivalent
1499» This header is called an “inode” in UNIX
1500– File Header format:
1501» First 10 pointers are to data blocks
1502» Block 11 points to “indirect block” containing 256 blocks
1503» Block 12 points to “doubly indirect block” containing 256
1504indirect blocks for total of 64K blocks
1505» Block 13 points to a triply indirect block (16M blocks)
1506• Discussion
1507– Basic technique places an upper limit on file size that is
1508approximately 16Gbytes
1509» Designers thought this was bigger than anything anyone
1510would need. Much bigger than a disk at the time…
1511» Fallacy: today, EOS producing 2TB of data per day
1512– Pointers get filled in dynamically: need to allocate
1513indirect block only when file grows > 10 blocks.
1514» On small files, no indirection needed
1515Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1516Example of Multilevel Indexed Files
1517• Sample file in multilevel
1518indexed format:
1519– How many accesses for
1520block #23? (assume file
1521header accessed on open)?
1522» Two: One for indirect block,
1523one for data
1524– How about block #5?
1525» One: One for data
1526– Block #340?
1527» Three: double indirect block,
1528indirect block, and data
1529• UNIX 4.1 Pros and cons
1530– Pros: Simple (more or less)
1531Files can easily expand (up to a point)
1532Small files particularly cheap and easy
1533– Cons: Lots of seeks
1534Very large files must read many indirect block (four
1535I/Os per block!)
15367
1537Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1538File Allocation for Cray-1 DEMOS
1539• DEMOS: File system structure similar to segmentation
1540– Idea: reduce disk seeks by
1541» using contiguous allocation in normal case
1542» but allow flexibility to have non-contiguous allocation
1543– Cray-1 had 12ns cycle time, so CPU:disk speed ratio about
1544the same as today (a few million instructions per seek)
1545• Header: table of base & size (10 “block group” pointers)
1546– Each block chunk is a contiguous group of disk blocks
1547– Sequential reads within a block chunk can proceed at high
1548speed – similar to continuous allocation
1549• How do you find an available block group?
1550– Use freelist bitmap to find block of 0’s.
1551basesize
1552file header
15531,3,2
15541,3,3
15551,3,4
15561,3,5
15571,3,6
15581,3,7
15591,3,8
15601,3,9
1561disk group
1562Basic Segmentation Structure:
1563Each segment contiguous on disk
1564Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1565Large File Version of DEMOS
1566• What if need much bigger files?
1567– If need more than 10 groups, set flag in header: BIGFILE
1568» Each table entry now points to an indirect block group
1569– Suppose 1000 blocks in a block group  80GB max file
1570» Assuming 8KB blocks, 8byte entries
1571(10 ptrsï‚´1024 groups/ptrï‚´1000 blocks/group)*8K =80GB
1572• Discussion of DEMOS scheme
1573– Pros: Fast sequential access, Free areas merge simply
1574Easy to find free block groups (when disk not full)
1575– Cons: Disk full  No long runs of blocks (fragmentation),
1576so high overhead allocation/access
1577– Full disk  worst of 4.1BSD (lots of seeks) with worst of
1578continuous allocation (lots of recompaction needed)
1579file header
1580base size 1,3,2
15811,3,3
15821,3,4
15831,3,5
15841,3,6
15851,3,7
15861,3,8
15871,3,9
1588base size disk group
1589indirect
1590block group
15918
1592Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1593How to keep DEMOS performing well?
1594• In many systems, disks are always full
1595– CS department growth: 300 GB to 1TB in a year
1596» That’s 2GB/day! (Now at 6 TB?)
1597– How to fix? Announce that disk space is getting low, so
1598please delete files?
1599» Don’t really work: people try to store their data faster
1600– Sidebar: Perhaps we are getting out of this mode with
1601new disks… However, let’s assume disks full for now
1602» (Rumor has it that the EECS department has 60TB of
1603spinning storage just waiting for use…)
1604• Solution:
1605– Don’t let disks get completely full: reserve portion
1606» Free count = # blocks free in bitmap
1607» Scheme: Don’t allocate data if count < reserve
1608– How much reserve do you need?
1609» In practice, 10% seems like enough
1610– Tradeoff: pay for more disk, get contiguous allocation
1611» Since seeks so expensive for performance, this is a very
1612good tradeoff
1613Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1614UNIX BSD 4.2
1615• Same as BSD 4.1 (same file header and triply indirect
1616blocks), except incorporated ideas from DEMOS:
1617– Uses bitmap allocation in place of freelist
1618– Attempt to allocate files contiguously
1619– 10% reserved disk space
1620– Skip-sector positioning (mentioned next slide)
1621• Problem: When create a file, don’t know how big it
1622will become (in UNIX, most writes are by appending)
1623– How much contiguous space do you allocate for a file?
1624– In Demos, power of 2 growth: once it grows past 1MB,
1625allocate 2MB, etc
1626– In BSD 4.2, just find some range of free blocks
1627» Put each new file at the front of different range
1628» To expand a file, you first try successive blocks in
1629bitmap, then choose new range of blocks
1630– Also in BSD 4.2: store files from same directory near
1631each other
1632• Fast File System (FFS)
1633– Allocation and placement policies for BSD 4.2
16349
1635Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1636Attack of the Rotational Delay
1637• Problem 2: Missing blocks due to rotational delay
1638– Issue: Read one block, do processing, and read next
1639block. In meantime, disk has continued turning: missed
1640next block! Need 1 revolution/block!
1641– Solution1: Skip sector positioning (“interleaving”)
1642» Place the blocks from one file on every other block of a
1643track: give time for processing to overlap rotation
1644– Solution2: Read ahead: read next block right after first,
1645even if application hasn’t asked for it yet.
1646» This can be done either by OS (read ahead)
1647» By disk itself (track buffers). Many disk controllers have
1648internal RAM that allows them to read a complete track
1649• Important Aside: Modern disks+controllers do many
1650complex things “under the covers”
1651– Track buffers, elevator algorithms, bad block filtering
1652Skip Sector
1653Track Buffer
1654(Holds complete track)
1655Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1656IBM/Hitachi Microdrive
1657Western Digital Drive
1658http://www.storagereview.com/guide/
1659Read/Write Head
1660Side View
1661Taking a step back: Hard Disk Drives
166210
1663Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1664Sector
1665Track
1666Platter
1667Properties of a Hard Magnetic Disk
1668• Properties
1669– Head moves in to address circular track of information
1670– Independently addressable element: sector
1671» OS always transfers groups of sectors together—”blocks”
1672– Items addressable without moving head: cylinder
1673– A disk can be rewritten in place: it is possible to
1674read/modify/write a block from the disk
1675• Typical numbers (depending on the disk size):
1676– 500 to more than 20,000 tracks per surface
1677– 32 to 800 sectors per track
1678• Zoned bit recording
1679– Constant bit density: more sectors on outer tracks
1680– Speed varies with track location
1681Track
1682Sector
1683Cylinder
1684Head
1685Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1686Performance Model
1687• Read/write data is a three-stage process:
1688– Seek time: position the head/arm over the proper track
1689(into proper cylinder)
1690– Rotational latency: wait for the desired sector
1691to rotate under the read/write head
1692– Transfer time: transfer a block of bits (sector)
1693under the read-write head
1694• Disk Latency = Queueing Time + Controller time +
1695Seek Time + Rotation Time + Xfer Time
1696• Highest Bandwidth:
1697– Transfer large group of blocks sequentially from one track
1698Software
1699Queue
1700(Device Driver)
1701Controller
1702Hardware
1703Media Time
1704(Seek+Rot+Xfer)
1705Request
1706Result
170711
1708Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1709Disk Performance
1710• Assumptions:
1711– Ignoring queuing and controller times for now
1712– Avg seek time of 5ms, avg rotational delay of 4ms
1713– Transfer rate of 4MByte/s, sector size of 1 KByte
1714• Random place on disk:
1715– Seek (5ms) + Rot. Delay (4ms) + Transfer (0.25ms)
1716– Roughly 10ms to fetch/put data: 100 KByte/sec
1717• Random place in same cylinder:
1718– Rot. Delay (4ms) + Transfer (0.25ms)
1719– Roughly 5ms to fetch/put data: 200 KByte/sec
1720• Next sector on same track:
1721– Transfer (0.25ms): 4 MByte/sec
1722• Key to using disk effectively (esp. for filesystems)
1723is to minimize seek and rotational delays
1724Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1725Disk Tradeoffs
1726• How do manufacturers choose disk sector sizes?
1727– Need 100-1000 bits between each sector to allow
1728system to measure how fast disk is spinning and to
1729tolerate small (thermal) changes in track length
1730• What if sector was 1 byte?
1731– Space efficiency – only 1% of disk has useful space
1732– Time efficiency – each seek takes 10 ms, transfer
1733rate of 50 – 100 Bytes/sec
1734• What if sector was 1 KByte?
1735– Space efficiency – only 90% of disk has useful space
1736– Time efficiency – transfer rate of 100 KByte/sec
1737• What if sector was 1 MByte?
1738– Space efficiency – almost all of disk has useful space
1739– Time efficiency – transfer rate of 4 MByte/sec
174012
1741Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1742Review: Disk Scheduling
1743• Disk can do only one request at a time; What order do
1744you choose to do queued requests?
1745• FIFO Order
1746– Fair among requesters, but order of arrival may be to
1747random spots on the disk  Very long seeks
1748• SSTF: Shortest seek time first
1749– Pick the request that’s closest on the disk
1750– Although called SSTF, today must include
1751rotational delay in calculation, since
1752rotation can be as long as seek
1753– Con: SSTF good at reducing seeks, but
1754may lead to starvation
1755• SCAN: Implements an Elevator Algorithm: take the
1756closest request in the direction of travel
1757– No starvation, but retains flavor of SSTF
1758• C-SCAN: Circular-Scan: only goes in one direction
1759– Skips any requests on the way back
1760– Fairer than SCAN, not biased towards pages in middle 2,2 5,2 7,2 3,10 2,1 2,3
1761User Head
1762Requests
17631
17644
17652
1766Disk Head
17673
1768Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1769Review: Example of Multilevel Indexed Files
1770• Sample file in multilevel
1771indexed format:
1772– How many accesses for
1773block #23? (assume file
1774header accessed on open)?
1775» Two: One for indirect block,
1776one for data
1777– How about block #5?
1778» One: One for data
1779– Block #340?
1780» Three: double indirect block,
1781indirect block, and data
1782• UNIX 4.1 Pros and cons
1783– Pros: Simple (more or less)
1784Files can easily expand (up to a point)
1785Small files particularly cheap and easy
1786– Cons: Lots of seeks
1787Very large files must read many indirect block (four
1788I/Os per block!)
178913
1790Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1791Review: How do we actually access files?
1792• All information about a file contained in its file header
1793– UNIX calls this an “inode”
1794» Inodes are global resources identified by index (“inumber”)
1795– Once you load the header structure, all the other blocks
1796of the file are locatable
1797• Question: how does the user ask for a particular file?
1798– One option: user specifies an inode by a number (index).
1799» Imagine: open(“14553344”)
1800– Better option: specify by textual name
1801» Have to map nameinumber
1802– Another option: Icon
1803» This is how Apple made its money. Graphical user
1804interfaces. Point to a file and click.
1805• Naming: The process by which a system translates from
1806user-visible names to system resources
1807– In the case of files, need to translate from strings
1808(textual names) or icons to inumbers/inodes
1809– For global file systems, data may be spread over
1810globeneed to translate from strings or icons to some
1811combination of physical server location and inumber
1812Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1813Directories
1814• Directory: a relation used for naming
1815– Just a table of (file name, inumber) pairs
1816• How are directories constructed?
1817– Directories often stored in files
1818» Reuse of existing mechanism
1819» Directory named by inode/inumber like other files
1820– Needs to be quickly searchable
1821» Options: Simple list or Hashtable
1822» Can be cached into memory in easier form to search
1823• How are directories modified?
1824– Originally, direct read/write of special file
1825– System calls for manipulation: mkdir, rmdir
1826– Ties to file creation/destruction
1827» On creating a file by name, new inode grabbed and
1828associated with new file in particular directory
182914
1830Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1831Directory Organization
1832• Directories organized into a hierarchical structure
1833– Seems standard, but in early 70’s it wasn’t
1834– Permits much easier organization of data structures
1835• Entries in directory can be either files or
1836directories
1837• Files named by ordered set (e.g., /programs/p/list)
1838Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1839Directory Structure
1840• Not really a hierarchy!
1841– Many systems allow directory structure to be organized
1842as an acyclic graph or even a (potentially) cyclic graph
1843– Hard Links: different names for the same file
1844» Multiple directory entries point at the same file
1845– Soft Links: “shortcut” pointers to other files
1846» Implemented by storing the logical name of actual file
1847• Name Resolution: The process of converting a logical
1848name into a physical resource (like a file)
1849– Traverse succession of directories until reach target file
1850– Global file system: May be spread across the network
185115
1852Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1853Directory Structure (Con’t)
1854• How many disk accesses to resolve “/my/book/count”?
1855– Read in file header for root (fixed spot on disk)
1856– Read in first data block for root
1857» Table of file name/index pairs. Search linearly – ok since
1858directories typically very small
1859– Read in file header for “my”
1860– Read in first data block for “my”; search for “book”
1861– Read in file header for “book”
1862– Read in first data block for “book”; search for “count”
1863– Read in file header for “count”
1864• Current working directory: Per-address-space pointer
1865to a directory (inode) used for resolving file names
1866– Allows user to specify relative filename instead of
1867absolute path (say CWD=“/my/book” can resolve “count”)
1868Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1869Where are inodes stored?
1870• In early UNIX and DOS/Windows’ FAT file
1871system, headers stored in special array in
1872outermost cylinders
1873– Header not stored near the data blocks. To read a
1874small file, seek to get header, seek back to data.
1875– Fixed size, set when disk is formatted. At
1876formatting time, a fixed number of inodes were
1877created (They were each given a unique number,
1878called an “inumber”)
187916
1880Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1881Where are inodes stored?
1882• Later versions of UNIX moved the header
1883information to be closer to the data blocks
1884– Often, inode for file stored in same “cylinder
1885group” as parent directory of the file (makes an ls
1886of that directory run fast).
1887– Pros:
1888» UNIX BSD 4.2 puts a portion of the file header
1889array on each cylinder. For small directories, can
1890fit all data, file headers, etc in same cylinderno
1891seeks!
1892» File headers much smaller than whole block (a few
1893hundred bytes), so multiple headers fetched from
1894disk at same time
1895» Reliability: whatever happens to the disk, you can
1896find many of the files (even if directories
1897disconnected)
1898– Part of the Fast File System (FFS)
1899» General optimization to avoid seeks
1900Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1901• Open system call:
1902– Resolves file name, finds file control block (inode)
1903– Makes entries in per-process and system-wide tables
1904– Returns index (called “file handle”) in open-file table
1905• Read/write system calls:
1906– Use file handle to locate inode
1907– Perform appropriate reads or writes
1908In-Memory File System Structures
190917
1910Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1911File System Caching
1912• Key Idea: Exploit locality by caching data in memory
1913– Name translations: Mapping from pathsinodes
1914– Disk blocks: Mapping from block addressdisk content
1915• Buffer Cache: Memory used to cache kernel resources,
1916including disk blocks and name translations
1917– Can contain “dirty” blocks (blocks yet on disk)
1918• Replacement policy? LRU
1919– Can afford overhead of timestamps for each disk block
1920– Advantages:
1921» Works very well for name translation
1922» Works well in general as long as memory is big enough to
1923accommodate a host’s working set of files.
1924– Disadvantages:
1925» Fails when some application scans through file system,
1926thereby flushing the cache with data used only once
1927» Example: find . –exec grep foo {} \;
1928• Other Replacement Policies?
1929– Some systems allow applications to request other policies
1930– Example, ‘Use Once’:
1931» File system can discard blocks as soon as they are used
1932Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1933File System Caching (con’t)
1934• Cache Size: How much memory should the OS allocate
1935to the buffer cache vs virtual memory?
1936– Too much memory to the file system cache  won’t be
1937able to run many applications at once
1938– Too little memory to file system cache  many
1939applications may run slowly (disk caching not effective)
1940– Solution: adjust boundary dynamically so that the disk
1941access rates for paging and file access are balanced
1942• Read Ahead Prefetching: fetch sequential blocks early
1943– Key Idea: exploit fact that most common file access is
1944sequential by prefetching subsequent disk blocks ahead of
1945current read request (if they are not already in memory)
1946– Elevator algorithm can efficiently interleave groups of
1947prefetches from concurrent applications
1948– How much to prefetch?
1949» Too many imposes delays on requests by other applications
1950» Too few causes many seeks (and rotational delays) among
1951concurrent file requests
195218
1953Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1954File System Caching (con’t)
1955• Delayed Writes: Writes to files not immediately sent
1956out to disk
1957– Instead, write() copies data from user space buffer
1958to kernel buffer (in cache)
1959» Enabled by presence of buffer cache: can leave written
1960file blocks in cache for a while
1961» If some other application tries to read data before
1962written to disk, file system will read from cache
1963– Flushed to disk periodically (e.g. in UNIX, every 30 sec)
1964– Advantages:
1965» Disk scheduler can efficiently order lots of requests
1966» Disk allocation algorithm can be run with correct size value
1967for a file
1968» Some files need never get written to disk! (e..g temporary
1969scratch files written /tmp often don’t exist for 30 sec)
1970– Disadvantages
1971» What if system crashes before file has been written out?
1972» Worse yet, what if system crashes before a directory file
1973has been written out? (lose pointer to inode!)
1974Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1975Important “ilities”
1976• Availability: the probability that the system can
1977accept and process requests
1978– Often measured in “nines” of probability. So, a 99.9%
1979probability is considered “3-nines of availability”
1980– Key idea here is independence of failures
1981• Durability: the ability of a system to recover data
1982despite faults
1983– This idea is fault tolerance applied to data
1984– Doesn’t necessarily imply availability: information on
1985pyramids was very durable, but could not be accessed
1986until discovery of Rosetta Stone
1987• Reliability: the ability of a system or component to
1988perform its required functions under stated conditions
1989for a specified period of time (IEEE definition)
1990– Usually stronger than simply availability: means that the
1991system is not only “up”, but also working correctly
1992– Includes availability, security, fault tolerance/durability
1993– Must make sure data survives system crashes, disk
1994crashes, other problems
199519
1996Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
1997Log Structured and Journaled File Systems
1998• Better reliability through use of log
1999– All changes are treated as transactions
2000– A transaction is committed once it is written to the log
2001» Data forced to disk for reliability
2002» Process can be accelerated with NVRAM
2003– Although File system may not be updated immediately,
2004data preserved in the log
2005• Difference between “Log Structured” and “Journaled”
2006– In a Log Structured filesystem, data stays in log form
2007– In a Journaled filesystem, Log used for recovery
2008• For Journaled system:
2009– Log used to asynchronously update filesystem
2010» Log entries removed after used
2011– After crash:
2012» Remaining transactions in the log performed (“Redo”)
2013» Modifications done in way that can survive crashes
2014• Examples of Journaled File Systems:
2015– Ext3 (Linux), XFS (Unix), etc.
2016Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2017How to make file system durable?
2018• Disk blocks contain Reed-Solomon error correcting
2019codes (ECC) to deal with small defects in disk drive
2020– Can allow recovery of data from small media defects
2021• Make sure writes survive in short term
2022– Either abandon delayed writes or
2023– use special, battery-backed RAM (called non-volatile RAM
2024or NVRAM) for dirty blocks in buffer cache.
2025• Make sure that data survives in long term
2026– Need to replicate! More than one copy of data!
2027– Important element: independence of failure
2028» Could put copies on one disk, but if disk head fails…
2029» Could put copies on different disks, but if server fails…
2030» Could put copies on different servers, but if building is
2031struck by lightning….
2032» Could put copies on servers in different continents…
2033• RAID: Redundant Arrays of Inexpensive Disks
2034– Data stored on multiple disks (redundancy)
2035– Either in software or hardware
2036» In hardware case, done by disk controller; file system may
2037not even know that there is more than one disk in use
203820
2039Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2040Solid State Disk (SSD)
2041• Becoming Possible to store
2042(relatively) large amounts of data
2043– E.g. Can buy a 1TB SSD for ~$200
2044– NAND FLASH most common
2045» Written in blocks – similarity to
2046DISK, without seek time
2047– Non-volatile – just like disk,
2048so can be disk replacement
2049• Advantages over Disk
2050– Lower power, greater reliability, lower noise (no moving parts)
2051– 100X Faster reads than disk (no seek)
2052• Disadvantages
2053– Cost (5+X) per byte over disk
2054– Relatively slow writes (but still faster than disk)
2055– Write endurance: cells wear out if used too many times
2056» 105 to 106 writes
2057» Multi-Level Cells  Single-Level Cells  Failed Cells
2058» Use of “wear-leveling” to distribute writes over less-used blocks
2059Trapped Charge/No charge
2060on floating gate
2061MLC: MultiLevel Cell
2062Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2063Conclusion
2064• File System:
2065– Transforms blocks into Files and Directories
2066– Optimize for access and usage patterns
2067– Maximize sequential access, allow efficient random
2068access
2069• File (and directory) defined by header
2070– Called “inode” with index called “inumber”
2071• Multilevel Indexed Scheme
2072– Inode contains file info, direct pointers to blocks,
2073– indirect blocks, doubly indirect, etc..
2074• Cray DEMOS: optimization for sequential access
2075– Inode holds set of disk ranges, similar to segmentation
207621
2077Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2078Conclusion
2079• 4.2 BSD Multilevel index files
2080– Inode contains pointers to actual blocks, indirect blocks,
2081double indirect blocks, etc
2082– Optimizations for sequential access: start new files in
2083open ranges of free blocks
2084– Rotational Optimization
2085• Naming: act of translating from user-visible names to
2086actual system resources
2087– Directories used for naming for local file systems
2088• Important system properties
2089– Availability: how often is the resource available?
2090– Durability: how well is data preserved against faults?
2091– Reliability: how often is resource performing correctly?
2092
20931
2094Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2095• Resources – passive entities needed by threads to do
2096their work
2097– CPU time, disk space, memory
2098• Two types of resources:
2099– Preemptable – can take it away
2100» CPU, Embedded security chip
2101– Non-preemptable – must leave it with the thread
2102» Disk space, plotter, chunk of virtual address space
2103» Mutual exclusion – the right to enter a critical section
2104• Resources may require exclusive access or may be
2105sharable
2106– Read-only files are typically sharable
2107– Printers are not sharable during time of printing
2108• One of the major tasks of an operating system is to
2109manage resources
2110Resources
2111Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2112Starvation vs Deadlock
2113• Starvation vs. Deadlock
2114– Starvation: thread waits indefinitely
2115» Example, low-priority thread waiting for resources
2116constantly in use by high-priority threads
2117– Deadlock: circular waiting for resources
2118» Thread A owns Res 1 and is waiting for Res 2
2119Thread B owns Res 2 and is waiting for Res 1
2120– Deadlock  Starvation but not vice versa
2121» Starvation can end (but doesn’t have to)
2122» Deadlock can’t end without external intervention
2123Res 1 Res 2
2124Thread
2125B
2126Thread
2127A
2128Wait
2129For
2130Wait
2131For
2132Owned
2133By
2134Owned
2135By
21362
2137Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2138Conditions for Deadlock
2139• Deadlock not always deterministic – Example 2 mutexes:
2140Thread A Thread B
2141x.P(); y.P();
2142y.P(); x.P();
2143y.V(); x.V();
2144x.V(); y.V();
2145– Deadlock won’t always happen with this code
2146» Have to have exactly the right timing (“wrong” timing?)
2147» So you release a piece of software, and you tested it, and
2148there it is, controlling a nuclear power plant…
2149• Deadlocks occur with multiple resources
2150– Means you can’t decompose the problem
2151– Can’t solve deadlock for each resource independently
2152• Example: System with 2 disk drives and two threads
2153– Each thread needs 2 disk drives to function
2154– Each thread gets one disk and waits for another one
2155Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2156Bridge Crossing Example
2157• Each segment of road can be viewed as a resource
2158– Car must own the segment under them
2159– Must acquire segment that they are moving into
2160• For bridge: must acquire both halves
2161– Traffic only in one direction at a time
2162– Problem occurs when two cars in opposite directions on
2163bridge: each acquires one segment and needs next
2164• If a deadlock occurs, it can be resolved if one car
2165backs up (preempt resources and rollback)
2166– Several cars may have to be backed up
2167• Starvation is possible
2168– East-going traffic really fast  no one goes west
21693
2170Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2171Train Example (Wormhole-Routed Network)
2172• Circular dependency (Deadlock!)
2173– Each train wants to turn right
2174– Blocked by other trains
2175– Similar problem to multiprocessor networks
2176• Fix? Imagine grid extends in all four directions
2177– Force ordering of channels (tracks)
2178» Protocol: Always go east-west first, then north-south
2179– Called “dimension ordering” (X then Y)
2180Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2181Recall: Dining Philosophers Problem
2182• Five chopsticks/Five philosophers
2183– Free-for all: Each philosopher will grab any one they can
2184– Need two chopsticks to eat
2185• What if all grab at same time?
2186– Deadlock!
2187• How to fix deadlock?
2188– Make one of them give up a chopstick (Hah!)
2189– Eventually everyone will get chance to eat
2190• How to prevent deadlock?
2191– Never let philosopher take last chopstick if no hungry
2192philosopher has two chopsticks afterwards
21934
2194Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2195Four requirements for Deadlock
2196• Mutual exclusion
2197– Only one thread at a time can use a resource.
2198• Hold and wait
2199– Thread holding at least one resource is waiting to
2200acquire additional resources held by other threads
2201• No preemption
2202– Resources are released only voluntarily by the thread
2203holding the resource, after thread is finished with it
2204• Circular wait
2205– There exists a set {T1
2206, …, Tn
2207} of waiting threads
2208» T1 is waiting for a resource that is held by T2
2209» T2
2210is waiting for a resource that is held by T3
2211» …
2212» Tn
2213is waiting for a resource that is held by T1
2214Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2215Symbols
2216Resource-Allocation Graph
2217• System Model
2218– A set of Threads T1
2219, T2
2220, . . ., Tn
2221– Resource types R1
2222, R2
2223, . . ., Rm
2224CPU cycles, memory space, I/O devices
2225– Each resource type Ri has Wi
2226instances.
2227– Each thread utilizes a resource as follows:
2228» Request() / Use() / Release()
2229• Resource-Allocation Graph:
2230– V is partitioned into two types:
2231» T = {T1
2232, T2
2233, …, Tn
2234}, the set threads in the system.
2235» R = {R1
2236, R2
2237, …, Rm}, the set of resource types in system
2238– request edge – directed edge T1  Rj
2239– assignment edge – directed edge Rj  Ti
2240R1
2241R2
2242T1 T2
22435
2244Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2245Resource Allocation Graph Examples
2246T1 T2 T3
2247R1 R2
2248R3
2249R4
2250Simple Resource
2251Allocation Graph
2252T1 T2 T3
2253R1 R2
2254R3
2255R4
2256Allocation Graph
2257With Deadlock
2258T1
2259T2
2260T3
2261R2
2262R1
2263T4
2264Allocation Graph
2265With Cycle, but
2266No Deadlock
2267• Recall:
2268– request edge – directed edge T1  Rj
2269– assignment edge – directed edge Rj  Ti
2270Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2271Methods for Handling Deadlocks
2272• Allow system to enter deadlock and then recover
2273– Requires deadlock detection algorithm
2274– Some technique for forcibly preempting resources
2275and/or terminating tasks
2276• Ensure that system will never enter a deadlock
2277– Need to monitor all lock acquisitions
2278– Selectively deny those that might lead to deadlock
2279• Ignore the problem and pretend that deadlocks
2280never occur in the system
2281– Used by most operating systems, including UNIX
22826
2283Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2284T1
2285T2
2286T3
2287R2
2288R1
2289T4
2290Deadlock Detection Algorithm
2291• Only one of each type of resource  look for loops
2292• More General Deadlock Detection Algorithm
2293– Let [X] represent an m-ary vector of non-negative
2294integers (quantities of resources of each type):
2295[FreeResources]: Current free resources each type
2296[RequestX]: Current requests from thread X
2297[AllocX]: Current resources held by thread X
2298– See if tasks can eventually terminate on their own
2299[Avail] = [FreeResources]
2300Add all nodes to UNFINISHED
2301do {
2302done = true
2303Foreach node in UNFINISHED {
2304if ([Requestnode] <= [Avail]) {
2305remove node from UNFINISHED
2306[Avail] = [Avail] + [Allocnode]
2307done = false
2308}
2309}
2310} until(done)
2311– Nodes left in UNFINISHED  deadlocked
2312Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2313What to do when detect deadlock?
2314• Terminate thread, force it to give up resources
2315– In Bridge example, Godzilla picks up a car, hurls it into
2316the river. Deadlock solved!
2317– Shoot a dining philosopher
2318– But, not always possible – killing a thread holding a
2319mutex leaves world inconsistent
2320• Preempt resources without killing off thread
2321– Take away resources from thread temporarily
2322– Doesn’t always fit with semantics of computation
2323• Roll back actions of deadlocked threads
2324– Hit the rewind button on TiVo, pretend last few
2325minutes never happened
2326– For bridge example, make one car roll backwards (may
2327require others behind him)
2328– Common technique in databases (transactions)
2329– Of course, if you restart in exactly the same way, may
2330reenter deadlock once again
2331• Many operating systems use other options
23327
2333Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2334Techniques for Preventing Deadlock
2335• Infinite resources
2336– Include enough resources so that no one ever runs out of
2337resources. Doesn’t have to be infinite, just large
2338– Give illusion of infinite resources (e.g. virtual memory)
2339– Examples:
2340» Bay bridge with 12,000 lanes. Never wait!
2341» Infinite disk space (not realistic yet?)
2342• No Sharing of resources (totally independent threads)
2343– Not very realistic
2344• Don’t allow waiting
2345– How the phone company avoids deadlock
2346» Call to your Mom in Toledo, works its way through the phone
2347lines, but if blocked get busy signal.
2348– Technique used in Ethernet/some multiprocessor nets
2349» Everyone speaks at once. On collision, back off and retry
2350– Inefficient, since have to keep retrying
2351» Consider: driving to Montreal; when hit traffic jam,
2352suddenly you’re transported back home and told to retry!
2353Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2354Techniques for Preventing Deadlock (con’t)
2355• Make all threads request everything they’ll need at
2356the beginning.
2357– Problem: Predicting future is hard, tend to overestimate
2358resources
2359– Example:
2360» If need 2 chopsticks, request both at same time
2361» Don’t leave home until we know no one is using any
2362intersection between here and where you want to go; only
2363one car on the bridge at a time
2364• Force all threads to request resources in a particular
2365order preventing any cyclic use of resources
2366– Thus, preventing deadlock
2367– Example (x.P, y.P, z.P,…)
2368» Make tasks request disk, then memory, then…
2369» Keep from deadlock on freeways around city by requiring
2370everyone to go clockwise
23718
2372Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2373• Toward right idea:
2374– State maximum resource needs in advance
2375– Allow particular thread to proceed if:
2376(available resources - #requested)  max
2377remaining that might be needed by any thread
2378• Banker’s algorithm (less conservative):
2379– Allocate resources dynamically
2380» Evaluate each request and grant if some
2381ordering of threads is still deadlock free afterward
2382» Technique: pretend each request is granted, then run
2383deadlock detection algorithm, substituting
2384([Maxnode]-[Allocnode] ≤ [Avail]) for ([Requestnode] ≤ [Avail])
2385Grant request if result is deadlock free (conservative!)
2386» Keeps system in a “SAFE” state, i.e. there exists a
2387sequence {T1
2388, T2
2389, … Tn
2390} with T1
2391requesting all remaining
2392resources, finishing, then T2
2393requesting all remaining
2394resources, etc..
2395– Algorithm allows the sum of maximum resource needs of all
2396current threads to be greater than total resources
2397Banker’s Algorithm for Preventing Deadlock
2398Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2399Banker’s Algorithm Example
2400• Banker’s algorithm with dining philosophers
2401– “Safe” (won’t cause deadlock) if when try to grab
2402chopstick either:
2403» Not last chopstick
2404» Is last chopstick but someone will have
2405two afterwards
2406– What if k-handed philosophers? Don’t allow if:
2407» It’s the last one, no one would have k
2408» It’s 2nd to last, and no one would have k-1
2409» It’s 3rd to last, and no one would have k-2
2410» …
24119
2412Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2413CPU Scheduling
2414• Earlier, we talked about the life-cycle of a thread
2415– Active threads work their way from Ready queue to
2416Running to various waiting queues.
2417• Question: How is the OS to decide which of several
2418tasks to take off a queue?
2419– Obvious queue to worry about is ready queue
2420– Others can be scheduled as well, however
2421• Scheduling: deciding which threads are given access
2422to resources from moment to moment
2423Scheduling Assumptions
2424• CPU scheduling big area of research in early 70’s
2425• Many implicit assumptions for CPU scheduling:
2426– One program per user
2427– One thread per program
2428– Programs are independent
2429• Clearly, these are unrealistic but they simplify the
2430problem so it can be solved
2431– For instance: is “fair” about fairness among users or
2432programs?
2433» If I run one compilation job and you run five, you get five
2434times as much CPU on many operating systems
2435• The high-level goal: Dole out CPU time to optimize
2436some desired parameters of system
2437USER1 USER2 USER3 USER1 USER2
2438Time
2439Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
244010
2441Assumption: CPU Bursts
2442• Execution model: programs alternate between bursts of
2443CPU and I/O
2444– Program typically uses the CPU for some period of time,
2445then does I/O, then uses CPU again
2446– Each scheduling decision is about which job to give to the
2447CPU for use by its next CPU burst
2448– With timeslicing, thread may be forced to give up CPU
2449before finishing current CPU burst
2450Weighted toward small bursts
2451Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2452Adapted from Kubiatowicz’s CS162 Lecture Slides. Copyright © 2010 UCB
2453Summary (Deadlock)
2454• Four conditions required for deadlocks
2455– Mutual exclusion
2456» Only one thread at a time can use a resource
2457– Hold and wait
2458» Thread holding at least one resource is waiting to acquire
2459additional resources held by other threads
2460– No preemption
2461» Resources are released only voluntarily by the threads
2462– Circular wait
2463»  set {T1
2464, …, Tn
2465} of threads with a cyclic waiting pattern
2466• Deadlock detection
2467– Attempts to assess whether waiting graph can ever
2468make progress
2469• Deadlock prevention
2470– Assess, for each allocation, whether it has the potential
2471to lead to deadlock
2472– Banker’s algorithm gives one way to assess this