操作系统实验 FCFS（先来先服务），HRRN（高响应比）

可能有错误或伪算法

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <windows.h>
#include <ctime>
#include <random>

#define out(x) cout << #x << ":\t" << x << endl
#define out2(x) cout << #x << ":\t"
#define nullptr 0

using namespace std;

/*输出指针控制*/
void gotoxy(int _x, int _y){
    COORD pos = {_x, _y};
    HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(hOut, pos);
}

class JCB{

public:

    string name;
    char statement = 'w';
    float priorityLevel = 0;
    int arrivalTime;
    int needTime;
    int usedTime = 0;
    int finTime = 0;
    int waitTime = 0;

    /*需要资源种类及数量,此处暂时没用*/
    vector<int> resource;

    JCB *next = nullptr;

    /*重载运算符以调用排序函数*/
    bool operator <(const JCB & _q) const{
        /*动态数组尾部为最大权值最小剩余服务时间*/
        if(priorityLevel != _q.priorityLevel)
            return priorityLevel < _q.priorityLevel;
        return (needTime-usedTime) > (_q.needTime-_q.usedTime);
    }

    void updateprio(){
        priorityLevel = 1.0+(float)(waitTime)/needTime;
    }

    void print(){
    	printf("-----------------\n");
        out(name);
        out(statement);
        out(priorityLevel);
        out(arrivalTime);
        out(needTime);
        out(usedTime);
        out(finTime);
        puts("");
		return ;
    }

	void print2(){
		printf("-----------------\n");
        out(name);
        out(statement);
        out(arrivalTime);
        out(needTime);
        out(finTime);
		return ;
	}
};


/*先来先服务*/
class FCFS{

public:
	/*进程数量，资源类数量*/
	int N, resourceNum = 0;

	/*资源名称*/
	vector<string> resourceName;
	vector<int> resourceCount;

	/*完成队列，就绪队列，运行队列，未到达队列*/
	JCB *finhead = nullptr, *readyhead = nullptr,
 		*running = nullptr, *notarrival = nullptr;

	/*就绪队尾*/
    JCB *readytail = nullptr;

	/*插入未到达队列*/
	void insertarrival(JCB *p){
		JCB *now, *nowf;
	    nowf = nullptr;
	    now = notarrival;
		while (now != nullptr){
			if (now->arrivalTime < p->arrivalTime){
	        	nowf = now;
	        	now = now->next;
			}else break;
		}

		if (nowf == nullptr){
	    	p->next = notarrival;
	    	notarrival = p;
		}else{
			p->next = nowf->next;
			nowf->next = p;
		}

		return ;
	}

	/*插入就绪队列*/
	void insertready(JCB *p){
	    p->next = nullptr;

	    if(readyhead == nullptr){
            readyhead = p;
            readytail = p;
	    }else{
            readytail->next = p;
            readytail = readytail->next;
	    }
	    return ;
	}

	/*JCB队列信息输出*/
	void information(){
	    JCB *p;
	    cout << "---------\nnotarrival:\n";
	    p = notarrival;
	    while (p != nullptr){
	    	p->print();
	    	p = p->next;
		}

		cout << "---------\nreadyhead:\n";
	    p = readyhead;
	    while(p != nullptr){
	        p->print();
	        p = p->next;
	    }

	    cout << "---------\nrunning:\n";
	    p = running;
	    while(p != nullptr){
	        p->print();
	        p = p->next;
	    }

	    cout << "---------\nfinhead:\n";
	    p = finhead;
	    while (p != nullptr){
	        p->print();
	        p = p->next;

	    }

	    cout << "---------\nnowresource:\n";
	    for (int i = 0; i < resourceNum; i++){
            cout << resourceName[i] << ":\t" << resourceCount[i] << endl;
	    }

	    return ;
	}

    /*JCB清空*/
	void clear(){
	    JCB *p,*nxt;

	    p = notarrival;
	    while (p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
		}

	    p = readyhead;
	    while(p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
	    }

	    p = running;
	    while(p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
	    }

	    p = finhead;
	    while (p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
	    }
	    finhead = nullptr, readyhead = nullptr,
		running = nullptr, notarrival = nullptr;

        resourceName.clear();
        resourceCount.clear();
        N = 0;
        resourceNum = 0;

	    return ;
	}

	/*建表*/
	void makelist(){

        cout << "please input N:" << endl;
        cin >> N;

        cout << "please input resourceNum:" << endl;
        cin >> resourceNum;

        cout << "please input resourceName&Count:" << endl;
        for (int i = 0; i < resourceNum; i++){
            cout << "#" << i << ":\n";
            string rs;
            cin >> rs;
            resourceName.push_back(rs);
            int rc;
            cin >> rc;
            resourceCount.push_back(rc);
        }

	    JCB *p;

	    for (int i = 1; i <= N; i++){
	        p = new JCB;
			cout << "input name:";
			cin >> p->name ;
			cout << "input needTime:";
			cin >> p->needTime ;
			cout << "input arrivalTime:";
			cin >> p->arrivalTime;


	        for (int j = 0; j < resourceNum; j++){
                int r;
                cin >> r;
                p->resource.push_back(r);
	        }

	        if (p->arrivalTime == 0){
	                insertready(p);
	        }else{
	        	if (notarrival != nullptr){
	                insertarrival(p);
	            }
	            else{
	                notarrival = p;
	            }
			}
			p->print();
	    }

		if (readyhead != nullptr){
		    running = readyhead;
		    readyhead = readyhead->next;
		    running->statement = 'r';
		    running->next = nullptr;
		    for (int i=0; i<resourceNum; i++){
                resourceCount[i] -= running->resource[i];
		    }
		}

	    return ;
	}

	/*运行完成信息*/
	void after_run(){

	    cout << endl << "after_run:" << endl;

		JCB *p = finhead;
		int cnt = 0;
		float wsum = 0.0;
		int ssum = 0;

		while (p != nullptr){
			int stayTime = p->finTime - p->arrivalTime;
			float weigthTime = (float)stayTime / p->needTime;
			p->print2();
			out(stayTime);
			out2(weigthTime);printf("%.2f\n",weigthTime);

			ssum += stayTime;
			wsum += weigthTime;
			cnt++;
			puts("");
			p = p->next;
		}

		float averageStayTime = (float)ssum / cnt;
		float averageWeigthTime = wsum / cnt;

		out2(averageStayTime);printf("%.2f\n",averageStayTime);
		out2(averageWeigthTime);printf("%.2f\n",averageWeigthTime);

		return ;
	}

	/*运行程序*/
	void run(){
		JCB *p;
		int runtime = 0;
		while (running != nullptr || notarrival != nullptr){
            runtime++;
            if(running != nullptr){
                running->usedTime++;
                if (running->usedTime == running->needTime){
                    running->next = finhead;
                    running->statement = 'f';
                    running->finTime = runtime;
                    finhead = running;
					for (int i=0; i<resourceNum; i++){
						resourceCount[i] += running->resource[i];
					}
                    running = nullptr;
                }
            }

            JCB *p;

            p = notarrival;
            while (p != nullptr){
                if (p->arrivalTime <= runtime){
                    notarrival = p->next;
                    insertready(p);
                    p = notarrival;
                }
                else
                    break;
            }

			if(running == nullptr){
                if(readyhead != nullptr){
                    running = readyhead;
                    readyhead = readyhead->next;
                    running->statement = 'r';
                    running->next = nullptr;
					for (int i=0; i<resourceNum; i++){
						resourceCount[i] -= running->resource[i];
					}
                }
            }

            system("cls");
            //gotoxy(0,0);
            cout << endl << "##RUNTIME: " << runtime << endl;information();
            Sleep(1000);

		}

		after_run();

		return ;
	}
};

/*高响应比*/
class HRRN{

public:
	/*进程数量，资源类数量*/
	int N, resourceNum = 0;

	/*资源名称*/
	vector<string> resourceName;
	vector<int> resourceCount;

	/*完成队列，运行队列，未到达队列*/
	JCB *finhead = nullptr,
 		*running = nullptr, *notarrival = nullptr;

	/*就绪数组*/
    vector<JCB> readylist;

	/*插入未到达队列*/
	void insertarrival(JCB *p){
		JCB *now, *nowf;
	    nowf = nullptr;
	    now = notarrival;
		while (now != nullptr){
			if (now->arrivalTime < p->arrivalTime){
	        	nowf = now;
	        	now = now->next;
			}else break;
		}

		if (nowf == nullptr){
	    	p->next = notarrival;
	    	notarrival = p;
		}else{
			p->next = nowf->next;
			nowf->next = p;
		}

		return ;
	}

	/*JCB队列信息输出*/
	void information(){
	    JCB *p;
	    cout << "---------\nnotarrival:\n";
	    p = notarrival;
	    while (p != nullptr){
	    	p->print();
	    	p = p->next;
		}

		cout << "---------\nreadylist:\n";
	    for(JCB o:readylist){
            o.print();
	    }

	    cout << "---------\nrunning:\n";
	    p = running;
	    while(p != nullptr){
	        p->print();
	        p = p->next;
	    }

	    cout << "---------\nfinhead:\n";
	    p = finhead;
	    while (p != nullptr){
	        p->print();
	        p = p->next;

	    }

	    cout << "---------\nnowresource:\n";
	    for (int i = 0; i < resourceNum; i++){
            cout << resourceName[i] << ":\t" << resourceCount[i] << endl;
	    }

	    return ;
	}

    /*JCB清空*/
	void clear(){
	    JCB *p,*nxt;

	    p = notarrival;
	    while (p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
		}


	    p = running;
	    while(p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
	    }

	    p = finhead;
	    while (p != nullptr){
	    	nxt = p->next;
	    	delete p;
	    	p = nxt;
	    }
	    finhead = nullptr,
		running = nullptr, notarrival = nullptr;

        resourceName.clear();
        resourceCount.clear();
        readylist.clear();
        N = 0;
        resourceNum = 0;

	    return ;
	}

	/*建表*/
	void makelist(){

        cout << "please input N:" << endl;
        cin >> N;

        cout << "please input resourceNum:" << endl;
        cin >> resourceNum;

        cout << "please input resourceName&Count:" << endl;
        for (int i = 0; i < resourceNum; i++){
            cout << "#" << i << ":\n";
            string rs;
            cin >> rs;
            resourceName.push_back(rs);
            int rc;
            cin >> rc;
            resourceCount.push_back(rc);
        }

	    JCB *p;

	    for (int i = 1; i <= N; i++){
	        p = new JCB;
			cout << "input name:";
			cin >> p->name ;
			cout << "input needTime:";
			cin >> p->needTime ;
			cout << "input arrivalTime:";
			cin >> p->arrivalTime;

			p->priorityLevel = 1.0;

	        for (int j = 0; j < resourceNum; j++){
                int r;
                cin >> r;
                p->resource.push_back(r);
	        }

			p->print();

	        if (p->arrivalTime == 0){
                readylist.push_back(*p);
                delete p;
	        }else{
	        	if (notarrival != nullptr){
	                insertarrival(p);
	            }
	            else{
	                notarrival = p;
	            }
			}
	    }

	    sort(readylist.begin(),readylist.end());

		if (readylist.size() > 0){
            p = new JCB;
            *p = readylist[readylist.size()-1];
            readylist.pop_back();
		    running = p;
		    running->statement = 'r';
		    running->next = nullptr;
		    for (int i=0; i<resourceNum; i++){
                resourceCount[i] -= running->resource[i];
		    }
		}

	    return ;
	}

	/*运行完成信息*/
	void after_run(){

	    cout << endl << "after_run:" << endl;

		JCB *p = finhead;
		int cnt = 0;
		float wsum = 0.0;
		int ssum = 0;

		while (p != nullptr){
			int stayTime = p->finTime - p->arrivalTime;
			float weigthTime = (float)stayTime / p->needTime;
			p->print2();
			out(stayTime);
			out2(weigthTime);printf("%.2f\n",weigthTime);

			ssum += stayTime;
			wsum += weigthTime;
			cnt++;
			puts("");
			p = p->next;
		}

		float averageStayTime = (float)ssum / cnt;
		float averageWeigthTime = wsum / cnt;

		out2(averageStayTime);printf("%.2f\n",averageStayTime);
		out2(averageWeigthTime);printf("%.2f\n",averageWeigthTime);

		return ;
	}

	/*运行程序*/
	void run(){
		JCB *p;
		int runtime = 0;
		while (running != nullptr || notarrival != nullptr){
            runtime++;
            if(running != nullptr){
                running->usedTime++;
                if (running->usedTime == running->needTime){
                    running->next = finhead;
                    running->statement = 'f';
                    running->finTime = runtime;
                    finhead = running;
					for (int i=0; i<resourceNum; i++){
						resourceCount[i] += running->resource[i];
					}
                    running = nullptr;
                }
                if(running != nullptr)
                    running->updateprio();
            }

            for(JCB &o:readylist){
                o.waitTime++;
                o.updateprio();
            }
            if(readylist.size())
                sort(readylist.begin(),readylist.end());

            JCB *p;

            p = notarrival;
            while (p != nullptr){
                if (p->arrivalTime <= runtime){
                    notarrival = p->next;
                    p->next = nullptr;
                    readylist.push_back(*p);
                    sort(readylist.begin(),readylist.end());
                    delete p;
                    p = notarrival;
                }
                else
                    break;
            }

			if(running == nullptr){
                if (readylist.size() > 0){
                    p = new JCB;
                    *p = readylist[readylist.size()-1];
                    readylist.pop_back();
                    running = p;
                    running->statement = 'r';
                    running->next = nullptr;
                    for (int i=0; i<resourceNum; i++){
                        resourceCount[i] -= running->resource[i];
                    }
                }
            }else{
                if (readylist.size() > 0 &&
                    readylist[readylist.size()-1].priorityLevel > running->priorityLevel)
                {
                    p = new JCB;
                    *p = readylist[readylist.size()-1];
                    readylist.pop_back();
                    running->statement = 'w';
                    for (int i=0; i<resourceNum; i++){
                        resourceCount[i] += running->resource[i];
                    }
                    readylist.push_back(*running);
                    delete running;

                    running = p;
                    running->statement = 'r';
                    running->next = nullptr;
                    for (int i=0; i<resourceNum; i++){
                        resourceCount[i] -= running->resource[i];
                    }
                }
            }

            system("cls");
            //gotoxy(0,0);
            cout << endl << "##RUNTIME: " << runtime << endl;information();
            Sleep(1000);

		}

		after_run();

		return ;
	}
};


int main(){
    //freopen("a.txt","r",stdin);

    FCFS runner;

    runner.makelist();

	runner.run();

    return 0;
}