#include <iostream>
#include <random>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
 
struct Process
{
    int pid;
    double arrival_time;
    double service_time;
};
struct Event
{
    int type;
    double time;
    Event* nextEvent;
};
double exponential(double lambda) // Generate Exponential Random Variable
{
    double u = (rand() + 1.0) / (RAND_MAX + 1.0); // Add 1 to avoid division by zero
    double exp = -log(u) / lambda; // Calculate - ln(U) / lambda
    return exp;
}
void sched_event(int type, double time, Event*& eq_head) {
    Event* e = new Event{type, time, nullptr};
 
    if (!eq_head || time < eq_head->time) 
    {
        e->nextEvent = eq_head;
        eq_head = e;
    } 
    else 
    {
        Event* cur = eq_head;
        while (cur->nextEvent && cur->nextEvent->time <= time) 
        {
            cur = cur->nextEvent;
        }
        e->nextEvent = cur->nextEvent;
        cur->nextEvent = e;
    }
}
void simulate(int arrival, double service)
{
	cout << "Simulation for lambda = " << arrival << '\n';
    double time = 0;
    int completedProc = 0;
    bool serverIdle = true;
    int readyQueueCount = 0;
    Event* eq_head = NULL;
    sched_event(0, exponential(arrival), eq_head);
    // Performance Metrics and helper variables
    double total_turnaround_time = 0;
    double total_throughput = 0;
    double untilization = 0;
    double avg_proc_rdy_q = 0;
    double busyTime;
    double totalBusy = 0;
    double areaQueue = 0;
    queue<double> arrivals; // arrival queue to maintain arrival times
    while (completedProc < 10000)
    {
        Event* e = eq_head;
        eq_head = eq_head->nextEvent;
        double old_clock = time;
        time = e->time;
        areaQueue += readyQueueCount * (time - old_clock);
        switch (e->type)
        {
            case 0:
            {
            	arrivals.push(time);
                sched_event(0,time+exponential(arrival),eq_head);
                if (serverIdle)
                {
                    serverIdle = false;
                    busyTime = time;
                    sched_event(1,time+exponential(1.0/service),eq_head);
                }
                else
                {
                    readyQueueCount++;
                }
                break;
            }
            case 1:
            {
                total_turnaround_time+= time - arrivals.front();
                arrivals.pop();
                completedProc++;
                if (readyQueueCount == 0)
                {
                    serverIdle = true;
                    totalBusy += time - busyTime;
                }
                else
                {
                    readyQueueCount--;
                    sched_event(1,time+exponential(1.0/service),eq_head);
                }
                break;
            }
        }
        delete(e);
    }
    if (readyQueueCount > 0) 
    // if CPU is busy as when 10000th process is completed
    // appropriately calculate busyTime
    {
    	totalBusy += time - busyTime;
    }
    cout << "Average Turnaround Time: " << total_turnaround_time / 10000.0 << '\n';
    cout << "Throughput: " << 10000.0 / time << '\n';
    cout << "CPU Utilization: " << totalBusy / time << '\n';
    cout << "Average # Processes in Ready Queue: " << areaQueue / time << '\n';
}
int main()
{
	// do 21 runs from lambda = 10 to lambda = 30
    int lambda = 10;
    double SERVICE_TIME = 0.04;
    while (lambda <= 30)
    {
    	simulate(lambda,SERVICE_TIME);
    	lambda++;
    }
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgUHJvY2Vzcwp7CiAgICBpbnQgcGlkOwogICAgZG91YmxlIGFycml2YWxfdGltZTsKICAgIGRvdWJsZSBzZXJ2aWNlX3RpbWU7Cn07CnN0cnVjdCBFdmVudAp7CiAgICBpbnQgdHlwZTsKICAgIGRvdWJsZSB0aW1lOwogICAgRXZlbnQqIG5leHRFdmVudDsKfTsKZG91YmxlIGV4cG9uZW50aWFsKGRvdWJsZSBsYW1iZGEpIC8vIEdlbmVyYXRlIEV4cG9uZW50aWFsIFJhbmRvbSBWYXJpYWJsZQp7CiAgICBkb3VibGUgdSA9IChyYW5kKCkgKyAxLjApIC8gKFJBTkRfTUFYICsgMS4wKTsgLy8gQWRkIDEgdG8gYXZvaWQgZGl2aXNpb24gYnkgemVybwogICAgZG91YmxlIGV4cCA9IC1sb2codSkgLyBsYW1iZGE7IC8vIENhbGN1bGF0ZSAtIGxuKFUpIC8gbGFtYmRhCiAgICByZXR1cm4gZXhwOwp9CnZvaWQgc2NoZWRfZXZlbnQoaW50IHR5cGUsIGRvdWJsZSB0aW1lLCBFdmVudComIGVxX2hlYWQpIHsKICAgIEV2ZW50KiBlID0gbmV3IEV2ZW50e3R5cGUsIHRpbWUsIG51bGxwdHJ9OwoKICAgIGlmICghZXFfaGVhZCB8fCB0aW1lIDwgZXFfaGVhZC0+dGltZSkgCiAgICB7CiAgICAgICAgZS0+bmV4dEV2ZW50ID0gZXFfaGVhZDsKICAgICAgICBlcV9oZWFkID0gZTsKICAgIH0gCiAgICBlbHNlIAogICAgewogICAgICAgIEV2ZW50KiBjdXIgPSBlcV9oZWFkOwogICAgICAgIHdoaWxlIChjdXItPm5leHRFdmVudCAmJiBjdXItPm5leHRFdmVudC0+dGltZSA8PSB0aW1lKSAKICAgICAgICB7CiAgICAgICAgICAgIGN1ciA9IGN1ci0+bmV4dEV2ZW50OwogICAgICAgIH0KICAgICAgICBlLT5uZXh0RXZlbnQgPSBjdXItPm5leHRFdmVudDsKICAgICAgICBjdXItPm5leHRFdmVudCA9IGU7CiAgICB9Cn0Kdm9pZCBzaW11bGF0ZShpbnQgYXJyaXZhbCwgZG91YmxlIHNlcnZpY2UpCnsKCWNvdXQgPDwgIlNpbXVsYXRpb24gZm9yIGxhbWJkYSA9ICIgPDwgYXJyaXZhbCA8PCAnXG4nOwogICAgZG91YmxlIHRpbWUgPSAwOwogICAgaW50IGNvbXBsZXRlZFByb2MgPSAwOwogICAgYm9vbCBzZXJ2ZXJJZGxlID0gdHJ1ZTsKICAgIGludCByZWFkeVF1ZXVlQ291bnQgPSAwOwogICAgRXZlbnQqIGVxX2hlYWQgPSBOVUxMOwogICAgc2NoZWRfZXZlbnQoMCwgZXhwb25lbnRpYWwoYXJyaXZhbCksIGVxX2hlYWQpOwogICAgLy8gUGVyZm9ybWFuY2UgTWV0cmljcyBhbmQgaGVscGVyIHZhcmlhYmxlcwogICAgZG91YmxlIHRvdGFsX3R1cm5hcm91bmRfdGltZSA9IDA7CiAgICBkb3VibGUgdG90YWxfdGhyb3VnaHB1dCA9IDA7CiAgICBkb3VibGUgdW50aWxpemF0aW9uID0gMDsKICAgIGRvdWJsZSBhdmdfcHJvY19yZHlfcSA9IDA7CiAgICBkb3VibGUgYnVzeVRpbWU7CiAgICBkb3VibGUgdG90YWxCdXN5ID0gMDsKICAgIGRvdWJsZSBhcmVhUXVldWUgPSAwOwogICAgcXVldWU8ZG91YmxlPiBhcnJpdmFsczsgLy8gYXJyaXZhbCBxdWV1ZSB0byBtYWludGFpbiBhcnJpdmFsIHRpbWVzCiAgICB3aGlsZSAoY29tcGxldGVkUHJvYyA8IDEwMDAwKQogICAgewogICAgICAgIEV2ZW50KiBlID0gZXFfaGVhZDsKICAgICAgICBlcV9oZWFkID0gZXFfaGVhZC0+bmV4dEV2ZW50OwogICAgICAgIGRvdWJsZSBvbGRfY2xvY2sgPSB0aW1lOwogICAgICAgIHRpbWUgPSBlLT50aW1lOwogICAgICAgIGFyZWFRdWV1ZSArPSByZWFkeVF1ZXVlQ291bnQgKiAodGltZSAtIG9sZF9jbG9jayk7CiAgICAgICAgc3dpdGNoIChlLT50eXBlKQogICAgICAgIHsKICAgICAgICAgICAgY2FzZSAwOgogICAgICAgICAgICB7CiAgICAgICAgICAgIAlhcnJpdmFscy5wdXNoKHRpbWUpOwogICAgICAgICAgICAgICAgc2NoZWRfZXZlbnQoMCx0aW1lK2V4cG9uZW50aWFsKGFycml2YWwpLGVxX2hlYWQpOwogICAgICAgICAgICAgICAgaWYgKHNlcnZlcklkbGUpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc2VydmVySWRsZSA9IGZhbHNlOwogICAgICAgICAgICAgICAgICAgIGJ1c3lUaW1lID0gdGltZTsKICAgICAgICAgICAgICAgICAgICBzY2hlZF9ldmVudCgxLHRpbWUrZXhwb25lbnRpYWwoMS4wL3NlcnZpY2UpLGVxX2hlYWQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJlYWR5UXVldWVDb3VudCsrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY2FzZSAxOgogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB0b3RhbF90dXJuYXJvdW5kX3RpbWUrPSB0aW1lIC0gYXJyaXZhbHMuZnJvbnQoKTsKICAgICAgICAgICAgICAgIGFycml2YWxzLnBvcCgpOwogICAgICAgICAgICAgICAgY29tcGxldGVkUHJvYysrOwogICAgICAgICAgICAgICAgaWYgKHJlYWR5UXVldWVDb3VudCA9PSAwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHNlcnZlcklkbGUgPSB0cnVlOwogICAgICAgICAgICAgICAgICAgIHRvdGFsQnVzeSArPSB0aW1lIC0gYnVzeVRpbWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmVhZHlRdWV1ZUNvdW50LS07CiAgICAgICAgICAgICAgICAgICAgc2NoZWRfZXZlbnQoMSx0aW1lK2V4cG9uZW50aWFsKDEuMC9zZXJ2aWNlKSxlcV9oZWFkKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGRlbGV0ZShlKTsKICAgIH0KICAgIGlmIChyZWFkeVF1ZXVlQ291bnQgPiAwKSAKICAgIC8vIGlmIENQVSBpcyBidXN5IGFzIHdoZW4gMTAwMDB0aCBwcm9jZXNzIGlzIGNvbXBsZXRlZAogICAgLy8gYXBwcm9wcmlhdGVseSBjYWxjdWxhdGUgYnVzeVRpbWUKICAgIHsKICAgIAl0b3RhbEJ1c3kgKz0gdGltZSAtIGJ1c3lUaW1lOwogICAgfQogICAgY291dCA8PCAiQXZlcmFnZSBUdXJuYXJvdW5kIFRpbWU6ICIgPDwgdG90YWxfdHVybmFyb3VuZF90aW1lIC8gMTAwMDAuMCA8PCAnXG4nOwogICAgY291dCA8PCAiVGhyb3VnaHB1dDogIiA8PCAxMDAwMC4wIC8gdGltZSA8PCAnXG4nOwogICAgY291dCA8PCAiQ1BVIFV0aWxpemF0aW9uOiAiIDw8IHRvdGFsQnVzeSAvIHRpbWUgPDwgJ1xuJzsKICAgIGNvdXQgPDwgIkF2ZXJhZ2UgIyBQcm9jZXNzZXMgaW4gUmVhZHkgUXVldWU6ICIgPDwgYXJlYVF1ZXVlIC8gdGltZSA8PCAnXG4nOwp9CmludCBtYWluKCkKewoJLy8gZG8gMjEgcnVucyBmcm9tIGxhbWJkYSA9IDEwIHRvIGxhbWJkYSA9IDMwCiAgICBpbnQgbGFtYmRhID0gMTA7CiAgICBkb3VibGUgU0VSVklDRV9USU1FID0gMC4wNDsKICAgIHdoaWxlIChsYW1iZGEgPD0gMzApCiAgICB7CiAgICAJc2ltdWxhdGUobGFtYmRhLFNFUlZJQ0VfVElNRSk7CiAgICAJbGFtYmRhKys7CiAgICB9Cn0K