Operating Systems Lab PCCSL407 Semester 4 KTU CS 2024 Scheme- Dr Binu V P

  Deadlock-Free Solution to Dining Philosophers Problem Using Semaphores 1. Aim To implement a deadlock-free solution for the Dining Philosophers Problem using semaphores . 2. Objective To study process synchronization To avoid deadlock and race conditions To ensure mutual exclusion using semaphores 3. Problem Statement Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating . To eat, a philosopher must acquire both left and right chopsticks . The challenge is to design a solution that: Avoids deadlock Avoids race condition Allows maximum parallelism 4. Theory Why Deadlock Occurs (Naive Solution) If all philosophers pick up their left chopstick first , a circular wait occurs → deadlock . Deadlock-Free Strategy Used We use a binary semaphore room that allows only 4 philosophers to try picking chopsticks at the same time. This breaks circular wait , one of the four deadlock conditions. 5...

  FIFO Page Replacement Algorithm  1. Aim To simulate the FIFO page replacement algorithm and display the frame contents in a tabular form for each page reference. 2. Objective To understand FIFO page replacement To observe page hits and faults To display memory frame status step-by-step 3. Theory  3.1 Virtual Memory Virtual memory allows execution of processes larger than physical memory by dividing memory into pages . When a required page is not in memory , a page fault occurs and the OS must replace an existing page. 3.2 FIFO Page Replacement Algorithm FIFO (First-In First-Out) replaces the page that entered memory earliest , irrespective of how frequently or recently it was used. ➡ Conceptually simple but may suffer from Belady’s anomaly . 3.3 Key Characteristics Feature                Description Replacement policy                   ...

  Least Recently Used (LRU) Page Replacement Algorithm 1. Aim To implement the Least Recently Used (LRU) Page Replacement Algorithm and display the frame contents after each page arrival . 2. Objective To understand how LRU selects a victim page To implement LRU using time (recency) tracking To analyze page hits and page faults 3. Theory The LRU algorithm replaces the page that has not been used for the longest time in the past. Key Idea: “The page that was least recently accessed is least likely to be used again.” LRU approximates optimal behavior better than FIFO but requires tracking past usage . 4. Data Structures Used Structure Purpose frames[]                     Stores pages in memory time[]                     Stores last-used time of each frame counter                   ...

  Least Frequently Used (LFU) Page Replacement Algorithm 1. Aim To implement the Least Frequently Used (LFU) Page Replacement Algorithm and display the frame contents after each page reference . 2. Objective To understand the working of LFU page replacement To replace the page with the minimum access frequency To analyze page hits and page faults 3. Theory The LFU algorithm replaces the page that has been used least often . Key Idea: “Pages with low access frequency are less likely to be used again.” When two pages have the same frequency, FIFO order (or oldest) is commonly used as a tie-breaker. 4. Data Structures Used Structure Purpose frames[]                Stores pages in memory freq[]                Stores access frequency time[]                Stores arrival time (tie-breaker) counter       ...

  Demonstration and Analysis of Belady’s Anomaly  1. Aim To demonstrate Belady’s Anomaly using FIFO page replacement by displaying the frame table with Hit/Miss status and comparing page faults for different frame sizes. 2. Objective To simulate FIFO page replacement To display frame contents after each reference To calculate total page faults To verify Belady’s anomaly 3. Theory 🔹 Belady’s Anomaly Belady’s anomaly occurs when: Increasing the number of frames results in an increase in page faults. This happens in FIFO , but not in LRU or Optimal (stack algorithms). 4. Classic Reference String 1 2 3 4 1 2 5 1 2 3 4 5 This string shows anomaly for FIFO when frames increase from 3 to 4. 5. Algorithm For each frame size: Initialize frames as empty. For each page reference: If page exists → Hit Else → Replace using FIFO → Miss Display frame contents and status. Count page faults. Compare results. C Program (With Frame ...

  Demonstration and Analysis of Thrashing 1. Aim To simulate and demonstrate Thrashing by analyzing page fault rates when the number of available frames is insufficient. 2. Objective To understand the concept of Thrashing To simulate page replacement under low memory conditions To observe high page fault rate To analyze the effect of increasing frames 3. Theory 🔹 What is Thrashing? Thrashing occurs when: The system spends more time handling page faults than executing actual instructions. This happens when: Number of frames is too small Processes do not get enough memory Page fault rate becomes extremely high 🔹 Why Does Thrashing Occur? When frames < working set size: Pages are continuously replaced CPU utilization decreases Disk I/O increases System performance drops 🔹 Working Set Concept Working Set = Set of pages actively used by a process. If allocated frames < working set size → Thrashing occurs. 4. Experim...