Operating Systems CS 35400
Popular in Course
Popular in ComputerScienence
This 137 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 35400 at Purdue University taught by Rodriguez-Rivera in Fall. Since its upload, it has received 4 views. For similar materials see /class/208069/cs-35400-purdue-university in ComputerScienence at Purdue University.
Reviews for Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
397Ar rli J If I i If 7r 739 if V V 7 7 V V 7 7 u 39 If 39 igln Fl Igtl InliEInlJlv I I u t It Jmnla1n II Ir 7 Iantnzl i hl 7 g r as a 1quotquot I39 I a n 739 quotIfquot a39 gt7 39 IUKH3rTult QUKS39 III II i Iquot e V Fa 39nv in lnwy39n39 lrtnz u39 39 a Iquot rah Ec rri w if w or t t a u z s n n w a 39 g t a u 7 rquot I y a 6 5 EC 9 r 4 u I nu39x r quot l a a II M ii In i393 I x gt Nigunu lul3939ll39I 393 u V r lt I F1111 11 if39 igf39 41 i i 7 Hymn In I 13illjjg39139 ELLE ailingmlgillijl flyinggi fgquot Fl 0L ELIE Lil g g L a 7 If h fgirff Spring 2009 Instructor Pascal Meunier Original slides created by Gustavo Rodri uezRivera Computer SCIEDCE epartment Purdue University Part 9 Memory Allocation ynamic Memory Allocation i Why do we need dynamic memory allocation I We do not know how the program will be used and the memory requirements of the program until it is used 39 We could define variables statically using a maXimum limit but I If the use of the program exceeds limit we need to modify program I Also this wastes memory With dynamic memory allocation the program calls mallocnew to allocate more memory To free memory there are two approaches 39 Explicit Memory Management call freedelete CCPascal 39 Implicit Memory Management Use Garbage collection Java C Perl Python Smalltalk Implicit Memory Management I The language runtime library provides a Garbage Collector GC that determines what objects are no longer in use and frees them 39 The language runtime library provides common language functionality to a program I There are two approaches 39 Reference Counting 39 Mark and Sweep Reference Counting 39 In reference counting every object has a counter with the number of reference pointing to the object When the reference count reaches 0 the object is removed i This is the approach used by languages such as Perl and Python Advantage 39 Easy to implement Incremental objects are freed while program is running Disadvantage 39 Slow Every pointer assignment needs to increasedecreased a reference count 39 Unable to free cycles loops of references Reference Counting Vars V as MarkandSweep Garbage Collection 3 Is this object in use 39 If it39s not referenced by anything then it isn39t and can never be again used 39 Delete it reclaim memory I Naive approach 39 Mark all objects as not in use mark bit I Find all pointers everywhere I Mark objects that are referenced as being in use 39 Delete objects not in use Naive Mark and Sweep Clear mark bits 1 Push root addresses to a mark stack While the stack is not empty 39 Pop an object from the mark stack I Search for pointers 39 If the pointers point to an unmarked object push it to the stack and mark object Free any unmarked objects Mark and Sweep Garbage Collection Global Vars Mark and Sweep Garbage Collection I The program needs to stop all the threads while the GC is taking place 3 This is done because if the pointers change while the GC is taking place some reachable objects may be unmarked and can be erroneously collected I Stopping all the threads except the GC thread is called Stoptheworld 39Program freezes generally unprediml L Various Improvements 3 Incremental garbage collection 39 Break it into phases to shorten pauses Tl Concurrent garbage collection I No significant stop I Generational garbage collection 39 Goup objects by age 39 Most die young hypothesis H Tricolor marking 39 Maintain sets as you go Explicit Memory Management H Explicitly ie not automatically request and free memory 1 Use a malloc library usually provided by the C standard library libc 3 Memory is initially requested from the OS 3 Difficult to return memory to the OS 39 OS handles memory in pages 39 Memory allocator handles memory in bytes Free List H Memory obtained from OS is put in free list I Requests from program satisfied using memory from the list 1 Freed memory goes back to the free list H In effect recycling memory and managing it without intervention from the OS I This decreases the number of times that memory is requested from the OS Explicit Memory Management Program mallocnew Freedelete Malloc Library 1 sbrksmunmap brk S S mmap not very common Explicit Memory Management I When the memory allocator runs out of memory in the free list it calls sbrks I Sbrks increases the size of the heap by s bytes I Sbrk retuns a pointer to the old heap limit 1 You can decrease the size of the heap by passing a negative size to sbrk This will shrink the heap Explicit Memory Management sbrks Explicit Memory Management 1 An alternative to sbrk is to use mmap with an anonymous mapping 139 This will return a group of pages initialized with 0 s I You Can return memory to the OS by using munmap Explicit Memory Management Returning memory back to the OS is difficult because 39 Sbrk only can return memory to the OS if it happens to be at the end of the heap 39 Munmap can return memory to the OS if whole pages are unused I Most memory allocators do not return memory to the OS However this has not been a problem Malloc Implementation 1 There are several data structures that can be used for memory allocation 39 Single Free list I Segregated Free Lists 39 Cartesian Tree 39 Boundary tags Malloc Single Free List I In this implementation of malloc all the free memory is stored in a single free list 139 Each Chunk in the free list has a header with the size of the Chunk and a pointer to the next Chunk Malloc Single Free List head 0X110 0X4000 OXBOOO Single Free List Allocation 39 A chunk of the right size if found 39 Split if necessary 39 Remainder is returned to the free list 1 Free 39 Free list is traversed to find the right place of insertion 39 Object is coalesced if possible 39 ie merged with contiguous free memory Properties of Single Free List Iquot Chunks in the list are ordered by address I Allocation On where n of Chunks H Free On 1 When requesting memory request in units of a full page eg 4 KB 39 minimizes number of requests Malloc Single Free List I Two Allocation Policies 39 First Fit 39 Use the first Chunk in the free list that satisfies the request 39 BestFit 39 Choose smallest Chunk that satisfies the request Notes on malloc i Malloc also allocates memory for a header The header stores the size of the object i The header will be needed when the object is freed i Malloc will return a pointer after the header i The memory returned by malloc is aligned to 8 bytes that is the address of the object is a multiple of 8 bytes i This is because RISC architectures need certain types to be stored in aligned memory Doubles have to be stored in 8 byte boundaries in memory i If you try to store an int value into a nonaligned address in SPARC you will get a SIGBUS error In the X86 architecture you will not get an error but the execution will slow down First Fit he 1 0X110 0X4000 OXBOOO p malloc8 8 bytes object 8 bytes header 16 bytes total P0x118head 0X12quot 0X4000 OXBOOO 0X110 Best Fit he d 0X110 0X4000 OXBOOO p malloc8 8 bytes object 8 bytes header 09 0t889 total head 0X11quot 0X4000 OXBOOO First Fit vs Best Fit First Fit is faster Best Fit uses less space i In first fit if the search always starts at the beginning it will create many small objects at the beginning of the list I Next fit 39 It is like first fit but the next search starts where the last ended This speeds first fit and it will prevent the accumulations of small chunks at the beginning of the list External Fragmentation 3 External Fragmentation is the waste of memory in the free list due to small noncontiguous blocks that cannot satisf a lar e request p malloc100 100 bytes object 8 bytes header 108 bytes total The allocation cannot be satisfied even though the free list has more than 108 bytes The allocator will need to get more memory from the OS External Fragmentation I Ext Fragmentation 1001 LT 39L is size of largest block 39T is total memory in free list 0xl10 0x4000 0x8000 Ext Fragmentation 100 16412047 If there is only one block in the list ext fragmentation0 Segregated Free Lists I It is another data structure for memory allocation 139 There are multiple free lists for different SIZES Slze 8 gt gt gt 16 32 64 gt gt gt T 128 256 gt512 gt gt Segregated Free Lists Very often the fixed sizes are powers of two Objects are allocated from the free list of the nearest size If a free list is empty the allocator gets a page of memory from the OS and populates the corresponding free list Some implementations of free lists do not have coalescing Once an object is created for a size it will he of that size for the entire execution of the program Segregated Free Lists Coalescing an object would require traversing all the blocks to find out if the neighboring blocks are free With segregated free lists 39 Allocation small objects 01 39 Free small objects O1 no coalescing Segregated free list allocators are fast but they use more memory The BSD UNIX allocator uses segregated free lists External and Internal Fragmentation 1 External Fragmentation I Waste of memory due to having non contiguous blocks in the free list that cannot satisfy an allocation for a large object I lnternal Fragmentation 39 Waste of memory due to the allocator returning a larger block than the memory requested I Internal Frag 1001 RA 39R is requested size 39A is allocated size Cartesian Trees 3 Binary Search tree 39 Each node has two children 39H Binary Heap 39 Heap property each node is greater than or equal to children according to some function 3 Nodes ordered 39 Lefttoright by address 39 Top to bottom by length Cartesian Tree Memory Addresses Properties of Cartesian Trees 1139 With high probability the tree is balanced bushy 39 Operations in OlogN I Cf Randomized Search Trees or Treaps I SunOS allocator uses Cartesian Trees Malloc Allocation Policies Iquot Other allocation policies based on various data structures 39 Watson allocation policy 39 Redblack trees I Malloc implementations may allow selecting a particular allocation policy I eg IBM AIX 1 Various malloc implementations available with varying performance Boundary Tags Boundary Tags allow identifying the neighboring objects in 01 This allows coalescing of objects in 01 Each object allocated or free has a header and a footer The header and the footer contain the size of the object as well as a flag that tells if the object is allocated or not When freeing an object it is possible to check if the neighbors are free in constant time and coalesce them if possible Boundary Tags HI d I I SEE Flags Data Heada SixI F t l II Flags h39l d Punter Hg I FI EE 1 Alhcate Boundary Tags Header 1 Data 1 Fe eter 1 Header 2 Data 2 Fe eter 2 Header 3 Data 3 Fe eter 3 Boundary Tags The memory allocator you will implement also stores the objects in segregated free lists This allows memory allocation in 01 for small objects There are 65 lists Lists 0 to 64 store objects of sizes 8 i including header and footer where i is the number of the list List 65 stores objects larger or equal than 512 III 1 2 3 4 5 E5 61 52 I53 64 Boundary Tags Boundary Tags 39 When the object is free the header also contains a pointer to the next object in the list and a pointer to the previous object in the list 39 This allows removal of an object in the middle of a list from a list in constant time That is needed after coalescing Header Nail H u Footer Free hjed Allocation Algorithm 1 Round up requested size to the next 8 byte boundary if size O assume 1 byte data 2 Add the size of the header and the footer realsize roundup8requested size sizeofheader sizeoffooter 3 Lookup the corresponding list a list realsize 2 512 64realsizegtgt3 41f the list is non empty and list lt64 remove a block from that list and return it Allocation Algorithm 5 If the list is empty search for a list with objects of larger size If there is one nonempty list with larger objects remove one of the objects and split it Use one portion of the object to satisfy the allocation request and return the remainder to the corresponding list 61f the remainder is smaller than the size of the header plus the footer plus next plus previous making the object unusable then do not split the object and use the entire object to satisfy the allocation Allocation Algorithm 71f there is not enough memory in the free lists to satisfy the allocation then request memory from the OS using sbrk Round up the request of memory to the OS to a 16KB boundary Free Algorithm 1 Check the footer of the left neighbor object the object just before the object being freed to see if it is also free If that is the case remove the left neighbor from its free list using the previous and next pointers and coalesce this object with the object being freed Free Algorithm 2 Check the header of the right neighbor object the object just after the object being freed to see if it is also free If that is the case remove the right neighbor from its free list using the previous and next pointers and coalesce it with the object being freed 3 Place the freed object in the corresponding free list and update the header and footer Fence Posts 1 If the object freed is at the beginning of the heap it is likely that your allocator will try erroneously to coalesce memory beyond the beginning of the heap 1 Also other libraries may call sbrk causing a hole in the heap Fence Posts To prevent coalescing with memory beyond the beginning or the end of the chunks that belong to the heap your allocator will 39 every time a chunk of memory is requested from the OS your allocator has to add a dummy footer at the beginning of the chunk with the flag set to allocated 39 Also at the end of the chunk you will add a header with the flag set to allocated If two chunks are consecutive you should remove the fence posts between them Fence Posts End of Heap Dummy Header flagallocated Dummy footer flagallocated Start of Heap Fence Posts End of Heap Dummy Footer flagallocated a t f If Li I 7 Ht J Ff x A Li g r a L t M v 7 w v 1 Dummy Header fla allocated Start of Heap L Malloc I The memory allocator you are building is based on Doug Lea s malloC implementation that is public domain httpgoswegoedudlhtmlmallochtml I This allocator is the standard allocator in LinuX Memory Allocation Errors I Explicit Memory Allocation calling free uses less memory and is faster than Implicit Memory Allocation GC However Explicit Memory Allocation is error prone and can result in vulnerabilities Memory Leaks 133 NVD entries Premature Free aka Use after free 37 NVD Double Free 60 NVD entries Wild Frees Memory Smashing W WNE Memory Leaks CWE4O 1 39 Memory leaks are objects in memory that are no longer in use by the program but that are not freed This causes the application to use excessive amount of heap until it runs out of physical memory and the application starts to swap slowing down the system i If the problem continues the system may run out of swap space H Often server programs 247 need to be rebounced shutdown and restarted because they become so slow due to memory leaks Memory Leaks In normal use memory leaks is a problem for long lived applications 247 39Shortlived applications return the memory when the program goes away usually before it becomes a problem Memory leaks can be specifically targeted by attackers So whether it is correct that there are other more serious problems in memory allocation depends on how exposed your program is Memory Leaks Silly example while 1 ptr malloc100 Premature Frees CWE 416 Freeing an object that is still needed 39aka Use after free i The freed object is added to the free list modifying the nextprevious pointer If the object is modified the next and previous pointers may be overwritten causing further calls to mallocfree to crash The memory can be given out for storing something else Difficult to debug because the crash may happen far away from the source of the error Premature Frees IExaHu e int p int mallocsizeofint p8 freep free adds object to free list updating next and prev p 9 next ptr will be modified int q int mallocsizeofint this call or other future mallocfree calls will crash because the free list is corrupted ouble Free 1 Double free is caused by freeing an object that is already free 1 This can cause the object to be added to the free list twice corrupting the free list 1 After a double free future calls to mallocfree may crash IExqu e ouble Free int p int mallocsizeofint freep freep free adds object to free list freeing the object again overwrites the nextprev ptr corrupting the free list future calls to freemalloc will crash Wild Frees Wild frees happen when a program attempts to free a pointer in memory that was not returned by malloC Since the memory was not returned by malloc it does not have a header Nonheap memory 39Pointers to somewhere else in the heap Memory allocated with a different library Different malloC or New Wild Frees Tl Incorrect information used blindly by free I Free call may crash 39 Segmentation fault etc 39 Lists can be corrupted Newelete vs MallocFree 39 Memory allocated with malloc should only he deallocated with free and memory allocated with new should only he deallocated with delete 39No guarantee that delete uses free internally or that new uses malloc nevermind the fact that the destructor is never called either by free Wild Frees Example int q int p ampq freew p points to an object without header Free will crash or it will corrupt the free list Wild Frees IExqu e char p char malloc1000 PP10 freep p points to an object without header Free will crash or it will corrupt the free list Memory Smashing 1 Memory Smashing happens when less memory is allocated than the memory that will be used 1 This causes overwriting the header of the object that immediately follows corrupting the free list I Subsequent calls to mallocfree may crash I Sometimes the smashing happens in the unused portion of the object causing no damage Memory Smashing Example char s malloc8 strcpys llhello worldquot We are allocating less memory for the string than the memory being used Strcpy will overwrite the header and maybe nextprev of the object that comes after s causing future calls to mallocfree to crash Special care should be taken to also allocate space for the null character at the end of strings ebugging Memory Allocation Errors Memory allocation errors are difficult to debug since the effect may happen farther away from the cause Memory leaks are the least important IF they can39t be triggered at will by an attacker 39Lifetime of program may be too short to matter As a first step comment out free calls and see if the problem goes away 39If so search for the free calls that cause the bugs ebugging Memory Allocation Errors 1 There are tools that help you detect memory allocation errors I IBM Rational Purify 39 Bounds Checker 39 Insure Explicit Memory Allocation Advantages and isadvantages Advantages 39 It is fast and 39 It is memory efficient Disadvantages 39 Error prone 39 Requires more expertise 39 Applications take longer to develop and debug 39 More insecure This is why managers prefer now to develop in J avaC Still there is room for CC for apps that need to be lowlevel and where speed is critical Some Improvements in Your Allocator You can add some checks to make your allocator more robust against memory errors You can check if a block has been returned by malloc by storing a magic number in the header and checking it during free to prevent wild frees Instead of only using one bit in the flags you could use the entire 4 bytes to store a magic number to indicate if the object is free or not 39 Free OXF7EEF7EE 39 Allocated OXAlOCA7ED When freeing an object check if in the header the flag contains the right magic number Heap Check You can implement also a heapCheck function that checks for the sanity of the heap and prints the free and allocated blocks You can call it during debugging before and after suspicious freemalloc calls Starting from the header at the beginning of the heap and follow the headers checkHeap iterates over all free and allocated blocks 1 To get around gaps in the heap you can store the correct size of the gaps in the fence posts around the gaps Heap Check I There is enough information in the headers to iterate over the end of the heap I Verify that the sizes and flags in header and footer match 1 Print also the blocks Add an extra flag value to differentiate Gaps in the heap from allocated and free blocks Heap Check End of Hea Footer4Hdr5 Footer3Hdr4 FooterZHdr3 GP P FooterlHdrz FooterOHdrl Start of Heap Malloc Implementation Notes class ObjectHeader public int flags flags ObjFree or ags ObjAllocated sizet objectSize Size of the object Used both when allocated and freed Class FreeObjectHeader public int flags flags ObjFree or ags ObjAllocated sizet objectSize Size of the object Used both when allocated and freed FreeObjectHeader next FreeObjectHeader prev char chunk FreeObjectHeader fhdr FreeObjectHeader chunk Get fhdrgtobjectSize fhdrgtpreV fhdrgtnext etc Part 2 Introduction to Operating Systems What is an Operating System It is a program that sits between the hardware and the application programs i The program starts running at boot time i It is compiled with a normal compiler I Narrow de nition kernel Wider de nition includes things installed along with it even a web browser What does an Operating System Offer Services Printing Windowing File Access Libraries Networking What does an Operating System Offer Capabilities Multitasking Atomic operations protect against race conditions Multiuser access Access control discretionary Protocols networking DeVice management with hosted drivers A Note on Isolation 39 Each program runs inside a sandbox If the process does something wrong like writing to an invalid memory it will receive a noti cation Processes will not get out of the sandbox The OS continues to run Types of Computer Systems Batch Processing Of ine processing 39 Put programs and input data in a queue of jobs spooler 39 Let the computer process the jobs one by one 39 The output of the program is saved or printed so the user can access it at a later time 39 This was the approach used for punch cards by students in the 60s70s I Write program by punching cards 39 Program and input data was represented by a lot of cards E g 100s of cards I The cards were taken to a card reader and students had to wait for about 24 hrs sometimes for the output that could be a compilation error Types of Computer Systems I Time Sharing 39 Multiple terminals are connected to a mainframe 39 This allows multiple to users to have interactive sessions with the computer simultaneously 39 The OS gives a small portion of the CPU to each user 39 It is possible to run interactive applications like editors Types of Computer Systems I Personal Computers 39 One computer one user 39 This was possible at the end of the 7 Os thanks to the arrival of the microprocessor that allowed inexpensive computers I The rst widely available PC was the Apple with a 6502 CPU 16 bits that typically had 48KB of RAM The killer app was called Visicalc a spreadsheet The OS was practically null 39 Now PCs typically have at least 256MB and the CPU is 32 bit They OS has the complexity of a mainframe Types of Computer Systems Parallel Systems I Have more than 1 CPU in the same computer 39 SMP Symmetric Multiprocessing Each CPU runs a copy of the Operating System 39 A task that takes T seconds to complete may take ideally TN seconds 39 However some tasks that have to be executed serially may not take full advantage of parallel computers Some other tasks can be parallelized very effectively 39 They are expensive The cost is On2 with the number of processors due to communication hardware that allows interaction between processors Types of Computer Systems Clusters 39 Collection of inexpensive computers connected through a fast network 39 Alternative to parallel computers 39 Cost is linear On with the number of nodes used More robust than parallel computers since they can be serviced while running 39 However the communication across nodes is slower than the communication across processors in parallel computers Types of Computer Systems Clusters c0nt 39 Programs may need to be rewritten to take advantage of clusters since each cluster will run different processes I Some Database servers may run better in parallel computers 39 The best example of a cluster is Google that has clusters with about 250000 computers distributed in different locations Google searches are resolved by multiple machines running in parallel 39 Another example are rendering farms used to create computer animated movies like Finding Nemo Shrek etc Types of Computer Systems I Grid 39 A collection of inexpensive computers across the internet running the same application to accomplish a collective task 39 People donate idle time of their computers to be used in the grid 39 Example SETIhome Search for extraterrestrial intelligence You can download a program that will analyze radio telescope data looking for quotintelligen quot patterns Types of Computer Systems Distributed Systems I Applications that span multiple hosts connected by a network I Examples I World Wide Web I NFS Network File system UNIX Remote File System I Java RMI Java remote method invocation Allows using server methods as if they were local I Sun RPC Remote procedure call I Advantages I Resource Sharing I Computer speed up Reliability I Communication among users amp computers Types of Computer Systems Network File Systems 39 A type of a distributed system 39 Provides remote file access as if it were local I Home directories in mainframes like mentorcc are usually located in an NFS like championcc 39 Try I CShgt df k List all le systems and locations used by this computer I chsgt df k List the le system used by the current directory 39 Examples of Network File Systems NFS UNIX I SMB Windows lAdditional Notes on Scheduling Ef cient Scheduling Constant time Ol Less ef cient On Where n is the number of processes in the system 39 Scheduling becomes slower as there are more processes Question Is the process aging technique 01 or On Answer Aging is On because you need to loop over all processes to update their priorities I Linux uses two arrays to replace aging 39 Processes are put in the expired array when they have exhausted their allocated CPU time dynamically determined 39 When all processes are in the expired array it becomes the active array 39 A11 processes get to run eventually Moving Average Question What is the starting value before any data is known I A Anything reasonable 39 Typically an operating system uses a full time quantum as the initial estimated CPU burst 39 The book uses 10 ms in an example 39 Good question because it means you think about border cases Kinds of Moving Averages i The formula we saw is known more precisely as an exponential moving average 39 There is also a linear moving average 39 Every data point has the same weigth 39 In the exponential version older data points are weighted less newer data has a higher weight following a decaying exponential formula Question Given the following values what would be the exponential moving averages after each Data 33 61 19 67 20 39 Start with O as the previous average 39 a If the coefficients are 01 new data point and 09 previous average I b If the coefficients are both 05 Answer Data Case A Case B 33 61 19 67 20 O 33 907 1006 1576 1618 0 165 3875 2888 4794 3397 What if it started at 50 Data Case A Case B 33 61 19 67 20 50 483 4957 4651 4856 4571 50 415 5125 3513 5106 3553 Uses of Moving Averages Also used for OS performance metrics 39 CPU utilization 39 Average process queue length lCan you change the quantum Part 5 Unix System Programming and The Shell Project Shell Project I To interact with the OS you use a shell program or command interpreter 39 Csh C Shell 39 Tcsh Enhanced C Shell 39 Sh Shell 39 Ksh Korn Shell 39 Bash GNU shell I There are also other graphical shells like 39 Windows Desktop 39 Mac OS Finder 39 X Windows Managers Shell Interpreter i The shell project is divided into several subsystems Parser reads a command line and creates a command table One entry corresponds to a component in the pipeline Example Command ls al grep me gt lel Co mand Table ls al grep me Inzdflt Outzfilel Errzdflt Shell Interpreter Executor 39 Creates new process for each entry in the command table 39 It also creates pipes to communicate the output of one process to the input of the next one 39 Also it redirects the stdinput stdoutput and stderr wowedquot A11 pipe entries share the same stderr Shell Interpreter Other Subsystems 39 Environment Variables Set Print Expand enV vars 39 Wildcards Arguments 0f the form aa are expanded to all the les that match them 39 Subshells Arguments with backticks are executed and the output is sent as input to the shell Shell Project Part 1 Shell Parser 39 Read Command Line and print Command Table i Part 2 Executer 39 Create Processes and communicate them With pipes Also do inouterr redirection Part 3 Other Subsystems 39 Wildcard Envars Subshells LeX and Yacc A parser is divided into a lexical analyzer that separates the input into tokens and a parser that parses the tokens according to a grammar The tokens are described in a le Shelll using regular eXpressions I The grammar is described in a le shelly using syntax expressions I Shelll is processed With a program called leX that generates a leXical analyzer I Shelly is processed With a program called yacc that generates a parser program Shell Project Final Com and Table ls al aab aaa grep me Inzdflt Outzfilel Errzdflt Lexer Parser r characters Sh 61H ls al 21 grep me gt filel Command Table ltagt ltPIPEgt grep me ltgrepgt ltmegt Inzdflt Outzfilel Errzd t ltGREATgt Shell Grammar You need to implement the following grammar in shelll and shelly cmd arg cmd arg gt filename lt filename gtamp filename gtgt filename gt gtamp filename ampJ I Currently the grammar implemented is very simple Examples of commands accepted by the new grammar 1s al Is a1 gt out Is al sort gtamp out awk fXaWk sort u lt in le gt out le amp What does this do programname ltdevnull gt mylogerr 2gtamp1 I Devnull is the null device Everything written there is discarded Used as input it automatically ends it gt redirects output to a le 2gtamp1 merges the standard error le descriptor 2 with the standard output le descriptor 1 Shortcutz in some shells just gtamp rny le does both gt my le and 2gtamp1 Standard UNIX File Descriptors Standard Input 0 stdin Standard Output 1 stdout I Standard Error 2 stderr File Descriptors Refer to 39 Files 39 Directories 39 Devices 39 Sockets 39 FIFOs named pipes 39 Pipes unnamed Jobs programname amp Run the program in the background 0 Concept Jobs job will stop be suspended if input or output is required 39 sleep 10 amp 39l 7187 39 jobs 391 Running sleep 10 Jobs iControlled with signals SIGSTOP SIGCONT 1 Example kipid SIGSTOP I Process state in process table changes Linux TASKSTOPPED Process Sleep States There is more than one sleep state Linux TASKSTOPPED TASKINTERRUPTIBLE TASKUNINTERRUPTIBLE Does not process signals TASKKLLABLE Like TASKUNNTERRUPTIBLE but responds to fatal signals Signals Signals are software interrupts 39 Your program stops executing from your point of View at some random instruction so that the signal can be handled 39 See Stevens book Whole chapter on signals I Signals can be created from 39 A hardware exception 39 Another process 39 Various events keys pressed etc Managing Signals Your program may decide to 39 Ignore certain signals 39 Block a signal for a While 39 Catch amp handle a signal 39 Use the default action lNote SIGKILL and SIGSTOP can39t be ignored Signal Handling Notion your program may register signal handlers 39 They get called When a given signal happens 39 Without them some default action is taken usually terminate your program 39 You specify the address of a function that becomes the signal handler 39 Jargon this is called catching a signal Handling Signals Handling signals can be tricky i If you manipulate a data structure during a signal you may cause problems 39 What if that data structure was being changed by your program at the time the signal happened 39 The data structure may be in an incorrect state 39 e g just before the program set the last pointer in a list to NULL Insert Security issues in shells Lexical Analyzer Lexical analyzer separates input into tokens I Currently shelll supports a reduced number of tokens Step I You Will need to add more tokens needed in the new grammar that are not currently in shelll le quotgtgtquot return GREATGREAT quot return PIPE quotampquot return AMPERSAND Etc Shell Parser Step 2 Add the token names to shelly token NOTOKEN GREAT NEWLINE WORD GREATGREAT PIPE AMPERSAND etc Shell Parser Rules I Step 3 You need to add more rules to helly S 7 pipelist cmd arg cmd arg arglist gt filename lt filename gtamp filename gtgt filename gtgtamp filename cmdandargs i0m0di er1ist i0m0di er amp commandline background0ptional Shell Parser Rules goal commandl i s t argl i s t argl i s t WORD empty cmdandargs WORD argl i s t o I Shell Parser Rules pipelist pipelist PIPE cmdandargs cmdandargs o I Shell Parser Rules iomodifier GREATGREAT Word GREAT Word GREATGREATAMPERSAND Word GREATAMPERSAND Word LESS Word Shell Parser Rules iomodifierl i s t iomodifierli s t iomodi fi er I empty backgroundoptional AMPERSAND empty 0 I Shell Parser Rules commandline pipelist iqmodifierlist backgroundppt NEWLINE NEWLINE accept empty cmd line I error NEWLINEyyerrok error recovery commandlist commandlist commandline command loop Yacc Actions i As part of a rule you can specify an action i If the pattern is recognized the action res I You need to ll the command table 39 So you need access to the values of strings 39 Lexer needs to set yylVal I yylval stringval strdup yytext 39 Parser makes it accessible to you 39 1 is the rst token 39 2 is the second 39 etc Shell Parser Rules You need to add actions in the grammar to ll up the command table Example arglist arglist WORDcurrsimpleCmd gtinsertArg2 I empty 3 Error Token Special token used for error recovery I error NEWLINEyyerrok 39 error will parse all tokens until a token that is known is found like ltNEWLINEgt 39 yyerrok tells the parser that the error was recovered The Open File Table I The process table also has a list with all the les that are opened Each open le descriptor entry contains a pointer to an open le object that contains all the information about the open le Both the Open File Table and the Open File Objects are stored in the kernel The Open File Table The system calls like writeread refer to the open les with an integer value ealled le descriptor or fd that is an index into the table The maximum number of les descriptor per process is 32 by default but but it can be Changed with the command ulimit up to l 024 The Open File Table Open File Table File 0b ea 0 INODE Mode erence Count kWNN 31 Open File Object An Open File Object contains the state of an open le I INode I It uniquely identi es a le in the computer An Inodes is made of two parts I Maj or number Determines the devices I Minor number It determines What le it refers to inside the device I Open Mode How the le was opened I Read Only I Read Write I Append
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'