alexander Posted October 26, 2007 Report Posted October 26, 2007 This simulates 4 job management algorithms at run time. It's actually far from the most efficient way of doing everything, but after being up for 36 hours, i am turning this code as-is for the assignment. Considering that this is still over a thousand of lines shorter then the next closest programs i've seen, i think it's definitely on the more officient of the programs written in this OS class. So, here's the code //use the following line to compile the code: g++ -o ui ui.cpp #include <iostream> #include <cstdio> #include <cstdlib> #include <list> using namespace std; #define catch_err(x) { if(!(x)) { cout << "An invalid value has been enteredn"; exit(1); } } class Job { private: int job_id; //job id int time_to_exec; //time it takes for the job to execute bool inuse; //is this job being ran? int time_in; //when does the job come in? int wait_time; //wait time of the job public: Job(); //constructor Job(int, int, int); //overloaded constructor with assignment void set_wait_time(int); //method to change wait time void set_wait_time(); //method to increase waiting time void change_state(); //method to change the state from active to inactive job bool state(); //returns current state (0 being not executing) void set_time_to_exec(int); //set time to execute (just in case we need to edit) void set_time_in(int); //set time the job enters (once again in case we need it) void set_job_id(int); //edit the job ID void dec_exec_time(); //decrement the execution time bool operator<(Job&); //overloaded < operator for easiness of comparison bool operator>(Job&); //overloaded > operator bool operator==(Job&); //overloaded == operator bool operator!=(Job&); //overloaded != operator Job& operator=(Job&); //this is the fun one, the = operator overload int show_time_in() {return time_in;} //method to display time in int show_time_to_exec() {return time_to_exec;} //method to display time to execute int show_job_id() {return job_id;} //method to display the job ID int show_wait_time() {return wait_time;} //method to display wait time bool empty(); //this is to check if the job is empty void clear(); //reset the job values to defaults }; Job::Job() //constructor that initializes everything to zero { job_id=0; time_to_exec=0; inuse = false; time_in = 0; wait_time = 0; }; Job::Job(int id, int tte, int ti) //constructor, init the two values we want from the input menu { if (tte >= 0) { time_to_exec = tte; //time to execute should be positive } else { time_to_exec = 0; //or 0 } if (ti >= 0) { time_in = ti; //time the job enters should be positive } else { time_in=0; //or zero } if (id >= 0) { job_id=id; //job id should not be less then zero } else { job_id=0; //or zero } inuse=false; //when we are setting up the program is not being used wait_time=0; //and since the simulation hasnt started, our wait time = 0 }; bool Job::operator<(Job& :hihi: //juse a comparison operator overload { if(time_to_exec < b.show_time_to_exec() && job_id<b.show_time_in() && time_in < b.show_time_in() && wait_time < b.show_wait_time() && inuse < b.state()) { return true; } if(time_to_exec < b.show_time_to_exec() && job_id<b.show_time_in() && time_in < b.show_time_in() && wait_time < b.show_wait_time()) { return true; } if(time_to_exec < b.show_time_to_exec() && job_id<b.show_time_in() && time_in < b.show_time_in()) { return true; } if(time_to_exec < b.show_time_to_exec() && job_id<b.show_time_in()) { return true; } if(time_to_exec < b.show_time_to_exec()) { return true; } return false; }; bool Job::operator>(Job& :applause: { if(time_to_exec > b.show_time_to_exec() && job_id > b.show_time_in() && time_in > b.show_time_in() && wait_time > b.show_wait_time() && inuse > b.state()) { return true; } if(time_to_exec > b.show_time_to_exec() && job_id > b.show_time_in() && time_in > b.show_time_in() && wait_time > b.show_wait_time()) { return true; } if(time_to_exec > b.show_time_to_exec() && job_id > b.show_time_in() && time_in > b.show_time_in()) { return true; } if(time_to_exec > b.show_time_to_exec() && job_id > b.show_time_in()) { return true; } if(time_to_exec > b.show_time_to_exec()) { return true; } return false; }; bool Job::operator==(Job& :applause: { if(time_to_exec == b.show_time_to_exec() && job_id == b.show_time_in() && time_in == b.show_time_in() && wait_time == b.show_wait_time() && inuse == b.state()) { return true; } if(time_to_exec == b.show_time_to_exec() && job_id == b.show_time_in() && time_in == b.show_time_in() && wait_time == b.show_wait_time()) { return true; } if(time_to_exec == b.show_time_to_exec() && job_id == b.show_time_in() && time_in == b.show_time_in()) { return true; } if(time_to_exec == b.show_time_to_exec() && job_id == b.show_time_in()) { return true; } if(time_to_exec == b.show_time_to_exec()) { return true; } return false; }; bool Job::operator!=(Job& { if(time_to_exec != b.show_time_to_exec()) { return true; } else { return false; } }; Job& Job::operator=(Job& :phones: //assignment operator overload { if (this != & { job_id = b.show_job_id(); time_to_exec = b.show_time_to_exec(); inuse = b.state(); time_in = b.show_time_in(); wait_time = b.wait_time; } return *this; }; void Job::change_state()//method to change the state from active to inactive job { inuse^=1; //xor of our current use state and one }; void Job::set_wait_time() //method to increase waiting time { wait_time++; }; void Job::set_wait_time(int time)//method to actually set the time to an integer { if(time>0) { wait_time+=time; } else { wait_time=0; } return; }; void Job::dec_exec_time() { if(time_to_exec > 0) { time_to_exec-=1; } else { time_to_exec=0; } return; }; bool Job::state() //returns current state (0 being not executing) { return inuse; }; void Job::set_time_to_exec(int tte) //set time to execute (just in case we need to edit) { if(tte >= 0) { time_to_exec=tte; } else { time_to_exec=0; } return; }; void Job::set_time_in(int ti) //set time the job enters (once again in case we need it) { if(ti >= 0) { time_in=ti; } else { time_in=0; } return; }; void Job::set_job_id(int id) { if(id >= 0) { job_id=id; } else { job_id=0; } return; }; bool Job::empty() { if(job_id==0 && time_in==0 && time_to_exec==0 && inuse==false && wait_time==0) { return true; } else { return false; } }; void Job::clear() { job_id=0; time_to_exec=0; inuse = false; time_in = 0; wait_time = 0; return; }; // wrote this, but never actually had a need to use it, but i figured to leave the code here nontheless /* Sorts first n elements of array a[] in non-decreasing order. */ /* template<typename T> void merge_sort(T a[], int n) { int i, j, k; T tmp; // For small arrays, insertion sort is much faster if (n < 64) { for (i = 1; i < n; i++) { tmp = a[i]; for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j]; a[j+1] = tmp; } return; } int f = n / 2; // f = number of elements in first half //Recursively sort both halves merge_sort(a, f); merge_sort(a+f, n-f); //Merge T *s = new T[n]; //temporary array to keep the sorted sequence for (i = 0, j = f, k = 0; i < f && j < n;) s[k++] = (a[i] < a[j]) ? a[i++] : a[j++]; while (i < f) s[k++] = a[i++]; while (j < n) s[k++] = a[j++]; for (i = 0; i < n; i++) a[i] = s[i]; delete[] s; } */ //templated check if the array is empty template<typename T>bool isempty(T a[], int n) { for(int i=0; i<=n-1; i++) //iterates through the array if it finds a time in or time to exec, it returns with a false { if(a[i].show_time_to_exec()!=0 || a[i].show_job_id()!=0 || a[i].show_time_in()!=0) { return false; } } return true; } //not templated check for active jobs template<typename T>int check_active_jobs(T a[], int max) { for(int i=0; i<=max-1; i++) { if(a[i].state()==true) { return i; } } return -1; //remember you can have a job #0 in an array } /* First In First Out/Shortest job next simulation: Jobs are executed in order that they enter the job queue */ template<typename T> void fifo_sjn_srt_sim(T orig[], int max, int sjn) { T temp[max]; list<T> job_queue; T curr_job; T changer; //this will be used if needed int i=0; int iteration=0; //setup a temporary array of the class we will work with for(i=0; i<=max-1 ;i++) { temp[i]=orig[i]; } //cout << "before the sort:n"; //for (int i = 0; i < max; i++) printf("%d - %dn", i, temp[i].show_time_to_exec()); //return; switch(sjn) { case 2: cout << "*****************************n"; cout << " Running SRT simulation:n"; cout << "*****************************n"; break; case 1: cout << "*****************************n"; cout << " Running SJN simulation:n"; cout << "*****************************n"; break; default: cout << "*****************************n"; cout << " Running the FIFO simulation:n"; cout << "*****************************n"; } while(1) { cout << "Time: " << iteration << "n"; //third rewrite and getting progressively more upset //first lets check if our array is empty, if it is then hey why run at all if(isempty(temp, max) && job_queue.empty() && curr_job.empty()) { cout << "tJob queue is empty, exiting.n"; return; } //by here we know that the job queue is not empty, time to check what's up, do we have an active job? //if(check_active_jobs(temp, max)==-1); //{ // cout << "tNo active Jobs in the queuen"; //} //this is here to go through my array and find jobs ready to enter the queue for(i=0; i<=max-1; i++) { if(temp[i].show_time_in()==iteration) { cout << "tJob " << temp[i].show_job_id() << " is entering the Job Queuen"; job_queue.push_back(temp[i]); temp[i].clear(); /* Thinking this through, i came up with yet another solution, this can do 3 algorithms i just need some checking and preempting */ if(sjn==2) { job_queue.sort(); //if we sort the queue first //and then implement preempt stuff if(job_queue.front()<curr_job) { cout << "tPreempting...n"; changer=job_queue.front(); cout << "tJob " << changer.show_job_id() << " is smaller then job " << curr_job.show_job_id() << "n"; cout << "tJob " << curr_job.show_job_id() << " is now preempted and back in the waiting queuen"; cout << "tJob " << changer.show_job_id() << " is now entering executionn"; curr_job.change_state(); job_queue.pop_front(); job_queue.push_front(curr_job); curr_job=changer; curr_job.change_state(); } } /* the differences between fifo and sjn are so minute that by just declaring sjn as a bool and adding this one line here, i can kill both algorithms in one function! */ if(sjn==1) { job_queue.sort(); } } } if(curr_job.show_time_to_exec()==0 && job_queue.size()>0) //basically if the job is empty pop off the first thing off the queue { curr_job=job_queue.front(); cout << "tJob " << curr_job.show_job_id() << " is entering executionn"; job_queue.pop_front(); curr_job.set_wait_time(iteration - curr_job.show_time_in()); curr_job.change_state(); } else { //cout << "Job " << curr_job.show_job_id() << " executing.n"; curr_job.dec_exec_time(); //decrease the time it's gonna take the job to execute } //when the job is done executing, we need to output what it did if(curr_job.show_time_to_exec()==0 && iteration > 0) { printf("tJob %d finished executing:n tTotal execution time: %dn tWait time: %dn tTurnaround time: %dn", curr_job.show_job_id(), iteration - curr_job.show_wait_time() - curr_job.show_time_in(), curr_job.show_wait_time(), iteration - curr_job.show_time_in()); curr_job.clear(); } iteration++; } return; } /* Round Robin simulation: This algorithm uses predetermine units of time to run processes; this unit is called the time quantum. In this algorithm jobs are run in the order they arrive, but they only run for however long the time quantum allows before being put back into the wait queue. */ template<typename T> void rr_sim(T orig[], int max, int quantum) { T temp[max]; list<T> job_queue; T curr_job; T changer; //this will be used if needed int i=0; int ii=0; int iteration=0; //setup a temporary array of the class we will work with for(i=0; i<=max-1 ;i++) { temp[i]=orig[i]; } //we can set the time quantum here cout << "*****************************n"; cout << " Running RR simulation:n"; cout << "*****************************n"; i=0; while(1) { cout << "Time: " << iteration << "n"; if(isempty(temp, max) && job_queue.empty() && curr_job.empty()) { cout << "tJob queue is empty, exiting.n"; return; } //manages qyanta if(i==quantum && curr_job.show_job_id()!=0) { i=0; cout << "tQuanta cycle timen"; cout << "tPutting job " << curr_job.show_job_id() << " in the back of the queue."; curr_job.change_state(); job_queue.push_back(curr_job); curr_job.empty(); } //this is split because initially you dont want to do the above or else you are going to go out of your mem space if(i==0 && job_queue.size()!=0) { curr_job=job_queue.front(); job_queue.pop_front(); curr_job.change_state(); cout << "Job " << curr_job.show_job_id() << " now executingn"; } //check for jobs entering the queue for(ii=0; ii<=max-1; ii++) { if(temp[ii].show_time_in()==iteration) { cout << "tJob " << temp[ii].show_job_id() << " is entering the Job Queuen"; job_queue.push_back(temp[ii]); temp[ii].clear(); } } if(curr_job.show_time_to_exec()==0 && job_queue.size()>0) //basically if the job is empty pop off the first thing off the queue { curr_job=job_queue.front(); cout << "tJob " << curr_job.show_job_id() << " is entering executionn"; job_queue.pop_front(); curr_job.change_state(); } else { //cout << "Job " << curr_job.show_job_id() << " executing.n"; curr_job.dec_exec_time(); //decrease the time it's gonna take the job to execute } //reporting, notice it's a bit different from the previous sim function if(curr_job.show_time_to_exec()==0 && iteration > 0) { printf("tJob %d finished executing:n tTotal execution time: %dn tWait time: %dn tTurnaround time: %dn", curr_job.show_job_id(), iteration - curr_job.show_wait_time() - curr_job.show_time_in(), curr_job.show_wait_time(), iteration - curr_job.show_time_in()); curr_job.clear(); } iteration++; if(!job_queue.empty() && !curr_job.empty()) { i++; } //this manages wait time (that should be pretty precise, and the reason it's done this way is because the stl list is limited in what it can do and i dont have time to write my own if(!job_queue.empty()) { for(ii=0; ii<=job_queue.size()-1; ii++) { changer=job_queue.front(); job_queue.pop_front(); changer.set_wait_time(); job_queue.push_back(changer); } } } } //walk through the list, and get the size int get_list_size(list<Job> l) { int i = 0; list<Job>::iterator iter; for(iter=l.begin(); iter!=l.end(); ++iter) { i++; } return i; } //this is the p[ause fuction void pause_n() { printf("press "n" key to continue..."); while(1) { if ('n' == getchar()) { break; } } } /* SIMULATION UI */ int main() { list<Job> jobs_queue; Job temp; int id; int exectime; int intime; int i=0; int ii=0; bool duplicate=false; list<Job>::iterator iter; int key = 0; int key_two = 0; //int length; while(key!=3) { system("clear"); cout << "************** Main Menu **************n"; cout << "1) Setup Simulationn"; cout << "2) Run Simulationn"; cout << "3) Exitn"; catch_err(cin >> key); if (key==1) { while(key_two!= 5) { system("clear"); cout << "************** Setup Menu **************n"; cout << "1) Create New Jobn"; cout << "2) View Jobsn"; cout << "3) Edit a Jobn"; cout << "4) Delete a Jobn"; cout << "5) Back to Main Menun"; catch_err(cin >> key_two); if(key_two==1) { duplicate=false; system("clear"); cout << "************** New Job **************n"; cout << "Please enter Job ID: "; catch_err(cin >> id); cout << "nPlease enter the time job will come in: "; catch_err(cin >> intime); cout << "nPlease enter time it will take the job to execute: "; catch_err(cin >> exectime); temp.set_job_id(id); temp.set_time_in(intime); temp.set_time_to_exec(exectime); jobs_queue.push_back(temp); temp.clear(); } if(key_two==2) { cout << "tJob IdttJob SizettTime Inn"; for(iter=jobs_queue.begin(); iter!=jobs_queue.end(); ++iter) { printf("t%dtt%dttt%dn", (*iter).show_job_id(), (*iter).show_time_to_exec(), (*iter).show_time_in()); } pause_n(); } if(key_two==3) { duplicate=false; system("clear"); cout << "************** Edit Job **************n"; cout << "tJob IdttJob SizettTime Inn"; for(iter=jobs_queue.begin(); iter!=jobs_queue.end(); ++iter) { printf("t%dtt%dtt%dn", (*iter).show_job_id(), (*iter).show_time_to_exec(), (*iter).show_time_in()); } cout << "Please enter Job ID: "; catch_err(cin >> id); cout << "nPlease enter the time job will come in: "; catch_err(cin >> intime); cout << "nPlease enter time it will take the job to execute: "; catch_err(cin >> exectime); //this will iterate through the list, reach the number of the one entered, and then edit the values for(iter=jobs_queue.begin(); iter!=jobs_queue.end(); ++iter) { if((*iter).show_job_id()!=id) { continue; } else { (*iter).set_job_id(id); (*iter).set_time_in(intime); (*iter).set_time_to_exec(exectime); duplicate=true; } } //or error out if(!duplicate) { cout << "Job " << id << " not found!"; } } if(key_two==4) { system("clear"); cout << "************** Delete Job **************n"; cout << "tJob IdttJob SizettTime Inn"; i=0; for(iter=jobs_queue.begin(); iter!=jobs_queue.end(); ++iter) { printf("%d)t%dtt%dtt%dn", i,(*iter).show_job_id(), (*iter).show_time_to_exec(), (*iter).show_time_in()); i++; } cout << "Please enter line to delete: "; catch_err(cin >> id); i=0; //this is a kinky way of accidentally omitting the job you don't want in the queue if(jobs_queue.size()!=0) { for(i=0; i<=jobs_queue.size(); i++) { temp=jobs_queue.front(); jobs_queue.pop_front(); if(i!=id) { jobs_queue.push_back(temp); } } } else { cout << "tNothing to deleten"; pause_n(); } } } } else { if (key == 2) { id=0; cout << "tRunning simulationn"; cout << "But before we go on, you get to make a difference, please choose the time quantum: "; catch_err(cin >> id); //convert the queue to a array (why? because i can, and because you may want to use an array if you were doing other algorithms) i=0; int length=get_list_size(jobs_queue); Job jobs[length]; for(iter=jobs_queue.begin(); iter!=jobs_queue.end(); ++iter) { jobs[i]=jobs_queue.front(); jobs_queue.pop_front(); i++; } fifo_sjn_srt_sim(jobs, length, 0); fifo_sjn_srt_sim(jobs, length, 1); fifo_sjn_srt_sim(jobs, length, 2); rr_sim(jobs, length, id); return 1; } } } /* //setup for testsing purposes jobs[0].set_job_id(1); jobs[0].set_time_to_exec(1); jobs[0].set_time_in(0); jobs[1].set_job_id(2); jobs[1].set_time_to_exec(5); jobs[1].set_time_in(2); jobs[2].set_job_id(3); jobs[2].set_time_to_exec(2); jobs[2].set_time_in(3); jobs[3].set_job_id(4); jobs[3].set_time_to_exec(6); jobs[3].set_time_in(4); jobs[4].set_job_id(5); jobs[4].set_time_to_exec(10); jobs[4].set_time_in(5); //cout << "before the sort:n"; //for (int i = 0; i < MAX_JOBS; i++) printf("%dn", jobs[i].show_time_to_exec()); //cout << "test full " << isempty(jobs, MAX_JOBS); //cout << "ntest empty " << isempty(emty,2); */ return 1; } To the coding monkeys like myself, not sure yet, but i think i'm going to start a contest here, just gotta order some stuff. So give me time, you can comment on the code, keep in mind that i will probably post something for whoever wants to join this soon to be a contest, and whoever wants to join will probably have to do something with the code above. I wanna see if there are people interested, i will think of some good prizes Quote
sanctus Posted October 26, 2007 Report Posted October 26, 2007 A contest would be a good way of learning, I may be in Quote
alexander Posted October 26, 2007 Author Report Posted October 26, 2007 well, ofcourse it would you would learn c++, templates, datastructures, as well as job management algorithms of OSes in general... Quote
Buffy Posted October 26, 2007 Report Posted October 26, 2007 So, just to clarify: all you're trying to show here is managing a job queue and allocating time-slices, right? And the priority in the queue is solely based on the up-front "time to execute?" I haven't gone through it more than to just scan what you've got here, but there are all sorts of interesting issues you could attack which would make your algorithm grow enormously! Continuously variable time-slices based on actual execution time (or when you add resource allocation, the size of the resources used (give the greediest ones more time to get them out of the run queue!))... I can't find much online, but back in the olden days at Berkeley we used something called the "Toy Operating System" which was an "OS for building OS's" (cf. "yacc"). All it *really* did was give you a decent semaphore simulator (which back then had to be written in VAX assembler!), and some dummy devices (tty, disk, tape) as a library, and it was up to you to build all the components. OSs are fun-damental, :PBuffy Quote
alexander Posted October 26, 2007 Author Report Posted October 26, 2007 this simulates 4 algorithms, the priority is based on the algorithm, but you define when the jobs come in in the initial setup this simulates First In First Out (really old job management) then Shortest Job Next (the queue get sorted, shortest to longest job) then Shortest Round Trip (one of the first algorithms to use preemption, the queue gets sorted shortest to longest, but if the shortest job is smaller then the currently running job, it will be preempted (granted the currently running job needs more time to finish executing that is) and the shorter job executes first. lastly the .02% that don't work quite as well as i hoped it would, Round Robin, Round robin is driven off of the time quantum, basically if there are jobs waiting in the queue, the currently executing job gets pushed to the back of the queue, and the next job in line gets to get process time (equal to the time quantum) then that one is preempted. Yes the final algorithm's efficiency is really dependant on the time quantum, and that in itself is the subject of many PhD Thesees. The algorithm provides equal opportunity to all processes, and in fact that is what Linux uses for job management (well, there are are other things that the job manager does that i simply did not have to simulate, nor were we asked to) obviously there are job priorities and some other stuff Actually i think that the latest kernel 2.6.23 has finally changed the job management algorithm to be even more efficient... i gotta do research on what they changed You absolutely can expand on it, and that is what one of the options of the contest may be. Buffy you in? I will probably come up with a package: shirt, mug, mouse pad.... maybe something a little more of value.... hmmm gots to think Quote
alexander Posted October 26, 2007 Author Report Posted October 26, 2007 ps you can see just how hard i'm thinking in this picture: :P oh, i should make it my um thing, like buffy always posts a line at the end of her response, i could post a picture hehe :P Quote
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.