Lab 01: Main Memory Management

Operating Systems Lab Exercise
Duration: 120 minutes (2 hours)
Language: Java
Testing: JUnit 5

Learning Objectives

By completing this lab, you will:

• Understand how Base and Limit registers provide memory protection
• Implement variable partition memory allocation strategies
• Compare the performance characteristics of First Fit, Best Fit, and Worst Fit algorithms
• Simulate dynamic memory allocation with hole list management

Project Setup

Clone the repository

git clone https://forgejo.skynet.ie/andrew/cs4023-lab-01

Open in IntelliJ IDEA

Ensure JUnit 5 is configured in the project

Part 1: Memory Protection (30 minutes)

Base and Limit Register Simulation

Concept: The CPU validates every logical address using Base and Limit registers to enforce memory protection, preventing processes from accessing unauthorized memory regions.

Exercise 1: Address Validation

File: MemoryManager.java

Task: Implement the isValidAddress method that validates if a logical address falls within the process's allocated memory space.

Steps:

1. Review the existing code structure in MemoryManager.java (15 mins)
2. Run the JUnit tests to verify correctness

Checkpoint 1

• Self-Check: Run all tests in MemoryManagerTest.java - do they pass?
• Concept Question: What is the physical address for logical address 50 if Base = 2000 and Limit = 100?

Part 2: Variable Partition Allocation (45 minutes)

🔧 Dynamic Memory Allocation Strategies

Concept: Implement three dynamic memory allocation strategies using a list of free memory blocks ("holes").

Data Structure: List of holes where each hole has:

• size: size of the hole

Exercise 2: Allocation Algorithms

File: AllocationStrategy.java

Step 1: Fix First Fit (5 mins)

• Locate and fix the bug in the firstFit method
• Test: firstFitShouldReturnFirstSuitableHole

Step 2: Implement Best Fit (10 mins)

• Complete the bestFit method to find the smallest suitable hole
• Test: bestFitShouldReturnSmallestSuitableHole

Step 3: Implement Worst Fit (10 mins)

• Complete the worstFit method to find the largest suitable hole
• Test: worstFitShouldReturnLargestSuitableHole

Step 4: Verify All Tests (5 mins)

• Run all four allocation strategy tests
• The test allStrategiesShouldReturnNegativeOneWhenNoFitFound should now pass

Implementation Tips:

java
// Return the index of the suitable hole, or -1 if no hole fits
// First Fit: First hole that's large enough
// Best Fit: Smallest hole that's large enough  
// Worst Fit: Largest hole that's large enough

🧪 Checkpoint 2 (10 mins)

• Self-Check: Do all four tests in AllocationStrategyTest.java pass?
• Concept Question: Why is First Fit generally faster than Best or Worst Fit?

---

Bonus Challenge: Dynamic Allocation

🔄 Real Memory Allocation Simulation

Objective: Go beyond hole selection to simulate actual memory allocation that modifies the system's state.

Task: Implement allocateBestFit in AllocationStrategy.java to:

1. Use the Best Fit algorithm to select a hole
2. If the hole is larger than needed, split it (allocate requested size, leave remainder as a new hole)
3. Update the list of holes to reflect the allocation
4. Return the starting address of the allocated block, or -1 if allocation fails

Test Verification:

java
// Run the dynamic allocation test allocateBestFitShouldCorrectlyUpdateHoleList

---

Algorithm Comparison

Strategy	Selection Criteria	Advantages	Disadvantages
First Fit	First hole that fits	Fastest search	May create external fragmentation
Best Fit	Smallest hole that fits	Minimizes wasted space	Slower; creates small unusable holes
Worst Fit	Largest hole that fits	Leaves large remainders	Poor utilization; slower search

📚 Additional Resources

• Operating System Concepts, 10th Edition (Silberschatz, Galvin, Gagne)
  • Chapter 8: Main Memory
  • Chapter 9: Virtual Memory
• JUnit 5 Documentation: https://junit.org/junit5/docs/current/user-guide/