Operating System - Unit - 4 Memory Management and File Managment

 Unit 4 - Part I - Memory Management

Physical and Virtual Address Space

Physical Address identifies a physical location of required data in a memory. The user never directly deals with the physical address but can access by its corresponding logical address. The user program generates the logical address and thinks that the program is running in this logical address but the program needs physical memory for its execution, therefore, the logical address must be mapped to the physical address by MMU before they are used. The term Physical Address Space is used for all physical addresses corresponding to the logical addresses in a Logical address space.

Logical Address is generated by CPU while a program is running. The logical address is virtual address as it does not exist physically, therefore, it is also known as Virtual Address. This address is used as a reference to access the physical memory location by CPU. The term Logical Address Space is used for the set of all logical addresses generated by a program’s perspective. 
The hardware device called Memory-Management Unit is used for mapping logical address to its corresponding physical address.

Parameter	Logical Address	Physical Address
Basic	Generated by CPU	Location in a memory unit
Address Space	Logical Address Space is set of all logical addresses generated by CPU in reference to a program.	Physical Address is set of all physical addresses mapped to the corresponding logical addresses.
Visibility	User can view the logical address of a program.	User can never view physical address of program.
Generation	Generated by the CPU	Computed by MMU
Access	The user can use the logical address to access the physical address.	The user can indirectly access physical address but not directly.
Editable	Logical address can be change.	Physical address will not change.
Also called	Virtual address.	Real address.

The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames. (fixed memory)

The Logical address Space is also split into fixed-size blocks, called pages. (fixed length block in secondary memory)

Page Size = Frame Size

Segment – Variable length block in secondary memory

 

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. This scheme permits the physical address space of a process to be non – contiguous.

·        Logical Address or Virtual Address (represented in bits): An address generated by the CPU

·        Logical Address Space or Virtual Address Space( represented in words or bytes): The set of all logical addresses generated by a program

·        Physical Address (represented in bits): An address actually available on memory unit

·        Physical Address Space (represented in words or bytes): The set of all physical addresses corresponding to the logical addresses

 

Memory Management:

Surveying the various mechanisms and policies associated with memory management, it is helpful to keep in mind the requirements that memory management is intended to satisfy. These requirements include the following:

• Relocation - the user should not have to know where the program is going to be located.  Consider the addressing requirements of a process as in Figure. The hardware and OS must work together in this process of relocation.

Protection - keep the process from accessing the address space of another process

Sharing - this cooperation is necessary in an OS: shared data areas, share code (DDL)

Logical organization - processes are composed of modules or varing sizes, modules independently compiled, modules with different protection needs even to the degree of sharing.

Physical organization - typically a two level organization: main memory and secondary memory.  The user/programmer cannot know how a program or process will be split across the levels.

 

 

Memory Allocation Strategies:

 

Memory allocation has two core types

 Static Memory Allocation: The program is allocated memory at compile time. 

 Dynamic Memory Allocation: The programs are allocated with memory at run time.

Fixed Partitioning - Split the physical memory into partitions and assigned to each process.

 

 

Two difficulties: 

1.     The programmer may have to rewrite a program in order to fit into even the largest available partition.  Overlaying may be used. 

2.     Internal fragmentation typically results--there's memory that is unused within each partition.

Placement algorithm.

• With equal sized partitions there's not much to consider.  Swapping out for more throughput may require some policies
• For unequal sized partitions, the programs may be queued to use the "best" partition.  This may not give the best throughput as some partitions may go unused.

Dynamic parititioning has the OS allocate the space for a process when it enters the system. 

External fragmentation occurs here.  Compaction may be used to help recover the space.

Placement algorithms

• best fit - waste the least amount of space from the list of available blocks
• worst fit - wasted the most amount of space (hope that what's left over is useful)
• first fit - performance gain
• next fit - performance

 

Paging

In Operating Systems, Paging is a storage mechanism used to retrieve processes from the secondary storage into the main memory in the form of pages. The main idea behind the paging is to divide each process in the form of pages. The main memory will also be divided in the form of frames. One page of the process is to be stored in one of the frames of the memory. The pages can be stored at the different locations of the memory but the priority is always to find the contiguous frames or holes. Pages of the process are brought into the main memory only when they are required otherwise they reside in the secondary storage.

 

Example

Let us consider the main memory size 16 Kb and Frame size is 1 KB therefore the main memory will be divided into the collection of 16 frames of 1 KB each.

There are 4 processes in the system that is P1, P2, P3 and P4 of 4 KB each. Each process is divided into pages of 1 KB each so that one page can be stored in one frame.

Initially, all the frames are empty therefore pages of the processes will get stored in the contiguous way.

Frames, pages and the mapping between the two is shown in the image below.

When a page is to be accessed by the CPU by using the logical address, the operating system needs to obtain the physical address to access that page physically.

The logical address has two parts.

1. Page Number – sequence number of a page
2. Offset – no:of bits required to represent a word in a page

Memory management unit of OS needs to convert the page number to the frame number.

Segmentation

In Operating Systems, Segmentation is a memory management technique in which the memory is divided into the variable size parts. Each part is known as a segment which can be allocated to a process. The details about each segment are stored in a table called a segment table. Segment table is stored in one (or many) of the segments.

Segment table contains mainly two information about segment:

1. Base: It is the base address of the segment
2. Limit: It is the length of the segment.

Why Segmentation is required?

Till now, we were using Paging as our main memory management technique. Paging is more close to the Operating system rather than the User. It divides all the processes into the form of pages regardless of the fact that a process can have some relative parts of functions which need to be loaded in the same page.

Translation of Logical address into physical address by segment table

CPU generates a logical address which contains two parts:

1. Segment Number – is mapped to the segment table
2. Offset – logical address ‘d’ should lie within segment size

For Example:

Suppose a 16 bit address is used with 4 bits for the segment number and 12 bits for the segment offset so the maximum segment size is 4096 and the maximum number of segments that can be refereed is 16.

When a program is loaded into memory, the segmentation system tries to locate space that is large enough to hold the first segment of the process, space information is obtained from the free list maintained by memory manager. Then it tries to locate space for other segments. Once adequate space is located for all the segments, it loads them into their respective areas.

The operating system also generates a segment map table for each program.

Advantages of Segmentation

1. No internal fragmentation
2. Average Segment Size is larger than the actual page size.
3. Less overhead
4. It is easier to relocate segments than entire address space.
5. The segment table is of lesser size as compared to the page table in paging.

Disadvantages

1. It can have external fragmentation.
2. it is difficult to allocate contiguous memory to variable sized partition.
3. Costly memory management algorithms.

Sr No.	Paging	Segmentation
1	Non-Contiguous memory allocation	Non-contiguous memory allocation
2	Paging divides program into fixed size pages.	Segmentation divides program into variable size segments.
3	OS is responsible	Compiler is responsible.
4	Paging is faster than segmentation	Segmentation is slower than paging
5	Paging is closer to Operating System	Segmentation is closer to User
6	It suffers from internal fragmentation	It suffers from external fragmentation
7	There is no external fragmentation	There is no external fragmentation
8	Logical address is divided into page number and page offset	Logical address is divided into segment number and segment offset
9	Page table is used to maintain the page information.	Segment Table maintains the segment information
10	Page table entry has the frame number and some flag bits to represent details about pages.	Segment table entry has the base address of the segment and some protection bits for the segments.

 

 

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. In this scheme, User can load the bigger size processes than the available main memory by having the illusion that the memory is available to load the process.

Instead of loading one big process in the main memory, the Operating System loads the different parts of more than one process in the main memory. By doing this, the degree of multiprogramming will be increased and therefore, the CPU utilization will also be increased.

Advantages of Virtual Memory

1. The degree of Multiprogramming will be increased.
2. User can run large application with less real RAM.
3. There is no need to buy more memory RAMs.

Disadvantages of Virtual Memory

1. The system becomes slower since swapping takes time.
2. It takes more time in switching between applications.
3. The user will have the lesser hard disk space for its use.

 

Part - II - File Management

File management

Directory Structure

What is a directory?

Directory can be defined as the listing of the related files on the disk. The directory may store some or the entire file attributes. To get the benefit of different file systems on the different operating systems, A hard disk can be divided into the number of partitions of different sizes. The partitions are also called volumes or mini disks. Each partition must have at least one directory in which, all the files of the partition can be listed. A directory entry is maintained for each file in the directory which stores all the information related to that file.

Every Directory supports a number of common operations on the file:

1. File Creation
2. Search for the file
3. File deletion
4. Renaming the file
5. Traversing Files
6. Listing of files

Single Level Directory

The simplest method is to have one big list of all the files on the disk. The entire system will contain only one directory which is supposed to mention all the files present in the file system. The directory contains one entry per each file present on the file system.

Advantages

1. Implementation is very simple.
2. If the sizes of the files are very small then the searching becomes faster.
3. File creation, searching, deletion is very simple since we have only one directory.

Disadvantages

1. We cannot have two files with the same name.
2. The directory may be very big therefore searching for a file may take so much time.
3. Protection cannot be implemented for multiple users.
4. There are no ways to group same kind of files.
5. Choosing the unique name for every file is a bit complex and limits the number of files in the system because most of the Operating System limits the number of characters used to construct the file name.

Two Level Directory

In two level directory systems, we can create a separate directory for each user. There is one master directory which contains separate directories dedicated to each user. For each user, there is a different directory present at the second level, containing group of user's file. The system doesn't let a user to enter in the other user's directory without permission.

Characteristics of two level directory system

1. Each files has a path name as /User-name/directory-name/
2. Different users can have the same file name.
3. Searching becomes more efficient as only one user's list needs to be traversed.
4. The same kind of files cannot be grouped into a single directory for a particular user.

Every Operating System maintains a variable as PWD which contains the present directory name (present user name) so that the searching can be done appropriately.

Tree Structured Directory

In Tree structured directory system, any directory entry can either be a file or sub directory. Tree structured directory system overcomes the drawbacks of two level directory system. The similar kind of files can now be grouped in one directory.Only administrator of the system has the complete access of root directory. Only administrator of the system has the complete access of root directory. Searching is more efficient in this directory structure. A tree structured directory system may consist of various levels therefore there is a set of permissions assigned to each file and directory. The permissions are R W X which are regarding reading, writing and the execution of the files or directory. The permissions are assigned to three types of users: owner, group and others.

 

Acyclic-Graph Structured Directories

The tree structured directory system doesn't allow the same file to exist in multiple directories therefore sharing is major concern in tree structured directory system. We can provide sharing by making the directory an acyclic graph. In this system, two or more directory entry can point to the same file or sub directory. That file or sub directory is shared between the two directory entries.These kinds of directory graphs can be made using links or aliases. We can have multiple paths for a same file. Links can either be symbolic (logical) or hard link (physical).

 

File Operations

A file is a collection of logically related data that is recorded on the secondary storage in the form of sequence of operations. The content of the files are defined by its creator who is creating the file. The various operations which can be implemented on a file such as read, write, open and close etc. are called file operations. These operations are performed by the user by using the commands provided by the operating system. Some common operations are as follows:

1.Create operation:

This operation is used to create a file in the file system. It is the most widely used operation performed on the file system. To create a new file of a particular type the associated application program calls the file system. This file system allocates space to the file. As the file system knows the format of directory structure, so entry of this new file is made into the appropriate directory.

2. Open operation:

This operation is the common operation performed on the file. Once the file is created, it must be opened before performing the file processing operations. When the user wants to open a file, it provides a file name to open the particular file in the file system. It tells the operating system to invoke the open system call and passes the file name to the file system.

3. Write operation:

This operation is used to write the information into a file. A system call write is issued that specifies the name of the file and the length of the data has to be written to the file. Whenever the file length is increased by specified value and the file pointer is repositioned after the last byte written.

4. Read operation:

This operation reads the contents from a file. A Read pointer is maintained by the OS, pointing to the position up to which the data has been read.

 

5. Re-position or Seek operation:

The seek system call re-positions the file pointers from the current position to a specific place in the file i.e. forward or backward depending upon the user's requirement. This operation is generally performed with those file management systems that support direct access files.

6. Delete operation:

Deleting the file will not only delete all the data stored inside the file it is also used so that disk space occupied by it is freed. In order to delete the specified file the directory is searched. When the directory entry is located, all the associated file space and the directory entry is released.

7. Truncate operation:

Truncating is simply deleting the file except deleting attributes. The file is not completely deleted although the information stored inside the file gets replaced.

8. Close operation:

When the processing of the file is complete, it should be closed so that all the changes made permanent and all the resources occupied should be released. On closing it deallocates all the internal descriptors that were created when the file was opened.

9. Append operation:

This operation adds data to the end of the file.

10. Rename operation:

This operation is used to rename the existing file.

File Allocation Methods

There are various methods which can be used to allocate disk space to the files. Selection of an appropriate allocation method will significantly affect the performance and efficiency of the system. Allocation method provides a way in which the disk will be utilized and the files will be accessed.

1. Contiguous Allocation.
2. Linked Allocation
3. FAT
4. I-node

Contiguous Allocation

If the blocks are allocated to the file in such a way that all the logical blocks of the file get the contiguous physical block in the hard disk then such allocation scheme is known as contiguous allocation.In the image shown below, there are three files in the directory. The starting block and the length of each file are mentioned in the table. We can check in the table that the contiguous blocks are assigned to each file as per its need.

 

Advantages	Disadvantages
It is simple to implement. We will get Excellent read performance. Supports Random Access into files.	The disk will become fragmented. It may be difficult to have a file grow.

 

Linked List Allocation

Linked List allocation solves all problems of contiguous allocation. In linked list allocation, each file is considered as the linked list of disk blocks. However, the disks blocks allocated to a particular file need not to be contiguous on the disk. Each disk block allocated to a file contains a pointer which points to the next disk block allocated to the same file.

Advantages	Disadvantages
There is no external fragmentation with linked allocation. Any free block can be utilized in order to satisfy the file block requests. File can continue to grow as long as the free blocks are available. Directory entry will only contain the starting block address.	Random Access is not provided. Pointers require some space in the disk blocks. Any of the pointers in the linked list must not be broken otherwise the file will get corrupted. Need to traverse each block

 

File Allocation Table

The main disadvantage of linked list allocation is that the Random access to a particular block is not provided. In order to access a block, we need to access all its previous blocks. File Allocation Table overcomes this drawback of linked list allocation. In this scheme, a file allocation table is maintained, which gathers all the disk block links. The table has one entry for each disk block and is indexed by block number. File allocation table needs to be cached in order to reduce the number of head seeks. Now the head doesn't need to traverse all the disk blocks in order to access one successive block. It simply accesses the file allocation table, read the desired block entry from there and access that block. This is the way by which the random access is accomplished by using FAT. It is used by MS-DOS and pre-NT Windows versions.

Advantages	Disadvantages
Uses the whole disk block for data. A bad disk block doesn't cause all successive blocks lost. Random access is provided although its not too fast. Only FAT needs to be traversed in each file operation.	Each Disk block needs a FAT entry. FAT size may be very big depending upon the number of FAT entries. Number of FAT entries can be reduced by increasing the block size but it will also increase Internal Fragmentation.

Indexed Allocation Scheme

Instead of maintaining a file allocation table of all the disk pointers, Indexed allocation scheme stores all the disk pointers in one of the blocks called as indexed block. Indexed block doesn't hold the file data, but it holds the pointers to all the disk blocks allocated to that particular file. Directory entry will only contain the index block address.

Advantages	Disadvantages
Supports direct access A bad data block causes the lost of only that block.	A bad index block could cause the lost of entire file. Size of a file depends upon the number of pointers, a index block can hold. Having an index block for a small file is totally wastage. More pointer overhead

 

Device Management

Device management in an operating system means controlling the Input/Output devices like disk, microphone, keyboard, printer, magnetic tape, USB ports, camcorder, scanner, other accessories, and supporting units like supporting units control channels. A process may require various resources, including main memory, file access, and access to disk drives, and others. If resources are available, they could be allocated, and control returned to the CPU. Otherwise, the procedure would have to be postponed until adequate resources become available. The system has multiple devices, and in order to handle these physical or virtual devices, the operating system requires a separate program known as an ad device controller. It also determines whether the requested device is available.

The fundamentals of I/O devices may be divided into three categories:

1. Boot Device
2. Character Device
3. Network Device

Boot Device

It stores data in fixed-size blocks, each with its unique address. For example- Disks.

Character Device

It transmits or accepts a stream of characters, none of which can be addressed individually. For instance, keyboards, printers, etc.

Network Device

It is used for transmitting the data packets.

Functions of the device management in the operating system

The operating system (OS) handles communication with the devices via their drivers. The OS component gives a uniform interface for accessing devices with various physical features. There are various functions of device management in the operating system. Some of them are as follows:

1. It keeps track of data, status, location, uses, etc. The file system is a term used to define a group of facilities.
2. It enforces the pre-determined policies and decides which process receives the device when and for how long.
3. It improves the performance of specific devices.
4. It monitors the status of every device, including printers, storage drivers, and other devices.
5. It allocates and  de-allocates the device.

Types of devices

There are three types of Operating system peripheral devices: dedicated, shared, and virtual. These are as follows:

1. Dedicated Device

In device management, some devices are allocated or assigned to only one task at a time until that job releases them. Devices such as plotters, printers, tape drivers, and other similar devices necessitate such an allocation mechanism because it will be inconvenient if multiple people share them simultaneously. The disadvantage of such devices is the inefficiency caused by allocating the device to a single user for the whole duration of task execution, even if the device is not used 100% of the time.

2. Shared Devices

These devices could be assigned to a variety of processes. By interleaving their requests, disk-DASD could be shared by multiple processes simultaneously. The Device Manager carefully controls the interleaving, and pre-determined policies must resolve all difficulties.

3. Virtual Devices

Virtual devices are a hybrid of the two devices, and they are dedicated devices that have been transformed into shared devices. For example, a printer can be transformed into a shareable device by using a spooling program that redirects all print requests to a disk. A print job is not sent directly to the printer; however, it is routed to the disk until it is fully prepared with all of the required sequences and formatting, at which point it is transmitted to the printers. The approach can transform a single printer into numerous virtual printers, improving performance and ease of use.

Features of Device Management

Here, you will learn the features of device management in the operating system. Various features of the device management are as follows:

1. The OS interacts with the device controllers via the device drivers while allocating the device to the multiple processes executing on the system.
2. Device drivers can also be thought of as system software programs that bridge processes and device controllers.
3. The device management function's other key job is to implement the API.
4. Device drivers are software programs that allow an operating system to control the operation of numerous devices effectively.
5. The device controller used in device management operations mainly contains three registers: command, status, and data.

Pipe

A pipe is a mechanism by which the output of one process is directed into the input of another process. Thus it provides one way flow of data between two related processes. Pipe is a used to transmit data from one process to another process. Pipeline is a connection between series of process to transmit data(pipe).pipe() is a system call used to generate InterProcessCommunication(IPC).

Processes in Linux can communicate with each other using a form of message passing. It is possible to create a channel between two processes into which one process can write a stream of bytes for the other to read. These channels are called pipes. Shell pipelines are implemented with pipes.

There are two types of pipes: named and unnamed. Only related processes can share unnamed pipes, while either related or unrelated processes can share named pipes.

Buffer

The buffer is an area in the main memory used to store or hold the data temporarily. In other words, buffer temporarily stores data transmitted from one place to another, either between two devices or an application. The act of storing data temporarily in the buffer is called buffering.

 

 

Shared Memory

shared memory is a method by which program processes can exchange data more quickly than by reading and writing using the regular operating system services.

Shared memory is a faster inter process communication system. It allows cooperating processes to access the same pieces of data concurrently. It speeds up the computation power of the system and divides long tasks into smaller sub-tasks and can be executed in parallel. Modularity is achieved in a shared memory system.

The two basic types of shared memory architectures are Uniform Memory Access (UMA) and Non-Uniform Memory Access (NUMA)

Advantage: comparatively Very fast than distributed memory.

Disadvantages: Requires careful locking to avoid trouble.(data loss or data mismatch)

Security Policy Mechanism

Protection

Authentication and Internal Authorization

 Important Questions

1 marks

1.-------------------------------- is called as dividing main Memory into small chunks [cookies / memory partition /memory schedule / process management]

2.Logical address is generated by ------------------- [LU / ALU/ CPU /MU]

3. ------------------------------- is also called as virtual address. [RAM/ROM/Physical Address/Logical Address]

4.We cannot have two files with the same name. – state true or false

5. Relocation is an important feature of Memory allocation - True / False

2 marks

1. memory allocation strategies

2. memory access types

3. pipe mechanism

4. the importance about Contiguous allocation of file allocation methods.

5. the importance of Relocation in memory management.

15 marks 

 1. Memory Management with neat diagram

2. All types of File allocation methods with neat diagrams