Operating System Tutorial

Operating System Tutorial Types of Operating System Evolution of Operating System Functions of Operating System Operating System Properties Operating System Services Components of Operating System Needs of the Operating System

Operating Systems

Linux Operating System Unix Operating System Ubuntu Operating System Chrome Operating Systems Fedora Operating System MAC Operating System MS Windows Operating System Solaris Operating System Cooperative Operating System CorelDRAW Operating System CentOS FreeBSD Operating Systems Batch Operating System MS-DOS Operating System Commercial Mobile Operating Systems

Differences

Difference Between Multi-programming and Multitasking Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK Difference between Process and Program in the Operating System Difference between Protection and Security in Operating System

How To

How to implement Monitors using Semaphores How to Install a Different Operating System on a PC

Questions

What is Kernel and Types of Kernel What is DOS Operating System What is Thread and Types of Thread What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock What is Paging and Segmentation What is Demand Paging What is Virtual Memory What is a Long term Scheduler What is Page Replacement in Operating System What is BSR Mode What is Convoy Effect What is Job Sequencing in Operating System Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Why is there a Need for an Operating System

Misc

Process Management Process State Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System N-Step-SCAN Disk Scheduling Feedback Queue in Operating System Contiguous Memory Allocation in Operating System Real-time Operating System Starvation in Operating System Thrashing in Operating System 5 Goals of Operating System Advantages of Operating System Advantages of UNIX Operating System Bit Vector in Operating System Booting Process in Operating System Can a Computer Run Without the Operating System Dining Philosophers Problem in Operating System Free Space Management in Operating System Inter Process Communication in Operating System Swapping in Operating System Memory Management in Operating System Multiprogramming Operating System Multitasking Operating Systems Multi-user Operating Systems Non-Contiguous Memory Allocation in Operating System Page Table in Operating System Process Scheduling in Operating System Segmentation in Operating System Simple Structure in Operating System Single-User Operating System Two Phase Locking Protocol Advantages and Disadvantages of Operating System Arithmetic operations in binary number system Assemblers in the operating system Bakery Algorithm in Operating System Benefits of Ubuntu Operating System CPU Scheduling Criteria in Operating System Critical Section in Operating System Device Management in Operating System Linux Scheduler in Operating System Long Term Scheduler in Operating System Mutex in Operating System Operating System Failure Peterson's Solution in Operating System Privileged and Non-Privileged Instructions in Operating System Swapping in Operating System Types of Operating System Zombie and Orphan Process in Operating System 62-bit operating system Advantages and Disadvantages of Batch Operating System Boot Block and Bad Block in Operating System Contiguous and Non - Contiguous Memory Allocation in Operating System Control and Distribution Systems in Operations Management Control Program in Operating System Convergent Technologies in Operating System Convoy Effect in Operating System Copy Operating Systems to SSD Core Components of Operating System Core of UNIX Operating System Correct Value to return to the Operating System Corrupted Operating System Cos is Smart Card Operating System Cosmos Operating Systems Examples Generation of Operating System Hardware Solution in Operating System Process Control Block in Operating System Function of Kernel in Operating System Operating System Layers History of Debian Operating Systems Branches and Architecture of Debian Operating Systems Features and Packages of Debian Operating Systems Installation of Operating System on a New PC Organizational Structure and Development in Debian Operating Systems User Interface in Operating System Types Of Memory in OS Operating System in Nokia Multilevel Paging in OS Memory Mapping Techniques in OS Memory Layout of a Process in Operating System Hardware Protection in Operating System Functions of File Management in Operating System Core of Linux Operating System Cache Replacement Policy in Operating System Cache Line and Cache Size in Operating System What is Memory Mapping? Difference Between Network Operating System And Distributed Operating System What is the difference between a Hard link and a Soft Link? Principles of Preemptive Scheduling Process Scheduling Algorithms What is NOS? What is the Interrupt I/O Process? What is Time Sharing OS What is process termination? What is Time-Sharing Operating System

Non-Contiguous Memory Allocation in Operating System

Memory is nothing but a storage space where various data are stored. We can store data in temporary and permanent memory as per our future requirements for data. We can also keep our data safe by storing them in memory. Allocation of memory simply means providing an individual space for individual data or files. For example, if F is a file, the system will allot a certain address at which this F-named file will be stored in the system's memory.

Memory Management Strategies

1) Non-Contiguous Memory Allocation

  1. Paging
  2. Multilevel Paging
  3. Inverted Paging
  4. Segmented Paging
  5. Segmentation

2) Contiguous Memory Allocation

a. Fixed Partition

b.Variable/Dynamic Partition

Non-Contiguous Memory Allocation in Operating System

Non-contiguous memory allocation

Non-contiguous memory allocation is one of the most important strategies for memory management in operating systems. As the name suggests, it stores the data in a discontinuous pattern. In this method, the allocation of memory is not contiguous, which means the allocation of memory for any file or track happens randomly. The memory is not branched into fixed parts and, the allocation of memory depends on the size of the file and the available space in the memory.

The file is stored wherever there is an unoccupied or empty space inside the memory. The wastage of memory becomes very less due to the random allocation of memory.

Let us see an example: if a process contains 3 blocks named Yi, Yii, and Yiii, the system will allocate/ provide a  non-contiguous or random address to the entire block of that process in the RAM. It is not mandatory to allocate Yi next to Yii and Yii next to Yiii if neighbor memory addresses are not available in the system. It takes slightly more time to access different blocks of a process due to the random allocation of the blocks. It uses a pointer to store the address, and it also requires an index.

Advantages of Non-Contiguous Memory Allocation:

There are certain advantages of using the non-contiguous strategy of memory allocation:

  1. It can help to reduce external fragmentation, as blocks of memory can be allocated and freed in any order rather than only being able to be freed in the reverse order in which they were allocated, as is the case with contiguous memory allocation.
  2. It allows for more flexible memory management, as blocks of memory can be allocated and freed independently of one another.
  3. It can be more systematic in terms of memory usage, as it allows the operating system to allocate memory more efficiently by using all available blocks of memory rather than leaving gaps between allocated blocks.
  4. It allows the operating system to allocate memory more dynamically. It can allocate free blocks of memory as needed rather than pre-allocating a large block of contiguous memory.
  5. It can be used to improve the execution of the operating system by reducing the time required to allocate and free memory, as blocks of memory can be allocated and freed more quickly than with contiguous memory allocation.

Disadvantages of Non-Contiguous Memory Allocation

There are a few disadvantages of using non-contiguous memory allocation in Operating system:

  1. It is more difficult to implement and manage than contiguous memory allocation, as the blocks of memory are scattered throughout the address space.
  2. It can lead to internal fragmentation, where there are many small blocks of free memory scattered throughout the address space that cannot be used to satisfy a request for a larger block of memory.
  3. It can lead to external fragmentation, where there are large blocks of free memory available, but they are not contiguous, so they cannot be used to satisfy a request for a larger block of memory.
  4. It can result in reduced performance, as the operating system must search for a suitable block of memory to satisfy a request, which can take longer than contiguous memory allocation.
  5. It can make it more difficult to share memory between processes, as the blocks of memory are not contiguous.
  6. It can make it more difficult to access data stored in non-contiguous blocks of memory, as the processor may need to perform multiple memory accesses to retrieve the data.

Working of Non-Contiguous Memory Allocation

In non-contiguous memory allocation, blocks of memory are scattered throughout the address space rather than being contiguous. When a memory request is made, the operating system searches for a suitable block of memory to satisfy the request.

To manage non-contiguous memory allocation, the operating system typically maintains a data structure called a "free list" or "free pool" that keeps track of all the available blocks of free memory. When a memory request is made, the operating system searches the free list for a suitable block of memory. If a suitable block is found, it is allocated to the requesting process and removed from the free list. If no suitable block is found, the operating system may need to perform additional memory management tasks, such as swapping blocks of memory to and from disk or requesting more memory from the system.

Once a block of memory has been allocated to a process, it can be used by the process to store data or program code. When the process no longer needs the memory, it can be returned to the free list by the operating system to be reused for future memory requests.

Types of Non-Contiguous Memory Allocation:

The non-contiguous memory allocation method is further classified into five different categories, which are mentioned below:-

1. Paging

Paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "pages" and mapping each page to a physical page of memory.

In a paging system, the operating system maintains a data structure called a "page table" that maps each page to a physical page of memory. When a process accesses a virtual address, the operating system translates the virtual address to a physical address using the page table. This allows the operating system to quickly translate virtual addresses to physical addresses, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

Paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory that are scattered throughout the address space in a more organized and efficient manner. It can also be used in concurrence with other memory management techniques, such as demand paging and multilevel paging, to improve the performance of the operating system.

2. Multilevel paging

Multilevel paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "pages" and "page tables".

In a traditional paging system, the virtual address space is divided into pages. The operating system maintains a page table that maps each page to a physical memory page. This allows the operating system to quickly transcribe a virtual memory or address to a physical address, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a multilevel paging system, the virtual address space is divided into pages and page tables. The operating system maintains a page table for each page table, and each page table maps a set of pages to physical pages of memory. This allows the operating system to translate a virtual address to a physical address using multiple levels of page tables, rather than a single, large page table.

This can be more efficient if the process has a large number of pages, as it requires a smaller page table and may result in fewer cache misses when accessing the page table. Multilevel paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to locate blocks scattered throughout the address space quickly. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.

3.  Inverted paging

Inverted paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by maintaining a data structure called an "inverted page table" that maps virtual addresses to physical addresses.

In a traditional page table, the entries in the table are indexed by the virtual addresses of the pages and contain the corresponding physical addresses. This allows the operating system to translate a virtual address to a physical address quickly, but it requires a separate entry in the table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In an inverted page table, the entries are indexed by the physical addresses of the pages and contain the corresponding virtual addresses. This allows the operating system to translate a physical address to a virtual address quickly, but it requires a separate entry in the table for each physical page of memory. This can be more efficient if the process has a large number of pages, as it requires a smaller page table and may result in fewer cache misses when accessing the page table.

Inverted paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to locate blocks scattered throughout the address space quickly. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.

4. Segmentation

Segmentation is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "segments" and "pages".

In a traditional paging system, the virtual address space is divided into pages. The operating system maintains a page table that maps each page to a physical memory page. This allows the operating system to translate a virtual address to a physical address quickly, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a segmentation system, the virtual address space is divided into segments. Each segment is a contiguous block of virtual addresses representing a logical grouping of related memory, such as code, data, or stack. The operating system maintains a data structure called a "segment table" that maps each segment to a physical memory block. This allows the operating system to translate a virtual address to a physical address using the segment table rather than a page table.

Segmentation can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory that are scattered throughout the address space in a more organized and efficient manner. It can also be used in concurrence with other memory management techniques, such as paging, to improve the performance of the operating system.

5. Segmented paging

Segmented paging is a technique used in non-contiguous memory allocation to improve the performance of the operating system. It works by dividing the virtual address space of a process into smaller units called "segments" and "pages".

In a traditional paging system, the virtual address space is divided into pages, and the operating system maintains a page table that maps each page to a physical page of memory. This allows the operating system to quickly transcribes a virtual memory or address to a physical address, but it requires a separate entry in the page table for each page of memory. This can be inefficient if the process has a large number of pages, as it requires a large page table and may result in a lot of cache misses when accessing the page table.

In a segmented paging system, the virtual address space is divided into segments and pages. Each segment is a contiguous block of virtual addresses representing a logical grouping of related memory, such as code, data, or stack. The operating system maintains a page table for each segment, and each page table maps a set of pages to physical pages of memory. This allows the operating system to translate a virtual address to a physical address using multiple levels of page tables, rather than a single, large page table.

Segmented paging can be particularly useful in non-contiguous memory allocation, as it allows the operating system to manage blocks of memory scattered throughout the address space more efficiently. It can also be used in concurrence with other memory management techniques, such as demand paging, to improve the production of the operating system.