DBMS ki tarah OS bhi GATE CSE me 8-10 marks ka hai. Aaj hum Chapter 1 start kar rahe hain – Process Scheduling.

What is Process Scheduling?

OS ka main kaam CPU ko kabhi khali na rehne dena. Iske liye OS decide karta hai kaunsa process kab chalega. Isko hi Scheduling kehte hain.

Process Scheduling ka kaam hai decide karna ki CPU pe kaunsa process kab chalega. Jab ek se zyada process ready state me hote hain, toh OS ko scheduler decide karta hai.

Why it is needed?
CPU ko kabhi khali nahi chhodna, waiting time kam karna, aur throughput badhana.

Types of Schedulers:

1. Long Term Scheduler (Job Scheduler): Kaunse process ko memory me lana hai, degree of multiprogramming control karta hai.

2-Short Term Scheduler (CPU Scheduler): Kaunse ready process ko CPU dena hai, sabse tez kaam karta hai.

3-Medium Term Scheduler: Process ko suspend/resume karta hai, swapping ka kaam.

Main Goals of Scheduling:

• Max CPU Utilization
• Max Throughput
• Min Waiting Time & Turnaround Time
• Min Response Time

Types of Scheduling Algorithms:

1. FCFS – First Come First Serve

Jo pehle aaya use pehle CPU. Non-preemptive hai.
Fayda: Simple
Nuksan: Convoy Effect – chota process bada process ke peeche atak jata hai.

GATE Trick: Avg waiting time jyada hota hai.

for example

FCFS Scheduling Simplified! 🚀
First Come First Serve – Sabse basic but GATE me sabse important!

Gantt Chart: P1(0-8) -> P2(8-12) -> P3(12-21)
Avg Waiting Time = 6.67ms

Save kar lo, exam me kaam aayega! 👨‍🎓
Follow: Gatestudy.in

GATE #OperatingSystem #FCFS #Gatestudy

2. SJF – Shortest Job First – GATE ka Baap

Jiska Burst Time kam usko pehle. Average Waiting Time sabse kam deta hai. Isliye Optimal kehte hain.
Non-preemptive hai.
Problem: Starvation ho sakta hai.

GATE Trick: Hamesha Gantt Chart banao.

3. SRTF – Shortest Remaining Time First

SJF ka preemptive version. Har 1 unit time pe check karta hai.

4. Round Robin (RR) – Time Sharing Systems ke liye Best

Har process ko Time Quantum (TQ) milta hai.
Example: TQ=2 hai, BT=5 hai to 2, 2, 1 me chalega.
TQ bada = FCFS
TQ chota = Context Switch zyada

5. Priority Scheduling

Har process ko priority. Low number = High priority (GATE me).
Problem: Starvation. Solution: Aging.

6.Multilevel Queue & Multilevel Feedback Queue.

Ready queue ko alag-alag queue me baant dete hain.

GATE PYQ Formula Yaad Rakh:

• TAT = Completion Time – Arrival Time

• WT = TAT – Burst Time

• RT = First Response – Arrival Time

Common Mistake jo Students Karte Hain:

FCFS me agar Arrival Time different hai toh Gantt Chart Arrival Time se banana, 0 se nahi.

Comparison Table

FCFS – Non Preemptive – No Starvation
SJF – Non Preemptive – Starvation Yes – Best Avg WT
SRTF – Preemptive – Starvation Yes – Best Avg WT
RR – Preemptive – No Starvation – For Time Sharing

Conclusion: GATE me sabse zyada question SJF, SRTF aur RR se aate hain. Roz 5 Gantt Chart practice karo.

Complete Operating System Notes for GATE CSE – Process to Deadlock

Operating System GATE CSE ka sabse important aur conceptual subject hai. Har saal OS se 6 se 10 marks aate hain. Is subject me Numerical aur Theory dono aate hain. Agar aapne Process Scheduling, Synchronization aur Memory Management pakka kar liya to 6 marks to pakke hain.

1. Process and Threads – Basic Concept

Program vs Process: Program hard disk par pada hua code hai, jab usko execute karte hain to wo Process ban jata hai. Process active entity hai.

Process Control Block (PCB): Har process ka ek PCB hota hai jisme uski sari information hoti hai – Process ID, State, Program Counter, CPU Registers, Memory Limits, Open Files. Jab CPU ek process se dusre process par jata hai to PCB me uski sari value save hoti hai. Isko hi Context Switch kehte hain.

Process State: New -> Ready -> Running -> Waiting -> Terminated. GATE me 5 state aur 7 state model poochte hain. 7 State model me Suspend Ready aur Suspend Blocked add ho jata hai.

Threads: Process ka ek light weight part. Ek process me multiple threads ho sakte hain. Thread ka apna PC aur Stack hota hai lekin Memory aur Code dusre threads ke sath share karta hai. Isliye Thread create karna Process create karne se 10x fast hota hai.

2. CPU Scheduling Algorithms – Har Saal Numerical

Scheduling ka matlab kaunsa process pehle CPU par jayega.

Algorithm	Type	Criteria	GATE Trap
FCFS	Non-Preemptive	Arrival Time	Convoy Effect hota hai
SJF	Preemptive / Non-Preemptive	Burst Time	Minimum Avg Waiting Time, Starvation hota hai
SRTF	Preemptive (SJF ka Preemptive version)	Remaining Time	Har saal iska numerical aata hai
Round Robin	Preemptive	Time Quantum	Quantum bada to FCFS ban jayega
Priority	Dono	Priority Number	Starvation ka solution = Aging

Important Formula: GATE me ye formula bhut poochte hain.

• Turn Around Time (TAT) = Completion Time – Arrival Time
• Waiting Time (WT) = TAT – Burst Time
• Response Time = First CPU milne ka time – Arrival Time

GATE Trick: Agar question me Arrival Time 0 hai to SJF aur SRTF same result denge. Agar Arrival Time different hai to SRTF best hai.

3. Process Synchronization – Sabse Tough Chapter

Jab 2 ya zyada process ek hi data ko access karte hain to Race Condition hoti hai. Isko rokne ke liye Synchronization chahiye.

Critical Section Problem ke 3 Rules:

1. Mutual Exclusion: Ek time par ek hi process Critical Section me jayega.
2. Progress: Agar koi process CS me nahi hai to dusre ko rokna nahi chahiye.
3. Bounded Wait: Kisi process ko infinite time tak wait nahi karwana.

Solutions:

1. Peterson Solution: 2 Process ke liye software solution hai. Flag aur Turn variable use karta hai. Ye teeno conditions satisfy karta hai.

2. Semaphore: Ye sabse important hai. Semaphore ek integer variable hai. 2 Operation hote hain – Wait(P) aur Signal(V).

• Binary Semaphore: Value 0 aur 1. Mutual Exclusion ke liye use hota hai.
• Counting Semaphore: Value 0 se N tak. Resource counting ke liye, jaise 5 printer hain.

Wait operation semaphore ko 1 se kam karta hai, agar value negative ho gayi to process ko Block kar deta hai. Signal operation value ko badhata hai.

Classical Problems: GATE me inka code poochte hain – Producer Consumer Problem, Reader Writer Problem, Dining Philosopher Problem. Producer Consumer me 2 Semaphore – Empty aur Full aur 1 Mutex chahiye hota hai.

4. Deadlock – 2 Marks Pakka

Deadlock ka matlab 2 process ek dusre ka wait karte rahenge, koi bhi aage nahi badhega.

Deadlock ke 4 Necessary Conditions (Coffman Conditions): Ye 4 condition ek sath hongi tabhi Deadlock hoga. Ek bhi tooti to Deadlock nahi hoga.

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

Deadlock Handling ke 4 Tarike:

A. Deadlock Prevention: 4 conditions me se kisi ek ko tod do. Circular Wait ko todne ke liye saare resource ko number de do, process ko increasing order me hi resource lena hoga.

B. Deadlock Avoidance – Banker’s Algorithm: Ye GATE ka favorite numerical hai. Process ko resource dene se pehle check karo ki system Safe State me rahega ya nahi. Safe State ka matlab koi Safe Sequence exist karti hai jisme saare process complete ho jayen.

GATE Trick for Banker’s: Need = Max – Allocation. Available ko check karo. Jiska Need <= Available hai, usko execute karwa do, uska Allocation Available me add kar do. Aise hi sab complete ho gaye to Safe hai.

C. Deadlock Detection and Recovery: Resource Allocation Graph (RAG) banao. Agar Graph me Cycle hai to Deadlock hai. (Single instance resource ke liye). Recovery ke liye ek process ko abort kar do ya resource preempt kar lo.

D. Deadlock Ignorance: Ostrich Algorithm. Kuch mat karo. Windows aur Linux isi ko follow karte hain.

5. Memory Management – Paging aur Segmentation

Contiguous Allocation: Har process ko ek sath memory milti hai. Isme 2 tarah ka Fragmentation hota hai.

• Internal Fragmentation: Process ko zarurat se zyada memory mil gayi. Jaise 2KB chahiye, 4KB block mil gaya, 2KB waste.
• External Fragmentation: Total memory hai lekin contiguous nahi hai. First Fit, Best Fit, Worst Fit se isko handle karte hain.

Paging – Sabse Important: Physical Memory ko fix size ke Frame me baat do, Logical Memory ko same size ke Page me. Page size = Frame size. Isse External Fragmentation khatam ho jata hai lekin Internal Fragmentation abhi bhi rehta hai (last page me).

Formula: Logical Address = Page Number + Page Offset. Page Table se Frame Number nikalte hain. Page Table ka size = Number of Pages * Entry Size. Multi-level paging se Page Table ka size kam karte hain. GATE me 2-level aur 3-level paging ka numerical har saal aata hai.

TLB (Translation Look-aside Buffer): Ye Page Table ka cache hai. Isme frequently used Page Table entries hoti hain. Effective Memory Access Time (EMAT) ka formula yaad rakho.

EMAT = TLB Hit Ratio * (TLB Time + Memory Time) + (1 – Hit Ratio) * (TLB Time + 2*Memory Time)

Ye formula 2 marks ka direct question hai.

Segmentation: Process ko Logical Parts me baat do – Code, Data, Stack. Har Segment ka alag size ho sakta hai. Isme External Fragmentation hota hai.

6. Virtual Memory – Page Replacement

Virtual Memory ka matlab RAM se badi process ko bhi chalana. Demand Paging se Page tabhi laate hain jab zarurat ho.

Page Fault: Jab CPU ko jo Page chahiye wo RAM me nahi hai. Tab OS disk se Page lakar RAM me daalta hai.

Page Replacement Algorithms: Agar RAM full hai aur naya Page lana hai to kaunsa purana Page nikalna hai.

• FIFO: Jo sabse pehle aaya, usko pehle nikalo. Isme Belady’s Anomaly hota hai – Frame badhane par Page Fault badh sakta hai.
• Optimal: Jo Page sabse late future me use hoga, usko nikalo. Minimum Page Fault. Practical nahi hai kyunki future ka pata nahi. Lekin GATE me isko benchmark ke liye use karte hain.
• LRU (Least Recently Used): Jo sabse purana use hua hai, usko nikalo. Stack ya Counter se implement hota hai. Isme Belady’s Anomaly nahi hota.

Thrashing: CPU zyada time Paging me laga raha hai, Execution me kam. Iska reason hai Degree of Multiprogramming zyada hona. Solution – Working Set Model ya Page Fault Frequency.

7. Disk Scheduling and File System

Disk Scheduling: Disk ke Head ko kaise move karwana hai.

• FCFS: Simple.
• SSTF (Shortest Seek Time First): Jo request sabse paas hai, usko pehle. Starvation ho sakta hai.
• SCAN (Elevator): Ek taraf end tak jao, fir dusri taraf aao.
• C-SCAN: Ek taraf jao, end se start par jump karo, fir ek taraf jao. Uniform wait time.
• LOOK aur C-LOOK: SCAN jaisa hi hai lekin end tak nahi jata, last request tak hi jata hai. GATE me C-LOOK sabse zyada poochte hain.

Final Revision Checklist for OS:

• Numerical: TAT, WT, SRTF, Banker’s Algorithm, EMAT, Page Replacement, Disk Scheduling
• Theory: Semaphore code, Deadlock 4 conditions, Paging vs Segmentation
• Formula: EMAT aur TAT/WT kabhi mat bhulna

Ye OS ke notes 2 baar padh lo aur PYQ laga lo, 8 marks pakke ho jayenge. Agla topic DBMS Indexing ya Computer Networks ka chahiye to bolo.