operating systems module 4 engineering.pptx

operating system

1. Module 4

2. Concept of address spaces Swapping Contiguous Memory Allocation Fixed and variable partitions Segmentation Paging Virtual Memory Demand Paging Page Replacement Algorithms Module 4

3. Background The memory consist of a large array or group of words or bytes, each with its own address. The primary motive of a computer system is to execute programs. These programs, along with the information they access, should be in the main memory during execution. The CPU fetches instructions from memory according to the value of the program counter. 

4. Each process has a separate memory space(memory address). Separate per-process memory space protects the processes from each other and is fundamental to have multiple processes loaded in main memory for concurrent execution. To separate the memory spaces, we need the ability to determine the range of legal addresses that the process may access and to ensure that the process can access only these legal addresses. This protection can be provided by using two registers Base register – holds the smallest legal physical memory address Limit register – size of the range

5. Hardware address protection with base and limit registers

6. Logical vs. Physical Address Space Logical address A logical address is generated by CPU while a program is running. Since a logical address does not physically exists it is also known as a virtual address . This address is used as a reference by the CPU to access the actual physical memory location.  There is a hardware device called Memory-Management Unit is used for mapping logical address to its corresponding physical address. The user program generates the logical address and believes that the program is running in this logical address space, but the program needs physical memory for its execution, therefore, the logical address must be mapped to the physical address by the MMU before the addresses are used. Physical address A physical address identifies the physical location of a specific data element in memory.

7. MMU

8. Swapping Swapping is a mechanism in which a process can be swapped temporarily out of main memory to secondary storage and make that memory available to other processes. At some later time, the system swaps back the process from the secondary storage to main memory. The system maintains a ready queue consisting of all processes who are ready to run The dispatcher checks whether the next process in the queue is in memory or not.

9. Memory Allocation Techniques Contiguous Allocation Non-contiguous Allocation

10. Contiguous Memory Allocation Contiguous memory allocation  is a memory allocation method that allocates a  single contiguous section of memory  to a process. Advantage: Less access time Disadvantage External fragmentation

11. Non-Contiguous Memory Allocation Allocates the memory space present in different locations to the process as per its requirement Contrary to contiguous allocation Advantage No External Fragmentation Disadvantage More access time compared to contiguous allocation

12. Contiguous Memory Allocation

13. Fixed Size Partition Also known as   Static partitioning. In this scheme, the system divides the memory into fixed-size partitions. The partitions may or may not be the same size. The size of each partition is fixed and it cannot be changed. In this partition scheme, each partition is allowed to contain exactly one process.

14. Problem with fixed sized partition Internal Fragmentation

15. Variable Partition Also called as Dynamic Partition It performs the allocation dynamically, there is no predefined partition. When a process arrives, a partition of size equal to the size of process is created. Then that partition is allocated to the process. No internal fragmentation

16. Fragmentation Internal Fragmentation allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used External Fragmentation total memory space exists to satisfy a request, but it is not contiguous

17. Used to decide which hole is to be allocated to the arrived process. The free blocks of memory  are known as holes Algorithms/Startegies: FIRST Fit BEST fit WORST Fit Partition Allocation Strategies

18. First Fit The first hole that is found to be large enough for a process to accommodate is selected.

19. Best Fit The smallest hole that is large enough for the process to accommodate is selected from the list of free holes.

20. Worst Fit The largest hole among the free holes is selected.

21. Non-Contiguous Memory Allocation Allocates the memory space present in different locations to the process as per its requirement Contrary to contiguous allocation Approaches Segmentation Paging

22. Segmentation Non-contiguous memory allocation method Memory-management scheme that supports user view of memory A program is a collection of segments A segment is a logical unit such as: main program, procedure, function, method etc User view of a program

23. Logical View of Segmentation

24. Segmentation Hardware/Architecture Logical address consists of a two tuple: <segment-number, offset> Segment table – maps two-dimensional logical addresses into one dimensional physical address ; Each table entry has: base – contains the starting physical address where the segments reside in memory limit – specifies the length of the segment Segment-table base register (STBR) points to the segment table’s location in memory

25. Segmentation Hardware

26. Paging Non-contiguous memory allocation Divide physical memory(main memory) into fixed-sized blocks called frames Size is power of 2, 512 bytes and 16 Mbytes Divide logical memory(secondary memory) into blocks of same size called pages Page size = frame size This technique keep track of all free frames

27. Paging Model of Logical and Physical Memory

28. Paging Hardware

29. Paging Example Physical address = frame number * page size + offset

30. Paging Hardware With TLB TLB – Translation Lookaside Buffer Special cache contains  page table entries  that have been most recently used.

31. Steps in TLB hit:    CPU generates logical address.    It is checked in TLB (present).    Corresponding frame number is retrieved, combining page number and offset tells where in the main memory page lies.  Steps in TLB miss:     CPU generates logical address.    It is checked in TLB (not present).    Now the page number is matched to page table residing in main memory   Corresponding frame number is retrieved, combining page number and offset tells where in the main memory page lies.    The TLB is updated with new PTE (if space is not there, one of the replacement technique). 

32. Effective access time(EAT) = h*m + (1-h)*2m where, h = hit ratio of TLB  m = Memory access time  If hit ratio is 80%, memory access time is 100 nanosecond, EAT = 0.80 x 100 + 0.20 x 200 = 120ns If hit ratio is 99%, memory access time is 100 nanosecond, EAT = 0.99 x 100 + 0.01 x 200 = 101ns Effective Access Time

33. Virtual Memory Virtual Memory is a storage scheme that provides user an illusion of having a very big main memory. This is done by treating a part of secondary memory as the main memory. A computer can address more memory than the amount physically installed on the system. This extra memory is actually called  virtual memory  

34. Background (Cont.) Virtual memory – separation of user logical memory from physical memory Only part of the program needs to be in memory for execution Logical address space can therefore be much larger than physical address space Allows address spaces to be shared by several processes Allows for more efficient process creation More programs running concurrently Less I/O needed to load or swap processes

35. Virtual Memory That is Larger Than Physical Memory

36. Virtual Address Space Virtual address space of a process refers to the logical(virtual) view of how process is stored in memory Usually start at address 0, contiguous addresses until end of space Meanwhile, physical memory organized in page frames MMU must map logical to physical Enables sparse address spaces with holes left for growth, dynamically linked libraries, etc

37. Shared Library Using Virtual Memory In addition to separating logical memory from physical memory, virtual memory allows files and memory to be shared by 2 or more processes through page sharing.

38. Demand Paging Pages are loaded only when they are demanded during program execution. A demand paging system is similar to a paging system with swapping. Lazy swapper – never swaps a page into memory unless page will be needed

39. Requirement – 5, 2, 4, 6, 1, 3

40. Valid-Invalid Bit With each page table entry a valid–invalid bit is associated ( v ⇒ in-memory – memory resident , i ⇒ not-in-memory) Initially valid–invalid bit is set to i on all entries Example of a page table snapshot: During MMU address translation, if valid–invalid bit in page table entry is i ⇒ page fault

41. Page Table When Some Pages Are Not in Main Memory

42. Steps in Handling a Page Fault A page fault occurs  when a program attempts to access data or code that is in its address space , but is not currently located in the system RAM.

43. Performance of Demand Paging Stages in Demand Paging (worse case) Trap to the operating system Save the user registers and process state Determine that the interrupt was a page fault Check that the page reference was legal and determine the location of the page on the disk Issue a read from the disk to a free frame: Wait in a queue for this device until the read request is serviced Wait for the device seek and/or latency time Begin the transfer of the page to a free frame While waiting, allocate the CPU to some other user Receive an interrupt from the disk I/O subsystem (I/O completed) Save the registers and process state for the other user Determine that the interrupt was from the disk Correct the page table and other tables to show page is now in memory Wait for the CPU to be allocated to this process again Restore the user registers, process state, and new page table, and then resume the interrupted instruction

44. Performance of Demand Paging (Cont.) Three major activities Service the interrupt – careful coding means just several hundred instructions needed Read the page – lots of time Restart the process – again just a small amount of time Page Fault Rate 0 ≤ p ≤ 1 if p = 0 no page faults if p = 1, every reference is a fault Effective Access Time (EAT) EAT = (1 – p ) x memory access + p (page fault overhead + swap page out + swap page in )

45. Demand Paging Example Memory access time = 200 nanoseconds Average page-fault service time = 8 milliseconds EAT = (1 – p) x 200 + p (8 milliseconds) = (1 – p x 200 + p x 8,000,000 = 200 + p x 7,999,800 If one access out of 1,000 causes a page fault, then EAT = 8.2 microseconds. This is a slowdown by a factor of 40!! If want performance degradation < 10 percent 220 > 200 + 7,999,800 x p 20 > 7,999,800 x p p < .0000025 < one page fault in every 400,000 memory accesses

46. Page Replacement Page replacement is a process of swapping out an existing page from the frame of a main memory and replacing it with the required page.

47. Basic Page Replacement Find the location of the desired page on disk Find a free frame: - If there is a free frame, use it - If there is no free frame, use a page replacement algorithm to select a victim frame - Write victim frame to disk if dirty Bring the desired page into the (newly) free frame; update the page and frame tables Continue the process by restarting the instruction that caused the trap

48. Need For Page Replacement

49. Page Replacement Algorithms Page Replacement Algorithms: Page replacement algorithms help to decide which page must be swapped out from the main memory to create a room for the incoming page. Algorithms: FIFO Page Replacement Algorithm LRU Page Replacement Algorithm Optimal Page Replacement Algorithm A good page replacement algorithm is one that minimizes the number of page faults

50. FIFO Page Replacement Algorithm Works on the principle of “ First in First out “. It replaces the oldest page that has been present in the main memory for the longest time. Simplest Algorithm In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal. 

51. Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames.

52. Belady’s anomaly   Bélády’s anomaly  is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.  Beladys anomaly can occur in FIFO page replacement algorithm. For example, if we consider reference string 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.

53. Eg:

54. LRU Page Replacement Algorithm Least Recently Used In this algorithm page will be replaced which is least recently used That is, it replaces the page that has not been referred by the CPU for the longest time

55. Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames. Find number of page faults. 

56. Optimal Page Replacement Algorithm In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.   Although it can not be practically implementable but it can be used as a benchmark. Other algorithms are compared to this in terms of optimality.

57. Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 , with 4 page frame. Find number of page fault.