Operating Systems COP 4600
University of Central Florida
Popular in Course
Popular in Computer Programming
This 130 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 4600 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/227475/cop-4600-university-of-central-florida in Computer Programming at University of Central Florida.
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: 10/22/15
COP 4600 Introduction To Operating Systems Summer 2011 Syllabus Course Prerequisites COP 3503 COP 3402 Passed Foundation Exam COT 3906 Class Meets Tuesday and Thursday from 1000 am 1150 am in MAP 359 Instructor Dr Mark Llewellyn Office H EC 236 Office Hours Monday 200400pm Tuesday 1200 200pm Wednesday 200 400pm Phone 4078232790 Email marklcsucfedu Course Web Site wwwcsucfeducoursescop4600sum2011 Course Description This course will introduce you to modern operating systems We ll deal with the fundamental concepts and algorithms used in the design of existing operating systems kernels You ll gain an understanding of how operating system abstractions are implemented on conventional hardware You ll also learn how to apply the main evaluation models used to evaluate a system We ll also detail how to properly synchronize multithreaded communicating processes using synchronization primitives such as semaphores and monitors We ll cover system calls processes threading CPU scheduling memory management and security issues We ll also deal with the terminology hardware and software associated with operating system components and structures Texts The following text will be referenced for this course Operating System Concepts Essentials Silberschatz Galvin Gagne 2011 John Wiley amp Sons ISBN 9780470889206 Grading Three exams will be given two regular exams and a final exam comprehensive Exams are given once be there as there are no dropped test scores There will be four to six homework assignments The homework assignments are to be individual efforts You must score at least 60 on the final exam to pass the course Homework assignments total 25 2 Regular Exams 25 each 50 Final Exam Thursday August 4th regular class time 25 Grading Scale Plusminus grading will be used in this course 90100 A 8890 A 8688 B 8086 B 7880 B 7678 C 7076 C 6870 C 6668 D 6066 D 5860 D lt58 F Some Important Dates Last Day to Withdraw Friday June 24th Final Exam Thursday August 4th regular class time Topics To Be Covered Introduction to Operating Systems Hardware Components User Interface Resource Management Processes and Threading CPU Scheduling Process Synchronization ooumanooNA Memory Management 0 File System 10 Security This is a general list of topics only and is subject to the needs ofthe class It will be altered without notice but will generally follow the same progression At the end of each class I will tell you what we will be discussing during the next class period Online notes will supplement the text in many areas COP 4600 Summer 2011 Introduction To Operating Systems Memory Management Part 1 Instructor Dr Mark Llewellyn marklcsucfedu HEC 236 4078232790 httpwww cs ucfeducou rsescop4600su m201 1 Department of Electrical Engineering and Computer Science Computer Science Division University of Central Florida COP 4600 Intro To OS Memory Management Part 1 Page 1 Dr Mark Llewellyn Memory Management In a uniprogramming environment main memory is divided into two parts one part for the OS and one part for the program currently being executed In a multiprogramming environment the user part of memory must be further subdivided to accommodate multiple processes The task of subdivision is carried out dynamically by the OS and is referred to as memory management Effective memory management is vital in a multiprogramming environment If only a few processes are in memory then for much of the time all of the processes will be waiting for IO and the processor will be idle Thus memory needs to be allocated to ensure a reasonable supply of ready processes to consume the available processor time COP 4600 Intro To OS Memory Management Part 1 Page 2 Dr Mark Llewellyn 6 Memory Management Memory Management Methods Contiguous Allocation NonContiguous Allocation Single Partition Multiple Partition Segmentation Paging Fixed Dynamic quotBasicquot Demand Allocation Allocation Paging Paging Virtual Memory COP 4600 Intro To OS Memory Management Part 1 Page 3 Dr Mark Llewellyn 6 Memory Management Requirements The memory management component of the operating system must satisfy ve basic requirements 1 Relocation 2 Protection 3 Sharing 4 Logical organization 5 Physical organization We ll consider each of these requirements separately COP 4600 Intro To OS Memory Management Part 1 Page 4 Dr Mark Llewellyn 1 Relocation In a multiprogramming system the available main memory is generally shared among a number of processes Typically it is not possible for the programmer to know in advance which other programs will be resident in main memory at the time of execution of their program In addition we would like to be able to swap active processes in and out of main memory to maximize processor utilization by providing a large pool of ready processes to execute See next page for an illustration of swapping Once a program has been swapped out to disk it would be quite limiting to require that it be placed into the same memory region it previously vacated when it is swapped back into the main memory Rather we would like to relocate the process to a different area of the memory COP 4600 Intro To OS Memory Management Part 1 Page 5 Dr Mark Llewellyn 6 1 Relocation Swapping operating system process P1 swap out 39 W process P2 swap In user Space backing store main memorv COP 4600 Intro To OS Memory Management Part 1 Page 6 Dr Mark Llewellyn Aside on Linking and Loading 0 The rst step in the creation of an active process is to load a program into main memory and create a process image Process Control Block Program Program Data Data Object code Stack Process Image in main memory COP 4600 Intro To OS Memory Management Part 1 Page 7 Dr Mark Llewellyn 6 Aside on Linking and Loading cont 0 Typically applications consist of a number of compiled or assembled modules in object code form 0 These are linked to resolve any references between the modules At the same time references to library routines are resolved The library routines themselves may be incorporated into the program or referenced as shared code that must be supplied by the OS at run time 0 This scenario is illustrated on the next page COP 4600 Intro To OS Memory Management Part 1 Page 8 Dr Mark Llewellyn 6 Aside on Linking and Loading cont Library 3 l Module 1 Module 2 Load Module ll 5 Module n Main memory COP 4600 Intro To OS Memory Management Part 1 Page 9 Dr Mark Llewellyn 6 Relocation cont A physical address or absolute address is an actual location in main memory These are the addresses with which the memory unit works A logical address or virtual address is a reference to a memory location independent of the current assignment of data to memory A translation must be made to a physical address before the memory access can be achieved Logical addresses are generated by the CPU A relative address is a particular example of a logical address in which the address is expressed as a location relative to some known point usually a value in a processor register 0 Programs that employ relative addressing are loaded using dynamic run time loading Typically all of the memory references in the loaded process are relative to the origin of the program Thus a hardware mechanism is required for translating relative addresses into physical addresses at the time of execution of the instruction that contains the reference COP 4600 Intro To OS Memory Management Part 1 Page 10 Dr Mark Llewellyn Aside on Linking and Loading cont Loading Looking at the gure on page 9 you ll see that the loader places the load module in main memory starting at location x In loading the program the addressing requirements of the program see next page must be satis ed In general three different approaches can be taken 1 Absolute loading 2 Relocatable loading 3 Dynamic runtime loading COP 4600 Intro To OS Memory Management Part 1 Page 11 Dr Mark Llewellyn 6 Aside on Linking and Loading cont Process mntml p 1 ml BladLII m quotI Information Entry paint I to program Branch Program Instruction Increasing ndtlness values Reference to data Data Current top of slack Addressing Requirements for a Process COP 4600 Intro To OS Memory Management Part 1 Page 12 Dr Mark Llewellyn 6 Aside on Linking and Loading cont Absolute Loading An absolute loader requires that a given load module always be loaded into the same location in main memory Thus in the load module presented to the loader all address references must be speci c or absolute main memory addresses For example if x in the gure on page 9 is location 1024 then the rst word in a load module destined for that region of memory has address 1024 The assignment of specific address values to memory references Within a program can be done either by the programmer or at compile or assembly time COP 4600 Intro To OS Memory Management Part 1 Page 13 Dr Mark Llewellyn 6 Aside on Linking and Loading cont Relocatable Loading The disadvantage of binding memory references to speci c addresses prior to loading is that the resulting load module can only be placed in one region of main memory The relocation requirement implies that we would like to be able to load a module anywhere in main memory To satisfy this requirement the assembler or compiler produces not absolute addresses but relative addresses The start of the load module is assigned relative address 0 and all memory references within the module are expressed in terms relative to 0 The loader now has the simple task of placing the module wherever room is available If as in the example the module is placed beginning at memory location x then the loader must simply add x to each memory reference as it COP 4600 Intro To OS Memory Management Part 1 loads the module into memory Page 14 Dr Mark Llewellyn 6 Aside on Address Binding cont 0 25600 30004 42094 88000 1 02400 operating The base and limit registers SyStem define the logical address space for a process process 1 1 30004 I process base s I 12090 process I39m39t COP 4600 Intro To OS Memory Management Part 1 Page 15 Dr Mark Llewellyn Aside on Linking and Loading cont Dynamic RunTime Loading 0 Relocatable loaders are common and provide obvious bene ts over absolute loaders However 1n a mult1programm1ng env1ronment even one that does not depend on virtual memory the relocating scheme 1s madequate 0 Since we may swap a given process in and out of main memory many times during its lifetime binding relative addresses to absolute addresses at the initial load time will not give us the exibility needed to relocate the same process image into different locations 0 The alternative is to defer the calculation of an absolute address until it is actually needed at run t1me 0 For this purpose the load module is loaded into main memory with all memory references in relative form It is not until an instruction is executed that the absolute address 1s calculated 0 To assure that this function does not degrade performance it is handled by special processor hardware rather than software COP 4600 Intro To OS Memory Management Part 1 Page 16 Dr Mark Llewellyn 6 Aside on Linking and Loading cont Dynamic RunTime Loading relocation register 14000 logical physical address address CPU memory 346 V 14346 MM U COP 4600 Intro To OS Memory Management Part 1 Page 17 Dr Mark Llewellyn Aside on Linking and Loading cont Dynamic RunTime Loading CPU address base base limit no no V i trap to operating system monitor addressing error memory COP 4600 Intro To OS Memory Management Part 1 Page 18 Dr Mark Llewellyn Aside on Linking and Loading cont Memory Management Unit MMU The MMU is a hardware device that maps logical addresses to physical addresses Base register replaced by relocation register In MMU scheme the value in the relocation register is added to every address generated by a user process at the time it is sent to memory The user program deals with logical addresses it never sees the real physical addresses COP 4600 Intro To OS Memory Management Part 1 Page 19 Dr Mark Llewellyn 6 Relative address Bounds Rnglsber Interrupt to I I I l I Iquot I I I operating system I Hardware Support For Relocation Fumes Guntml Blank ngmm Slack Process image In main memory COP 4600 Intro To OS Memory Management Part 1 Page 20 Dr Mark Llewellyn Aside on Address Binding 0 In order to load a program instructions and associated data must be mapped or bound to speci c locations in memory 0 Address binding can happen at three different stages Compile time o If memory location known a priori absolute code can be generated must recompile code if starting location changes Load time Must generate relocatable code if memory location is not known at compile time Execution or Run time 0 Binding delayed until run time if the process can be moved during its execution from one memory segment to another Special hardware cg MlVlUs required for address mapping COP 4600 Intro To OS Memory Management Part 1 Page 21 Dr Mark Llewellyn 6 Aside on Address Binding cont PROBLEM User Compile TIme programs Binding Goes through ASSEMBLER several steps OR before being EXECUTABLE L39NKER OBJECT COMPILER CODE CODE executed LIBRARIES LOADER Load Time Binding Executing Run Time Process Binding COP 4600 Intro To OS Memory Management Part 1 Page 22 Dr Mark Llewellyn 6 SINGLE PROGRAM COMPILE TIME BINDING Compiled View Programmer System View Absolute Code System View V39e Starting at 1000 Magn39f39e j 1000 1000 Fence 1001 Register 1001 Top of Memory m 0 OS 1000K int x 99999 1351 LD R1 1790 1333 1351 LD R1 1790 int y 1 1352 Single Partition 1352 c ST R1 1791 1899 P1 900K ST R1 1791 E 1900 g y x m 1704 Wasted 1704 Memory 1705 1705 3 1790 99999 x 5999 1790 99999 i 1791 y 1791 E 1899 1899 COP 4600 Intro To OS Memory Management Part 1 Page 23 Dr Mark Llewellyn SINGLE PROGRAM LOAD TIME BINDING Programmer Compiled View S Stem View System View View Relocatable Code y Magnified 0 Fence 100 1 Register 1001 T quot Memory 0 I os I a j 1000K in x 99999 351 LD R1 790FR 1339 1351 LD R1 1790 In y 1 352 ST R1 791FR smgle Pamt39on 1352 ST R1 1791 I lt 1899 P1 900K E 39 1900 39 21 quot y x gt m I 704 Wasted 1704 I Memory I 705 com 1705 I a I I I I 790 99999 x 9999 1790 99999 i 791 y 1791 E I 899 1899 COP 4600 Intro To OS Memory Management Part 1 Page 24 Dr Mark Llewellyn 1 Relocation cont Since we cannot know ahead of time where a program will be placed in the memory and we must allow it to be moved about in the memory due to swapping some technical concerns related to addressing must be considered The diagram on page 23 shows a process image For simplicity assume that the process image occupies a contiguous region of main memory Obviously the OS will need to know the location of the PCB and the execution stack as well as the entry point to begin execution of the program for this process Since the OS is managing the memory and is responsible to loading the process into main memory these addresses are easy to come by COP 4600 Intro To OS Memory Management Part 1 Page 25 Dr Mark Llewellyn 6 1 Relocation cont However the processor must also deal with memory references within the program Branch instructions contain an address which reference the instruction to be executed next Data reference instructions contain the address of the word or byte of the data referenced Somehow the processor hardware and the OS software must be able to translate the memory references found in the code of the program into actual physical memory addresses which re ect the current location of the program in main memory COP 4600 Intro To OS Memory Management Part 1 Page 26 Dr Mark Llewellyn e 2 Protection Each process should be protected against unwanted interference by other processes whether accidental or intentional Programs in other processes should not be able to reference memory locations in a process for reading or writing purposes without permission In one sense satisfying the relocation requirement increases the difficulty of satisfying the protection requirement Because the location of a program in main memory is unpredictable it is impossible to check absolute addresses at compile time to assure protection Furthermore most programming languages allow the dynamic calculation of addresses at run time eg computing an array subscript or a pointer into a data structure COP 4600 Intro To OS Memory Management Part 1 Page 27 Dr Mark Llewellyn 6 2 Protection cont Because of this situation all memory references generated by a process must be checked at run time to ensure that they refer only to the memory space allocated to that process Fortunately as we shall see later the mechanisms that support relocation also support the protection requirement Normally a user process cannot access any portion of the OS neither program nor data Again usually a program in one process cannot branch to an instruction in another process Without special arrangement a program in one process cannot access the data area of another process The processor must be able to abort such instructions at the point of execution COP 4600 Intro To OS Memory Management Part 1 Page 28 Dr Mark Llewellyn 6 2 Protection cont Note that the memory protection requirement must be satis ed by the processor hardware rather than the OS software This is because the OS cannot anticipate all of the memory references that a program will make Even if such anticipation were possible it would be prohibitively time consuming to screen each program in advance for possible memoryreference violations Thus it is only possible to assess the permissibility of a memory reference either a data access or a branch at the time of execution of the instruction making the reference To accomplish this the processor hardware must have this capability COP 4600 Intro To OS Memory Management Part 1 Page 29 Dr Mark Llewellyn 6 3 Sharing Any protection mechanism must have the exibility to allow several processes to access the same portion of main memory For example if a number of processes are executing the same program it is advantageous to allow each program to access the same copy of the program rather than have its own separate copy Processes that are cooperating on some task may need to share access to the same data structure The memory management system must allow controlled access to shared areas of the memory without compromising essential protection As before the mechanisms that are used to support relocation also support sharing capabilities We ll see evidence of this later COP 4600 Intro To OS Memory Management Part 1 Page 30 Dr Mark Llewellyn 6 4 Logical Organization Main memory in a computer system is almost always organized as a linear or oned1mens10nal address space cons1st1ng of a sequence of bytes or words While this organization closely mirrors the actual machine hardware it does not correspond to the way which programs are typically constructed Most programs are organized into modules some of which are unmodifiable read only execute only and some of which contain data that may be modified If the OS and computer hardware can effectively deal with user programs and data in the form of modules of some sort then a number of advantages can be realized COP 4600 Intro To OS Memory Management Part 1 Page 31 Dr Mark Llewellyn 6 4 Logical Organization cont 1 Modules can be written and compiled independently with all references from one module to another resolved by the system at run time 2 With only slight additional overhead different degrees of protection read only execute only can be given to different modules 3 It is possible to introduce mechanisms by which modules can be shared among processes 0 The advantage is that this corresponds to the user s way of viewing the problem and hence it is easy for the user to specify the sharing that is desired The mechanism that most readily satisf1es these requirements is segmentation which we will see a bit later COP 4600 Intro To OS Memory Management Part 1 Page 32 Dr Mark Llewellyn 6 5 Physical Organization Computer memory is typically organized into a least two levels referred to as main memory and secondary memory Main memory Provides fast access at relatively high cost Volatile not permanent requires refresh Secondary memory Slower and cheaper Typically not volatile Typically massive amounts COP 4600 Intro To OS Memory Management Part 1 Page 33 Dr Mark Llewellyn 6 5 Physical Organization cont The ow of information between the main and secondary memory is a major system concern in this twolevel memory organization scheme While the responsibility for this ow could be assigned to the individual programmer but this is impractical and undesirable for two reasons 1 The main memory available for a program plus its data may be insuf cient In this case the programmer must use overlays Overlays waste programmer time See next page for overlay detail 2 In a multiprogramming environment the programmer does not know at the time of coding how much space will be available nor where that space will be located Clearly the task of moving information between the two levels must be a system responsibility This task is the essence of memory management COP 4600 Intro To OS Memory Management Part 1 Page 34 Dr Mark Llewellyn G 5 Physical Organization cont Overlays Keep in memory only those Sm 20K instructions and data that are needed at any given time Needed when process is 30K larger than amount of memory allocated to it overlay 0K driver Examples 2Pass Assembler Multi Pass lt Compiler COP 4600 Intro To OS Memory Management Part 1 Page 35 Dr Mark Llewellyn 6 Memory Partitioning The principle operation of memory management is to bring processes 1nto mam memory for executlon by the processor In almost all modern multiprogramming systems this involves a sophisticated scheme known as virtual memory Virtual memory is in turn based on the use of one or both of two basic techniques known as segmentation and paging Before we examine virtual memory systems we need to look at some simpler techniques most of which were used in earlier OS on which virtual memory systems are based It will make it easier to understand the virtual memory systems if you rst understand the basics of partitioning simple paging and simple segmentation The table on the next two pages provides a brief summary of the most common memory management techniques COP 4600 Intro To OS Memory Management Part 1 Page 36 Dr Mark Llewellyn 6 Technique Description Strengths Weaknesses Main memory is diVided into a number of static partitions at Simple to implement Inef cient use of memory due to internal is loaded by loading all of its pages into available not necessarily contiguous frames Fixed Partitioning system generation time A fragmentation process may be loaded into a thtle OS overhead Maximum number of partition of equal or greater size active processes is xed Partitions are created dynamically so that each process NO Internal Inef mem use Of the Dynamic is loaded into a partition of fragmentatlon processor due to the need Partitioning exactly the same Size as the More ef cient use of for compaction to offset process main memOIy external fragmentation Main memory is diVided into a number of equalsize frames Each process is diVided into a Simple Paging number of equalsize pages of the No external small amount of I same length as frames A process fragmentatlon internal fragmentation Summary of Memory Management Techniques Part 1 COP 4600 Intro To OS Memory Management Part 1 Page 37 Dr Mark Llewellyn G Paging process Nonresident pages that are needed are brought in later automatically Large Virtual address space Technique Description Strengths Weaknesses Each process is divided into a NO internal fragmentation number of segments A 39 Simple process is loaded by loading Improved memOIy utilization and reduced External fragmentatlon Segmentatlon all of 1ts segments mto h d d dynamic partitions that need over ea com to not be contiguous dynamrc partrtlomng same as Simple paging No external fragmentation except that 1t 1s not necessary Hi her de me of VirtualMemory to load all of the pages of a mi pmgfammmg Overhead of complex memory management VirtualMemory Segmentation Same as simple segmentation except that it is not necessary to load all of the segments of a process Nonresident segments that are needed are brought in later automatically No internal fragmentation Higher degree of multiprogramming Large Virtual address space Protection and sharing support Overhead of complex memory management Summary of Memory Management Techniques Part 2 COP 4600 Intro To OS Memory Management Part 1 Page 38 Dr Mark Llewellyn Fixed Partitioning In most schemes for memory management we can assume that the OS occupies some xed portion of main memory and that the rest of main memory is available for use by multiple processes The simplest scheme for managing this available memory is to partition it into regions with xed boundaries COP 4600 Intro To OS Memory Management Part 1 Page 39 Dr Mark Llewellyn 6 Fixed Partitioning Partition Sizes The gure on the next page illustrates the two alternatives for xed partitions One possibility is to partition the memory into equal size partitions This is illustrated by the gure on the left The other possibility illustrated by the gure on the right is to partition the memory into varying size partitions COP 4600 Intro To OS Memory Management Part 1 Page 40 Dr Mark Llewellyn 6 Operating System 8 M Fixed Partitioning Equalsize partitions Operating System 8 M 8M 8M 12 M Fixed Partitioning Unequalsize partitions 16M COP 4600 Intro To OS Memory Management Part 1 Page 41 Dr Mark Llewellyn 6 Fixed Partitioning Partition Sizes cont Equalsize partitions There are two problems associated with equalsize xed partitioning l A program may be too big to t into a partition In this case the programmer must design the program using overlays 2 Main memory utilization is extremely inef cient Any program no matter how small occupies an entire partition In the example shown on the previous page if we have a program that requires only 1 MB of space it will occupy an 8 MB partition whenever it is swapped in rendering 7 MB of wasted space The phenomenon of wasted space internal to a partition which results whenever the programdata loaded into the partition is smaller than the partition is known as internal fragmentation COP 4600 Intro To OS Memory Management Part 1 Page 42 Dr Mark Llewellyn 6 Fixed Partitioning Partition Sizes cont Unequalsize partitions The two problems associated with equalsize xed partitioning can both be lessened though not solved by using unequalsized partitions 1 Using the example partitioning shown on page 41 programs as large as 16 MB can be accommodated without using overlays 2 Again using the example on page 41 partitions as small as 2 MB exist so that a lMB program would result in only 1 MB of wasted space rather than the 7 MB that would be wasted using equalsize partitioning This results in less internal fragmentation COP 4600 Intro To OS Memory Management Part 1 Page 43 Dr Mark Llewellyn 6 Fixed Partitioning Placement Algorithm Equalsize partitions As long as there is an available partition a process can be loaded into that partition Because all partitions are of equal size it does not matter which partition is used If all partitions are occupied with processes that are not ready to run then one of these processes must be swapped out to make room for a new process 0 Which one to swap out is a scheduling decision not a memory management decision COP 4600 Intro To OS Memory Management Part 1 Page 44 Dr Mark Llewellyn 6 Fixed Partitioning Placement Algorithm Unequalsize partitions 0 With unequalsize partitions there are two possible ways in which to assign processes to partitions The simplest way is to assign each process to the smallest partition within which it will t See gure a on page 47 In this case a scheduling queue is needed for each partition to hold swapped out processes destined for that partition The advantage of this approach is that processes are always assigned in such a way as to minimize internal fragmentation Although this approach seems optimal from the point of view of an individual partition it is not optimal from the point of view of the system as a whole For example consider the case when there are no processes with a size between 12 MB and 16 MB Then the entire 16 MB partition will remain unused even though some smaller processes could have been assigned to it COP 4600 Intro To OS Memory Management Part 1 Page 45 Dr Mark Llewellyn 6 Fixed Partitioning Placement Algorithm Unequalsize partitions For this reason a better approach is to use a single queue for all processes See gure b on page 47 When it is time to load a process into main memory the smallest available partition that will hold the process is selected If all partitions are occupied then a swapping decision must be made Preference might be given to swapping out the smallest process from the partition that will hold the incoming process Although other factors such as priority and a preference for swapping out blocked processes rather than ready processes may also be used COP 4600 Intro To OS Memory Management Part 1 Page 46 Dr Mark Llewellyn 6 Opemlisn lswlem opemgnquystm I l I l I l l 2M 2M 39f39l39l39l39l39i39i39l 4 M 4 M m 6M m s M 8 M New New Fromm IIIIIIIIJ 8M Pm m 8M IIEDIU 12 M u M m 16 M 16M all One process queue per partition by Sing It queue COP 4600 Intro To OS Memory Management Part 1 Page 47 Dr Mark Llewellyn 6 Fixed Partitioning Summary The use of unequalsize partitions provides a degree of exibility to the xed partitioning scheme In addition xed partitioning schemes are relatively simple and require minimal OS software and processing overhead However there are distinct disadvantages to this approach The number of partitions speci ed at system generation time limits the number of active not suspended processes in the system at any given time Because partition sizes are preset at system generation time small jobs will not utilize partition space ef ciently causing internal fragmentation The use of xed partitioning is almost unknown today One example of a successful OS that utilized this technique was an early IBM mainframe operating system OSMFT Multiprogramming with a Fixed Number of Tasks COP 4600 Intro To OS Memory Management Part 1 Page 48 Dr Mark Llewellyn 6 Dynamic Partitioning To overcome some of the problems associated with xed partitioning an approach known as dynamic partitioning was developed Again this approach has been replaced by more sophisticated memory management techniques but it is helpful to understand the basic concepts behind this strategy With dynamic partitioning the partitions are of variable length and number When a process is brought into main memory it is allocated exactly as much memory as it requires and no more COP 4600 Intro To OS Memory Management Part 1 Page 49 Dr Mark Llewellyn 6 Dynamic Partitioning cont 0 The gures on the next page illustrate a dynamic partitioning example using 64 MB of memory 0 In gure a main memory is initially empty except for the OS 0 In gures b c and d the rst three processes are loaded starting where the OS ends and occupying just enough space for each process This leaves a hole at the end of memory which is too small for a fourth process 0 At some point in time gure e the OS swaps out process 2 which leaves enough room to load another process process 4 as shown in gure f 0 Since process 4 is smaller than process 2 another smaller hole is created 0 Later a point is reached when none of the processes in main memory are ready but process 2 in the ready suspend state is available However since there is insuf cient room for process 2 the OS swaps out process 1 gure g and swaps process 2 back in gure h COP 4600 Intro To OS Memory Management Part 1 Page 50 Dr Mark Llewellyn e W EM W Lipnull Lulu l Franz l 33M Pmm l 20M Pmum l SE Prunea 1 Le r 36M 141M PM 1 14M E 22M Places 3 131 AM 1 lb It d Will hymn15 W 3 M M m l Pmm 2 1 111M Pmnm 1 33M Plans 1 20M IIM ISM HM Pmnnd 3M Plucan 3M Pmuad 354 GM 6M 5M Frames 3 1 EM PM 3 13M Pmun 3 13M Pincus 3 13M E and b Am F 4M 4 11M 1 g1 ll COP 4600 Intro To OS Memory Management Part 1 Page 51 Dr Mark Llewellyn Dynamic Partitioning cont As the example illustrates dynamic partitioning starts out well enough but eventually leads to a situation in which there are a lot of small holes in memory As time goes by the memory becomes more and more fragmented and memory utilization declines This phenomenon is known as external fragmentation External fragmentation is the memory that is external to all partitions This is indirect contrast to the internal fragmentation which was the result of fixed partitioning COP 4600 Intro To OS Memory Management Part 1 Page 52 Dr Mark Llewellyn 6 Dynamic Partitioning cont One technique for overcoming external fragmentation is compaction With compaction from time to time the OS shifts the processes so that they are contiguous and all of the unoccupied free memory is placed together in one block For example in gure h on page 51 compaction would result in a free block of memory 16 MB in size since the free blocks of size 6 MB 6 MB and 4 MB would be coalesced into a single block of free memory The difficulty with compaction is that it is a time consuming process and wasteful of processor time Note that compaction implies the need for a dynamic relocation capability COP 4600 Intro To OS Memory Management Part 1 Page 53 Dr Mark Llewellyn e Dynamic Partitioning Placement Algorithm Because memory compaction is time consuming the OS designer must be clever in deciding how to assign processes to memory how to plug the holes When it is time to load or swap a process into main memory and if there is more than one free block of memory of suf cient size then the OS must decide which free block to allocate to the process There are three basic placement algorithms that might be considered 1 Best t chooses the block that is closest in size to the request 2 First t scans memory from the beginning and chooses the rst available block which is large enough to accommodate the request 3 Next t scans memory from the location of the last placement and chooses the next available block with suf cient size COP 4600 Intro To OS Memory Management Part 1 Page 54 Dr Mark Llewellyn e Dynamic Partitioning Placement Algorithm Figure a on the next page shows an example memory con guration after a number of placement and swapping out operations The last block that was used was a 22 MB block from which a 14 MB partition was created Figure b illustrates the differences between the best f1rst and next t placement algorithms in satisfying a 16 MB allocation request Best t will search the entire list of available blocks and make use of the 18 MB block leaving a 2 MB fragment Firstfit results in a 6 MB fragment Next t results in a 20 MB fragment COP 4600 Intro To OS Memory Management Part 1 Page 55 Dr Mark Llewellyn 6 Best t and firstfit start searching from here Nextfit starts searching from here Best t considers blocks 8MB 12 MB 22 MB 18 MB 8MB 6 MB 14 MB and 20 MB Best t partitions 18 MB block leaving a 2 MB fragment First t considers blocks 8 MB 12 MB 22 MB Firstfit partitions 22 MB block Leaving a 6 MB fragment Next t considers blocks 8 MB 6 MB 14 MB 36 MB Nextfit partitions 36 MB block leaving a 20 MB fragment Last allocated block lib11K gr gt El 12M First Fit 12 M Best Flt 13M 8M 6M D Allocated black D Frazbluck 14M El Possible new allmatiun Next Flt 36M a Before 14M b After COP 4600 Intro To OS Memory Management Part 1 Page 56 Dr Mark Llewellyn Dynamic Partitioning Placement Algorithm 0 Which of the placement algorithms is best depends on the exact sequence of process swapping that occurs and the size of those processes However some generalizations can be made The rst t algorithm is not only the simplest but is usually the best and fastest as well The next t algorithm tends to produce slightly worse results than the f1rstf1t The next t algorithm will more frequently lead to an allocation from a free block at the end of memory The result is that the largest block of free memory which usually appears at the end of the memory space is quickly broken up into small fragments Thus compaction may be required more frequently under the next t protocol On the other hand the rst t scheme tends to litter the frontend of the memory space with small free partitions that need to be searched on each subsequent f1rstf1t pass Despite its name best t usually performs the worst Since this algorithm looks for the smallest block which satis es the request the remaining fragment is as small as possible The result is many small blocks too small to satisfy any request Thus compaction is required even more frequently COP 4600 Intro To OS Memory Management Part 1 Page 57 Dr Mark Llewellyn 6 Dynamic Partitioning Summary Dynamic partitioning is rarely utilized in modern OS One example of a successful OS that utilized this technique was an early IBM mainframe operating system OSMV T Multiprogramming with a Variable Number of Tasks COP 4600 Intro To OS Memory Management Part 1 Page 58 Dr Mark Llewellyn 6 Processes Scheduling and Resource Management 0 Fairness 0 Give equal and fair access to resources 0 Differentialresponsiveness o Discriminate among different classes ofjobs o Efficiency 0 Maximize throughput minimize response time and accommodate as many uses as possible Key Elements of an OS 0 Service call handler 0 Service call from process 0 Interrupt handler o Interrupt from process 0 Interrupt from 10 ShortTerm scheduler Long term queue Short term queue I O queues System structure 0 Modular programming alone is not sufficient to manage development oflarge systems of code for OS 0 Hierarchical approach 0 Views the OS as a series oflevels where each level performs a related subset of functions 0 Each level relies on lower level to perform primitive functions 0 Lower levels deal with shorter time scales 0 Some parts of OS interact directly with the computer hardware 0 Some parts of OS communicate with the user issuing commands Process Hardware Levels 0 Level 1 0 Electronic circuits 0 Objects are registers memory cells and logic gates 0 Operations I Clearing a register I Reading memory location 0 LevelZ o Processor s instruction set I Add I Subtract I Load I Store 0 Level3 0 Concept ofa procedure or subroutine 0 Call return operations 0 Level 4 o Interrupts Concepts with Multiprogramming 0 Level 5 0 Process as a program in execution o Suspend and resume processes 0 Level 6 0 Secondary storage devices 0 Transfer of blocks of data 0 Level 7 o Creates logical address space for processes 0 Organizes virtual address space into blocks Deal with External Objects 0 Level 8 0 Communication ofinformation and messages between processes 0 Level 9 0 Supports longterm storage of named files 0 Level 10 0 Provides access to external devices using standardized interfaces 0 Level 11 o Responsible for maintaining the association between the external and internal identifiers 0 Level 12 0 Provides fullfeatured facility for the support ofprocesses 0 Level 13 0 Provides interface to the operating system for the user Modern OS 0 Monolithic Kernel 0 Most ofwhat is viewed as OS functionality is provided in a large kernel 0 Microkernel architecture 0 Assigns only a few essential functions to the kernel I Address spaces basic scheduling o Simplifies implementation by providing exibility o Suited for a distributed environment 0 Multithreading 0 Process is divided into threads that can run concurrently I Thread 0 Dispatch able unit of work 0 Processor context PC and stack pointer o Stack o Executes sequentially and is interruptible I Process 0 Collection of one or more threads and associated system routines o Symmetric Multiprocessing SMP o Achieve greater efficiency and reliability with multiple processors 0 Describes both a hardware architecture and OS behavior 0 Processors share same main memory and IO facilities I Interconnected by a communication bus or other internal connection scheme 0 All processors can perform same functions 0 Distributed OS 0 Illusion ofa single main memory space and single secondary memory space 0 Objectoriented design 0 Adding modular extensions to a small kernel 0 Enables customization of OS without disrupting system integrity Threads and SMP 0 OS routines can run on any available processor 0 Different routines can execute simultaneously on different processes 0 Multiple threads within a single process 0 Share data and resources between process Requirements of an OS 0 Maximize processor utilization by interleaving the execution of multiple processes 0 Providing reasonable response time o Supportinterprocess communication and user creation of processes Process 0 Program in execution o Instance ofa program running on a computer 0 Entity that can be assigned to and executed on a processor Process Elements 0 Identifier 0 Unique process ID 0 State 0 Running suspended etc 0 Priority 0 Relative to other processes 0 Program counter 0 Address of next instruction to be executed 0 Memory pointers o Pointers to program code and data 0 Context data 0 Data present in registers while the process is executing 0 IO status information o All outstanding IO request IO devices assigned to process 0 Accounting information 0 Processor time used clock time used account numbers etc Process Control Block PCB 0 Contains the process elements 0 Created and managed by OS 0 Allows support for multiple processes 0 Process Identification o Identifiers I User identifier I Parent identifier I Process identifier 0 Process state information 0 User Visible registers I One that may be referenced by means of the machine language that the processor executes while in user mode 0 Control and status registers I Control operation ofprocessor 0 Program counter 0 Condition codes 0 Result ofmost recent arithmetic or logical operation I Sign I Zero 0 Status information o Interrupt enableddisabled ags 0 Execution mode 0 Stack pointers I Stores parameters and calling addresses for procedure and system calls 0 Scheduling and state Information I Process state 0 Defines readiness ofprocess to be scheduled for execution 0 Running 0 Ready I Priority I Schedulingrelated information o Depend on scheduling algorithm used 0 Ex 0 Amount of time waited I Event 0 Event the process is awaiting before it can be resumed 0 Data structuring I Process may be linked to other process in a queue ring or some other structure 0 Interprocess Communication I Various ags signals and messages may be associated between 2 independent processes 0 Process Privileges I Granted privileges in terms 0 the memory that may be accessed and types ofinstructions that may be executed 0 Memory management I Includes pointers to segment andor page tables describing virtual memory assigned to process 0 Resource ownership and utilization I Resources by process may be indicated 0 Opened files 0 Contents ofprocessor registers I Uservisible registers I Control and status registers I Stack pointers 0 Program status word I Contains status information Trace of Process 0 Behavior of an individual process can be characterized by listing the sequence of instructions that execute for that process 0 Trace o Dispatcher o Switches the processor from one process to another TwoState Process Model 0 Process may be in one of two states 0 Running 0 Not running I Go into a queue Reasons for Process Creation 0 New batch job 0 When OS is prepared to take on new work it will read the next sequence ofjob control commands 0 Interactive logon 0 User at a terminal logs onto the system 0 Created by OS to provide a service 0 To perform a function on behalf ofa user program without having the user to wait I Printer control 0 Spawned by existing process 0 Modularity or to exploit parallelism Reasons for Process Termination 0 Normal completion 0 OS service call gets executed indicating that a process has finished running 0 Time limit exceeded 0 Process has run longer than the specified total time limit 0 Memory unavailable 0 Process requires more memory than the system can provide 0 Bounds violation 0 Process tries to access a memory location that is not allowed to access 0 Protection error 0 Process attempts to use a resource that it is not allowed to use 0 Arithmetic error 0 Process tries a prohibited computation I Division by zero Processes o Notrunning 0 Ready to execute 0 Blocked 0 Waiting for IO 0 Dispatcher cannotjust choose a process that has been waiting the longest it could be blocked Fivestate Process model 2 queue implementation for 1 blocked state 0 New 0 Ready 0 Running 0 Blocked 0 Exit Suspended Processes 0 Processor is faster than 10 so all processes could be waiting for IO 0 Swap the processes to disk to free up more memory 0 Blocked state becomes suspended when swapped to disk 0 Two new states 0 BlockedSuspend o ReadySuspend Reasons for Process Suspension 0 Swapping 0 OS needs to release sufficient main memory to bring in a process that is ready to execute 0 Interactive user request 0 User suspending execution to debug 0 Timing 0 Process may be executed periodically and may be suspended while waiting for the next time interval 0 Parent process request 0 Parent process may wish to suspend execution 0fa descendent OS System Control Structures 0 Information about the current status of each process and resource 0 Tables are constructed for each entity the OS manages Memory Tables 0 Allocation of main memory to processes 0 Allocation of secondary memory to processes 0 Protection attributes for access to shared memory regions 0 Information needed to manage virtual memory I 0 Tables 0 IO device is available or assigned 0 Status of IO operation 0 Location in main memory being used as the source or destination of the IO transfer File Tables Existence of files Location on secondary memory Current status Attributes Sometimes this information is maintained by a file management system Process Table 0 Where process is located 0 Attributes in the process control block 0 Program Typical Elements of a Process Image 0 User data 0 Modifiable part of the user space 0 May include I Program data I User stack area I Programs that may be modified 0 User Program 0 Program to be executed 0 System Stack 0 Each process has one or more lastinfirstout LIFO system stack associated with it 0 Stores parameters and calling addresses for procedure and system calls 0 PCB 0 Data needed by OS to control processes Process Creation 0 Assign unique process identifier o Allocate space for the process 0 Initialize process control block 0 Set up appropriate linkages 0 Add new process to linked list used for scheduling queue o Create or expand other data structures 0 Maintaining accounting file When to switch a process Clock interrupt 0 Process has executed for maximum allowable time slice IO interrupt Memory fault 0 Memory address is in virtual memory so it must be brought into main memory Trap 0 Errorexception occurred 0 May cause to terminate Supervisor call 0 File open Change of Process State Save context of processor including program counter and other registers Update PCB ofprocess that is running Move PCB to appropriate queue 0 Ready 0 Blocked o ReadySuspend Select another process for execution Update PCB of the process selected Update memorymanagement data structures Restore context of selected process COP 4600 Summer 2011 Introduction To Operating Systems Memory Management Part 2 Instructor Dr Mark Llewellyn marklcsucfedu HEC 236 4078232790 httpwww cs ucfeducou rsescop4600su m201 1 Department of Electrical Engineering and Computer Science Computer Science Division University of Central Florida COP 4600 Intro To OS Memory Management Part 2 Page 1 Dr Mark Llewellyn Memory Management Memory Management Methods Contiguous Allocation NonContiguous Allocation Single Partition Multiple Partition Segmentation Paging Fixed Dynamic quotBasicquot Demand Allocation Allocation Paging Paging Virtual Memory COP 4600 Intro To OS Memory Management Part 2 Page 2 Dr Mark Llewellyn 6 Both unequal fixedsize and variablesize partitions are inefficient in the use of memory Unequal xedsize partitions result in internal fragmentation Variable size partitions result in external fragmentation Paging is a technique which attempts to resolve both types of fragmentation In paging the main memory is partitioned into fixedsize chunks that are relatively small and each process is also divided into small fixed size chunks of the same size The chunks of a process are referred to as pages While the chunks of main memory are referred to as frames or page frames Paging results in a small amount of internal fragmentation in only the last frame assigned to a process and no external fragmentation COP 4600 Intro To OS Memory Management Part 2 Page 3 Dr Mark Llewellyn e Assignment of Process Pages to Free Frames Frame Main memmwr Malquot memm y Main memnrv number ID I 310 I All 1 1 AJ 1 151 2 2 A 2 ml 3 3 Ana 3 A 4 4 4 KNEE 5 5 5 warm 6 6 6 mnfzm 739 7 7 8 E 8 9 9 9 ID 10 ll 1 1 ll 1 l2 12 12 L1 13 13 l4 l4 14 a Available Frames Eb Luau Process A c Load Process COP 4600 Intro To OS Memory Management Part 2 Page 4 Dr Mark Llewellyn 6 Assignment of Process Pages to Free Frames Primquot murmur Main memory Ham memnry 0 AD 0 AJ 0 AJ 1 AA 1 Al J AJ 2 Aquot 2 A3 2 A1 3 A3 3 AJ 3 AJ 4 NEW 4 4 mi 5 Warm 5 5 31 6 m yw 6 I I I 15 this 7 migtm v mew v WACW a W xiii25 H WcW 3 Mai 9 a a a w Macaw4 m Weed2Z5 m l l I l l J D 3 12 12 12 114 u 13 13 l4 14 H 1 Load Process C E Swap out E f Load Process D COP 4600 Intro To OS Memory Management Part 2 Page 5 Dr Mark Llewellyn 6 Paging cont Notice that process pages do not need to be loaded into contiguous page frames Recall our discussions of logical addressing With paging a simple relocation register is no longer sufficient for calculating physical addresses at execution time The OS maintains a page table for each process The page table shows the frame location for each page of the process Within the program each logical address consists of a page number and an offset within the page Recall that with simple partitioning a logical address is the location of the word relative to the beginning of the program which the processor translated into a physical address With paging the logicaltophysical address translation is still done by processor hardware but now the processor must know how to access the page table of the current process COP 4600 Intro To OS Memory Management Part 2 Page 6 Dr Mark Llewellyn 6 Paging cont 0 When presented with a logical address page number offset the processor uses the page table to produce a physical address page frame offset 0 The next page illustrates the page tables for the processes in the preVious example at the time illustrated by gure f which is shown again for continuity COP 4600 Intro To OS Memory Management Part 2 Page 7 Dr Mark Llewellyn 6 Page Tables for Example on Page 4 Main mentor D AD 1 AJ 2 1L 3 A 4 my 5 111 6 DJI v mam s macij n fwgaaw 0 Wmm 1 D3 12 DA 13 I4 1quot Load Process D l MNF Q Process A page table 0 1 2 Process B page table QEDlb ll 12 Process D page table hMNHG Process B currently has no pages loaded in main memor 7 S 9 10 Process C page table bahMs Free frame list COP 4600 Intro To OS Memory Management Part 2 Page 8 Dr Mark Llewellyn 6 Paging cont 0 Simple paging is similar to xed partitioning The differences are that with paging the partitions are rather small a program may occupy more than one partition frame and these partitions need not be contiguous To make simple paging convenient for use the page size and hence the frame size as well is set to be a power of 2 0 When the page size is a power of 2 it is easy to demonstrate that the relative address which is de ned with reference to the origin of the program and the logical address expressed as a page number and offset are the same 0 The example on the next page illustrates this point COP 4600 Intro To OS Memory Management Part 2 Page 9 Dr Mark Llewellyn 6 Paging Address Translation Scheme Address generated by CPU is divided into Page number p used as an index into a page table which contains base address of each page in physical memory Page offset 1 combined with base address to define the physical memory address that is sent to the memory unit page number page offset mn l7 For given logical address space 2 and page size 211 COP 4600 Intro To OS Memory Management Part 2 Page 10 Dr Mark Llewellyn 6 Paging Hardware logical physical address address fOOOO 0000 CPU f1111 1111 f physical memory page table COP 4600 Intro To OS Memory Management Part 2 Page 11 Dr Mark Llewellyn Paging Model of Logical and Physical Memory frame number page 0 0 page 1 1 page 0 page 2 2 page 3 page table 3 page 2 logical 4 page 1 memory 5 6 7 page 3 physical mm COP 4600 Intro To OS Memory Management Part 2 Page 12 Dr Mark Llewellyn 6 Simple Paging Example 0 a O FrameNumbers 1 b 0 2 c 3 d 4 e 4 I 5 f j 6 g g k 1 7 h 1 I 8 i N 8 m 9 j n 10 k 3 o 2 11 l pagetable p 13 Z 2 3 32byte memory 14 o 7 5 P and 4byte pages logical memory 15 4 O a b c 5 d e 24 f 6 g h 28 7 physical memory COP 4600 Intro To OS Memory Management Part 2 Page 13 Dr Mark Llewellyn e Free Frames freeframe list free frame list 1 31 13 15 13 page1 14 14 page 0 15 15 16 16 17 17 18 18 page 2 19 19 20 20 page 3 21 newprocess page table 21 a b Before allocation After allocation COP 4600 Intro To OS Memory Management Part 2 Page 14 Dr Mark Llewellyn Implementation of Page Table Page table is kept in main memory Pagetable base register PTBR points to the page table Pagetable length register PRLR indicates size of the page table In this scheme every datainstruction access requires two memory accesses One for the page table and one for the datainstruction The two memory access problem can be solved by the use of a special fastlookup hardware cache called associative memory or translation lookaside buffers TLBs Some TLBs store addressspace identi ers ASIDs in each TLB entry uniquely identi es each process to provide addressspace protection for that process COP 4600 Intro To OS Memory Management Part 2 Page 15 Dr Mark Llewellyn 6 Associative Memory Associative memory parallel search Page Frame Address translation p r d If p is in associative register get frame out Otherwise get frame from page table in memory COP 4600 Intro To OS Memory Management Part 2 Page 16 Dr Mark Llewellyn 6 Paging Hardware With TLB logical address CPU p page frame number number TLB hit physical I address TLB p TLB miss f physical memory page table COP 4600 Intro To OS Memory Management Part 2 Page 17 Dr Mark Llewellyn Effective Access Time Associative Lookup 8 time unit Assume memory cycle time is 1 microsecond Hit ratio percentage of times that a page number is found in the associative registers ratio related to number of associative registers Hit ratio or Effective Access Time EAT EAT180L281 oc 28 a COP 4600 Intro To OS Memory Management Part 2 Page 18 Dr Mark Llewellyn 6 Memory Protection Memory protection implemented by associating a protection bit with each frame Validinvalid bit attached to each entry in the page table valid indicates that the associated page is in the process logical address space and is thus a legal page invalid indicates that the page is not in the process logical address space COP 4600 Intro To OS Memory Management Part 2 Page 19 Dr Mark Llewellyn 6 Valid v or Invalid i Bit In A Page Table O 1 2 page 0 00000 frame number valid invalid bit Page 0 3 page 1 o pagel 1 4 page2 page 2 2 5 a page 8 4 a 6 5 a page 4 6 7 page 3 10468 page 5 7 all 8 page 4 12287 page table 9 page 5 2 page n COP 4600 Intro To OS Memory Management Part 2 Page 20 Dr Mark Llewellyn Paging Example 0 Suppose 16bit addresses are used in our machine and that the page size is set at 1K 1024 bytes 210 The logical address 150210 SDE16 00000101110111102 A page size of 1K requires an offset eld of 10 bits This leaves 6 bits to represent the page number 0 This implies that a program can consist of a maximum of 26 64 pages each of 1K bytes 00001H0111011110l2 page 1 offset 0111011112 I I lDE16 47810 page offset COP 4600 Intro To OS Memory Management Part 2 Page 21 Dr Mark Llewellyn e Paging Example cont Logical address Relative address 1502 Page L Offset 478 0000010111011110 00000 0111011110 c E a a L 3930 E 539 5 a 1 L I a a r an 2 Ci a N a 2 E a a E E a Partitioning g E H 33 a bi Paging page size 1K COP 4600 Intro To OS Memory Management Part 2 Page 22 Dr Mark Llewellyn Paging Example cont 16bit Ingical address 1 II 51 page u 104m offset InIololo010l1l1l101111o WW I Process page tab 2 r AJF FWK J Hs lUIOIUl11l0011101l11l101 1 16939quot physical address COP 4600 Intro To OS Memory Management Part 2 Page 23 Dr Mark Llewellyn Paging cont 0 The consequences of using a page size that is a power of 2 are twofold l The logical addressing scheme is transparent to the programmer the assembler and the linker Each logical address page number offset of a program is identical to its relative address 2 It is a relatively easy matter to implement a function in hardware to perform dynamic address translation at run time 0 Consider an address of n m bits where the leftmost n bits are the page number and the right most m bits are the offset In our preVious example n 6 and m 10 COP 4600 Intro To OS Memory Management Part 2 Page 24 Dr Mark Llewellyn G Paging cont The following steps are needed to perform address translation Extract the page number as the leftmost 11 bits of the logical address Use the page number as an index into the process page table to nd the frame number k The starting physical address of the frame is NZ and the physical address of the referenced byte is that number plus the offset This physical address does not need to be calculated it is easily constructed by appending the frame number to the offset Using the preVious example Where the logical address 00000101110111102 yields page number 1 offset 478 Assuming this page is residing in page frame 610 0001102 then the physical address is frame number 6 offset 478 00011001110111102 COP 4600 Intro To OS Memory Management Part 2 Page 25 Dr Mark Llewellyn 6 Paging Summary 0 With simple paging main memory is divided into many small equalsize frames In this respect paging is similar to xedsize partitioning 0 Each process is diVided into framesize pages smaller processes require fewer pages larger processes require more pages 0 When a process is brought in all of its pages are loaded into available frames and a page table is set up for the process Paging results in only a small amount of internal fragmentation No external fragmentation occurs COP 4600 Intro To OS Memory Management Part 2 Page 26 Dr Mark Llewellyn e Segmentation A user program can be subdivided using segmentation in which the program and its associated data are diVided into a number of segments It is not required that all segments of a program be of the same length although there is a maximum segment length As with paging a logical address using segmentation consists of two parts in this case a segment number and an offset Because of the unequalsize segments segmentation is similar to dynamic partitioning In the absence of an overlay scheme or the use of Virtual memory it would be required that all of a program s segments be loaded into memory for execution COP 4600 Intro To OS Memory Management Part 2 Page 27 Dr Mark Llewellyn 6 User s View of a Program subroutine stack symbol table Sqrt main program logical address COP 4600 Intro To OS Memory Management Part 2 Page 28 Dr Mark Llewellyn Logical View of Segmentation user space physical memory space COP 4600 Intro To OS Memory Management Part 2 Page 29 Dr Mark Llewellyn Segmentation Architecture Logical address consists of a two tuple ltsegmentnumber offsetgt Segment table maps twodimensional physical addresses each table entry has base contains the starting physical address Where the segments reside in memory limit speci es the length of the segment Segmenttable base register STBR points to the segment table s location in memory Segmenttable length register STLR indicates number of segments used by a program segment number s is legal ifs lt STLR COP 4600 Intro To OS Memory Management Part 2 Page 30 Dr Mark Llewellyn 6 Segmentation Architecture cont Protection With each entry in segment table associate validation bit 0 gt illegal segment readwriteexecute privileges Protection bits associated with segments code sharing occurs at segment level Since segments vary in length memory allocation is a dynamic storageallocation problem A segmentation example is shown in the following diagram COP 4600 Intro To OS Memory Management Part 2 Page 31 Dr Mark Llewellyn 6 Segmentation Hardware limit base segment table CPU 8 A A no v trap addressing error physical memory COP 4600 Intro To OS Memory Management Part 2 Page 32 Dr Mark Llewellyn Example of Segmentation subroutine stack 1400 segment 3 segment 0 2400 symbol segment 0 table limit base sq segment 4 0 1000 1400 1 400 6300 3200 main 2 400 4300 program 3 1100 3200 segment 3 4 1000 4700 segment table 4300 segment 2 segment 2 4700 logical address space segment 4 5700 6300 segment 1 6700 thsical memory COP 4600 Intro To OS Memory Management Part 2 Page 33 Dr Mark Llewellyn Segmentation cont The difference compared to dynamic partitioning is that With segmentation a program may occupy more than one partition and these partitions need not be contiguous Segmentation eliminates internal fragmentation but like dynamic partitioning it suffers from external fragmentation However since a process is broken up into a number of smaller pieces the external fragmentation should be less Whereas paging is invisible to the programmer segmentation is usually visible and is provided as a convenience for organizing programs and data into different segments For purposes of modular programming the program or data may be further broken down into multiple segments The principal inconvenience of this service is that the programmer must be aware of the maximum segment size limitation COP 4600 Intro To OS Memory Management Part 2 Page 34 Dr Mark Llewellyn 6 Segmentation cont 0 Another consequence of unequalsize segments is that there is no simple relationship between logical addresses and physical addresses Analogous to paging a simple segmentation scheme would make use of a segment table for each process and a list of free blocks of main memory 0 Each segment table entry would have to list the starting address in main memory of the corresponding segment The entry would also need to provide the length of the segment to assure than invalid addresses are not used COP 4600 Intro To OS Memory Management Part 2 Page 35 Dr Mark Llewellyn e Segmentation cont 0 When a process enters the running state the address of its segment table is loaded into a special register used by the memorymanagement hardware 0 Assume an address of nm bits where the leftmost n bits are the segment number and the rightmost m bits are the offset In the example on page 38 n 4 and m 12 Thus the maximum segment size would be 212 4096 bytes COP 4600 Intro To OS Memory Management Part 2 Page 36 Dr Mark Llewellyn 6 Segmentation cont 0 Address translation using segmentation proceeds as follows 1 Extract the segment number as the leftmost n bits of the logical address 2 Use the segment number as an index into the process segment table to find the starting physical address of the segment 3 Compare the offset expressed in the rightmost m bits to the length of the segment If the offset is greater than or equal to the length the address is invalid 4 The desired physical address is the sum of the starting physical address of the segment plus the offset COP 4600 Intro To OS Memory Management Part 2 Page 37 Dr Mark Llewellyn 6 Segmentation Example Suppose 16bit addresses are used in our machine and that n 4 and m 12 thus the maximum segment size is 212 4096 bytes The program is placed into two segments Where segment 0 750 bytes and segment 1 1950 bytes The logical address 00010010111100002 yields a segment number of 1 and an offset of 0010111100002 2F016 75210 00010010111100002 segment 1 offset 39 I I 39 0010111100002 page offset 2F016 75210 COP 4600 Intro To OS Memory Management Part 2 Page 38 Dr Mark Llewellyn e Segmentation Example cont 39 Logical address Relative address 1502 Segment L Offset 752 0000010111011110 0001001011110000 E 33 a VA r 539 E a Q E I 3 5 3 E 539 En 5 3 b Segnmnlalion a Parljlinning COP 4600 Intro To OS Memory Management Part 2 Page 39 Dr Mark Llewellyn 6 Segmentation Example cont J 16 bit logical ad dress alabit segment 124m n set h F IDInl lllolalllnlllllllllolaInlnl bF Mf KFPHE d Starting address of t Length 3359 the segment CI00201110111IJIiDODDC1DCIOIIIEIODCIODI quot39 1 0111091111 i olunouoonlonuool b A Process segment table 001011101102 2EE16 75010 WES F AH FF W l l lll l l lllll lDlolllUlDl l i 1 0111100111102 l ebit physical address 79315 lt19501o COP 4600 Intro To OS Memory Management Part 2 Page 40 Dr Mark Llewellyn Segmentation Summary With simple segmentation a process is divided into a number of segments that need not be of equal size When a process is brought in all of its segments are loaded into available regions of memory and a segment table is set up for the process Segmentation results in no internal fragmentation External fragmentation occurs however its effects should be less severe than occurs With dynamic partitioning as the segment size is typically smaller COP 4600 Intro To OS Memory Management Part 2 Page 41 Dr Mark Llewellyn 6 COP 4600 Introduction To Operating Systems Summer 2011 Introductory Material Instructor Dr Mark Llewellyn marklcsucfedu HEC 236 4078232790 httpwww cs ucfeducou rsescop4600su m201 1 Department of Electrical Engineering and Computer Science Computer Science Division University of Central Florida COP 4600 Introduction To Operating Systems Intro Page 1 Dr Mark Llewellyn What is an Operating System In the most general sense an operating system is a collection of system software routines that sit between an application program and the computer hardware on which that application is to be executed The OS sits between the Interfaces application program and the hardware HARDWARE COP 4600 Introduction To Operating Systems Intro Page 2 Dr Mark Llewellyn What is an Operating System cont For now we can think of an OS as l is the interface or intermediary between a user application and the computer hardware 2 provides an environment in which the user can execute programs conveniently and application andor system software 3 manages the computer s resources ef ciently 0 memory disk space CPU time 10 software etc Often an OS is a tradeoff between convenience and ef c1ency Windows GUI vs Unix command interpreter COP 4600 Introduction To Operating Systems Intro Page 3 Dr Mark Llewellyn 6 The 08 As An Intermediary 0 What s an application user user user user 1 2 Software to accomplish a task lilk tin m Q l Spread sheet word processor browser v v t compiler assembler text editor database ema11 system What about Sy S t e m system and application programs software 0 Depending on who you operating system ask can be considered application programs a computer resource or WW a39dwa e part of the OS 7 COP 4600 Introduction To Operating Systems Intro Page 4 Dr Mark Llewellyn 6 What Is A Process PROBLEM ASSEMBLER OR L39NKER OBJECT COMPILER CODE UBRARES EXECUTABLE CODE LOADER PROCESS COP 4600 Introduction To Operating Systems Intro Page 5 Dr Mark Llewellyn 6 What Is A Process cont A process is a program in execution has a process control block PCB has a program counter PC A process can have one or more threads A thread is sometimes known as a lightweight process COP 4600 Introduction To Operating Systems Intro Page 6 Dr Mark Llewellyn 6 Types of Operating Systems Focus on two system resources CPU processor Utilization Main Memory Utilization Utilization is measure of busy time over total study time TbusyTTotal In the old days computers were physically very large but very small in terms of resources and capabilities also very very expensive Important to achieve high utilization of resources COP 4600 Introduction To Operating Systems Intro Page 7 Dr Mark Llewellyn 6 Early Systems Instructions and data written in binary Loaded using switches on front panel Computers also had a few buttons Halt Run Load Set PC displayed contents Increment PC Everything done by programmer there was no real user as we know them today Very slow set up time Very limited output set PC and check lights CPU sat idle much of the time Very little wasted memory since RAM was so small Programmers always squeezed program into Main Memory COP 4600 Introduction To Operating Systems Intro Page 8 Dr Mark Llewellyn 6 Early Systems Hardware Innovations Needed way to speed up Input amp Output IO Paper Tape Data entry dif cult splicing needed or recopy tape Paper tape output faster than looking at lights but hard to read Punch Cards Faster form of input Of ine CardtoPrinter improved readability of output Magnetic Tape Input even faster Cardtotape tapetoCPU CPUtotape tapetoprinter Disk drives as a replacement for tapes COP 4600 Introduction To Operating Systems Intro Page 9 Dr Mark Llewellyn 6 Early Systems Software Innovations Assemblers Symbolic programming rather than ls and Os 11 relationship between assembler statements and machine instructions Linkers amp Loaders allowed the use of code libraries didn t have to rewrite common code Compilers Programming in High Level Languages Fortran COBOL ln relationship between a program statement and machine instructions Eased programming task and improved operational ef ciency COP 4600 Introduction To Operating Systems Intro Page 10 Dr Mark Llewellyn 6 Early Systems PeopleProcedural Changes Too much work for programmer Division of labor became necessary Divided tasks between a programmer and professional operator Operator could now organize the work more effectively and batch jobs Batching allows similar jobs to run sequentially efficient use of system software today refers more to jobs which lack user interaction Example billing systems used by companies still took long time to set up jobs CPU frequently sat idle COP 4600 Introduction To Operating Systems Intro Page 11 Dr Mark Llewellyn 6 Running Multiple Programs SerialSequential Execution One job rnust finish before next job starts Results in very low utilization of resources Concurrent Execution Two or more processes executing at the same time but doing different activities Processes take turns using single shared resource Gives the illusion of parallel processing ParallelSimultaneous Execution Two or more processes performing the same activity at the same time Requires two or more of the same resource eg processors printers disk drives COP 4600 Introduction To Operating Systems Intro Page 12 Dr Mark Llewellyn 6 Resident Monitor Precursor to the Operating System The beginnings of computer selfgovernance Resident in memory all the time Monitored operations Primary task was job sequencing In beginning read jobs sequentially from tape already prepared offline With disks could select which jobs to run and when Job Scheduling Resident Monitors Improved CPU Utilization Faster setup less idle time Memory Utilization Sharing of IO driverscode Functionality Accounting and run time amp IO limits COP 4600 Introduction To Operating Systems Intro Page 13 Dr Mark Llewellyn 6 The Beginnings of Multiprogramming With RM had two programs running serially Application RM Application RM Application etc Application ran to completion before RM took over Reduced CPU idle time between jobs but not between 10 operations IO speed very slow compared to CPU speed Much of IO deals with accessing data tape disk COP 4600 Introduction To Operating Systems Intro Page 14 Dr Mark Llewellyn 6 An Aside On The Memory Hierarchy Both special and general purpose faster more On processor chip expensive smaller amounts Buffers memory requests Maybe multiple levels O 39 d 39 d d b t PrimaryMain RAM rgamze m wor an y es Fixed media including hard Secondary disks optical disks etc Slower cheaper larger amounts v Removable media includin Tertiary tapes oppy disks CDs etc COP 4600 Introduction To Operating Systems Intro Page 15 Dr Mark Llewellyn 6 Multiprogramming cont Need some way to perform CPU and IO operations at the same time Keep more than one user program in memory Switch between programs during IO operations Operating System Process 1 Process 2 Process 3 COP 4600 Introduction To Operating Systems Intro Page 16 Dr Mark Llewellyn Multiprogramming cont More ef cient use of system less idle time Made possible because of reduced memory costs Created a Whole new set of problems Memory Management Protection Mechanisms Job Scheduling CPUProcess Scheduling Improves resource utilization but not user interaction munuges the computer s resources efficiently What about conveniences the user can execute programs conveniently COP 4600 Introduction To Operating Systems Intro Page 17 Dr Mark Llewellyn 6 Time Sharing Introduced to improve the interaction with computer Use of terminals and teleprinters Allows user to input data and interact With program Give each process a slice of CPU time Don t wait for next IO operation Similar to multiplexing Possible because user input is so slow 1 char takes 1000 milliseconds to enter While only 2 milliseconds required for an interrupt handler Required the development of virtual memory online file systems and directory structures Today s systems generally support a combination of batch and time sharing COP 4600 Introduction To Operating Systems Intro Page 18 Dr Mark Llewellyn e Other Operating System Developments Real Time Response time is critical Hard Real Time Industrial amp Robotic controls Very small bounded delays Little use of swapping or secondary storage Soft Real Time Immediate response not as critical Monitoring devices etc Longer delays tolerated Use of secondary storage amp priority scheduling COP 4600 Introduction To Operating Systems Intro Page 19 Dr Mark Llewellyn 6
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'