Operating system

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...

In systems that use virtual memory, processes often require more memory than is available in physical RAM. To manage this, the operating system swaps pages between RAM and disk storage (such as a hard drive or SSD). When the system runs out of RAM and needs to load a new page, it has to decide which of the currently loaded pages to swap out to disk. This decision is made by the page replacement algorithm. 1. FIFO (First-In, First-Out) : The oldest page in RAM (the first one loaded) is the first one to be replaced. Example: Page Slots in RAM: 3 slots Page Sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Load page 1 → [1, -, -] Load page 2 → [1, 2, -] Load page 3 → [1, 2, 3] Load page 4 (remove 1) → [4, 2, 3] Load page 1 (remove 2) → [4, 1, 3] Load page 2 (remove 3) → [4, 1, 2] Load page 5 (remove 4) → [5, 1, 2] Load page 1 (already in RAM) → [5, 1, 2] Load page 2 (already in RAM) → [5, 1, 2] Load page 3 (remove 1) → [5, 3, 2] Load page 4 (remove 2) → [5, 3, 4] Load page 5 (already in RAM) →...

Virtual memory Virtual memory is a memory management technique that allows a computer to use more memory than what is physically available in RAM. It creates an illusion for the user that there's more RAM than there actually is by using a combination of the computer's RAM and a portion of the hard drive.  Imagine you have a computer with 4 GB of RAM, but you're running several programs that together require 6 GB of memory. The operating system will use 4 GB from the physical RAM and then take 2 GB from the hard drive, which acts as an extension of the RAM. This portion of the hard drive is called the swap space or page file . Here's how it works: Running Programs: Suppose you're using a browser, a word processor, and a game simultaneously. Memory Requirement: These applications together need more memory than your 4 GB of RAM can provide. Swapping: The OS decides which parts of the data or applications are not actively in use and temporarily moves them from RAM to th...

Drawbacks of paging When pages are scattered far apart in physical memory, it can lead to additional drawbacks: 1. Reduced Cache Efficiency: Explanation: If the pages of a process are spread out across distant locations in RAM, it can reduce the efficiency of the CPU cache, which relies on the locality of reference. The CPU cache works best when data is close together, as it can quickly load and reuse it. When data is scattered, it increases the chances of cache misses, slowing down memory access. Example: Imagine a book is split into sections and stored on shelves all over a large library (representing RAM). If you have to walk across the library to read each section, it takes much longer than if the sections were on the same or nearby shelves. Similarly, if pages of a process are spread far apart in memory, the CPU might need to fetch data from multiple distant locations, reducing performance 2. Increased Page Table Lookup Time: Explanation: If the pages of a process are not stored c...

The reason why paging is slow Every time a process accesses a memory location, the CPU must translate the logical address to a physical address using the page table. This translation involves multiple steps: Look Up the Page Table: The CPU must first access the page table to find out which physical frame corresponds to the logical page. Access the Physical Memory: Then, it uses the frame number obtained from the page table to access the actual memory location. Example: Page Size: 4 KB Logical Address: 6 KB Page Table Entry: 2 (The logical address 6 KB is in page 2) Frame Number: 5 (Page 2 maps to frame 5 in physical memory) Steps: Access the Page Table: The CPU checks the page table to find out which frame contains the data for page 2. This involves accessing the page table entry for page 2. Access Physical Memory: Once the frame number (5) is known, the CPU accesses the physical memory at frame 5. Total Time: This process involves two memory accesses: One to look up the page table Ano...

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 ...

Contiguous memory Fixed Partitioning Equal-Sized Partitions : All partitions have the same size. For example, if you have 16 KB of RAM, you could divide it into four partitions of 4 KB each. This approach is simple but may lead to significant internal fragmentation, especially if the processes are much smaller than the partition size. Unequal-Sized Partitions : Partitions are of different sizes to accommodate different process sizes more efficiently. For example, in a 16 KB RAM, you might have partitions of 2 KB, 4 KB, 6 KB, and 4 KB. This allows processes of different sizes to be allocated more fittingly, potentially reducing internal fragmentation compared to equal-sized partitions.It is a memory management technique where the available memory is divided into fixed-size blocks or partitions. Each partition can hold exactly one process. The size of the partitions is determined ahead of time and doesn't change during execution. Equal-sized partitioning :  Example: Let's say we ...

Without virtual memory  In a multiprogramming environment, multiple processes are loaded into RAM to maximize CPU utilization and overall system efficiency. Let's consider an example where three processes, P1, P2, and P3, are allocated specific memory spaces in RAM. The operating system occupies the initial portion of RAM, followed by P1 in the memory range 50-60, P2 in the range 60-70, and P3 in the range 90-100. Now, suppose P1 contains a line of code that attempts to access a memory location by adding 10 to the current address. If the current address is 55, this calculation would result in an address of 65, which falls within the memory space allocated to P2. This situation would violate memory protection and process isolation principles, as P1 should not be aware of or able to access the memory allocated to P2. To prevent such violations, there must be mechanisms in place to ensure that each process operates within its allocated memory space without interfering with others. Wit...

Difference between deadlock prevention and deadlock avoidance Deadlock Avoidance : What it does: It’s like driving a car and always checking the road ahead to make sure you never get stuck in traffic. Before giving a resource to a process, the system checks if doing so could lead to a deadlock in the future. If it’s safe, the process gets the resource. If not, the process has to wait. How it works: The system carefully manages resources by constantly keeping track of what’s available, what’s being used, and what each process might need in the future. This way, it can avoid any situation where processes might get stuck waiting for each other. Deadlock Prevention: What it does: Instead of constantly checking like in avoidance, deadlock prevention sets up rules from the beginning to make sure a deadlock can never happen. It’s like setting up traffic lights and one-way streets to ensure cars never get stuck in a loop. How it works: The system makes sure that at least one of the conditions ...

Mutual Exclusion Understanding Mutual Exclusion : Mutual exclusion means that a resource can only be used by one process or thread at a time. If a resource is non-shareable (like a printer), only one process can use it at a time, which is a typical cause of deadlock. Preventing Mutual Exclusion: To prevent deadlock, one strategy is to minimize or eliminate the use of mutual exclusion whenever possible. This means allowing resources to be shared by multiple processes if it is safe to do so. Example: Sharable Resources:  Read-Only Files: A read-only file is a good example of a sharable resource. Multiple processes can read from the same file simultaneously without causing any conflict, so there’s no need for mutual exclusion (locking). Since the file is not being modified, there's no risk of inconsistency, so the system doesn't need to enforce mutual exclusion. Memory Spaces: Similarly, if a memory space can be safely accessed by multiple processes without causing data corruptio...

What is a deadlock? Consider two processes, P1 and P2, each requiring two resources, R1 and R2, to execute. Currently, P1 is holding R1, and P2 is holding R2. However, neither P1 nor P2 can continue their execution without acquiring both resources. Since P1 is waiting for R2 (held by P2), and P2 is waiting for R1 (held by P1), this creates a deadlock situation where both processes are stuck, and unable to proceed. How does a process or thread utilize a resource? Request: The process or thread first checks if the resource (e.g., R) is available. This is often done by attempting to acquire a lock or checking the status of the resource. If the resource is locked: This means another process or thread is currently using it, so the requesting process must wait.  If the resource is not locked: The process can acquire the lock, indicating that it now has control over the resource. Use: Once the resource is acquired, the process or thread uses it to perform its task. During this time, the r...

What is the Dining Philosophers' problem? In the Dining Philosophers problem, we have a table where five philosophers are sitting, with a bowl of noodles in the center. Each philosopher has a plate and a fork, totaling five forks. The philosophers spend their time either eating or thinking—they don't do anything else or communicate with each other. To eat, a philosopher needs to use two forks, one on each side. The issue arises if all five philosophers try to eat at the same time; they would need a total of 10 forks, but only 5 are available. This could lead to a deadlock, where no philosopher can proceed because each is waiting for a fork that another philosopher is holding. To prevent this deadlock, we use semaphores. Each fork is treated as a binary semaphore. In this scenario, each philosopher represents a process, and the forks represent resources. By carefully managing the semaphores, we can avoid the deadlock and ensure that the philosophers can take turns eating. The so...

What is the read-write problem? Threads Involved: Reader Threads: Read the shared resource without modifying it. Writer Threads: Modify or update the shared resource. Rules for Safe Access: Multiple Readers: Multiple reader threads can read the resource simultaneously without causing inconsistencies, as long as no writer is updating the resource. Single Writer: Only one writer thread should be allowed to modify the resource at a time. During this period, no other readers or writers should access the resource. File Example: Multiple Writers: If two writers, W1 and W2, are writing to the same file simultaneously, they can corrupt or overwrite each other's changes, leading to data inconsistency. This is because the file might end up with mixed or incorrect data if both writers modify it at the same time.  Reader and Writer Interaction (Concurrent Reading and Writing):  If a reader, R1, reads from a file while a writer, W1, is updating it, the reader might see a partially updated ...

What is the producer-consumer problem? In the producer-consumer problem, there are two threads: the producer and the consumer. The producer generates data and adds it to a buffer (is a temporary storage area that holds data produced by the producer before it is consumed by the consumer), while the consumer retrieves and processes this data from the buffer. If there are  n slots in the buffer, they start off empty. The producer's job is to produce data and add it to the buffer, while the consumer's job is to consume that data. The buffer acts as a critical section because it is a shared resource that both the producer and consumer access. We need to ensure that the producer and consumer do not interfere with each other. Specifically, the producer should not add data when the buffer is full, as this would waste CPU cycles. Similarly, the consumer should not try to consume data when the buffer is empty, which would also waste CPU cycles. Why is it important for the producer to fi...

Lock : The primary purpose of a lock is to enforce mutual exclusion, which means that only one process or thread can hold the lock at any given time and access the critical section.  Locking: When a process or thread wants to enter a critical section, it must first acquire the lock. If the lock is already held by another process or thread, the requesting process must wait until the lock is released.  Unlocking: After the process or thread has finished its operation in the critical section, it releases the lock, allowing other waiting processes or threads to acquire it.  Mutex (Mutual Exclusion Object): A simple binary lock where the lock can either be held (locked) or not held (unlocked). Only the process that locked the mutex (lock) can unlock it. Disadvantages of locks: A scenario where a lower-priority thread holds a lock that a higher-priority thread needs, causing the higher-priority thread to wait or vice versa. When a process holding a lock dies or is terminated u...