New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer Operating Systems

by: Trent Dare

Computer Operating Systems CS 481

Marketplace > University of New Mexico > ComputerScienence > CS 481 > Computer Operating Systems
Trent Dare
GPA 3.76

Dorian Arnold

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Dorian Arnold
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 47 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 481 at University of New Mexico taught by Dorian Arnold in Fall. Since its upload, it has received 28 views. For similar materials see /class/212204/cs-481-university-of-new-mexico in ComputerScienence at University of New Mexico.


Reviews for Computer Operating Systems


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/15
THE UNIVERSITY of NEW MEXICO File System Components Logical file system Manages filedirectory metadata file control block inode m Protection and security Implementation File organization module Logical to physical block translation Physical block drive cylinder track sector Manages and allocates physical blocks to files Basic file system Issues readwrite commands to device driver Plot Dona Amo39d I I File system buffering and caching CS 481 Operating System PrInCIples Spring 09 File lO System application programs User process Virtual File Systems One API many file systems types logical file system File system filesystem interface fileorganization module VFS interface lO control devices local file system local file system remote file system type 2 l network 4 File System Structure on disk Boot control block For booting OS if present on file system Volume control block Volume information block count free blocks Directory structure Directory entry filename inode File table Perfile FCB inode File System Structure in memory Mount table Information about each mounted volume Directorystructure cache Systemwide openfile table Perprocess openfile table Data buffers Directory Implementation Remember your data structures class Linear lists Linked lists Trees Hash tables File Allocation How do we allocate disk blocks to individual files 2 primary considerations Speed of accessing requested data block Types of access sequential and direct random Storage Efficiency Contiguous Allocation Linked Allocation File is a linked list of disk blocks lZlBlocks need not be contiguous IZlFiles can grow lZlNo external fragmentation Files occupy contiguous blocks on disk lZlSimple start block of blocks IZlGood for sequential and random access Finding space for new file Bad for random access Files cannot grow Internalexternal fragmentation 11 Contiguous Allocation cont d Linked Allocation A directory file start length quot90 ory count file start end 0D 1B 2C 3D count 0 2 jeep 9 25 f tr 14 3 4D 5D 6D 7D mail 19 6 8D 9ll1oll11ll quotSt 28 4 tr f 6 2 12D13lZl14lZl15D 16I17EI18I19I mail 20D21D22D23El 2021 223 24lj25l126l27l 24l252627D list 28D29ElsoE31El 28l2913031 11 W 10 12 File Allocation Table FAT Indexed Allocation Separate table for linked list of disk blocks Indexed by block number Bring all pointers into single index block Entry is pointer to next block Each has index block Directory entry points to first block of file Array of disk block addresses lZlGood for random access I I I IZlRead FAT to find requested block IZlEffICIent random access Without FAT IZlNo external fragmentation Internal fragmentation Potentially wasted space in index block Can require significant disk latency Moving between FAT and disk blocks to read File Allocation Table FAT lndexed Allocation A d39 t t irec ory en ry directory n name start block file index blOCk 0 oll 1 2l 3l Jeep 19 4 5 7 217 D D 1 8D 9 1o 11l 12El13ll14 1 389 618 20 D21 D22 23D 24 D25 26j27lZl waDmeD 14 16 no of disk blocks 1 Indexing Large Files Linked index blocks Index block contains set of indices and pointer to next block Multilevel index blocks 2 levels 1st level block points to set of 2nd level blocks 2nd level blocks point to file data blocks Combination schemes Direct and indirect blocks UNIX Combined Allocation Scheme mode owners 2 timestamps 3 size block count direct blocks 0 n 0 single indirect double indirect triple indirect Bit vector Good for finding contiguous free blocks Space inefficient Linked list of free blocks No wasted space Inefficient to traverse read each block Expensive to find contiguous free blocks Grouping linked list of block groups Counting linked list of disk block and number of contiguous free blocks Free Disk Space Management THE UNIVERSITY 0f NEW MEXICO Memory Management Considerations Performance memory devices have different latencies Main Memory Protection OS must be protected Processes must be protected from each other Prof Dorian Arnold 08481Opergtin9 ngtem Principles Processes must have consistent view of data prlng Background Address Space Protection A process has own disjoint address space Hardware validates every memory access Instruction execution cycle Base register smallest legal physical address CPU fetch instruction from mainmemory via PC register Limit register Size Of process address space CPU decodes instruction 0 operating CPU executes Instruction system load data from memory to register CPU can only access registers or main memory All instructions or data must be in register or main memory 2 560 00 haso Ease inquot store data from register to memory process 39 mOdifY register Value eg increment 300040 MW 7 m m process base CPU Register access fast typically one cycle 420940 Memory access slow many cycles CPU stalls Cache fast memory between CPU and main memory trap in operating system quot moniIm acxs essmg error mam W 880000 1024000 2 I I I I 4 Should user have writeaccess to base and limit registers Process Address Space stack temporary per function call data h p dwmmmNWaMmamdmemow data static globals initialized unitialized 0 t8 prograntcode Why Dynamic Memory Don t know needs at compile time If using static allocation must be pessimistic overestimate before underestimate Recursive procedures How many times will procedures be called Processes have 2 types of dynamic allocations Stack Heap Process Stack Stack frame implicitly allocated per function call Used for procedure s local data Arguments Local variables Return address Process Stack cont d main int a O foo a fooint b int c l foo 2 2nd foo s stack 1St foo s stack main s stack b2 return foo c1 b0 a0 return main Explicitly allocate at any point in time 08 View one contiguous area of memory being used by process Typical process View many small chunks of potentially noncontiguous allocations Process Heap cont d free main a mallocl6 b malloc24 c malloc48 w 48 bytes of process heap c V t 24 bytes free f re e b b 16 bytes 39 a Heap allocation can be slow Can have many small chunks of free space fragmentation l0 Fragmentation Free memory too small to be useful External fragmentation unused unallocated fragment Internal fragmentation unused fragment allocated w used fragment eg padding allocation fragments Want to minimize memory fragmentation Dynamic Memory Implementations Often free list of available memory chunks can use bit map for fixed size chunks Chunk header size next free chunk Allocate 4 choose chunk large enough for allocation update free list data structure Free add free d chunk backto free list maybe compact free list data structure Allocation Policies Multiprogramming Goals Best fit Sharing search all entries for Closest match Multiple processes simultaneously in main memory Cooperating processes can share portions of address space a Flrst flt Transparency Search free 31 for rst match Processes should be unaware ofmemoly shari Works regardless of number or location of processes a NeXt flt Protection search free st for rst match 08 should be protected from processes Processes should be protected from each other start search from last searched posttlon I Efficien y Worst fit C High CPUmemory utilization find largest available chunk Freeing Memory Memory Management Overview l Explicit deallocation free El Recycling storage that is still in use Pro ram relocation eg two pointers to same chunk free 15 use 2quotd g Programs must be in memory to be executed El Memory leak lose pointer to nonfreed chunk Implicit deallocation El Needs languagesystem support Segmentation Partition address space into distinct areas Reference countin tree when last reference goes away Paging Garbage collection Fine grain address space partitioning pages maintain all objects and pointers to objects comprise segments recycle all objects not pointed to by any pointers lZl Expensive Relocation Cannot predict where process will be loaded into main memory Adjust program to run in different memory areas Static vs dynamic relocation Memory Allocation Contiguous Virtual Address Space Physical Memory Naming The Relocation Problem Source code uses symbolic address naming Eg int a char foo Compiler binds symbolic addresses to relocatable addresses Eg 14 bytes from start of this modulequot Loader binds relocatable addresses to absolute addresses Eg 0x8888 Whenhow do we bind to absolute addresses 9 Static Relocation Compiler binds to absolute address Must know program memory location at compile time Loader binds to absolute address Compiler generates relocatable code Requires reloading if program39s main memory location to change IZI No hardwareOS support needed Program location cannot change Swap in must restore original location Requires contiguous memory allocation Must overallocate stackheap Fragmentation how Dynamic Relocation Address Space cont d p Main Memory Bind to absolute address on every messes 0000 reference I I 0000 Programs generate logIcal or Virtual 0010 1000 addresses 1010 Hardware translates to physical or real address 2000 lZlProgram can be relocated at any time Address resolution can be costly Requires OShardware support Memory management unit MMU 21 Two Address Space Views Dynamic Relocation Implementation MMU uses base and limit registers Logical virtual address process view my 256000 basal im Imir Physncal real address actual address In p rrrr 35 3971 main memory p rrrr SS 3330 3939ffjgt quot jf39393939fjaw Memory Management Unit MMU I maps logical to physical addresses 880000 p rrrr SS quotgem CPU MMU Memory logical physical addresses addresses 22 24 Dynamic Relocation Implementation relocation register logical physical address address C PU memo ry 346 V 14346 MMU Context switching 1 Change to privileged mode 2 Save limit register of old process 3 Load limit and set relocation registers of new process 4 Change back to user mode 5 Run new process 25 BaseLimit Relocation IZlProtects address spaces IZlSupports dynamic relocation IZlSimple and inexpensive Few registers fast logic add and compare Requires contiguous memory allocation Overallocation gt fragmentation No partial sharing cannot share proper subset of address space Segmentation Divide address space into independent logical areas Map to user s view of memory areas Eg code stack heap libraries functions Placed separately in physical memory Can grow and shrink Have distinct protection bits 27 Memory Allocation Segmentation P0 Po 51 P1 So P P PZSZ P S PO S Virtual Address Space Physical Memory 28 User s View of a Program stack symbol table main program loqical address Logical View of Segmentation user space physical memory space Segmentation Architecture Virtual Address Segment Offset I Seg Base Limit R Segment 1 0X4000 0X1000 Table 2 0X1000 0X0570 3 0X2000 0X0120 4 OXOOOO 0X0800 5 0X3000 0X0300 L L L L L AO L LOE O o OX Highorder bits of address segment Look up segment base in segment table Loworder bits of address offset Compare offset to segment limit Segmentation IZlSparse allocation of address space lZlDifferentiate protection on per segment basis Ilendependent segment swappingrelocation Segment requires contiguous memory allocation Large segments Simplify swapping allocation Eliminate external fragmentation Fixed size chunks pages Typically 512 8096 bytes PCB includes page table Memory Allocation Paging PJer ll Porpo POrPI P0 PJrPo PJrPJ P1 r Po p PM 1 PM Virtual Address Space Physical Memory 34 Page table maps virtual pagesaddresses to physical framesaddresses Paging Translating Virtual Addresses Highorder bit gt page number Loworder bit gt page offset Logical address space 2m page size 2n Page number mn bits page offset n bits 32 bits 20 bits 12 bits Logical address page number page offset page table Physical address page offset Paging Hardware logical physical address address lOOOO I I39ll 1111111 0000 physical memor page table y a free frame list free frame list d 14 13 15 13 page 1 e 4 I f j 1 T 14 14 page 0 i 2 1 T 15 15 J n k 3 2 o page table p m 12 1 5 1 6 n 2 if 17 17 logical memory 16 18 18 page 2 2 3 19 19 C d 2T 20 20 page 3 a 21 newprocess page table 21 28 a b 37 39 physical memory Paging and Fragmentation FramePage sizes Range from 512B to 8KB Typically 4KB or 8KB No external fragmentation Any free frame can be allocated to a process Large page sizes Greater internal fragmentation Possible internal fragmentation Sma Page SizeS Greater page table overhead Entire frame may not be used 4 bytes per pagetable entry Eg How much memory for page table to manage 64 GB of physical memory divided into 512 B frames 64 GB 236 bytes physical memory 512 B 28 bytes page size 236 28 228 pages 228 entries X 4 bytes per entry 230 bytes or 1 GB for page table 40 Page Table Implementations Paging requires two lookups per access 1St to page table to resolve requested address 2ncl to access requested address Desire page table reference to be fast Small page tables can use fast registers In general page tables too large for registers 41 Paging and Memory Access Overhead Generally page table kept in memory Pagetable base register PTBR points to location of page table Not all processes need entire page table Pagetable limit register PTLR indicates size of page table Accessing main memory is slow 2 accessesreference doubles effective memory latency Solution translation lookaside buffer highspeed associative cache 42 Translation Lookaside Buffer TLB Fast associative hardware cache mapping keyvalue pairs Typically 64 1 024 entries Used to store page frame mappings TLB hit referenced page found Mapped frame returned immediately TLB miss referenced page not found Look up page in page table in physical memory Store page frame mapping in TLB TLB entry replacement strategies Paging Hardware with TLB logical page frame number number TLB hit physical address TLB p TLB miss physical memory page table 44 11 Effective Memory Access Time TLB hit ratio percentage of time referenced pages are found in TLB Example Hit ratio 08 TLB lookup latency 20 nanoseconds Memory access 100 nanoseconds Effective access time 08 x 120 02 x 220 140 nanoseconds mi latency e TLB memory access miss latency e TLB 2 memory accesses 45 TLB and address space protection Two strategies 1 Address space identifiers ASle in TLB entry 2 Flush TLB on context switch Paging Issues Page tables can get large Eg 32 bit logical address and 4KB page size 232 2 2 220 entries At 4 bytes per entry 222 byte 4MB page table 32 bits 20 bits 12 bits MultiIevel Paging Page tables need to be contiguous Solution sub divide the page table Page the page table Same example 2 levels each w 210 entries 2 0 x 2 0 220 entries At 4 bytes per entry 2 2 byte 4KB page tables 32 bits 10 bits 10 bits 12 bits Logical address ot fngzge page offset 2level Paging Hashed Page Tables 39 Common in address spaces gt 32 bits 1 550 100 o Virtual page hashed into page table 5 Page table contains a chain of elements x m 505 hashing to the same location m Virtual page numbers are compared in this 4 f chain searching for a match o omgblfge 9 900 39 If a match is found the corresponding physical gtlt frame is extracted 900 pageof 925 page table page table 49 51 mpmorv 2level Paging Address Translation Hashed Page Table logical address physical logical address address P1 P2 r P1 pet outer page gt table d physical q S P r l39 39 memory page of page table hash table Inverted Page Table Inverted Page Table Architecture One entry for each real page of memory Inverted page table entry logical address CPU pid p d i d physical address physical memory Decreases memory needed to store each page table but increases time needed to search the table when a page reference searchl lfi occurs W p Use hash table to limit the search to one or at most a few pagetable entries page table 53 55 lnverted Page Table Segmentation and Paging l l Virtual Addrss Segment Offset 4 8 12 Regular per process page table 1 entry per page whether valid or not u if Page Table Inverted global Table is a ma 1 entry per physical page 255 entry ltprocess id page numbergt lt 12 gt On reference search table for pid page match MSTmum Ileaves memory space PhysicalPageff I Offset 2ookups are expensive J Physical Memory 54 56 0 l 2 3 4 5 6 Deadlock What is Deadlock When competition for same resources leads to an impasse When two trains approach each other at a crossing both shall corrie to atull stop and neither shall start up again until the other has gonequot A set of processes are deadlocked when each process is waiting for an event that must come from one of the waiting processes Physical or logi cal resources Deadlock adlock two or more processes are waiting indetinitely tor an event that can be caused by only one ot the waiting process Physical or logical res es ource contention Let S and Q be two semaphores initialized to t Pu mutexgockls mutexgocklo mutexiunlock s mutexiunlock 07 Pl mutexlock0i mutexlockS muteLunlock O muteLunlock s Necessary Conditions for Deadlock 1 Mutual exclusion multiple processes cannot access resource simultaneously 2 Hold and wait process holding one resource and waiting for another 3 No resource preemption 4 Circular wait P0 is waiting for P1 is waiting for is waiting for P0 All 4 conditions must be true for deadlockto exist5 Representing Deadlock Two common ways Vertices Threads or processes Resources physical or logical Wait For Graph waiting forquot Waiting forquot ResourceAllocation Graph Handling Deadlock Deadlock prevention Ensure deadlock does not happen Ensure at least one of4 conditions does not occur Deadlock avoidance Ensure deadlock does not ha pen Use information about resource requests to dynamically avoid unsafe situations Deadlock detection and recove Allow deadlocks but detect when occur Recover and continue Do nothing Most OSes Deadlock Prevention Prevent at least one of tour necessary conditions from occurlng 1 Mutual Exclusion Usually not optional 2 Hold and Wait Allocate all resources at start u release any resource before requesting new one Low utilization Possible starvation Deadlock Prevention cont d 3 No resource preemption lf request not immediately grantable Release all current resources Preempt needed resources from waiting processes Preemption not always viable eg printer a 4 Circular wait Ordered resource requesting Deadlock Avoidance Safe state Future resource requests can be granted without causing deadlock Sequence in which each process only needs resources held by preceding processes Deadlock only caused by unsafe states Avoidance methodology assure that resource allocations maintains a safe state Avoidance ResourceAllocationGraph Add claim edge to resourceallocationgraph requires knowledge of future allocation requests A If O Safe state Safe state Unsafe state P1 is allocated R1 No deadlock if P2 has requested R1 P1 is allocated RIY and P1 and P2 have claimed R2 later P2 requests R2 Deadlock cycle if P2 is allocated RIY and later P1 requests R2 ll Avoidance Banker s Algorithm Give as much as possible while avoiding unsafe states Each process specifies maximum requests for each resource cannot exceed Do not grant request if allocation may prevent first process from finishing when 15 process finishes allocation may prevent 2nd process from finishing when first k processes finish and release resources allocation may prevent k1 h process from finishing Deadlock Detection Check for cycles in allocation or waitfor graphs Expensive On2 where n is number of processes When to run Every request Arbitrary intervals Deadlock Recovery Process Termination Terminate all processes Terminate one at a time until cycle is broken Which ones Process priority Process runtime Process remaining run time Resources held number type Resources needed Deadlock Recovery cont d Resource Preemption Which processes and which resources Rollback process to safe state Total rollback abort and restart Is it safe to redo all operations eg write to device Starvation File System Updates B Bitmap free list update allocatetree blocks D Data written to data blocks lnode updated to reflect changes NT 9 Journaling and Distributed File Systems Problem Multiple write operations All or none must complete Crash may occur any time CS 481 Operating System Principles Does updatete order matter File System Recovery Consider these update orders Bthen I then D Computers crash Must ensure consistenc when the do I the B the D y y I then Dthen B Crashes may interrupt disk updates Dthen 1 then B Upon recovery file system must be sensible Dthen Bthen I File data and metadata must agree Crash after 18 operation but before 2 d Disk updates either completed or never begun R It atomicit es 39 7 Updates completed in writerorder d 39 d 7 At reboot system returned to consistent state craSh after 2 operat39on bm before 3 Result Crash Recovery Solution Consistency checker ensures free blocks on free list 1 Allocate temporary bitmap initialize all disk blocks to free 2 Starting with inode for the root directory traverse 1 For each data block in directory file marks as quotallocatedquot 2 For each file in directory mark its data blocks as quotallocatedquot 3 For each directory in this directory traverse 3 Upon completion actual bitmap a temp bitmap a falled allocations Poor performance Can take hours to sanity check large disks Avoiding Long Scans Write ahead log orjournal Log disk transactions before starting Log file metadata or file metadata and data Delete transaction from log upon completion Use log to fix file system structures Upon crash redoundo incomplete transactions Don t need to scan entire file system only components involved in incomplete transactions Distributed File Systems Multiple clients on multiple machines accessing same files Why Distributed File Systems Roaming users Ease of administration Save space less replication backups Filesharing Flexibility multiple FSs Reliability Improved performance distributing load Challenges of Distributed Filesystems Transparency Single global filesystem view Consistency Same directoryfile contents from different views Performance Many users many access points many files ReliabilityCrash recovery Security Tradeoff between performance and consistency NFS Main ideas Stateless servers Servers retain no information about clients open files Server state doesn t grow with of clients All requests contain complete request information ldempotent operations Easily repeatable Simple recovery crash server looks like lost message or slow server retry NFS Architecture I client server systemcalls interface VFS interface VFS interface NFS I UNIX file NFS client other types of UNIX file file systems server system system NFS Implementation 39 Remote Procedure Call RPC based mechanisms 39 Client Transparent access via VFS 39 Stateless server Synchronous operation all modified data written to stable storage NFS Performance vs Consistency Strongest level of consistency any write by any client will be seen by any subsequent read on any client Expensive to maintain this strong consistency Good performance periodically synchronize different copies of same data Data copies can diverge vastly NFS Caching Read operations Metadata file attribute cache Update every 3 seconds Discard every 60 seconds Data cache Discard all file blocks when metadata updated Write operations Directories synchronously write to server Files flush every 30 seconds and on close GDB QUICK REFERENCE GDB version 4 Essential Commands gdb program core debug program using coredump core b lefartctrort set breakpoint at function in le run arglt39st start your program with arglt39st bt backtrace display program stack p eapr display the value of an expression c continue runni g your pro ram n next line stepping over functi n calls s next line stepping into function calls Starting GDB gdb start GDB with no debugging les gdb program begin debugging program gdb program core debug coredump core produced by program gdb sshelp describe command line options Stopping GDB quit exit GDB also q or EUF eg cad INTERRUPT eg csc terminate current command or send to running process Getting Help help list classes of commands help class onerline descriptions for commands in class help commarta describe commarta Executing your Program run arglz st start your program with arglz st run start your program with current argument Ist run ltt nf gtoutf start your program with input output redirected kill kill running program tty dcu use dcu as stdin and stdout for next run set args arglz st specify arglz st for next run set args specify em ty argument list show args display argument list show env show all environment variables show en 7 s w value of environment variable var set env var string set environment variable um unset env um remove um from environment Shell Commands cd arr change working directory to arr pwd Print working directory call make shell cma execute arbitrary shell command string surround optional arguments show one or more arguments 1993 Free Software Foundation Inc Permissions on back Breakpoints and Watchpoints break lelrrte set breakpoint at lt39rte number in le 1 lglmg eg break mainc break lefartc set breakpoint at func in le break offset set break at offset lines from current stop break o set break s aar set breakpoint at address aaar reak set break oint at next instruction break if eapr break conditionally on nonzero eapr cond rt eapr new conditional expression on breakpoint rt make unconditional if no eapr break temporary break disa le when reached rbreak rcgcz break on all functions matc lng rcgcz watc czpr set a watchpolnt for expression czpr catch event break at event whic ma ca ch hrow exec fork vfork load or unload info break info watch show de ned breakpoints show de ned watchpoints clear delete breakpoints at next instruction clear lefart delete breakpoints at entry to farto clear lc delete n lrrte delete breakpoints on source line delete breakpoints or breakpoint rt disable disable breakpoints or breakpoint rt enable rt enable breakpoints or breakpoint rt enable once n enable breakpoints or breakpoint n disable again when r ached enable del rt enable breakpoints or breakpoint rt delete when reached ignore n count ignore breakpoint n count times commands n execute GDB commandrlist every time silent breakpoint rt is reached silent commandslist suppresses default display end end of commandrlist Program Stack backtrace rt print trace of all frames in stack or of rt f a esiinnermost if rtgt0 outermost if frame rt select frame number rt or frame at address rt i no rt display current frame up n select frame n frames u down n select frame n frames down info frame addr describe selected frame or frame at addr lnfo ar s arguments of selected frame info locals local variables of selected frame info reg rrt register values for regs rrt in selected info allcreg frame allsreg includes oating point Execution Control continue count continue running if count speci ed ignore C mum t is breakpoint next count times step coartt execute until another line reached repeat 5 mum count times if speci e stepi coartt step by machine instructions rather than si coarit source lines next coartt execute next line including any function n coartt calls nexti coartt next machine instruction rather than m mum source line until location run until next instruction or location finish run until selected stack frame returns return eapr pop selected stack frame without executing setting return value signal num resume execution with signal 5 none if 0 jump lr39rte resume execution at speci ed line number jump add ress aaaress set Varczpr evaluate czpr without displaying it use for altering program variables Display print f eapr show value of eapr or last value as P f mm according to format f x hexadecimal unsigned decimal octal inary address absolute and relative character oating point Hawsoch call f eapr x Nuf eapr like print but does not display Void examine memory at address eapr optional format spec follows slash N count of how many units to display u unit size on 39 divi byt h halfwords two bytes w ords our es print format or ullrterminated string i machine instructions disassem aaar display memory as machine instructions Automatic Display display f eapr show value of eapr each time rogram stops according to format fp displa display all enabled expressions on list undisplay n remove number s n from list o automatically displayed expressions disable disp rt disable display for expressions number rt enable disp n info display enable display for expressions number rt numbered list of display expressions Expressions ezpr addTQlen le m type addr show Values show conv Symbol Table info address 5 info func Tegez info var Tegez whatis ezpr Ptype mil PWPe type GDB Scripts source sciipt def ine cm a comm andrlist d document cmd hel r ezt end Signals handle signal act rint noprint sto P nostop ass nopass info signals n expression in C C or Modulae2 including function calls or an array of len elements beginning at a r a variable or function Wm de ned in le read memory at addr as speci ed type most recent displayed value nth displayed value displayed value previous to nth displayed value back from last address examined with x value at address as convenience variable assign any value show last 10 values or surrounding n display all convenience variables show where symbol 5 is stored show names types of de ned functions all or matching Tegez show names types of global variables all or matching Tegez show data type of esz or 39 without evaluating ptype gives more detail describe type struct union or enum read execute GDB commands from le sc ri t create new GDB command cmd execute script de ned by commandrlist end f commandrlist create online documentation for new GDB mand cm end of helpstezt specify GDB actions for signal 39 l announce be silent for l alt execution on sl nal do t halt e utlo n allow your program to handle signal do not allow your program to see signal show table of signals GDB action for each Debugging Targets target type param connect to tar et machine process or le 1 ts help t arge att ach param det ach g isplay available targe connect to another process release target from GDB control Controlling GDB set param value show param set one of GDB s internal parameters isplay current setting of parameter Parameters understood by set and show comp aint limit number of messages on unusual symbols confirm ono enable or disable cautionary queries editing ono control readline commandsline editing height lpp number of lines before pause in display language lang Language for GDB expressions auto c or modulas2 listsize n prompt str ra ix base number of lines shown by list use str as GDB prom t octal decimal or hex number representation verbose ono control messages when loading symbols width epl write ono number of characters before line folded Allow or forbid patching binary core les when reopened with exec or core history groups with the following options h exp 0 on disableenable readline history expansion h file lename le for recording GDB command history h size size number of commands ke t in history list h save o on control use of external le for command histo print groups with the following options p p address ono print memory addresses in stacks values p array o on compact r attractive format for arrays p demangl ono source demangled or internal form for C symbols p asmsdem ono demangle C symbols in machine instruction outpu p elements limit number of array elements to display p object ono print C derived types for objects p pretty o on struct display compact or indented p union ono p vtbl o on display of union members display of C virtual function tables show commands show last 10 commands show commands n show 10 commands around number n show commands d show next 10 comman s Working Files file le use le for both symbols and executable with no arg discard both core le read le as coredump or discard exec le use le as executable only or discard symbol le use symbol table from le or discard load le namically lin le and add its symbols addpsym le addr read additional symbols from ynamically lo e at info files dls lay wor lng les and targ s in use path airs add airs to front of path searched for ex c l and symbol le show path info share list names aded Source Files dir names add directory names to front of source ath clear source path show dir show current source path list show next ten lines of source list 7 show previous ten lines list lines display source surrounding lines speci ed as lenum line number in named le lefunction beginning of function in named le off offlines after last printed soff offlines previous to last printed soddreee line containing add 55 list fl info line num compiled de for sou ce line n info source show na e of current source le i 0 sources lst all source le 1 se n search following source lines for Tegez rev Tegez search preceding source lines for Tegez GDB under GNU Emacs Max gdb run GDB under Emacs h m describ GD mo e Mas step one line step Min next line n x Mai step one instruction stepi csc csf nish current stack frame finish Mic continue cont Msu up my frames up Mid down my frames down csx amp copy number from point insert at end csx SPC in source le set break at point GDB License show copying show warranty Display GNU General Public License There is NO WARRANTY for GDB Display full nowarranty statement Copyright 1991 gt92 gt93 gt93 Free Software Foundation Inc Roland H Pesch The author assumes no responsibility for any errors on this card This card may be freely distributed under the terms of the GNU General Public License Please contribute to development of this card by annotating it Improvements can be sent to bugegdbognu org GDB itself is free software you are welcome to distribute copies of h GN 39 it under the terms of t e U General Public License T ere is absolutely no warranty for GD FileSystem Interface The 2 general tasks of a process 1 Processing 2 InputOutput So far we ve studied processing concepts Now we focus on file lO Are there useful programs with no lO Role of OS for lO Standard library Abstractions mkdlr create read write Access to hardware devices privileged Resource coordination Protection fairness and ef ciency What is a File User view A named sequence of bytes Typeduhtyped Structuredunstructured Persistent storage OS view Collection of blocks on nonvolatile storage Magnetic disks tapes NVRAM File Attributes Name humanreadable identifier Identifier unique tag within file system 39 Type Special files directory symbolic link Location Size Protection who can read write execute Times creation modification access File metadata also stored on disk in directory structure File Operatio Drezne ReadNV rite ReposMonseekthane elete Truncate Free disk space allocated to file Rename Copy Changeaccesspennbsbns Open Files Metadata Open 1 time lookup of file metadata Metadata cached in perprocess open file table File seek pointer current position for next readwrite Cached information for efficiency Disk location oi tile 7 Access rights Close deletes entry from process file table Flushes dirty cached information to persistent storage Directories Map file names to directory entries Directory entry for file contains its attributes Directory operations Search for file List contents Rename file Traverse file system Directory implementations Singlelevel Twolevel Treestructured AcyclicGraphs s General Graphs Singlelevel Directory TreeStructured Directories Globally unique file names Directory listing ltname indexgt IZlSimple Name can be another directory Naming Directory storedtreated like a special file Grouping Specral characters separate name components 0 homeusersjoetheplumber absolute path cs48llab4 relative path Special names files a m IZlGrouping Twolevel TreeStructured Directories cont d root bin 1 directory per user Naming user namefile name I am I mail I dis I I find Iooum hex IreorderI I p I 9 I mail I Grouping O 5 Q masterfile direCtory user1 usere users user4 Iprog I copyI prr I exp I IrearderI list I find I I hex IcounII Q user file 3 Q directory catI boI a ItestII a dataII a ItestII x IdataI aI 1 wwmglwlo Acyclic Graphs General Graph Directories Create links from one file or directory to another Shared subdirectories and files Idea Different names resolve to same file data 39 Hard link ln filel file2 Multiple directory entries point to same metadata No hard links to directories in UNIX Symbolic soft link in s filel file2 Contents of file2 contain name of filel 13 How can we prevent cycles 15 AcyclicGraph Directories File Protection Which users which type of access Read Write Execute Append Delete List What happens if dict deletes count 14 16 Access Control Mode read write execute User class owner group other public 06 ojoo o xg r A H HI drwx 7777 if 17 darnold faculty 4096 2009703713 00 8 drwxrixrix 44 darnold faculty 4096 2009703724 11 3 irw 7 1 darnold faculty 213 2009703713 00 5 ACKNOWLEDGME 1 darnold faculty 1639 2009703713 00 5 aclocalm4 3 darnold faculty 4096 2009703713 00 8 bin 5 darnold faculty 4096 2009703713 00 7 boost 1 darnold faculty 79 2009703713 00 7 bugstxt 1 darnold faculty 301 2009703713 00 7 classestxt 3 darnold faculty 4096 2009703713 00 5 conf 1 darnold faculty 41468 2009703713 00 7 configlog 1 darnold faculty 32379 2009703713 00 8 configstat 17 q wer wagiclxp I iJMUGDrs aptU51penntsmln For Spccral Formls ion or far advanced scumgs mm Alarmed A 5 mlt chums CS 481 Operating System Principles Pint m Old File System Performance Utilized 4 of peak disk bandwidth Small block sizes Data placement No locality of file inode and data blocks No locality of sequerttial file blocks No locality of file inodes in same directory Poor free list organization Randomly allocated data blocks Performance degradation over time 175 KBs a 30 KBs A Fast File System for UNIX The old file system superblock lnodes Data blocks 512 bytes A File ownership A 4 ol data blocks t Max 0 193 A Time stam s create access modity t power 0 We 8 A Direct and indirect indices to data blocks 15 8 books indices in inode 01 data blocks A Single double and triple indirection IZl Simplicity at its finest New File System Disk partition divided into cylinder groups 1 or more consecutive cylinders Each cylinder group has Copy of superblock for robustness lnodes 1 per 2K bytes Free blocks bit map Block usage information New File System Large variable block size 2 4K Problems Internal fragmentation Block size Waste 512 bytes 69 1024 bytes 118 2048 bytes 224 4096 bytes 456 1 MB 996 Solution to Internal Fragmentation Divide large blocks into smaller fragments 1 block a 2 4 or 8 fragments Manage free space at fragment granularity Example 11000 byte file 4096 blocks1024 fragments 2 full blocks 3 fragments Total space 11264 24 waste vs 12288 117 waste IZl Efficient space utilization for small files IZl Good bandwidth for large files Allocating 1 fragment at atime gt high overhead User program writes full block at a time Leveraging HW Characteristics Allocate file blocks on same cylinder Rotationally optimal block placement Where will disk head be after data transfer Compute rotational separation milliseconds CPU processing speed Service interrupt schedule next request Blocks per track Disk rotation speed Data L out File metadata Collocate inodes of files in same directory New directory cylinder group placement Many free inodes Not many other directories File data Rotationally optimal blocks in same cylinder 1 MB of contiguous blocks per large file Performance Miscellaneous Long file names 255 characters 12 to 18 total disk accesses for Is File locking Old separate lock file 0 read on old f3 New lock operations for advisorylocking 1447 write bandwidth 5 on old fs Links I Old hard links only a 39 39 N bl39 f l39kf39l h 39 h l39kedf39l Non degrading throughput over time ftizyzys39m ntgzs 39 Higher block allocation overhead R ename fewer block allocations Old 3 system calls create new copy rename new copy rm old copy 40 of data xfer overhead attributed to NJ g g g 353533 buffer copying Quotas THE UNIVERer of NEW MEXICO Scheduling Prof Dorian Arnold CS 481 Operating System Principles Spring 09 CPU Scheduling 1 processor gt1 process atatime Short term scheduler determines which process runs for how long Systemcentric considerations CPU utilization Job throughput Usercentric considerations Turnaround time Waiting time Response time Other Considerations CPUbound or IObound process spends more time doing CPU processing or lO Preemptive or nonpreemptive process uses resource until finished or process can be interrupted admitted interrupt exit terminated Process States scheduler dispatch 10 or event completion 0 or event wait scheduler sets policy for which process to run and for how long dispatcher provides mechanism for switching process contexts Firstcome Firstserved aka FIFO Processes scheduled in arrival order yield CPU go to tail of queue lZl Simple and straightforward IZI Excessive wait times arriving process waits for all queued processes IZI One process can monopolize CPU RoundRobin Processes in circular queue run for set CPU time slice FCFS w preemption What if time slice set too long or too short 5 ShortestJobFirst Process with shortest next burst runs first FCFS can break ties lZl Optimal waiting times IZI Difficult to know or predict CPU bursts approximate SJF eg exponential average of previous bursts Priority Scheduling Process with highest priority runs first FCFS can break ties Preemptive new process w higher priority gets CPU IZl Priorities can map to complex policies Eg importance usage patterns job characteristics IZI Starvation low priority jobs may never run solution gradually increase process priorities Multilevel Queues multiple prioritized ready queues static queue assignments exhaust jobs in higher queues or time slice highest priority batch processes El student processes 3 lowest Drioritv Multilevel Feedback Queues multiple prioritized queues with dynamic assignments jobs move between queues Can be used to implement any algorithm Policies number of queues scheduling algorithm for each queue when to upgrade a process when to downgrade a process which queue a process starts in MLFQ Example 7 FCFS Protection and Security CS 481 Operating System Principles Protect hardwaresoftware resources Accidental misuse relatively easy Intentional abuse very hard Problem statement ensure that each resource is accessed correctly and only by authorized entities Three Main Protection Concepts Authentication Who is doing what Authorization What a user is and is not allowed to do Access enforcement Enforce policy and ensure no loopholes Weakness in any of these reduces a system s protection 3 Authentication How do you prove who you are Passwords Secret known only to user Stored in nonrreadable form r trway lranslormalion irreversible Should be lorg and obscure lZlHumans choose poor passwords lZlOften don t know when password has been compromised Keys Physical badge key 7 Possession is 910 ti secure lZlRelatively expensive to make radox should be cheap to make hard to replicate lZlOwner knows when key has been compromised Authorization Operate in protection domain Domain is set of accessrights Accessrights ltobject rightsgt Eg user process procedure Operate on objects resources Eg files devices Access Matrix maps domains to objects object F1 F2 F3 printer domain D1 read read D2 print D3 read execute read read D4 write write 6 Access Matrix Representation Access Control Lists For each resource indicate what operations which users can perform IZlSimple and straightfonNard IZlEasy to revoke capabilities Tedious to have entry for each user 0 User classes Eg UNIX self group other Access Matrix Representation Capabilities For each user indicate accessible resourcesoperations lZlMore secure default access to nothing Difficult to revoke capabilities Access Enforcement Security Threats cont d Responsibility of security kernel Virus Small simple protected Selfreplicating code Protect identificationauthorization information Spread over networks storage devices Enforce access control Needs a host and trigger to spread Trojan horse Worm Paradox Spreads self from machine to machine gt Less without host by exploiting security 3532 vulnerabilities Security Threats Security Threats cont d Abuse of privileges E Covert Channels leaked information g superuser can do anything lmposter Trojan horse Time power page faults erform requested functionbutalso undisclosed functions E I T d k Egdownoaded programs ATMs xampe enex passwor crac mg Trap door Password checked character by character Designer leaves holes in software to leverage later Listener snooper Check gt failure or unrecoverable page fault Eavesdrop to steal information Place input string across boundary of valid and Eg set ethernet card to promiscuous mode inVaiid page Spoiler Denial of Service Iterativer detect larger correct password prefixes Consume resources to make system crash or unusable Eg Fork bomb Example Power consumption on smart cards Security Threats cont d Buffer overflows Exploit faulty program not bounds checking Eg using strcpy instead of strncpy OvenNrite buffer such that Write exploit code into address space overwrite return address on stack to jump to exploit code Port scans Look for vulnerable services on a program Security Mechanisms Encryption L 2 Intrusion Detection 3 Virus Protection 4 Firewalls Encryption Motivation Constrain the senders and receivers of a message Withlulnprotected channels others can eavesdrop and Inject messages Goals Privacy for your eyes only unintended recipients cannot understand message contents IntegrityAuthenticity Message contents not altered Nonrepudiation no take backs Encryption Concepts and Mechanisms Message obfuscation Clear plain text unencrypted message Cipher text encrypted version of clear text Keys used to encryptdecrypt messages Steps Sender uses key to encrypt clear text Transfer resulting cipher text to receiver Receiver uses key to decrypt cipher text Encrypted Communications 5 E encryption encryption key k algorithm E l gt lt attacker ID txetu 39 i gt decryption decryption key k algorithm D m read 1 7 Asymmetric Encryption Different encryptiondecryption keys Insecure channel Lu gt03 0 xeueudp M000 LU xetuicld Public key known to everyone Private key known only by sender Messages encoded w one decoded w other Eg RSA Asymmetric Encryption Uses Privacy send private messages pb B s public key sb B s secret key A gt B msgpb B decodesmsgpb using sb ibme Only B can decode messages encoded with pb Anyone can send messages to B Asymmetric Encryption Uses cont d Authentication reliably identify sender Authentication Digital signatures Nonrepudiation Example 1 pa A39s public key 2 saA s secret key 3 A gt B msgsa 4 B decodesmsg 1 using pa Only messages sent by A can be decoded with pa Anyone can verify message author 20 Asymmetric Encryption Uses cont d Privacy and Authentication 7 pa A s public Key 7 ea A s secret key 7 pb B s public key 7 sh B s secret key 7A gt B msglpbsa WOUIdA gt B msgisaipbwork Problems w Asymmetric Keys How do you trust public keys What if public key belongs to someone else Solution Authentication Servers As Everyone knowstrusts As AS broadcasts public key pas e As distributes public keys of others AS gt B public key of A is pa5A5 Eg certificate authorities https and ssl Problems w Asymmetric Keys cont d Message replays Problem confuse recipients Solution Sequence numbers Relativer slowly encodingdecoding Symmetric Encryption Same encryptiondecryption keys Eg DES AES How is key exchanged Key must be kept private Solution 1 Use public key encryption to exchange conversation key A B A Kisaipb Symmetric Encryption cont d Key exchange solution 2 authentication server Each user has private key Kl known by AS H A asks authentication server for a conversation key CK with B A A AS B N AS replies with new conversation key CK As a A K ACKkbka 3 A uses private key ka to decrypt message and get CK 4 A sends message to B telling it CK kb ACK No one could modify message to change name of sender from A ls encryption safe How easy is it to discover private keys Depends on key length and computational power Brute force guess key and look for sensible text DES 56 bit keys 9 258 possible keys Relativer easy to crack AES has 128 bit keys Use larger keys as computers get faster Remove known patterns from clear text eg compression or obfuscation algorithms Change keys frequently Multiple keys for large amounts of data


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.