GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 16-Mar-2011, 15:03
neojb1989 neojb1989 is offline
New Member
 
Join Date: Mar 2011
Posts: 4
neojb1989 is on a distinguished road

Help with an assignment: Simulating CPU scheduling.


I am to simulate the execution of a process and how it would be scheduled in a computer system. So how it goes in and out of the ready Queues. The program will end up outputting one line when each process starts/terminates. The line should output the process sequence number, its class (interactive/realtime) and the current simulated time. It will also ultimately output the number of RealTime processes completed, percentage that missed their deadline, # of interactive processes completed, # of disk accesses, average duration of disk access (including wait time in Queue), total time elapsed since first process started, and Cpu and Disk utilizations. My input is a sequence of pairs such as:

INTERACTIVE 12000 // new process
CPU 100 // CPU resource request
TTY 5000 // Terminal Access resource request
DISK 10 // Disk Read resource request.
REALTIME 12000 // new process
DEADLINE 13000// absolute time it must end by.

and so on.

I need a separate ready Q for both interactive and ready processes.

I have managed to make a Queue class which holds processes. My hurdle currently is trying to read the file to find all the of the times a process is made, place all of the processes in their rightful spots in the FIFO Queues, they are supposed to be first in first out, Give them their deadlines within the process, I have a process class holding a bunch of info, one of which is a deadline if there is one, and then go back and execute their resource requests.

That is how I figured it should be done but I have made little progress on it.

For the assigment, I am to use input redirection but I have no idea how to do that. He gave us:
CPP / C++ / C Code:
./a.out < input.txt
as how to do it but... those words mean nothing to me So my first question is how do I properly do input redirection? I have an input.txt file in my VisualC++ project but I don't know where the
CPP / C++ / C Code:
 ./a.out 
is coming from, or what each bit means.

Second question being how do I read through the file and pick out the pairs of input which create a process and place them in their appropriate Queues and Queue index. And then go back once more to actually execute their resource requests.

Or is there another way someone can think that would be less complicated?

Thanks for the help in advance.

I don't want to add more as this is already getting a little long but here is what my Process class looks like. The Queue class is a template class which I found in one of my older books and seems to be working fine, although I have not attempted the pop() or push() functions of it yet.

CPP / C++ / C Code:
class Process{
public:
	Process ();
	int psn;
	string pclass;
        string state;
	int arrival;
	int timetaken;
	int deadline;
	
private:
};

CPP / C++ / C Code:
template <class T>
class Queue{
public:
	Queue (int capacity);
	T& Front() const;
	T& Rear() const;
	void push (const T& item);
	void Pop();
	~Queue();
	T* queue;
	int front, rear, capacity;	
};
  #2  
Old 19-Mar-2011, 03:34
Mexican Bob's Avatar
Mexican Bob Mexican Bob is offline
Regular Member
 
Join Date: Mar 2008
Location: Chicxulub, Yucatán
Posts: 686
Mexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the rough

Re: Help with an assignment: Simulating CPU scheduling.


Wow...you have a LOT of content in this post. I have a number of questions regarding it.

It appears that your data file (you should include the real file) is a series of scheduler events, not anything necessarily identified with a "process."

Also, the content that you provide as your input seems rather ambiguous. How does one know what:

INTERACTIVE 12000 // new process
CPU 100 // CPU resource request
TTY 5000 // Terminal Access resource request
DISK 10 // Disk Read resource request.
REALTIME 12000 // new process
DEADLINE 13000// absolute time it must end by.

...DEADLINE refers to? Is it a property of the REALTIME process? You seem to suggest it as is noted in your Process class public members, which brings up the question of why do you define a class with public data members?

In reviewing the members, when would arrival, timetaken and/or deadline be negative?

./a.out < input.txt

...what this is doing is invoking the program named a.out with the content of input.txt as its argument(s). There are some important nuances.

a.out is the default name of the output from the linker when no output name is specified. This doesn't happen under VC++ from the IDE, but is commonplace in Unix when not -o (output to a specific file name) is specified.

CPP / C++ / C Code:
[user@localhost redir]$ cat main.cpp 
#include <iostream>

int main(int argc, char* argv[]) {
    for (int i = 0; i < argc; i++) {
	std::cout << argv[i] << std::endl;
    }
    return 0;
}


This code prints the contents of the arguments passed into the program such that any redirected input is displayed. Note that none of the input.txt file is displayed in the following:

input.txt

Code:
[user@localhost redir]$ cat input.txt abc 123 def 456 ghi 789 jkl 012 mno 345 pqr 678 stv 901 wxy 234 zzz 555

Output:

Code:
[user@localhost redir]$ ./a.out < input.txt ./a.out

However:

Code:
[user@localhost redir]$ ./a.out `cat input.txt` ./a.out abc 123 def 456 ghi 789 jkl 012 mno 345 pqr 678 stv 901 wxy 234 zzz 555

...works, because it is sending the contents in as arguments instead of bytes available on the stdin file pointer. If you want to read from stdin, you can using std::cin. In other words, in order for the redirection to work, you will have to read the data available on the standard input stream.

CPP / C++ / C Code:
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
    if (argc > 1) {
	for (int i = 0; i < argc; i++) {
	    std::cout << argv[i] << std::endl;
	}
    } else {
	std::string s;
	do {
	    std::getline(std::cin, s);
	    if (std::cin.good()) {
		std::cout << s << std::endl;
	    }
	} while (std::cin.good());
    }
    
    return 0;
}


Output:

Code:
[user@localhost redir]$ ./a.out < input.txt abc 123 def 456 ghi 789 jkl 012 mno 345 pqr 678 stv 901 wxy 234 zzz 555

I would think a lot less about a "Process" class and more about a scheduler that takes events from stdin.

What I didn't see here is any process ID, but I guess that 'psn' is supposed to be it. There doesn't seem to be any priority to processes, but priority is presumed to be important because of the distinction between a normal process and a real time process.

I didn't see any process state being used and I certainly wouldn't make it a string variable. The best case is you're wasting time doing string compares when a simple bit mask or #define'd value comparison is all that is needed.

There are a lot of gaps in your code. I suppose that you realize it and that's why you're here. I would encourage you to consider what is important and to also consider what is possible based on your data types.

I probably wouldn't use a C++ queue implementation, particularly if I didn't expect a lot of processes. This is yet another reason why C++ isn't used to implement operating systems. You get a lot of bloat for no apparent reason. I would expect that this would be a linked list implementation with queue like functions where linking and unlinking process pointers between queues (lists) would be performed by the scheduler. Using your Queue template class, which is incomplete because there is no underlying storage defined in it, is haphazard. At best, whenever you decide on your storage, you're going to be making a lot of copies in and out of the storage for the "items" in the queue. That results in scheduler hell. Operating system schedulers need to be as fast as possible in order to reduce the latency of the system and to give as much real processing power to the tasks and not consume CPU cycles by the OS itself.


MxB
  #3  
Old 19-Mar-2011, 19:49
neojb1989 neojb1989 is offline
New Member
 
Join Date: Mar 2011
Posts: 4
neojb1989 is on a distinguished road

Re: Help with an assignment: Simulating CPU scheduling.


We weren't given a file, our professor is saying he will use a file named input.txt along with the program we make to test the program. We dont know whats in it other than pairs similar to the example he gave us.

the Deadline is part of the last process that was made. and yes it is a property of realtime processes. I have it in my process class because It seems easier for me to have it there and not use it than make two process classes for real-time and interactive. May not be the best way, but its at least within my abilities.

And your right, it is a series of scheduler events but the way I understood it is that the events consist of making a process, and then that process issuing resource requests.

As for linked lists, you think that would be a better idea?

Priority is supposed to be FIFO but i'm confused as whether to base it on arrival times or when it shows up in whatever he decides to put in his Input.txt file. It would make sense to me to base it on arrival times, but i'm not sure with this professor. I've asked him but he doesn't want to answer most questions to "make it fair to other students".

As far as I know, arrival time/ deadline/ time taken should never be negative since you will always be adding to the time taken, the arrival times are always positive, and so are the deadlines.

The help is appreciated, so I hope this helps you help me further
  #4  
Old 20-Mar-2011, 07:38
Mexican Bob's Avatar
Mexican Bob Mexican Bob is offline
Regular Member
 
Join Date: Mar 2008
Location: Chicxulub, Yucatán
Posts: 686
Mexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the rough

Re: Help with an assignment: Simulating CPU scheduling.


Quote:
Originally Posted by neojb1989
I am to simulate the execution of a process and how it would be scheduled in a computer system.

...this is the first line that you wrote after the thread title. What I took from this is a combination of the two major elements above and the following line:

Quote:
Originally Posted by neojb1989
So how it goes in and out of the ready Queues.

I don't see more than one "ready" queue, but there are definitely more than one queue, not all of which are "ready," in a "typical" scheduler.

Quote:
Originally Posted by neojb1989
We weren't given a file, our professor is saying he will use a file named input.txt along with the program we make to test the program. We dont know whats in it other than pairs similar to the example he gave us.

...the problem is that there is a hierarchy to the events. Some are dependent on others. For example, we're saying that REALTIME when followed by a DEADLINE creates a relationship between the two "text file items" in such a way that REALTIME is modified by DEADLINE. What other, if any, "scheduler events" are modified by other scheduler events? For example, are the "resource" events utilized by the most previous process or by the "system?" All of these things require that a process "lock" and/or "hold" a resource until completion.

Also, in what units are the time? Did you state that somewhere and I missed it?

Quote:
Originally Posted by neojb1989
the Deadline is part of the last process that was made. and yes it is a property of realtime processes. I have it in my process class because It seems easier for me to have it there and not use it than make two process classes for real-time and interactive. May not be the best way, but its at least within my abilities.

...let's quit worrying about "the best way" and just focus on something that is "good enough." I would try to express the notion away from doing things for "convenience" (easier for me to have it there) and more toward the idea of "naturally fits there" as a goal. If it seems naturally a part of the process, then it probably should be an attribute of the process. My concern is that process doesn't use it or even really know/care about it. "Scheduler" uses it. However, it does seem like a property of the process, so it is data that the process probably should carry around with it.

Quote:
Originally Posted by neojb1989
And your [sic] right, it is a series of scheduler events but the way I understood it is that the events consist of making a process, and then that process issuing resource requests.

If that is the way that you understand it, that's fine. But I'm guessing that you're going to get thrown a curve ball when you get the "real" text file of events. What I'm seeing in the events list is what appears to be a "run to completion" for every process/task. Do we know if the list is all-inclusive of the range of possible events or that there are names of either resources and/or processes for which no name is mentioned in the list?

For example, I don't see any context switching. I don't see any preemption. I don't even see any need for a queue, rather, just a straight line execution through the even list. The list is like a "report" of scheduler events that happened in the past and less like input to that which will happen in the future. Furthermore, we don't usually know in advance how long a process will request/utilize a resource, we can design a system (and we do have such systems) that always allow any task/process to run in exactly the same amount of time for every "cycle" through the processes. But, I suspect that this isn't that.

If we "miss" the deadline, it will be because the list gave us a resource utilization "report" that exceeded our deadline value.


Quote:
Originally Posted by neojb1989
As for linked lists, you think that would be a better idea?

No...not for this effort, if you're going to utilize a queue. Your template queue would be great, but (FYI) you don't have a way to traverse it.

I would suggest that you take your mind off of the storage requirements for a moment and focus on the interactions between the events list and the actions of the scheduler. For each event, scheduler will perform some work. I don't see any indication of that work; except as is represented by the "state" variable in the process.

Imagine what you're going to do BEYOND creation of processes and pushing them onto some appropriate queue. Don't all of the processes startup being "ready to run?"

Using a linked list here would be more work. Using a queue seems appropriate, but it is an incomplete implementation. It doesn't have any internal storage, so it is more of a set of interfaces, which you do note as being unimplemented so far.

What are we going to do when we see a process creation event? Where is the specification that parses the list and makes the appropriate Scheduler calls?

Are you familiar with a Three-card Monte?

http://en.wikipedia.org/wiki/Three-card_Monte

Imagine that the "pea" (the card that one is supposed to follow) is the currently executing process. The actual cards in their relative positions represent queues. One of which is ready to run, another is blocked another is running.

Quote:
Originally Posted by neojb1989
Priority is supposed to be FIFO but i'm confused as whether to base it on arrival times or when it shows up in whatever he decides to put in his Input.txt file. It would make sense to me to base it on arrival times, but i'm not sure with this professor. I've asked him but he doesn't want to answer most questions to "make it fair to other students".

If we consider that we're pushing and popping from a queue and that the queue is a realization of a FIFO, we would have to consider "priority" to be a function of two things; realtime-ness and the next item that could be popped from the appropriate queue. For example, we can't pop but the "FI" item out of the queue, so whatever is "under it" is irrelevant in terms of "right now" priority. If it is the FI and it is in the REALTIME queue, it *must* be the highest priority, if it is ready to run.

Quote:
Originally Posted by neojb1989
As far as I know, arrival time/ deadline/ time taken should never be negative since you will always be adding to the time taken, the arrival times are always positive, and so are the deadlines.

...which was what I was thinking, too, but then I see that your implementation uses "int" which is a signed type. If we're not going to be able to deal with negative numbers in some kind of useful way, then we probably want to ensure that we never accept them by making our data type an unsigned type. What do you think?

I'm a bit concerned with the specification of Queue. I'm guessing that it was given to you. The public members of front, rear and capacity concern me. Would you return -1 if the queue is empty for the value of "front" and "rear," as these appear to be an "index into" the queue, but the array operator is not specified, so what value are they? I don't think that we would want to implement the array operator, since that would provide for a rudimentary "random access" method in our FIFO, which should diligently honor our FIFO contract. For that matter, why would we have a "rear?" Aren't we again saying that you (some user of the implementation) is "allowed" to access elements in some fashion OTHER than FIFO?

In the Process specification, what value is "psn?" Do we use it in some way? Is it expected that our "reporting" will use it? I don't see it in the requirements or in the data input; it sounds a lot like a "programmer generated" requirement that should be removed until deemed a real requirement. Do not add anything extra without a very good reason, at which time it probably won't be "extra."

Quote:
Originally Posted by neojb1989
The help is appreciated, so I hope this helps you help me further

I don't know if I'm helping much by all of this blabber.

Usually, front and back will return a reference to the element or it will return Queue::end() if empty. I don't see how capacity can return a negative number. It is either empty or has some elements. When is capacity negative? (back to the signed versus unsigned types) I don't see any usefulness for having a "front" and a "Front" with separate functionality. I'd defer to the convention of the standard template library implementations of containers and do away with Front and Rear and implement "front and back" operations that return references to the elements held by the queue. Of course, I wouldn't *really* implement back, because then that would give the potential for violating the FIFO-ness of the implementation.

Why isn't std::deque "good enough?" I would probably use it for my internal storage for Queue and have my Queue::push perform a std::deque::push_back as follows:


Queue.h

CPP / C++ / C Code:
#ifndef Queue_h_
#define Queue_h_

#include <deque>

template<class T> class Queue {
public:
    T& front();
    const T& front() const;
    void push(const T& t);
    void pop();
    size_t size() const;
private:
    std::deque<T> m_q;
};

template<class T> T& Queue<T>::front() {
    return m_q.front();
}

template<class T> const T& Queue<T>::front() const {
    return m_q.front();
}

template<class T> void Queue<T>::push(const T& t) {
    m_q.push_back(t);
}

template<class T> void Queue<T>::pop() {
    m_q.pop_front();
}

template<class T> size_t Queue<T>::size() const {
    return m_q.size();
}

#endif // ! Queue_h_


main.cpp

CPP / C++ / C Code:
#include <iostream>

using namespace std;

#include "Queue.h"

typedef Queue<int> iq;

int main(int argc, char* argv[]) {
    iq q;
    for (int i = 0; i < 10; i++) {
        q.push(i);
    }
    cout << "Size of Queue: " << q.size() << endl;
    for (int i = 0; i < 10; i++) {
        int j = q.front();
        cout << j << endl;
        q.pop();
    }
    cout << "Size of Queue: " << q.size() << endl;
    return 0;
}


Output:

Code:
Size of Queue: 10 0 1 2 3 4 5 6 7 8 9 Size of Queue: 0

...once you get past the basic underlying storage, you'll have to start tackling the challenge of what you're really trying to accomplish, which is only modestly associated with the actual implementation of Queue. If we accept that Queue enforces the FIFO requirement, we still have a lot of work to do in order to accomplish the remainder of the coding.


MxB
  #5  
Old 20-Mar-2011, 14:13
neojb1989 neojb1989 is offline
New Member
 
Join Date: Mar 2011
Posts: 4
neojb1989 is on a distinguished road

Re: Help with an assignment: Simulating CPU scheduling.


Looking over the assignment, I shit the bed a little. It's FCFS not FIFO. Sorry.
Secondly, thank you for taking the time to help, it's very much appreciated.
Context switch times can be neglected.
I also thought it seemed more to me that it's just a list of things that happened and I don't really need a Queue for it but it's supposed to simulate scheduling which is the only reason I even have them. In an attempt to clarify everything i'll post what the actual assignment sheet looks like for me. Maybe this will help be more clear on what needs to do. Because the more I think about it, the more I confuse myself.

1. Objective
This assignment will introduce you to CPU scheduling.

2. Specifications
You are to simulate the execution of processes by a computer system with a large memory, one terminal per user, a CPU, and one disk drive. Each process will be described by it's class (REAL-TIME or INTERACTIVE) and its start time followed by a sequence of resource requests.
These resource requests will include CPU requests (CPU), disk reads (DISK0 and terminal accesses (TTY). In addition, all real-time processes will have a DEADLINE, by which they must complete.
Your input will be a sequence of pairs as in (the ones I included at the start)
All time will be expressed in milliseconds.
Your program should maintain separate ready queues for real-time and interactive processes and give absolute priority to real-time processes over interactive processes:
a) Your scheduler should never allocate the CPU to an interactive process as long as there are one or more real-time processes in the ready state.
b) When a real-time process returns to the ready queue and finds that the CPU is currently allocated to an interactive process, the scheduler should take the CPU away from the interactive process and give it to the real-time process. The pre-empted process should return to the end of the ready queue for interactive processes. When this is the case your program should update the duration of the CPU request by subtracting from the orginal duration te time the process has already spent in the running state.

Disk scheduling will be strictly FCFS (not FIFO, sorry) without any distinction of process classes.
To simplify your life, we will assume that there is enough memory space for all processes, context switch times can be neglected, user think times are included in the terminal access times, and each process reads and writes to a different terminal.
Your program should read its input file name through input redirection as in:
./a.out < input.txt
If by accident, two resources allocations need to be made at the same time, you should allocate the CPU first then the disk then the terminals.
Your program should have on process table with one entry per process containing a process sequence number, the process class, its process arival time and its current statues (READY,RUNNING,WAITING).
It should print out one line of output every time a process starts or terminates. This line should include the process sequence number, its class and the current simulated time in milliseconds.
When all processes in your input stream have completed, your simulator should print a summary report listing:
a) The number of real-time processes that have completed.
b) The percentage of real-time processes that missed their deadline.
c) The number of interactive processes that have completed.
d) The total number of disk accesses.
e) The average duration of a disk access (including the waiting time in the disk queue).
f) The total time elapsed since the start of the first process.
g) The CPU and DISK utilizations, that is, the fraction of time the CPU or the DISK was busy.

A little about myself so that you can understand my abilities I guess I would say. I had no programming experience when I entered college. I am currently 2nd term sophmore and this is for a 300 level operating systems class. Before this I had 1 java class, 1 c++ class, and 1 Abstract Data Types class. Anything that wasn't taught in those classes I have learned by scouring the internet. In total, I don't know much. So when you:
Why isn't std::deque "good enough?" I would probably use it for my internal storage for Queue and have my Queue::push perform a std::deque::push_back as follows
I barely not what any of that means. Never really used the standard libraries and I didn't really know what they were (other than include <iostream> and include <ifstream>) and didn't know what they were until I started looking up stuff on the internet.

Again thanks for the help.
  #6  
Old 20-Mar-2011, 18:04
Mexican Bob's Avatar
Mexican Bob Mexican Bob is offline
Regular Member
 
Join Date: Mar 2008
Location: Chicxulub, Yucatán
Posts: 686
Mexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the roughMexican Bob is a jewel in the rough

Re: Help with an assignment: Simulating CPU scheduling.


Quote:
Originally Posted by neojb1989
Disk scheduling will be strictly FCFS (not FIFO, sorry) without any distinction of process classes.

How is FCFS different than FIFO? (They are the same thing.)


MxB
  #7  
Old 20-Mar-2011, 20:17
neojb1989 neojb1989 is offline
New Member
 
Join Date: Mar 2011
Posts: 4
neojb1989 is on a distinguished road

Re: Help with an assignment: Simulating CPU scheduling.


You know what, you're right. had a brain fart there. Sorry.
  #8  
Old 27-Mar-2017, 17:09
ZPhuang ZPhuang is offline
New Member
 
Join Date: Mar 2017
Posts: 1
ZPhuang is on a distinguished road

Re: Help with an assignment: Simulating CPU scheduling.


Hi, I got the same problem with this project, have you finally solve this assignment.
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Circular Linked Queue Copy Constructor and Assignment Operator Not Working? wc3promet C++ Forum 1 06-Oct-2008 03:00
help with c++ object assignment Mjkramer21 C++ Forum 31 14-Apr-2004 18:51

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 22:11.


vBulletin, Copyright © 2000 - 2017, Jelsoft Enterprises Ltd.