Review Basics Allocation Policies Data Structures Segmentation & PagingOperating SystemsTutorial 2 & 16Michael Tänzeros-tut@nhng.dehttp://os-tut.nhng.deCalendar Week 51OS-Tutorial – Week 51 Michael TänzerReview Basics Allocation Policies Data Structures Segmentation & PagingOutline1 Review2 Memory Management Basics3 Memory Allocation Policies4 Memory Management Data Structures5 Segmentation & PagingPagingSegmentation and PagingOS-Tutorial – Week 51 Michael TänzerReview Basics Allocation Policies Data Structures Segmentation & PagingTrue or FalseIf the system is in a safe state all resource requests fromexisting processes which don’t exceed their maximum canbe granted and still no deadlock can occurA circle in a WFG indicates a deadlockBounded waiting is a necessary condition for a deadlockOS-Tutorial – Week 51 Michael TänzerReview Basics Allocation Policies Data Structures Segmentation & PagingExternal vs. internal fragmentationInternal fragmentationApplication gets more memory than neededCan’t be avoided when using fixed size allocation units(pages)Internal fragmentation< page size (on average ½ pagesize)External fragmentationUsed memory contains holes that may be too small tosatisfy an incoming request although on the whole there’senough space) Need to defragment memory to close holesCurrently unusable memory is called externalfragmentationOS-Tutorial – Week 51 Michael TänzerReview Basics Allocation Policies Data Structures ...
If the system is in a safe state all resource requests from existing processes which don’t exceed their maximum can be granted and still no deadlock can occur A circle in a WFG indicates a deadlock Bounded waiting is a necessary condition for a deadlock
ic1MelhanzTä
True or False
er
Internal fragmentation Application gets more memory than needed Can’t be avoided when using fixed size allocation units (pages) Internal fragmentation < page size (on average ½ page size) External fragmentation Used memory contains holes that may be too small to satisfy an incoming request although on the whole there’s enough space ⇒ Need to defragment memory to close holes Currently unusable memory is called external fragmentation
Logical addresses Applications run in their own logical address space All addresses in the programme are logical ones Physical addresses Are put on the bus to get the data from the memory chips On runtime some logical addresses are mapped to physical ones The translation is done by the MMU (memory management unit) In some systems logical addresses = physical addresses
128MB (2 27 bytes) of physical memory Units of n bytes Each node in a linked list contains Memory address Length Pointer(s) to the next (and previous) node Each entry 32 bit How many bytes are required for the three kinds of control structures (bit maps, singly and doubly linked lists) assuming the cases no memory allocated, all memory allocated and worst case?
re
Linked lists vs. bit maps
1Miceek5Tänzhael
Tlnäezr15iMhceaial–WeekOS-Tutor
Each logical address is divided into two parts Segment number Offset in the segment The segment number is used as an index into the segment table which contains Segment base address (physical address of the start of the segment) Segment limit (size of the segment) (Status bits, e. g. protection, valid) Check whether offset < limit if not throw error Physical address := base address + offset
Logical address space is contiguous while physical space occupied doesn’t need to be Logical memory is divided into fixed size blocks called pages Physical memory is divided into blocks of the same size which are called frames The page table maps pages to frames
1 Each logical address is divided into two parts Page number Page offset 2 The page number is used as an index into the page table which contains Frame number (Status bits, e. g. protection, valid) 3 Physical address := frame number × frame size + offset
Typically the page/frame size is a power of two ⇒ frame number × frame size is a simple shift operation
Paging
Address translation using a single-level page table
rzeSOT-
eaTlnäezr
What is the disadvantage of single-level page tables?
Paging
Size(page table) = Size(page table entry) × (#logical addresses ÷ page size) Increases linearly with the size of the address space ⇒ Page tables become quite large (espacially with 64-bit processors)