Operating Systems OS PCCST403 Semester 4 KTU CS 2024 Scheme - Dr Binu V P

  Resource-Allocation-Graph Algorithm (Deadlock Avoidance) This algorithm is used when: ✔ Each resource type has only one instance It is a modification of the regular resource-allocation graph used for deadlock detection, but here it is used for avoidance . Basic Idea The goal is: Never allow the system to enter an unsafe state. The algorithm checks whether granting a resource request would create a cycle in the graph. If granting the request creates a cycle → Unsafe → Deny request If no cycle is formed → Safe → Grant request Since each resource has only one instance: A cycle in the graph implies unsafe state (and potential deadlock). Types of Edges in This Algorithm In addition to the usual edges, we introduce a new edge type. (1) Request Edge (Ti → Rj) Thread Ti is requesting resource Rj. (2) Assignment Edge (Rj → Ti) Resource Rj is allocated to thread Ti. (3) Claim Edge (Ti → Rj) ← New Concept Represented as a dashed line Indicates thread ...

  Deadlock Avoidance Deadlock prevention works by breaking one of the four necessary conditions. However, prevention can cause: Low resource utilization Reduced system throughput Inefficiency Deadlock avoidance takes a different approach. Instead of restricting how resources are requested, the system: Dynamically examines each resource request and decides whether granting it could lead to a future deadlock. Core Idea of Deadlock Avoidance To avoid deadlock, the system must know in advance the maximum resource needs of each thread. Using this information, the system ensures: The system never enters an unsafe state.    Safe State (Core Concept) This is the most important idea in avoidance. Definition A system is in a safe state if there exists a safe sequence of threads: < T 1 , T 2 , . . . , T n > <T_1, T_2, ..., T_n> Such that for each thread T i T_i : Its remaining resource needs can be satisfied by: The currently available ...

  Linux Kernel Synchronization Using Mutexes Mutexes are a sleeping lock used in the Linux kernel to ensure mutual exclusion —only one task can access a shared resource (critical section) at a time. 1. Why mutexes were introduced Earlier, the kernel mainly used semaphores for sleeping locks. Many semaphores were initialized with count = 1 and used like mutual-exclusion locks. Problems with semaphores: Too generic and flexible No strict usage rules Harder to debug misuse More complex interface To solve this, Linux introduced struct mutex , which is: Simpler Faster Safer (has strict constraints) 2. What a mutex does A mutex protects shared kernel data by: Locking before entering critical section Sleeping if already locked Unlocking when done Basic usage DEFINE_MUTEX (name); // static initialization mutex_init (&mutex); // dynamic initialization mutex_lock (&mutex); // acquire lock (sleep if unavailable) /*...

  💤 Semaphores in Linux Kernel  ✅ What is a semaphore? A semaphore in Linux is a sleeping lock used to protect shared resources. If the semaphore is free → the task acquires it immediately If unavailable → the task is: placed in a wait queue put to sleep CPU executes other tasks When released → one waiting task is woken up and allowed to acquire it 👉 Unlike spin locks, no busy waiting occurs , so CPU time is not wasted. ✅ Why semaphores are used Semaphores are suitable when: ✔ Lock may be held for a long time ✔ Task may need to sleep ✔ Synchronization involves user-space interaction ✔ Blocking is acceptable They are not good for very short locks because: sleeping + wakeup overhead managing wait queues can cost more than the protected operation. ✅ Important properties 1️⃣ Sleeping behavior When a task waits: it sleeps instead of spinning improves CPU utilization allows scheduler to run other tasks 2️⃣ Process-cont...

  🔐 Spin Locks in Linux Kernel  ✅ Why spin locks are needed Simple atomic operations work only for very small actions (like incrementing a counter). Real kernel code often: removes data from one structure processes it inserts it into another structure This whole sequence must run without interruption . To protect such larger critical sections , the kernel uses locks , and the most common is the spin lock . ✅ What is a spin lock? A spin lock is a synchronization mechanism where: Only one thread can hold the lock at a time. If another thread tries to acquire it while locked: it busy-waits (spins) in a loop repeatedly checks until the lock becomes free. 🧠 Simple analogy Like waiting outside a locked room holding a key: If the room is free → enter immediately If occupied → stand outside checking continuously ✅ Key characteristics 1️⃣ Mutual exclusion Guarantees only one execution thread enters the critical region. Prevents...