Basics of CPU Scheduling

Preemptive scheduling: In preemptive scheduling, processes can exit the CPU when they complete their tasks, require I/O, or if their allotted time quantum runs out. 

Non-preemptive scheduling: In non-preemptive scheduling, a process remains on the CPU until it either completes its execution or requires I/O operations. There is no time quantum involved, as the process is not interrupted by the scheduler before it finishes or voluntarily gives up control.

Starvation, CPU utilization, and overhead: In non-preemptive scheduling, starvation can be high because there is no time quantum, so a process running for an extended period (e.g., 20-30 minutes) can block other processes from getting CPU time. In preemptive scheduling, CPU utilization is higher because the CPU frequently switches between processes, allowing more processes to get executed. However, preemptive scheduling involves more overhead, as frequent context switches occur, especially if the time quantum is very short (e.g., 1 second), causing processes to switch often.

Goals of CPU scheduling

  • Maximum CPU Utilization: The scheduling algorithm should keep the CPU as busy as possible, ensuring that it spends minimal time idle. 
  • Minimum Turnaround Time: Turnaround time is the total time taken from when a process enters the Ready queue until it completes its execution. The goal is to minimize this time, so processes are completed quickly. For example, 
  1. P1 enters the Ready queue: 10:00 AM. 
  2. P1 first gets the CPU: 10:05 AM (after waiting 5 minutes). 
  3. P1 goes to perform I/O: Let’s assume it does some processing between 10:05 AM and 10:07 AM before going for I/O. 
  4. P1 comes back to the Ready queue: 10:10 AM. 
  5. P1 gets the CPU again: 10:12 AM (after waiting 2 more minutes). 
  6. P1 completes execution: Let’s assume it finishes execution at 10:15 AM. 
Turnaround Time Calculation: Turnaround Time = Time of completion - Time of first entry into the Ready queue. Turnaround Time = 10:15 AM - 10:00 AM = 15 minutes.

  • Minimum Waiting Time: Waiting time is the amount of time a process spends in the Ready queue waiting for CPU access. Minimizing waiting time ensures that processes spend less time idle in the queue, especially after returning from I/O operations. According to the above example the Total Waiting Time: 5 minutes (first wait) + 2 minutes (second wait) = 7 minutes. 
  • Minimum Response Time: Response time is the time taken from when a process first enters the Ready queue to the first time it gets CPU access. Minimizing response time is crucial for interactive processes, as it makes the system more responsive to user inputs. According to the above example, the response time is 5 minutes.
  • Maximum Throughput: Throughput refers to the number of processes that are completed per unit of time. A good scheduling algorithm aims to maximize throughput, meaning more processes are finished in a given period.
Basic terminologies
  • Burst time: It is the total amount of time a process requires to execute on the CPU without any interruptions. It represents the actual time the process spends using the CPU to perform its computations. According to the above example, the burst time: 2 minutes (from 10:05 AM to 10:07 AM) + 3 minutes (from 10:12 AM to 10:15 AM) = 5 minutes
  • Arrival time: It is the exact moment when a process enters the system and is placed in the Ready queue for the first time. It represents the time when the process is ready to start competing for CPU time. According to the above example, the burst time is 10:00 AM.
  • Completion time (or finish time): It is the moment when a process has finished its execution on the CPU and has exited the system. According to the above example, Completion Time for P1 = 10:15 AM.



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