SBI Specialist Officer Exam 2024 General IT Knowledge PDF

Specialist Officer Exam 2024 GENERAL IT KNOWLEDGE Infra Support Part 1: Basics of OS For Notes & Test Series www.piyushwairale.com  Piyush Wairale MTech, IIT Madras Course Instructor at IIT Madras BS Degree SBI SO Test Series 2024 Gen...

Specialist Officer Exam 2024 GENERAL IT KNOWLEDGE Infra Support Part 1: Basics of OS For Notes & Test Series www.piyushwairale.com  Piyush Wairale MTech, IIT Madras Course Instructor at IIT Madras BS Degree SBI SO Test Series 2024 General IT Knowledge Tests Price: Rs.400 Get at Rs.200, use code SBI100 to get Rs.200 Off (Offer Valid for Limited Seats) Click here to register for Test Series Preparing for GATE DA 2025??? www.piyushwairale.com  Infra Support : Part 1 by Piyush Wairale Instructions: Kindly go through the lectures/videos on our website www.piyushwairale.com Read this study material carefully and make your own handwritten short notes. (Short notes must not be more than 5-6 pages) Attempt the mock tests available on portal. Revise this material at least 5 times and once you have prepared your short notes, then revise your short notes twice a week If you are not able to understand any topic or required a detailed explanation and if there are any typos or mistake in study materials. Mail me at [email protected] 1 Contents 1 Basics of Operating System 5 1.1 Definition of Operating System....................................... 5 1.2 Functions of Operating System....................................... 5 1.3 Types of Operating Systems......................................... 5 1.4 Examples of Popular Operating Systems.................................. 6 2 System Calls 6 2.1 Process Control................................................ 6 2.2 File Management............................................... 6 2.3 Device Management............................................. 6 2.4 Information Maintenance.......................................... 7 2.5 Communication................................................ 7 3 Processes 8 3.1 PROCESS STATE TRANSITIONS.................................... 8 3.2 Threads.................................................... 10 3.2.1 Structure of a Thread........................................ 10 3.2.2 Advantages of Threads........................................ 10 3.2.3 Thread Management......................................... 10 3.3 Differences Between Processes and Threads................................ 10 4 Inter-Process Communication (IPC) 11 5 Concurrency 12 6 Synchronization 12 7 Deadlock 13 8 Memory Management 15 9 Virtual Memory 16 10 Types of Memory 17 10.1 Cache Memory................................................ 17 10.2 Main Memory................................................. 17 10.3 Secondary Storage.............................................. 18 10.4 Comparison of Memory Types........................................ 18 11 Paging 19 11.1 Page Replacement Algorithms........................................ 19 11.2 FIFO (First-In, First-Out).......................................... 19 11.3 Optimal Page Replacement......................................... 19 11.4 LRU (Least Recently Used)......................................... 20 11.5 Most Recently Used (MRU)......................................... 20 12 CPU Scheduling Algorithms 21 12.1 Scheduling Criteria.............................................. 21 12.2 Scheduling Algorithms............................................ 21 12.2.1 First-Come, First-Served (FCFS).................................. 21 12.2.2 Shortest Job First (SJF)....................................... 21 12.2.3 Shortest Remaining Time First (SRTF).............................. 21 12.2.4 Round Robin (RR).......................................... 22 12.2.5 Priority Scheduling.......................................... 22 12.3 Comparison of Scheduling Algorithms................................... 22 2 13 I/O Scheduling Algorithms 23 13.1 Algorithms.................................................. 24 13.1.1 First-Come, First-Served (FCFS).................................. 24 13.1.2 Shortest Seek Time First (SSTF).................................. 24 13.1.3 SCAN (Elevator Algorithm)..................................... 24 13.1.4 LOOK................................................. 24 13.1.5 Circular SCAN (C-SCAN)...................................... 24 13.1.6 Circular LOOK (C-LOOK)..................................... 25 13.1.7 RSS (Random Scheduling)..................................... 25 13.1.8 LIFO (Last-In First-Out)...................................... 25 13.1.9 N-STEP SCAN............................................ 25 13.1.10 F-SCAN............................................... 25 13.2 Comparison of I/O Scheduling Algorithms................................. 25 LinkedIn Youtube Channel Instagram Telegram Group Facebook Download Andriod App 1 Basics of Operating System An operating system (OS) is system software that manages computer hardware and software resources and provides services for computer programs. The operating system acts as an intermediary between users and the computer hardware. Some of the fundamental concepts related to operating systems are described below: 1.1 Definition of Operating System An Operating System (OS) is a software that: Manages computer hardware. Provides a user interface and environment for application programs to run. Controls and coordinates the use of the hardware among various application programs for various users. 1.2 Functions of Operating System The primary functions of an operating system include: Process Management: The OS manages processes in a system, including process scheduling, creation, and termination. It ensures that processes can share resources and efficiently transition between states. Memory Management: The OS handles memory allocation and deallocation for processes, ensuring that the memory is efficiently utilized and processes do not interfere with each other. File System Management: The OS manages files on disk, providing functions like creating, deleting, reading, writing, and organizing files into directories. Device Management: The OS controls peripheral devices such as printers, scanners, and hard drives, ensuring smooth communication between devices and the system. Security and Protection: The OS enforces access control to ensure that unauthorized users or processes do not access sensitive data or resources. User Interface: The OS provides a user interface, either Command-Line Interface (CLI) or Graphical User Interface (GUI), to allow users to interact with the system. 1.3 Types of Operating Systems There are several types of operating systems, each designed to meet specific needs: Batch Operating System: In this type, similar jobs are batched together and executed one after another. Users interact with the system indirectly. Time-Sharing Operating System: Multiple users can access the system simultaneously, with each user getting a share of the CPU time. Distributed Operating System: Multiple computers are used to perform tasks across different machines. They appear as a single coherent system to users. Real-Time Operating System (RTOS): These systems are designed for real-time applications that require precise timing and synchronization (e.g., in embedded systems). Embedded Operating System: A lightweight OS designed to operate in embedded systems like sensors, cameras, and IoT devices. 1.4 Examples of Popular Operating Systems Some of the widely-used operating systems include: Microsoft Windows: A proprietary OS developed by Microsoft, known for its graphical interface. Linux: An open-source OS that is widely used for servers, desktops, and embedded systems. macOS: A Unix-based OS developed by Apple for its line of Mac computers. Android: A Linux-based mobile OS developed by Google for smartphones and tablets. 2 System Calls A system call is a mechanism that allows user-level processes to request services from the operating system’s kernel. System calls provide an essential interface between a process and the OS. Types of System Calls System calls are used by programs to interact with the operating system. They are the interface between a process and the operating system, allowing the execution of tasks such as process control, file management, and communication. Below is a detailed description of the main types of system calls: 2.1 Process Control These system calls are used to manage processes. Examples include: fork(): Used to create a new process by duplicating the calling process. The new process is a child process of the caller. exec(): Replaces the current process image with a new process image, effectively running a new program. exit(): Terminates the calling process and returns an exit status to the parent process. wait(): Makes the calling process wait until one of its child processes exits or a signal is received. 2.2 File Management These system calls handle files and directories. Examples include: open(): Opens a file for reading, writing, or both. read(): Reads data from a file. write(): Writes data to a file. close(): Closes an open file, releasing any resources associated with it. unlink(): Deletes a file from the filesystem. 2.3 Device Management These system calls are used to manage devices, such as printers or disks. Examples include: ioctl(): Allows device-specific input/output operations. It provides control over devices, such as setting parameters. read(): Reads data from a device. write(): Writes data to a device. 2.4 Information Maintenance These system calls retrieve or set system information. Examples include: getpid(): Returns the process ID of the calling process. alarm(): Schedules an alarm signal to be delivered to the process after a specified number of seconds. sleep(): Suspends the calling process for a specified number of seconds. 2.5 Communication These system calls facilitate inter-process communication. Examples include: pipe(): Creates a unidirectional communication channel between processes. shmget(): Allocates a shared memory segment for communication between processes. mmap(): Maps files or devices into memory, providing efficient file I/O. socket(): Creates a socket for network communication between processes. System Call Mechanism When a system call is invoked: 1. The process switches from user mode to kernel mode. 2. The OS kernel performs the requested service. 3. Control returns to the user process in user mode. Processes and Threads In computer science, processes and threads are fundamental concepts that are crucial for understanding multitasking and concurrent execution in operating systems. 3 Processes A process is an instance of a program in execution. It is an independent entity that contains its own memory space, data, and system resources. The operating system manages processes to ensure that they execute correctly and efficiently. Structure of a Process A process typically consists of: Program Code: The executable instructions. Process Stack: Contains temporary data such as function parameters, return addresses, and local variables. Data Section: Contains global variables and static variables. Heap: Dynamically allocated memory during process execution. Process Control Block (PCB): A data structure used by the operating system to store all information about a process, including process state, program counter, CPU registers, memory management information, and I/O status. Process States A process can exist in several states: New: The process is being created. Ready: The process is waiting to be assigned to a processor. Running: Instructions are being executed. Waiting (Blocked): The process is waiting for an event to occur (e.g., I/O completion). Terminated: The process has finished execution. 3.1 PROCESS STATE TRANSITIONS Process state transitions can be depicted by a diagram as shown in Figure. This shows the way a process typically changes its states during the course of its execution. We can summarize these steps as follows: When you start executing a program, i.e. create a process, the operating system puts it in the list of new processes as shown by (i) in the figure. The operating system at any time wants only a certain number of processes to be in the ready list to reduce competition. Therefore, the operating system introduces a process in a new list first, and depending upon the length of the ready queue, upgrades processes from new to the ready list. This is shown by the admit (ii) arrow in the figure. Some systems bypass this step and directly admit a created process to the ready list. When its turn comes, the operating system dispatches it to the running state by loading the CPU registers with values stored in the register save area. This is shown by the dispatch (iii) arrow in the figure. Each process is normally given certain time to run. This is known as time slice. This is done so that a process does not use the CPU indefinitely. When the time slice for a process is over, it is put in the ready state again, as it is not waiting for any external event. This is shown by (iv) arrow in the figure.  Before the time slice is over, if the process wants to perform some I/O operation denoted by the I/O request (v) in the diagram, a software interrupts results because of the I/O system call. At this juncture, the operating system makes this process blocked, and takes up the next ready process for dispatching. When the I/O for the original process is over, denoted by I/O completion (vi), the hardware generates an interrupt whereupon the operating system changes this process into a ready process. This is called a wake up operation denoted by (vi) in the figure. Now the process can again be dispatched when its turn arrives. The whole cycle is repeated until the process is terminated. Figure 1: www.vidyalankar.org Events Pertaining to a Process Process state transitions are caused by the occurrence of events in the system. A sample list of events is as follows: 1. Request event: Process makes a resource request 2. Allocation event: A requested resource is allocated. 3. I/O initiation event: Process wishes to start I/O. 4. I/O termination event: An I/O operation completes. 5. Timer interrupt: The system timer indicates end of a time interval. 6. Process creation event: A new process is created. 7. Process termination event: A process finishes its execution. 8. Message arrival event: An interprocess message is received. An event may be internal to a running process, or it may be external to it. For example, a request event is internal to the running process, whereas the allocation, I/O termination and timer interrupt events are external to it. When an internal event occurs, the change of state, if any, concerns the running process. When an external event occurs, OS must determine the process affected by the event and mark an appropriate change of state. Process Management The operating system is responsible for process management, which includes: Process Scheduling: Determining the order in which processes will execute. Inter-process Communication (IPC): Mechanisms that allow processes to communicate and synchronize their actions. Deadlock Handling: Techniques to prevent or resolve deadlocks when multiple processes compete for limited resources. 3.2 Threads A thread is the smallest unit of processing that can be scheduled by an operating system. A thread is sometimes referred to as a lightweight process because it shares the same memory space with other threads in the same process. 3.2.1 Structure of a Thread Each thread has its own: Thread ID: A unique identifier for the thread. Program Counter: Keeps track of the next instruction to execute. Registers: Store the thread’s current working variables. Stack: Contains local variables and function calls. However, threads within the same process share the following: Heap Memory: Threads can communicate by reading and writing to the same heap. Global Variables: Shared among all threads of the same process. 3.2.2 Advantages of Threads Using threads offers several advantages: Lightweight: Threads are less resource-intensive than processes, leading to lower overhead. Fast Context Switching: Switching between threads is faster compared to switching between processes. Shared Resources: Threads within the same process can easily share data, making communication more efficient. 3.2.3 Thread Management Thread management involves: Creation and Termination: The operating system must manage the lifecycle of threads. Synchronization: Techniques like mutexes and semaphores are used to coordinate thread execution and access to shared resources. Scheduling: Similar to processes, threads are scheduled to run on available CPU cores. 3.3 Differences Between Processes and Threads The following table summarizes the key differences between processes and threads: Feature Process Thread Memory Space Separate memory space Shared memory space Overhead Higher overhead due to resource allocation Lower overhead due to shared resources Communication More complex IPC mechanisms Easier communication via shared memory Context Switching Slower context switching Faster context switching Multithreading Models Many-to-One: Many user-level threads mapped to one kernel thread. One-to-One: Each user-level thread maps to a kernel thread. Many-to-Many: Many user-level threads map to many kernel threads. 4 Inter-Process Communication (IPC) Inter-process communication is a mechanism that allows processes to communicate and synchronize their actions without sharing the same address space. Processes Frequently need to communicate with other processes. For example: In a shell pipeline, the output of the first process must be passed to the second process, and so on down the line. Thus there is a need for communication between processes, preferably in a well-structured way not using interrupts. Situations like, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions. The part of the program where the shared memory is accessed is called the critical section. Mutual exclusion: Some way of making sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing. Methods of IPC 1. Pipes: Unidirectional communication channels used for communication between related processes. 2. Named Pipes (FIFOs): Similar to pipes but can be used between unrelated processes. 3. Message Queues: Allow messages to be sent between processes in a FIFO manner. 4. Shared Memory: Multiple processes can access a common memory area. 5. Sockets: Endpoints for bidirectional communication over a network. 6. Signals: Notifications sent to a process to notify it of events. Concurrency and Synchronization 5 Concurrency Concurrency refers to the execution of multiple instruction sequences at the same time. Concurrency encompasses a host of design issues, including communication among processes, sharing of and competing for resources, synchronization of the activities of multiple processes and allocation of processor time to processes. Concurrency arises in 3 different contexts : 1. Multiple applications Multiprogramming was invented to allow processing time to be dynamically shared among a number of active applications. 2. Structured applications As an extension of the principles of modular design and structured programming, some applications can be effectively programmed as a set of concurrent processes. 3. Operating system structure The same structuring advantages apply to the system programmer and operating systems are implemented as a set of processes or threads 6 Synchronization Synchronization is the coordination of concurrent processes or threads to ensure correct execution and to prevent race conditions. With multiple active processes having potential access to shared address spaces or shared I/O resources, care must be taken to provide effective synchronization. Synchronization is a facility that enforces mutual exclusion and event ordering. A common synchronization mechanism used in multiprocessor OS is locks. Suppose two or more processes require access to a single sharable resource. During the course of execution, each process will be sending commands to the I/O device, receiving status information, sending data and receiving data. Such a resource is called critical resource and the portion of the program that uses it is called as critical section of the program. Mutual Exclusion does not allow any other process to get executed in their critical section, if a process is already executing in its critical section. Critical Section Problem A critical section is a section of code that accesses shared resources and must not be concurrently accessed by more than one thread. Requirements for a solution: – Mutual Exclusion – Progress – Bounded Waiting Synchronization Mechanisms 1. Mutex Locks: Provide mutual exclusion by allowing only one thread at a time to access the critical section. 2. Semaphores: Integer variables used to solve synchronization problems. Counting Semaphores Binary Semaphores  3. Monitors: High-level synchronization constructs that combine mutual exclusion and condition synchroniza- tion. 4. Condition Variables: Used with monitors to block and wake up threads. 7 Deadlock A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process. Necessary Conditions For a deadlock to occur, the following four conditions must hold simultaneously: 1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. 2. Hold and Wait: A process is holding at least one resource and is waiting to acquire additional resources. 3. No Preemption: Resources cannot be forcibly removed from processes. 4. Circular Wait: A circular chain of processes exists, where each process waits for a resource held by the next process. Deadlock Handling Strategies 1. Deadlock Prevention: Design the system to negate one of the necessary conditions. 2. Deadlock Avoidance: Dynamically examine resource-allocation state to ensure a circular wait condition cannot hold (e.g., Banker’s Algorithm). 3. Deadlock Detection and Recovery: Allow deadlocks to occur, detect them, and recover. 4. Ignoring Deadlock: Assume that deadlocks will never occur (used in most operating systems). Deadlock Prevention 1. Mutual Exclusion The mutual exclusion condition must hold for non-sharable types of resources. For example: Several processes cannot simultaneously share a printer. Sharable resources, on the other hand, do not require mutually exclusive access, and thus cannot be involved in a deadlock. Read-only files are a good example of a sharable resource. If several processes attempt to open a read-only file at the same time, they can be granted simultaneous access to the file. A process never needs to wait for a sharable resource. It is not possible to prevent deadlocks by denying the mutual-exclusion condition. 2. Hold and Wait In order to ensure that the hold-and-wait condition never holds in the system, one must guarantee that whenever a process request a resource it does not hold any other resources. One protocol that can be used requires each process to request and be allocated all of its resources before it begins execution. For Example : Consider a process which copies from a card reader to a disk file, sorts the disk file, and then prints the results to a line printer and copies them to a magnetic tape. If all resources to be requested at the beginning of the process, then the process must initially request the card reader, disk file, line printer, and tape drive. It will hold the magnetic tape drive for its entire execution, even though it needs only at the end.  An alternative protocol allows a process to request resources only when it has none. A process may request some resources and use them. Before it can request any additional resources, it must release all the resources that it is currently allocated. To illustrate the difference between these two protocols. 3. No Preemption The third necessary condition is that there is no preemption of resources that have already been allocated. Guaranteeing a situation so that the “no preemption” condition is not met is very difficult. The preempted resources are added to the list of resources for which the process is waiting. The process will only be restarted when it can regain its old resources, as well as the new ones that it is requesting. For Example : If a process request some resources, we first check if they are available. If so, we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting or held by a waiting process, the requesting process must wait. While it is waiting, some of its resources may be preempted, but only if another process requests them. A process can only be restarted when it is allocated the new resources it is requesting and recovers any resources that we preempted while it was waiting. 4. Circular Wait If a circular wait condition is prevented, the problem of the deadlock can be prevented too. One way in which this can be achieved is to force a process to hold only one resource at a time. If it requires another resource, it must first give up the one that is held by it and then request for another. Figure 2: www.vidyalankar.org Memory Management and Virtual Memory Memory management is a crucial function of an operating system that manages the computer’s primary memory. It involves keeping track of each byte in a computer’s memory and the processes that use this memory. Virtual memory, on the other hand, extends the apparent amount of memory available to a process by using disk storage to simulate additional RAM. 8 Memory Management Memory management is the activity of managing computer memory, including the allocation, tracking, and deallo- cation of memory. The primary goal is to optimize the use of RAM while providing each process with a dedicated address space. Key Functions of Memory Management Allocation: Assigning blocks of memory to processes when they need it. Deallocation: Freeing memory that is no longer in use so it can be reused by other processes. Tracking: Keeping records of which memory locations are allocated and which are free. Protection: Ensuring that processes do not interfere with each other’s memory space. Swapping: Temporarily transferring data from RAM to disk storage to free up memory. Memory Management Techniques Contiguous Memory Allocation In contiguous memory allocation, each process is allocated a single contiguous block of memory. This method is simple but can lead to fragmentation. Paging Paging divides physical memory into fixed-size units called frames and divides logical memory into units of the same size called pages. When a process is executed, its pages can be loaded into any available frames, eliminating the problem of contiguous memory allocation. Segmentation Segmentation is similar to paging but divides memory into segments based on the logical divisions of a program, such as functions or objects. Each segment can be of varying lengths and has its own base and limit. Fragmentation 1. External Fragmentation External fragmentation occurs when free memory is split into small, non-contiguous blocks, making it difficult to allocate larger memory requests. 2. Internal Fragmentation Internal fragmentation occurs when fixed-size memory blocks are allocated to processes, leading to unused memory within the allocated block. 9 Virtual Memory Virtual memory is a memory management technique that allows an operating system to use hardware and disk space to simulate additional RAM. This creates an illusion of a larger main memory, enabling processes to run without being constrained by the physical memory size. Benefits of Virtual Memory Increased Address Space: Processes can utilize more memory than physically available, enhancing multi- tasking capabilities. Isolation and Security: Each process operates in its own virtual address space, preventing them from accessing each other’s memory. Efficient Use of RAM: Less frequently used pages can be stored on disk, freeing up RAM for active processes. Simplified Memory Management: Memory allocation and deallocation can be managed more easily. Paging in Virtual Memory In virtual memory, paging allows the operating system to divide the virtual address space into pages that can be loaded into any available physical memory frames. The system maintains a page table to map virtual pages to physical frames. Page Replacement Algorithms When a page fault occurs (when a process tries to access a page not currently in memory), the operating system must choose a page to evict from physical memory. Common page replacement algorithms include: First-In, First-Out (FIFO): The oldest page is replaced. Least Recently Used (LRU): The page that has not been used for the longest time is replaced. Optimal Page Replacement: Replaces the page that will not be used for the longest time in the future. Segmentation in Virtual Memory Segmentation complements paging by allowing logical divisions of a program to be mapped to non-contiguous physical memory. Each segment has a base (starting address) and a limit (length). Swapping Swapping is the process of transferring pages or segments between physical memory and disk storage. When the operating system needs to free up physical memory, it may swap out entire processes or parts of processes to the disk. 10 Types of Memory Memory is a fundamental component of a computer system that allows data storage and retrieval. Different types of memory serve various purposes, each with its characteristics, speed, capacity, and volatility. The primary types of memory include cache memory, main memory, and secondary storage. 10.1 Cache Memory Cache memory is a small-sized type of volatile computer memory that provides high-speed data access to the processor. It is faster than main memory and is used to temporarily store frequently accessed data and instructions. Characteristics Speed: Cache memory is much faster than both main memory and secondary storage. Volatility: Cache memory is volatile, meaning it loses its contents when power is turned off. Size: Typically smaller in size compared to main memory, ranging from a few kilobytes to several megabytes. Levels: Modern processors often have multiple levels of cache (L1, L2, L3), with L1 being the fastest and smallest, followed by L2 and L3. Functionality Cache memory stores copies of frequently accessed data from main memory. When the CPU needs data, it first checks the cache. If the data is found (cache hit), it can be retrieved much faster than from main memory. If the data is not found (cache miss), it is fetched from main memory, and a copy is stored in the cache for future access. Cache Organization Cache memory can be organized in different ways: Direct Mapping: Each block of main memory maps to exactly one cache line. Associative Mapping: A block of main memory can be placed in any cache line. Set-Associative Mapping: Combines both approaches, allowing a block to be placed in a specific set of cache lines. 10.2 Main Memory Main memory, also known as Random Access Memory (RAM), is the primary storage area that is directly accessible by the CPU. It stores data and programs that are currently in use, allowing for quick read and write operations. Characteristics Speed: Faster than secondary storage but slower than cache memory. Volatility: Main memory is volatile, meaning its contents are lost when power is turned off. Capacity: Typically larger than cache memory, ranging from a few gigabytes to several terabytes in modern systems. Accessibility: Directly accessible by the CPU, enabling rapid data retrieval and execution. Functionality Main memory holds the operating system, application programs, and data in current use, enabling the CPU to access this information quickly. When a program is executed, its instructions and data are loaded from secondary storage into main memory, allowing for immediate access by the CPU. Types of Main Memory Dynamic RAM (DRAM): Stores each bit of data in a separate capacitor; needs to be refreshed periodically. Static RAM (SRAM): Uses flip-flops to store each bit; faster and more reliable than DRAM but more expensive. Synchronous DRAM (SDRAM): Synchronized with the system clock for improved performance. 10.3 Secondary Storage Secondary storage refers to non-volatile storage devices that retain data even when the power is turned off. This type of memory is used for long-term data storage. Characteristics Capacity: Much larger than both cache and main memory, often ranging from hundreds of gigabytes to several terabytes. Speed: Slower than both cache and main memory, with access times measured in milliseconds. Volatility: Non-volatile, meaning data is retained without power. Cost: Generally cheaper per gigabyte compared to RAM and cache. Types of Secondary Storage Hard Disk Drives (HDD): Magnetic storage devices with moving mechanical parts, providing high capacity at a lower cost. Solid State Drives (SSD): Use flash memory with no moving parts, offering faster access times and greater durability. Optical Discs: Storage media such as CDs, DVDs, and Blu-rays, used primarily for media storage and data archiving. USB Flash Drives: Portable flash memory devices used for transferring and storing data. Functionality Secondary storage serves as the main repository for data and programs not currently in use. It allows for the long-term storage of files, applications, and system data, which can be loaded into main memory when needed. 10.4 Comparison of Memory Types Feature Cache Memory Main Memory Secondary Storage Speed Fast Moderate Slow Volatility Volatile Volatile Non-volatile Size Small Moderate to Large Large Cost Expensive per GB Moderate per GB Cheap per GB Usage Temporary data storage Active process data Long-term data storage Table 1: Comparison of Cache Memory, Main Memory, and Secondary Storage 11 Paging Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus eliminates the issues of fitting varying sized memory chunks onto the backing store. Definition Paging is a method of memory management in which the process is divided into fixed-size blocks called pages in logical memory and frames in physical memory. The operating system maintains a page table that maps logical pages to physical frames. Advantages of Paging Elimination of Fragmentation: No external fragmentation occurs as pages are of fixed size. Efficient Memory Use: Physical memory can be allocated more flexibly. Isolation of Processes: Each process operates in its own virtual address space. Simplified Memory Management: Paging simplifies memory allocation and management. Paging Mechanism When a process is executed, its pages are loaded into available memory frames. The page table keeps track of where each page of the process is stored in physical memory. 11.1 Page Replacement Algorithms Page replacement algorithms are techniques used in operating systems to manage memory efficiently when the virtual memory is full. When a new page needs to be loaded into physical memory , and there is no free space, these algorithms determine which existing page to replace. If no page frame is free, the virtual memory manager performs a page replacement operation to replace one of the pages existing in memory with the page whose reference caused the page fault. It is performed as follows: The virtual memory manager uses a page replacement algorithm to select one of the pages currently in memory for replacement, accesses the page table entry of the selected page to mark it as “not present” in memory, and initiates a page-out operation for it if the modified bit of its page table entry indicates that it is a dirty page 11.2 FIFO (First-In, First-Out) The FIFO page replacement algorithm replaces the oldest page in memory, following the order in which pages were brought into memory. This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal. Characteristics Simple to implement. Can suffer from the Belady’s anomaly, where increasing the number of frames leads to more page faults. 11.3 Optimal Page Replacement The Optimal page replacement algorithm replaces the page that will not be used for the longest period of time in the future. Characteristics Produces the lowest possible page fault rate for a given reference string. Requires knowledge of future requests, making it impractical for real systems but useful for benchmarking. 11.4 LRU (Least Recently Used) The LRU page replacement algorithm replaces the page that has not been used for the longest time. Characteristics Good approximation of the optimal algorithm. More complex to implement due to the need to track the order of page usage. 11.5 Most Recently Used (MRU) In this algorithm, page will be replaced which has been used recently. Belady’s anomaly can occur in this algorithm. Example Question 1 Given a reference string of pages: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, and a system with three frames, calculate the number of page faults using FIFO, LRU, MRU and Optimal page replacement algorithms. Example Question 2 If a system has 4 frames and the following page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, compute the number of page faults for FIFO, LRU, MRU and Optimal algorithms. 12 CPU Scheduling Algorithms CPU scheduling is the process of determining which process in the ready state should be moved to the running state. The CPU Scheduling is the process by which a process is executed by the using the resources of the CPU. The process also can wait due to the absence or unavailability of the resources. These processes make the complete use of Central Processing Unit. 12.1 Scheduling Criteria CPU Utilization: Keep the CPU as busy as possible. Throughput: Number of processes completed per time unit. Turnaround Time: Total time taken for a process to execute. Waiting Time: Total time a process spends in the ready queue. Response Time: Time from the submission of a request until the first response. 12.2 Scheduling Algorithms 12.2.1 First-Come, First-Served (FCFS) Algorithm: Processes are scheduled in the order they arrive. Characteristics: – Jobs are executed on first come, first serve basis. – It is a non-preemptive, pre-emptive scheduling algorithm. – Easy to understand and implement. – Its implementation is based on FIFO queue. – Poor in performance as average wait time is high. 12.2.2 Shortest Job First (SJF) Algorithm: Processes with the shortest execution time are scheduled first. Characteristics: – This is also known as shortest job first, or SJF – This is a non-preemptive, pre-emptive scheduling algorithm. – Best approach to minimize waiting time. – Easy to implement in Batch systems where required CPU time is known in advance. – Impossible to implement in interactive systems where required CPU time is not known. – The processer should know in advance how much time process will take. 12.2.3 Shortest Remaining Time First (SRTF) Algorithm: Preemptive version of SJF; if a new process arrives with a shorter remaining time, it preempts the current process. Characteristics: – Shortest remaining time (SRT) is the preemptive version of the SJN algorithm. – The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion. – Impossible to implement in interactive systems where required CPU time is not known. – It is often used in batch environments where short jobs need to give preference. 12.2.4 Round Robin (RR) Algorithm: Each process is assigned a fixed time slice (quantum) and is scheduled in a cyclic order. Characteristics: – Round Robin is the preemptive process scheduling algorithm. – Each process is provided a fix time to execute, it is called a quantum. – Once a process is executed for a given time period, it is preempted and other process executes for a given time period. – Context switching is used to save states of preempted processes. 12.2.5 Priority Scheduling Algorithm: Processes are scheduled based on priority. Characteristics: – Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems. – Each process is assigned a priority. Process with highest priority is to be executed first and so on. – Processes with same priority are executed on first come first served basis. – Priority can be decided based on memory requirements, time requirements or any other resource re- quirement. 12.3 Comparison of Scheduling Algorithms Algorithm Preemptive Fairness Complexity FCFS No Low Low SJF No Low Medium SRTF Yes Low High Round Robin Yes High Medium Priority Both Depends Medium Table 2: Comparison of CPU Scheduling Algorithms 13 I/O Scheduling Algorithms Disk scheduling algorithms are crucial in managing how data is read from and written to a computer’s hard disk. These algorithms help determine the order in which disk read and write requests are processed, significantly impacting the speed and efficiency of data access. Common disk scheduling methods include First-Come, First-Served (FCFS), Shortest Seek Time First (SSTF), SCAN, C-SCAN, LOOK, and C-LOOK. By understanding and implementing these algorithms, we can opti- mize system performance and ensure faster data retrieval. I/O scheduling determines the order in which I/O requests are processed. Efficient scheduling improves disk performance. Importance of Disk Scheduling in Operating System Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled. Two or more requests may be far from each other so this can result in greater disk arm movement. Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner. Key Terms Associated with Disk Scheduling Seek Time: Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or written. So the disk scheduling algorithm that gives a minimum average seek time is better. Rotational Latency: Rotational Latency is the time taken by the desired sector of the disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better. Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and the number of bytes to be transferred. Disk Access Time: Disk Access Time = Seek Time + Rotational Latency + Transfer Time Total Seek Time = Total head Movement * Seek Time Disk Response Time: Response Time is the average time spent by a request waiting to perform its I/O operation. The average Response time is the response time of all requests. Variance Response Time is the measure of how individual requests are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum variance response time is better. Note: Average Rotational latency is generally taken as 1/2(Rotational latency). Goal of Disk Scheduling Algorithms Minimize Seek Time Maximize Throughput Minimize Latency Fairness Efficiency in Resource Utilization 13.1 Algorithms 13.1.1 First-Come, First-Served (FCFS) FCFS scheduling algorithm is the simplest disk scheduling algorithm. As the name suggests, it is a first-come, first-serve algorithm. In this algorithm, the I/O requests are processed in the order they arrive in the disk queue. Algorithm: Processes requests in the order they arrive. Advantages: Fair and simple. Disadvantages: May lead to long wait times and increased seek time. 13.1.2 Shortest Seek Time First (SSTF) In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed first. So, the seek time of every request is calculated in advance in the queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of the system Algorithm: Selects the request closest to the current head position. Advantages: Reduces total seek time. Disadvantages: May cause starvation of distant requests. 13.1.3 SCAN (Elevator Algorithm) In the SCAN algorithm the disk arm moves in a particular direction and services the requests coming in its path and after reaching the end of the disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works as an elevator and is hence also known as an elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait. Algorithm: Disk arm moves in one direction servicing requests until it reaches the end, then reverses. Advantages: Provides better service distribution. Disadvantages: Longer wait times for requests just visited by the head. 13.1.4 LOOK LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk. Algorithm: Similar to SCAN but the arm only goes as far as the last request in each direction. Advantages: Reduces unnecessary head movement. 13.1.5 Circular SCAN (C-SCAN) n the SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area. These situations are avoided in the CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to the SCAN algorithm hence it is known as C-SCAN (Circular SCAN). Algorithm: Disk arm moves in one direction servicing requests, then returns to the beginning without servicing. Advantages: Provides more uniform wait times. Disadvantages: Can have increased average response time. 13.1.6 Circular LOOK (C-LOOK) As LOOK is similar to the SCAN algorithm, in a similar way, C-LOOK is similar to the CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk. Algorithm: Similar to C-SCAN but only goes as far as the last request. Advantages: Reduces unnecessary head movement compared to C-SCAN. 13.1.7 RSS (Random Scheduling) It stands for Random Scheduling and just like its name it is natural. It is used in situations where scheduling involves random attributes such as random processing time, random due dates, random weights, and stochastic machine breakdowns this algorithm sits perfectly. Which is why it is usually used for analysis and simulation. 13.1.8 LIFO (Last-In First-Out) In LIFO (Last In, First Out) algorithm, the newest jobs are serviced before the existing ones i.e. in order of requests that get serviced the job that is newest or last entered is serviced first, and then the rest in the same order.. 13.1.9 N-STEP SCAN It is also known as the N-STEP LOOK algorithm. In this, a buffer is created for N requests. All requests belonging to a buffer will be serviced in one go. Also once the buffer is full no new requests are kept in this buffer and are sent to another one. Now, when these N requests are serviced, the time comes for another top N request and this way all get requests to get a guaranteed service Advantages of N-STEP SCAN: It eliminates the starvation of requests completely 13.1.10 F-SCAN This algorithm uses two sub-queues. During the scan, all requests in the first queue are serviced and the new incoming requests are added to the second queue. All new requests are kept on halt until the existing requests in the first queue are serviced. Advantages of F-SCAN F-SCAN along with N-Step-SCAN prevents “arm stickiness” (phenomena in I/O scheduling where the schedul- ing algorithm continues to service requests at or near the current sector and thus prevents any seeking) Each algorithm is unique in its own way. Overall Performance depends on the number and type of requests. 13.2 Comparison of I/O Scheduling Algorithms Algorithm Seek Time Fairness FCFS High High SSTF Low Low SCAN Medium Medium LOOK Medium Medium C-SCAN Medium Medium C-LOOK Medium Medium Table 3: Comparison of I/O Scheduling Algorithms