Swapping



Memory ManagementMain Memory refers to a physical memory that is the internal memory to the computer. The word main is used to distinguish it from external mass storage devices such as disk drives. Main memory is also known as RAM. The computer is able to change only data that is in main memory. Therefore, every program we execute and every file we access must be copied from a storage device into main memory.All the programs are loaded in the main memeory for execution. Sometimes complete program is loaded into the memory, but some times a certain part or routine of the program is loaded into the main memory only when it is called by the program, this mechanism is called?Dynamic Loading, this enhance the performance.Also, at times one program is dependent on some other program. In such a case, rather than loading all the dependent programs, CPU links the dependent programs to the main executing program when its required. This mechanism is known as?Dynamic Linking.SwappingA process needs to be in memory for execution. But sometimes there is not enough main memory to hold all the currently active processes in a timesharing system. So, excess process are kept on disk and brought in to run dynamically. Swapping is the process of bringing in each process in main memory, running it for a while and then putting it back to the disk.fixed partitioningdynamic partitioningsimple pagingsimple segmentationFixed PartitioningPartition main memory into a set of non overlapping regions called partitionsPartitions can be of equal or unequal sizes any process whose size is less than or equal to a partition size can be loaded into the partitionif all partitions are occupied, the operating system can swap a process out of a partitiona program may be too large to fit in a partition. The programmer must then design the program with overlayswhen the module needed is not present the user program must load that module into the program’s partition, overlaying whatever program or data are thereMain memory use is inefficient. Any program, no matter how small, occupies an entire partition. This is called internal fragmentation.Unequal-size partitions lessens these problems but they still remain...Equal-size partitions was used in early IBM’s OS/MFT (Multiprogramming with a Fixed number of Tasks) Placement Algorithm with PartitionsEqual-size partitionsIf there is an available partition, a process can be loaded into that partitionbecause all partitions are of equal size, it does not matter which partition is usedIf all partitions are occupied by blocked processes, choose one process to swap out to make room for the new processUnequal-size partitions: use of multiple queuesassign each process to the smallest partition within which it will fitA queue for each partition sizetries to minimize internal fragmentationProblem: some queues will be empty if no processes within a size range is presentUnequal-size partitions: use of a single queueWhen its time to load a process into main memory the smallest available partition that will hold the process is selectedincreases the level of multiprogramming at the expense of internal fragmentationDynamic PartitioningPartitions are of variable length and numberEach process is allocated exactly as much memory as it requiresEventually holes are formed in main memory. This is called external fragmentation Must use compaction to shift processes so they are contiguous and all free memory is in one blockUsed in IBM’s OS/MVT (Multiprogramming with a Variable number of Tasks)Dynamic Partitioning: an exampleA hole of 64K is left after loading 3 processes: not enough room for another processEventually each process is blocked. The OS swaps out process 2 to bring in process 4another hole of 96K is createdEventually each process is blocked. The OS swaps out process 1 to bring in again process 2 and another hole of 96K is created...Compaction would produce a single hole of 256KPlacement AlgorithmUsed to decide which free block to allocate to a processGoal: to reduce usage of compaction (time consuming)Possible algorithms:Best-fit: choose smallest hole First-fit: choose first hole from beginning Next-fit: choose first hole from last placementNext-fit often leads to allocation of the largest block at the end of memory First-fit favors allocation near the beginning: tends to create less fragmentation then Next-fitBest-fit searches for smallest block: the fragment left behind is small as possiblemain memory quickly forms holes too small to hold any process: compaction generally needs to be done more often RelocationBecause of swapping and compaction, a process may occupy different main memory locations during its lifetimeHence physical memory references by a process cannot be fixedThis problem is solved by distinguishing between logical address and physical address Address TypesA physical address (absolute address) is a physical location in main memoryA logical address is a reference to a memory location independent of the physical structure/organization of memory Compilers produce code in which all memory references are logical addressesA relative address is an example of logical address in which the address is expressed as a location relative to some known point in the program (ex: the beginning)Simple PagingMain memory is partition into equal fixed-sized chunks (of relatively small size)Trick: each process is also divided into chunks of the same size called pages The process pages can thus be assigned to the available chunks in main memory called frames (or page frames)Consequence: a process does not need to occupy a contiguous portion of memoryNow suppose that process B is swapped outWhen process A and C are blocked, the pager loads a new process D consisting of 5 pagesProcess D does not occupied a contiguous portion of memoryThere is no external fragmentationInternal fragmentation consist only of the last page of each processPage Tables :The OS now needs to maintain (in main memory) a page table for each processEach entry of a page table consist of the frame number where the corresponding page is physically locatedThe page table is indexed by the page number to obtain the frame numberA free frame list, available for pages, is maintained Simple SegmentationEach program is subdivided into blocks of non-equal size called segmentsWhen a process gets loaded into main memory, its different segments can be located anywhereEach segment is fully packed with instructs/data: no internal fragmentationThere is external fragmentation; it is reduced when using small segmentsIn contrast with paging, segmentation is visible to the programmerprovided as a convenience to organize logically programs (ex: data in one segment, code in another segment)must be aware of segment size limitThe OS maintains a segment table for each process. Each entry contains: the starting physical addresses of that segment. the length of that segment (for protection)Simple segmentation and paging comparisonSegmentation requires more complicated hardware for address translationSegmentation suffers from external fragmentationPaging only yield a small internal fragmentationSegmentation is visible to the programmer whereas paging is transparentSegmentation can be viewed as commodity offered to the programmer to organize logically a program into segments and using different kinds of protection (ex: execute-only for code but read-write for data) for this we need to use protection bits in segment table entriesVirtual Memory :A computer can address more memory than the amount physically installed on the system. This extra memory is actually called?virtual memory?and it is a section of a hard disk that's set up to emulate the computer's RAM.The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using disk. Second, it allows us to have memory protection, because each virtual address is translated to a physical address.Following are the situations, when entire program is not required to be loaded fully in main memory.User written error handling routines are used only when an error occurred in the data or computation.Certain options and features of a program may be used rarely.Many tables are assigned a fixed amount of address space even though only a small amount of the table is actually used.The ability to execute a program that is only partially in memory would counter many benefits.Less number of I/O would be needed to load or swap each user program into memory.A program would no longer be constrained by the amount of physical memory that is available.Each user program could take less physical memory, more programs could be run the same time, with a corresponding increase in CPU utilization and throughput.Modern microprocessors intended for general-purpose use, a memory management unit, or MMU, is built into the hardware. The MMU's job is to translate virtual addresses into physical addresses. A basic example is given below ?Virtual memory is commonly implemented by demand paging. It can also be implemented in a segmentation system. Demand segmentation can also be used to provide virtual memory.Demand PagingA demand paging system is quite similar to a paging system with swapping where processes reside in secondary memory and pages are loaded only on demand, not in advance. When a context switch occurs, the operating system does not copy any of the old program’s pages out to the disk or any of the new program’s pages into the main memory Instead, it just begins executing the new program after loading the first page and fetches that program’s pages as they are referenced.While executing a program, if the program references a page which is not available in the main memory because it was swapped out a little ago, the processor treats this invalid memory reference as a?page fault?and transfers control from the program to the operating system to demand the page back into the memory.AdvantagesFollowing are the advantages of Demand Paging ?Large virtual memory.More efficient use of memory.There is no limit on degree of multiprogramming.DisadvantagesNumber of tables and the amount of processor overhead for handling page interrupts are greater than in the case of the simple paged management techniques.Page Replacement Algorithm :Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated. Paging happens whenever a page fault occurs and a free page cannot be used for allocation purpose accounting to reason that pages are not available or the number of free pages is lower than required pages.When the page that was selected for replacement and was paged out, is referenced again, it has to read in from disk, and this requires for I/O completion. This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.Reference StringThe string of memory references is called reference string. Reference strings are generated artificially or by tracing a given system and recording the address of each memory reference. The latter choice produces a large number of data, where we note two things.For a given page size, we need to consider only the page number, not the entire address.If we have a reference to a page?p, then any immediately following references to page?p?will never cause a page fault. Page p will be in memory after the first reference; the immediately following references will not fault.For example, consider the following sequence of addresses ? 123,215,600,1234,76,96If page size is 100, then the reference string is 1,2,6,12,0,0When there is a page fault, the referenced page must be loaded.If there is no available frame in memory, then one page is selected for replacementIf the selected page has been modified, it must be copied back to disk (swapped out)A page replacement algorithm is said to satisfy the inclusion property or is called a?stack algorithm?if the set of pages in a k-frame memory is always a subset of the pages in a (k + 1) frame memoryFirst-In-First-Out (FIFO) ReplacementFIFO is not a stack algorithm. In certain cases, the number of page faults can actually increase when more frames are allocated to the process. In the example below, there are 9 page faults for 3 frames and 10 page faults for 4 frames.Optimal ReplacementThe Belady’s optimal algorithm cheats. It looks forward in time to see which frame to replace on a page fault. Thus it is not a real replacement algorithm. It gives us a frame of reference for a given static frame access sequence.Least Recently Used (LRU) ReplacementOn a page fault, the frame that was least recently used in replaced.Device ControllersDevice drivers are software modules that can be plugged into an OS to handle a particular device. Operating System takes help from device drivers to handle all I/O devices.The Device Controller works like an interface between a device and a device driver. I/O units (Keyboard, mouse, printer, etc.) typically consist of a mechanical component and an electronic component where electronic component is called the device controller.There is always a device controller and a device driver for each device to communicate with the Operating Systems. A device controller may be able to handle multiple devices. As an interface its main task is to convert serial bit stream to block of bytes, perform error correction as necessary.Any device connected to the computer is connected by a plug and socket, and the socket is connected to a device controller. Following is a model for connecting the CPU, memory, controllers, and I/O devices where CPU and device controllers all use a common bus for communication.FileA file is a named collection of related information that is recorded on secondary storage such as magnetic disks, magnetic tapes and optical disks. In general, a file is a sequence of bits, bytes, lines or records whose meaning is defined by the files creator and user.File StructureA File Structure should be according to a required format that the operating system can understand.A file has a certain defined structure according to its type.A text file is a sequence of characters organized into lines.A source file is a sequence of procedures and functions.An object file is a sequence of bytes organized into blocks that are understandable by the machine.When operating system defines different file structures, it also contains the code to support these file structure. Unix, MS-DOS support minimum number of file structure.File TypeFile type refers to the ability of the operating system to distinguish different types of file such as text files source files and binary files etc. Many operating systems support many types of files. Operating system like MS-DOS and UNIX have the following types of files ?Ordinary filesThese are the files that contain user information.These may have text, databases or executable program.The user can apply various operations on such files like add, modify, delete or even remove the entire file.Directory filesThese files contain list of file names and other information related to these files.Special filesThese files are also known as device files.These files represent physical device like disks, terminals, printers, networks, tape drive etc.These files are of two types ?Character special files?? data is handled character by character as in case of terminals or printers.Block special files?? data is handled in blocks as in the case of disks and tapes.File Access MechanismsFile access mechanism refers to the manner in which the records of a file may be accessed. There are several ways to access files ?Sequential accessDirect/Random accessIndexed sequential accessSequential accessA sequential access is that in which the records are accessed in some sequence, i.e., the information in the file is processed in order, one record after the other. This access method is the most primitive one. Example: Compilers usually access files in this fashion.Direct/Random accessRandom access file organization provides, accessing the records directly.Each record has its own address on the file with by the help of which it can be directly accessed for reading or writing.The records need not be in any sequence within the file and they need not be in adjacent locations on the storage medium.Indexed sequential accessThis mechanism is built up on base of sequential access.An index is created for each file which contains pointers to various blocks.Index is searched sequentially and its pointer is used to access the file directly.Space AllocationFiles are allocated disk spaces by operating system. Operating systems deploy following three main ways to allocate disk space to files.Contiguous AllocationLinked AllocationIndexed AllocationContiguous AllocationEach file occupies a contiguous address space on disk.Assigned disk address is in linear order.Easy to implement.External fragmentation is a major issue with this type of allocation technique.Linked AllocationEach file carries a list of links to disk blocks.Directory contains link / pointer to first block of a file.No external fragmentationEffectively used in sequential access file.Inefficient in case of direct access file.Indexed AllocationProvides solutions to problems of contigous and linked allocation.A index block is created having all pointers to files.Each file has its own index block which stores the addresses of disk space occupied by the file.Directory contains the addresses of index blocks of files.Security refers to providing a protection system to computer system resources such as CPU, memory, disk, software programs and most importantly data/information stored in the computer system. If a computer program is run by an unauthorized user, then he/she may cause severe damage to computer or data stored in it. So a computer system must be protected against unauthorized access, malicious access to system memory, viruses, worms etc. We're going to discuss following topics in this chapter.AuthenticationOne Time passwordsProgram ThreatsSystem ThreatsComputer Security Classifications ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download