1. Memory allocation

Memory Management

Memory Management वह process है जिसमें Operating System (OS) computer की memory को control और organize करता है। इसमें memory को छोटे-छोटे blocks में divide करके अलग-अलग running programs को allocate किया जाता है, जिससे system performance improve होती है।

मुख्य बिंदु (Key Points):

• Operating System का सबसे important function है primary memory को manage करना
• यह एक साथ multiple processes को memory में support करता है
• Processes को unauthorized access से protect करता है
• Efficient तरीके से swapping और virtual memory को handle करता है

Techniques in Memory Allocation (मेमोरी एलोकेशन की तकनीकें)
ये techniques Operating System (OS) द्वारा use की जाती हैं ताकि memory को efficiently allocate, utilize और manage किया जा सके।

👉 विभिन्न techniques को broadly दो categories में divide किया जाता है:

Swapping (स्वैपिंग)

Swapping एक memory management technique है जिसमें processes को temporarily main memory (RAM) से secondary storage (disk) में भेजा जाता है ताकि दूसरी processes के लिए memory free हो सके।

• Multiple processes efficiently run कर सकते हैं
• Low-priority processes को swap out किया जा सकता है
• Swap होने के बाद process वापस load होकर resume करता है
• Transfer time data के size पर depend करता है

Contiguous Memory Allocation (सतत मेमोरी एलोकेशन)

इसमें हर process को एक continuous memory block दिया जाता है, जहाँ उसका पूरा data और instructions stored होते हैं।

Single Contiguous Memory Allocation

यह सबसे simple technique है।

👉 Memory को 2 parts में divide किया जाता है:

• एक हिस्सा Operating System के लिए
• दूसरा हिस्सा single user process के लिए

Characteristics (विशेषताएँ):

• एक समय में केवल एक process
• OS fixed memory use करता है
• कोई multiprogramming नहीं
• Simple management

Advantages (फायदे):

• Simple memory management
• Fragmentation नहीं होता

Disadvantages (नुकसान):

• Poor memory utilization
• Multitasking support नहीं

Partitioned Memory Allocation (विभाजित मेमोरी एलोकेशन)

Memory को multiple partitions में divide किया जाता है, और हर partition में एक process चलता है।

1. Fixed Partition Allocation

• Memory fixed partitions में divide होती है
• हर partition का size fixed होता है
• एक partition = एक process
• Internal Fragmentation होता है
• OS partition table से track करता है

2. Variable (Dynamic) Partition Allocation

• Memory process size के अनुसार dynamically allocate होती है
• Internal fragmentation कम होता है
• लेकिन External Fragmentation होता है

Advantages:

• Multiprogramming possible
• Better utilization

Disadvantages:

• Fragmentation issues
• Complex management

Non-Contiguous Memory Allocation (असतत मेमोरी एलोकेशन)

इसमें process को छोटे-छोटे parts में divide करके अलग-अलग memory locations में store किया जाता है।

Features (विशेषताएँ):

• Process कई जगह store हो सकता है
• Memory utilization improve होता है
• External fragmentation कम होता है
• MMU (Memory Management Unit) required होता है

Advantages:

• Better utilization
• Large programs support
• Continuous memory की जरूरत नहीं

Disadvantages:

• Complex system
• Address translation overhead
• Extra tables (page table / segment table) की जरूरत

Techniques (तकनीकें):

• Paging → fixed-size pages
• Segmentation → logical segments (code, data, stack)
• Segmentation + Paging → दोनों का combination

Memory Management Mechanisms

Virtual Memory

• Program RAM से बड़ा हो सकता है
• Disk को extra memory की तरह use करता है

Page Replacement Algorithms (PRA)

जब memory full हो जाती है तो कौन सा page हटाना है:

• FIFO → सबसे पहले आया page हटाओ
• LRU → least recently used हटाओ
• Optimal → future में सबसे कम use होगा उसे हटाओ
• LFU → least frequently used हटाओ

Demand Paging

• केवल required pages load होते हैं
• Memory और I/O बचता है

Memory Problems (समस्याएँ)

Fragmentation (फ्रैगमेंटेशन)

• Internal Fragmentation → extra allocated space waste
• External Fragmentation → scattered free memory

Thrashing (थ्रैशिंग)

• System बार-बार swapping करता है
• CPU utilization बहुत कम हो जाता है

Memory Allocation Strategies (रणनीतियाँ)

Fixed Partition Allocation

• Fixed size partitions
• Partition table से track

Dynamic Partition Allocation

• Process size के अनुसार memory

Placement Algorithms (एल्गोरिदम):

• First Fit → पहला suitable block
• Best Fit → smallest suitable block
• Worst Fit → largest block
• Next Fit → last position से search

2. First Fit

First-Fit Allocation

Operating System (OS) में memory management एक important function है जो memory resources का efficient allocation और utilization सुनिश्चित करता है। जब processes start होते हैं, तो उन्हें execution के लिए memory blocks allocate किए जाते हैं।

👉 OS इन processes को memory देने के लिए कुछ memory allocation algorithms use करता है।

Main Algorithms (मुख्य एल्गोरिदम):

ये सभी Contiguous Memory Allocation techniques हैं:

1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit

First-Fit Memory Allocation (फर्स्ट फिट मेमोरी एलोकेशन)

Definition (परिभाषा):
First Fit method में OS memory blocks को शुरुआत (start) से check करता है और पहला ऐसा block choose करता है जो process को fit कर सके।

Working (कार्य करने का तरीका):

• किसी भी process Pn के लिए OS available memory blocks को check करता है
• जो पहला free block process के size के बराबर या उससे बड़ा होता है, उसे allocate कर देता है
• बाकी blocks check नहीं किए जाते

Simple Meaning (आसान भाषा में):

First Fit मतलब — पहली suitable जगह मिलते ही memory दे दो

Advantages (फायदे):

• Fast और simple algorithm
• Implementation आसान

Disadvantages (नुकसान):

• Memory fragmentation हो सकता है
• कभी-कभी space properly utilize नहीं होता

First-Fit Memory Allocation Algorithm (फर्स्ट फिट एल्गोरिदम)

Steps (स्टेप्स):

1. Process list के पहले process से शुरू करें
2. हर process Pn के लिए:
   • Step 1: Memory blocks को शुरुआत (first block) से search करें
   • Step 2: Check करें कि block free है और उसका size ≥ process size है
   • Step 3: अगर suitable block मिल जाए → उसे allocate करें और block को occupied mark करें
   • Step 4: अगर कोई block नहीं मिलता → process को unallocated / waiting mark करें
3. यही steps सभी processes के लिए repeat करें

Pseudocode (सरल कोड):

Advantages (फायदे):

• Simple और easy to implement
• Fast allocation (पहले ही block में मिल जाता है)
• Small और similar size processes के लिए अच्छा

Disadvantages (नुकसान):

• External Fragmentation → memory छोटे-छोटे parts में बंट जाती है
• Internal Fragmentation → extra memory waste हो सकती है
• हमेशा best allocation नहीं देता
• Large processes के लिए slow हो सकता है (कई blocks search करने पड़ते हैं)

3. Paging and Segmentation

Paging vs. Segmentation

Paging vs Segmentation (पेजिंग और सेगमेंटेशन)

Paging और Segmentation दोनों ही memory management techniques हैं, लेकिन दोनों का तरीका अलग होता है:

• Paging → memory को fixed-size pages में divide करता है
• Segmentation → memory को logical units (जैसे functions, arrays, data) के हिसाब से variable-size segments में divide करता है

👉 Modern systems में अक्सर दोनों techniques को combine करके use किया जाता है

Paging (पेजिंग)

Definition (परिभाषा):
Paging एक technique है जो non-contiguous memory allocation के लिए use होती है। इसमें memory को fixed-size blocks में divide किया जाता है।

• Secondary memory के blocks → pages
• Main memory (RAM) के blocks → frames

👉 हर process को equal-size pages में divide किया जाता है और उन्हें अलग-अलग frames में store किया जाता है

Features of Paging (विशेषताएँ):

• Fixed Size Division → memory fixed-size pages में divide होती है
• Hardware Defined Page Size → page size hardware decide करता है
• OS Managed → OS page table maintain करता है
• No External Fragmentation → external fragmentation खत्म हो जाता है
• Internal Fragmentation possible → थोड़ा space waste हो सकता है
• User के लिए invisible → programmer को पता नहीं चलता

Working (कार्य करने का तरीका):

• Process को equal-size pages में divide किया जाता है
• Pages को available frames में load किया जाता है
• Page table के through address mapping होती है

👉 Simple Language (आसान भाषा में):
Paging में process को छोटे-छोटे बराबर size के parts में तोड़कर memory में अलग-अलग जगह रखा जाता है, जिससे memory efficiently use होती है।

Segmentation 

Segmentation एक non-contiguous memory allocation technique है, जो Paging की तरह ही होती है, लेकिन इसमें memory को fixed-size pages में नहीं बल्कि variable-size segments में divide किया जाता है।

यह segments program के logical units जैसे:

• functions
• arrays
• data structures

के आधार पर बनाए जाते हैं।

🔹 Features of Segmentation (विशेषताएँ)

• Variable-Size Division
  Memory को अलग-अलग size के segments में divide किया जाता है।
• User/Programmer-Defined Sizes
  Segment का size programmer या compiler decide करता है।
• Compiler-Managed
  Segmentation mainly compiler द्वारा manage होती है, लेकिन OS भी support करता है।
• Supports Sharing and Protection
  Segmentation में data और code को आसानी से share और protect किया जा सकता है।
• Visible to User
  Paging के opposite, Segmentation user/programmer को दिखाई देती है, जिससे control बेहतर होता है।

🔹 Working of Segmentation (कैसे काम करता है)

• Segmentation में main memory और secondary memory को equal parts में divide नहीं किया जाता।
• Memory को different size के segments में divide किया जाता है।
• इन segments को track करने के लिए एक data structure use होता है जिसे segment table कहते हैं।

🔹 Segment Table में क्या होता है

• Base → segment का starting address (memory में कहां से शुरू हो रहा है)
• Limit → segment का size (length)

🔹 Address Translation (Address कैसे बनता है)

जब CPU memory access करता है, तो वह एक logical address generate करता है जिसमें:

• Segment Number
• Offset (distance)

शामिल होता है।

👉 फिर MMU (Memory Management Unit):

• segment number से segment table में entry ढूंढता है
• check करता है कि offset < limit है या नहीं

✔ अगर सही है →
Physical Address = Base + Offset

❌ अगर offset limit से ज्यादा है →
Segmentation Fault (error) आता है

📊 Paging vs Segmentation 

4. Page faults

Page Fault 

Page fault तब होता है जब कोई program ऐसे data या code को access करने की कोशिश करता है जो उसके address space में तो होता है, लेकिन वह उस समय RAM (main memory) में मौजूद नहीं होता।

इस situation में Operating System (OS) एक process शुरू करता है जिसमें:

• missing data को secondary storage (disk) से लाया जाता है
• और उसे RAM में load किया जाता है

इस पूरी process को handle करने के लिए OS को कुछ steps follow करने पड़ते हैं, ताकि program सही तरीके से continue कर सके।

Page Fault Handling

1. Trap to Kernel
   जब CPU किसी ऐसे page को access करता है जो RAM में नहीं है, तो hardware kernel को signal देता है।
   इस समय Program Counter (PC) और CPU की current state save कर ली जाती है।
2. Save State Information
   OS एक assembly routine की मदद से CPU के registers और जरूरी data को save करता है ताकि information lost न हो।
3. Determine Cause of Fault
   OS पता लगाता है कि कौन सा virtual page चाहिए और page fault क्यों हुआ।
4. Validate Address
   OS check करता है कि requested address valid है या नहीं और कोई protection violation तो नहीं है।
5. Allocate Page Frame
   OS देखता है कि कोई free frame available है या नहीं।
   अगर नहीं है तो page replacement algorithm apply किया जाता है।
6. Handle Dirty Pages
   अगर selected page dirty है (modified है), तो उसे पहले disk में save किया जाता है, और process temporarily suspend हो जाता है।
7. Load Page into Memory
   OS required page को secondary storage (disk) से लेकर RAM में load करता है।
8. Update Page Table
   Page आने के बाद page table update की जाती है और frame को normal state में mark किया जाता है।
9. Restore State & Continue Execution
   Saved state वापस load होती है और program फिर से वहीं से execute होता है जहाँ रुका था।

📌 Causes of Page Fault (कारण)

• Demand Paging → page memory में loaded नहीं था
• Invalid Memory Access → गलत address access करना
• Process Violation → read-only page पर write करने की कोशिश

📌 Types of Page Fault

• Minor Page Fault → page memory में है, पर current process में नहीं
• Major Page Fault → page disk से load करना पड़ता है
• Invalid Page Fault → invalid memory access

📌 Impact of Page Fault on System Performance

• Thrashing → बार-बार page fault होने से system slow हो जाता है
• Increased Latency → disk से data लाने में ज्यादा time लगता है
• CPU Utilization कम हो जाता है → CPU idle रहता है memory wait करते समय

5. Page Replacement Algorithm

📌 Page Replacement Algorithm 

जब paging system में page fault होता है और कोई free frame available नहीं होता, तब OS को किसी पुराने page को हटाकर नया page लाना पड़ता है। इसे page replacement कहते हैं।

🔹 Virtual Memory Manager क्या करता है

• एक victim page select करता है (algorithm के अनुसार)
• उसकी page table entry को “not present” mark करता है
• अगर page dirty (modified) है → उसे पहले disk में write करता है

👉 Algorithm की efficiency directly page fault rate और system performance को affect करती है।

📌 Common Page Replacement Techniques

• FIFO (First In First Out)
• Optimal Page Replacement
• LRU (Least Recently Used)
• MRU (Most Recently Used)

🔹 1. FIFO (First In First Out)

यह सबसे simple algorithm है।

• Memory में pages को queue में रखा जाता है
• जो page सबसे पहले आया (oldest) → वही सबसे पहले remove होगा

📊 Example (FIFO)

Page Reference String:
1, 3, 0, 3, 5, 6, 3

Frames = 3

✅ Total Page Faults = 6

📌 Optimal Page Replacement

Optimal algorithm में वह page replace किया जाता है जो future में सबसे देर से use होगा या बिल्कुल use नहीं होगा।

📊 Given Example

Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3

Frames = 4

🔹 Step-by-Step Solution

✅ Total Page Faults = 6

📌 3. Least Recently Used (LRU) – हिंदी + कुछ English words

LRU (Least Recently Used) algorithm में वह page replace होता है जो सबसे लंबे समय से use नहीं हुआ है।

📊 Given Example

Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3

Frames = 4

🔹 Step-by-Step Solution

✅ Total Page Faults = 6

📌 4. Most Recently Used (MRU) 

MRU (Most Recently Used) algorithm में वह page replace होता है जो सबसे हाल ही में (recently) use हुआ है।

👉 LRU का उल्टा concept है।

📊 Given Example

Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3

Frames = 4

🔹 Step-by-Step Solution

✅ Total Page Faults = 8