Latest types of Scheduling

Multi-level queue scheduling: Ready Queue is divided into separate queues for each class of processes. Let us take three different types of processes System processes, Interactive processes, and Batch Processes. All three processes have their own queue. The Description of the processes in the above diagram is as follows:

  • System Processes: The CPU itself has its own process to run which is generally termed a System Process.
  • Interactive Processes: An Interactive Process is a type of process in which there should be the same type of interaction.
  • Batch Processes: Batch processing is generally a technique in the Operating system that collects the programs and data together in the form of a batch before the processing starts.

                                         

The scheduling algorithm can be customized to meet the specific requirements of different types of processes. Different scheduling algorithms can be used for each queue, depending on the requirements of the processes in that queue.  For example, queue 1 and queue 2 use Round Robin while queue 3 can use FCFS to schedule their processes.  Each queue has absolute priority over the lower-priority queue. Let us consider the following priority order queue 1 > queue 2 > queue 3. According to this algorithm, no process in the batch queue (queue 3) can run unless queues 1 and 2 are empty. If any batch process (queue 3) is running and any system (queue 1) or Interactive process (queue 2) enters the ready queue the batch process is preempted. Some processes may starve for CPU if some higher priority queues are never becoming empty. Hence, it falls prey to the convoy effect.

Multi-level feedback queue scheduling: It is like Multilevel Queue(MLQ) Scheduling but in this process can move between the queues. Processes can move between queues based on their CPU burst characteristics. For example, a process that uses too much CPU time might be moved to a lower-priority queue, while a process that uses less CPU time might be moved to a higher-priority queue. 

  • Let's consider a scenario where three processes, P1, P2, and P3, start in different queues based on their initial characteristics:
  1. P1 (Video Rendering Task): This process is CPU-intensive, meaning it requires a lot of processing power for a continuous period.
  2. P2 (Text Editor): This process is interactive, requiring quick responses to user inputs, but it doesn’t use much CPU time.
  3. P3 (Background System Scan): This process runs in the background and is less urgent, requiring occasional CPU time.
  • Queue Setup:
  1. Queue 1 (High Priority): Time slice = 5ms.
  2. Queue 2 (Medium Priority): Time slice = 10ms.
  3. Queue 3 (Low Priority): Time slice = 20ms.
  • Initial Assignment:
  1. P1 starts in Queue 2 because it’s a CPU-intensive task but doesn’t need immediate, high-priority CPU access.
  2. P2 starts in Queue 1 because it’s an interactive application that requires quick responses.
  3. P3 starts in Queue 3 as it’s a background task that can be delayed without affecting the user experience.
  • Dynamic Movement Between Queues:

  1. P1 (Video Rendering Task): Initial Behavior: P1 starts in Queue 2 and uses up its 10ms time slice continuously. Since it’s CPU-intensive and doesn’t yield the CPU frequently, it’s demoted to Queue 3 (the low-priority queue) where it will get longer time slices but at a lower priority.
  2. P2 (Text Editor): Initial Behavior: P2 starts in Queue 1 with a 5ms time slice. It frequently yields the CPU because it’s waiting for user input (like typing). The OS recognizes that P2 doesn’t consume much CPU time, so it stays in Queue 1 or might even be given a higher priority within the same queue to ensure it remains highly responsive.
  3. P3 (Background System Scan): Initial Behavior: P3 starts in Queue 3 and occasionally uses its 20ms time slice. Since it’s a background task, it stays in Queue 3 unless it suddenly requires more CPU time, which might cause it to be demoted further (if there were more queues) or stay in the same queue.

  • Explanation of Queue Movement:

  1. Promotion: If P2 (the text editor) continues to use less CPU time by frequently yielding (waiting for user input), it might remain in Queue 1 or even be prioritized within that queue to ensure that it remains responsive. This is because the OS recognizes that it’s efficiently using its CPU time and needs to remain interactive.
  2. Demotion: P1 (the video rendering task), which is CPU-intensive, is demoted to Queue 3 because it continuously uses large amounts of CPU time without yielding. The OS moves it to a lower-priority queue to give more responsive tasks like P2 higher-priority access to the CPU.
  • Aging is used to prevent issues like starvation and the convoy effect, especially when processes are demoted to lower-priority queues. 








Comments

Post a Comment

Popular posts from this blog

Indexed allocation

Image
  Indexed allocation is a file allocation method used by operating systems to manage how files are stored on disk. The core idea is simple but powerful: instead of storing a file in contiguous blocks or linking blocks one-by-one, the system uses a special index block that contains a list of all the disk block addresses where the file’s data is stored. This removes many limitations of earlier methods like contiguous and linked allocation. In indexed allocation, each file has its own index block . This index block acts like a table of contents. Every entry inside it points to a data block that belongs to that file. When a file is created, the OS allocates an index block and then fills it with pointers to the actual data blocks as the file grows. These data blocks can be located anywhere on the disk , so the file does not need contiguous space. This makes storage much more flexible and avoids external fragmentation. When the system needs to access a particular part of a file, it fir...
Read more

Thrashing

Image
Thrashing occurs in a computer system when the operating system spends a significant amount of time swapping pages in and out of memory, rather than executing actual processes. This typically happens when the system's memory is overcommitted, meaning there are too many processes competing for too little physical memory, leading to frequent page faults. How Memory is Used 1. Initial State: App1 is running, and its two pages are loaded into memory: Frame 1: App1, Page 1 Frame 2: App1, Page 2 Frame 3 and 4 are free. App3's pages are present in swap memory. 2. Switch to App2: Now, you switch to App2, which also requires 2 pages: Frame 3: App2, Page 1 Frame 4: App2, Page 2 Memory is now full with both App1 and App2’s pages. App3's pages are present in swap memory. 3. Switch to App3: You decide to switch to App3, which needs 2 pages as well. Since the memory is full, the system needs to make room: App1’s pages are moved to swap memory: Swap Memory: [App1, Page 1] [App1, Page 2] F...
Read more

Basics of paging

Image
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus helps in handling fragmentation. It involves breaking down memory into fixed-size blocks called pages and frames. The OS typically decides the page size when the system is configured or during the OS design phase. This page size is constant for the entire system and is determined based on considerations such as hardware architecture, efficiency, and the type of applications running. Common page sizes are 4 KB, 8 KB, or 16 KB. Here's a simple explanation with an example: Basic Concepts Page: A fixed-size block of logical memory (virtual memory) used by a process. Frame: A fixed-size block of physical memory (RAM) where a page is mapped. Page Table: A data structure used by the operating system to keep track of the mapping between pages and frames. The Page Table Base Register (PTBR) is a special register in the CPU that holds the starting address of the page table for ...
Read more