Operating System
OS Part-1
OS Part-2
- File Concepts and Access methods
- Free Space Management and Allocation methods
- Directory Systems and Protection
- File Organization, Sharing and Implementation issues
- Disk and Drum Scheduling
- I/O Devices Organisation & I/O Buffering
- I/O Hardware, Kernel I/O subsystem and Transforming I/O Requests to Hardware Operations
- Device Drivers and Path Management
- Device Driver Sub Modules and Procedure
- Device Scheduler and Handler
- Interrupt Service Routine (ISR)
- File System in Linux and Windows
OS Part-3
- Process and Process Control Block(PCB)
- Process Scheduling( Preemptive and Non Preemptive)
- Scheduling Algorithms
- Algorithm Evaluation
- Multiple Processor Scheduling
- Real Time Scheduling
- Operations on Processes
- Threads
- Inter-Process Communication
- Precedence Graphs
- Critical Section Problem
- Semaphores
- Classical Problems of Synchronization
- DeadLock
- Deadlock Prevention and Avoidance
- Deadlock Detection and Recovery
- Process Management in Linux
OS Part-4
- Memory Hierarchy in OS
- Concepts of Memory Management
- MFT and MVT
- Logical and Physical Address Space
- Swapping
- Contiguous and Non Contiguous Memory Allocation
- Paging
- Segmentation
- Paging Combined with Segmentation
- Structure and Implementation of Page Table
- Virtual Memory in OS
- Cache Memory Organization
- Demand Paging
- Page Replacement Algorithms
- Allocation of Frames and Thrashing
- Demand Segmentation
OS Part-5
- Distributed Operating System: Introduction and Types
- Distributed OS: Design Issues
- Distributed OS: File System
- Distributed OS: Remote File Access
- Remote Procedure Call(RPC)
- Remote Method Invocation(RMI)
- Distributed Shared Memory
- Parallel Processing and Concurrent Programming
- Security and Threats Protection in Distributed OS
- Security Design Principles and Authentication in Distributed OS
- Sensor Network and Parallel OS
Precedence Graphs in Operating System
Precedence Graph Kya Hota Hai?
Precedence Graph (jise Serializability Graph ya Conflict Graph bhi kehte hain) ek directed graph hota hai jo alag-alag transactions ya processes ke beech ke dependencies ko represent karta hai.
Ye graph multi-process execution aur database transactions mein kaafi useful hota hai, kyunki ye help karta hai:
Serializability check karne mein (matlab transactions safely execute ho sakti hain ya nahi). Deadlocks detect karne mein (jab ek process dusre pe dependent ho). Conflicts identify karne mein (jab do transactions ek hi resource ko access ya modify kar rahi ho).
Graph ke Elements:
-
Nodes (Vertices) → Alag-alag transactions ya processes ko represent karte hain.
-
Edges (Arrows) → Dependencies dikhate hain (matlab ek transaction/process ko dusre se pehle execute hona zaroori hai).
Precedence Graph Kyun Zaroori Hai?
Problem: Jab multiple transactions/processes ek saath execute hoti hain, to conflicts ho sakte hain (jaise ek transaction kisi data ko modify kar rahi ho aur dusri transaction bhi wahi data access kare). Solution: Precedence Graph se hum check kar sakte hain ki transactions safely execute ho sakti hain ya nahi.
Example 1: Precedence Graph in Database Transactions
Maan lo do transactions hain:
-
T1: Read (X), phir Write (X)
-
T2: Read (X), phir Write (X)
| Step | Transaction T1 | Transaction T2 |
|---|---|---|
| 1 | Read (X) | |
| 2 | Read (X) | |
| 3 | Write (X) | |
| 4 | Write (X) |
Conflict: Dono transactions X ko access aur modify kar rahi hain, to check karna hoga ki kya ye serializable hain ya nahi.
Precedence Graph Banane ke Steps:
Nodes banayein: T1 aur T2 ke liye alag-alag nodes.
Edges draw karein jo conflicts represent karein:
-
Read(X) → Write(X)
-
Write(X) → Read(X)
-
Write(X) → Write(X)
Graph Representation:
T1 → T2 (Cycle Detected 
→ Not Serializable)
Agar graph mein cycle detect hoti hai, to transactions serializable nahi hain!
Example 2: Precedence Graph in Process Scheduling
Maan lo teen processes hain: P1, P2, aur P3 jo resources R1 aur R2 use kar rahi hain.
| Process | Konsa Resource Chahiye | Kaunsa Resource Hold Kiya Hai |
|---|---|---|
| P1 | R1 | R2 |
| P2 | R2 | R3 |
| P3 | R3 | R1 |
Precedence Graph Banane ke Steps:
Nodes banayein: P1, P2, P3 ke liye alag-alag nodes. Edges draw karein jo dependency represent karein:
Graph Representation:
P1 → P2 → P3 → P1 (Cycle Detected → Deadlock Exists)
Agar cycle detect hoti hai, to deadlock exist karta hai!
Conclusion
Precedence Graph ka use serializability check karne aur deadlock detect karne ke liye hota hai. Agar cycle detect hoti hai, to ya to transactions serializable nahi hain ya deadlock ho sakta hai. Agar cycle nahi hoti, to transactions/processes safely execute ho sakti hain.
Ye technique database transactions, parallel processing aur resource management ke liye kaafi useful hai! 