Batch Memory Allocation Simulator

An event-driven simulation system that compares First-Fit and Best-Fit memory allocation strategies in a fixed-partition multiprogramming environment.

Overview

This project simulates a large batch-processing computer installation running under fixed partition multiprogramming with real storage (non-virtual memory). It helps determine which storage placement strategy yields optimal performance by comparing First-Fit and Best-Fit allocation algorithms.

Features

• Event-Driven Simulation: Models job arrivals, allocations, and completions
• Two Allocation Strategies:
  • First-Fit: Allocates jobs to the first available partition that fits
  • Best-Fit: Allocates jobs to the smallest partition that fits
• Comprehensive Performance Metrics:
  • Throughput (jobs processed per time unit)
  • Storage utilization statistics
  • Waiting queue length analysis
  • Average waiting time
  • Internal fragmentation measurements

System Requirements

• C compiler (GCC recommended)
• Standard C libraries
• Unix-like environment (Linux, macOS) or Windows with MinGW/Cygwin

Installation

# Clone the repository
git clone https://github.com/yourusername/batch-memory-allocation-simulator.git
cd batch-memory-allocation-simulator

# Compile the program
gcc -o simulator memory_simulator.c -lm

# Run the simulation
./simulator

Usage

Running First-Fit Simulation

./simulator --strategy first-fit --jobs jobs.txt --memory memory.txt

Running Best-Fit Simulation

./simulator --strategy best-fit --jobs jobs.txt --memory memory.txt

Input File Formats

Memory Partitions File (memory.txt):

partition_id, start_address, size
1, 0, 5000
2, 5000, 10000
3, 15000, 15000
...

Job Stream File (jobs.txt):

job_id, arrival_time, memory_required, cpu_time
1, 0, 4500, 10
2, 2, 8000, 15
3, 5, 12000, 8
...

Performance Metrics

The simulator outputs the following metrics for each strategy:

1. Throughput

• Total jobs completed per time unit
• Completion rate over simulation period

2. Storage Utilization

• Percentage of partitions never used
• Percentage of partitions heavily used (>75% of time)
• Average partition utilization

3. Queue Statistics

• Maximum queue length
• Average queue length
• Queue length over time

4. Waiting Time

• Average waiting time per job
• Maximum waiting time
• Waiting time distribution

5. Internal Fragmentation

• Total wasted memory across all allocations
• Average fragmentation per partition
• Fragmentation percentage

How It Works

Event-Driven Architecture

The simulator operates on three main event types:

1. Job Arrival Event: New job enters the system

   • Check for available partition
   • Allocate if possible, otherwise add to waiting queue

2. Job Completion Event: Running job finishes

   • Free the partition
   • Check waiting queue for next job to allocate

3. Time Tick Event: Advance simulation clock

   • Update job execution times
   • Update waiting times for queued jobs

Conflict Resolution (FCFS)

When multiple jobs are waiting and a partition becomes available:

• Jobs are served strictly in First-Come, First-Served (FCFS) order
• The job at the front of the queue is evaluated first
• If it doesn't fit, the next job in queue is checked
• Process continues until a fitting job is found or queue is exhausted

Clock Management

Job Clocks: Track CPU time consumed by each running job

• Initialized to 0 when job starts
• Incremented each time unit
• Job completes when clock reaches requested CPU time

Wait Clocks: Track time spent in waiting queue

• Start counting when job enters queue
• Stop when job is allocated to a partition
• Used for waiting time statistics

Sample Output

=== FIRST-FIT SIMULATION RESULTS ===
Total Simulation Time: 1000 time units
Jobs Completed: 87
Throughput: 0.087 jobs/time unit

Storage Utilization:
  - Never Used: 10% (2 partitions)
  - Lightly Used (<25%): 15% (3 partitions)
  - Moderately Used (25-75%): 45% (9 partitions)
  - Heavily Used (>75%): 30% (6 partitions)

Queue Statistics:
  - Maximum Queue Length: 12 jobs
  - Average Queue Length: 4.3 jobs
  
Waiting Time:
  - Average: 23.5 time units
  - Maximum: 87 time units

Internal Fragmentation:
  - Total: 45,230 memory units wasted
  - Average per allocation: 520 units
  - Percentage: 18.2%

Analysis and Conclusions

Key Findings

Based on simulation results:

First-Fit Advantages:

• Faster allocation (O(n) worst case)
• Better for large jobs
• More predictable performance

Best-Fit Advantages:

• Better memory utilization
• Lower internal fragmentation
• More efficient for varied job sizes

Recommendations

1. For homogeneous workloads: First-Fit often performs comparably with less overhead
2. For heterogeneous workloads: Best-Fit typically yields better utilization
3. For time-critical systems: First-Fit provides more consistent allocation times
4. For memory-constrained systems: Best-Fit maximizes memory efficiency

Note: Results are workload-dependent. Run simulations with your specific job mix for accurate recommendations.

Project Structure

batch-memory-allocation-simulator/
│
├── src/
│   ├── memory_simulator.c      # Main simulation engine
│   ├── event_queue.c            # Event management
│   ├── partition_manager.c     # Memory partition handling
│   └── statistics.c             # Performance metrics calculation
│
├── include/
│   ├── simulator.h
│   ├── event_queue.h
│   ├── partition_manager.h
│   └── statistics.h
│
├── data/
│   ├── memory.txt               # Sample memory configuration
│   └── jobs.txt                 # Sample job stream
│
├── results/
│   ├── first_fit_results.txt
│   └── best_fit_results.txt
│
├── docs/
│   └── design_document.md
│
├── tests/
│   └── test_simulator.c
│
├── Makefile
├── README.md
└── LICENSE

Contributing

Contributions are welcome! Please follow these steps:

1. Fork the repository
2. Create a feature branch (git checkout -b feature/improvement)
3. Commit your changes (git commit -am 'Add new feature')
4. Push to the branch (git push origin feature/improvement)
5. Create a Pull Request

Future Enhancements

• Implement Worst-Fit allocation strategy
• Add Next-Fit algorithm
• Support dynamic partition creation
• Add visualization of memory usage over time
• Implement priority-based scheduling
• Add support for job preemption
• Create web-based visualization dashboard

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

• Based on classical operating systems memory management concepts
• Inspired by fixed-partition multiprogramming systems from batch-processing era
• Educational project for understanding memory allocation strategies

References

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.)
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems (4th ed.)

Contact

For questions or suggestions, please open an issue or contact [your-email@example.com]

---

Note: This is an educational simulation and does not represent production-quality memory management systems.