Lab 4

Lab 4

by Tarmo Pajusaar -
Number of replies: 12

Hi,

I'm somewhat stuck at Round Robin scheduling as well as selecting the "right" answer to some arithmetics questions.

Round Robin

  1. Process B has estimated run time 4 ms for the first two scheduling algorithms but 3 ms for the Round Robin. All other run time estimates are identical between the three algorithms. Is this intentional? For whichever time quantum from 3 to 5 ms I choose in this case, process B appears to finish before 9 ms which is when its I/O request is about to happen. I can of course be mistaken. However, with 4 ms I can make sense of this I/O request.
  2. What happens when a single remaining process has estimated run time greater than the time quantum? Will it still be split into time slices so it alternates between running and ready state or will it run to completion in one pass?
Arithmetics

Some values require more bits than specified in the task. What is the priority in such cases, should the bit count be extended accordingly or should they overflow?

In reply to Tarmo Pajusaar

Re: Lab 4

by Sourav Bakshi -
Hi. I may not be able enough to answer all questions correctly, but I would like to talk a little about it.

In round robin, the run time for process B can be intentionally kept at 3 ms, but that shouldn't matter. Maybe you can think of the I/O process to be a different process, so for some time (time quantum), process B will run and then later for some time (same time quantum), the B I/O process will run. I can't assure you on this, because there is no proper example in the lecture files, but this would kind of make sense to me. If you had 4 ms for process B and considered 5ms as time quantum, then you are probably thinking that process B I/O would interrupt like in FCFS scheduling. But what happens if you had to choose 3ms as time quantum, or even 4 ms.

When a single remaining process has estimated run time longer than time quantum, it should run multiple times for the same time quantum, which basically means the process will run until it finishes. As per your question, if there would be a considerate amount of time delay in switching from running state and ready state, then I would bother about the intensity of the question. But in our assumptions, or at least for the lab assignment, it should be ok to say that the last process will finish until end, in one pass.


For the arithmetic part, I think you meant in the IEEE standard part (if not, then re-check because others seem fine to me). IEEE standard can't be changed, so you have to fit as many bits as possible within the Mantissa (that is, max 23 bits).
In reply to Sourav Bakshi

Re: Lab 4

by Tarmo Pajusaar -
Hi, thanks for your reply.
As unfortunate as it is, I'm still lost. However, due to time pressure I'm just going to provide my answers as how I see fit and send them away. I'm not likely to comment or ask more here in the forum.
Two more specific examples are below for those interested.

Round Robin example. Time Quantum 3 ms. First comes process A that needs 7 ms of run time. It gets 3 ms as per TQ value. While A is running, process B arrives, requiring 3 ms of run time. A uses its time slice up and is moved back to the queue, then B starts to run. When B has used its time slice of 3 ms, it has come to completion because it did not need more than 3 ms to run. So within the first 6 ms, B has finished and gets removed from the queue. Now I have hard time interpreting the B I/O request occurring at 9 ms. Because B is not running nor ready anymore. It's gone, its work has been done. We have instructions that when I/O request occurs, "the corresponding process should go into waiting state (either from ready or from running state)". There is nothing to explain the behaviour upon I/O request from the finished state.

Arithmetics example. Task is to represent decimal -224 in 2's complement format with 8 bits. 8-bit signed integer range is from -128 to 127. -224 does not fit into this range, re-check or not.
In reply to Tarmo Pajusaar

Re: Lab 4

by Sourav Bakshi -
Hi,
I can't provide any explanation on the I/O process because there were nothing in the lecture files and if our teacher added any information regarding this in class then I am sorry I wasn't there (most of the times). In my opinion, what I suggested previously was that I/O request can be considered a separate process irrespective of the name (such as I/O of process B or process D, doesn't matter...). It is not like process B has to be running and then I/O of process B must interrupt, in that case shouldn't it be more logical for the person who made the question paper, to keep the event time of both the process as same (or very close). So what I did was, I considered 3 ms time quantum, solve A for 3 ms, then B for 3 ms, then C for 3 ms and then B I/O for 3 ms, then D for 3 ms, and so on. Later on, I will come back to solve A for another 3 ms, then C for the remaining 2 ms, B I/O for the remaining 1 ms, and so on... Again, I'm not saying that this is correct, but this seems fair enough. If you think, process A takes 2 or 3 ms only instead of 7 ms, then you can never make an interruption of I/O while B is either running or ready and this will be the case in all the 3 scheduling (FCFS, Priority and round robin). This is how I justified my thinking and clearly, I don't know if it is right. If you can manage to ask the teacher, please do it because I'm not willing to confidently give the wrong answer. I'm just providing my opinion on this.

As for the arithmetic part, yes you were right about overflow. Basically, I did that sub-consciously and I forgot about it because I did it like 2 weeks back. Technically, that is inappropriate but it can also be a trick question, although I am not intrigued at this. In fact, later you have to transform negative number such as 10000000 (which is -128 in decimal) into positive number using 2's complement. Again, this does not make sense with only 8 bits because you can't represent +128. I don't know what is the objective of such questions, but you can do it with ignoring the overflow, as I did, or raise a query against it.
In reply to Sourav Bakshi

Re: Lab 4

by Tarmo Pajusaar -
I've submitted my work, no more changes to be made.

1. The assignment says "I/O Requests should be interpreted as parts of main tasks and when such an event occurs, the corresponding process should go into waiting state (either from ready or from running state)." I interpreted it like "the corresponding process will stay in waiting state while the OS services its I/O request". This resulted in total run time of 40 ms which fitted nicely into the provided table without modifications. Setting process B estimated run time to 4 ms (like it was for previous two algorithms) eliminated the disconcerting occurrence of an I/O request from a finished process.

2. Whether the questions in arithmetics were meant to be "tricky" was the main motivation behind me raising this topic in the first place.

Since no teacher nor assistant appears to read this forum, I guess there is nothing more left for us to achieve any better insight here than we already have.
In reply to Tarmo Pajusaar

Re: Lab 4

by Mohammadreza Heidari Iman -
Dear Tarmo,

IO requests are not served by the CPU and there is no need for considering them when you are completing the CPU run timetable. So, in the CPU run timetable, you can only put the other processes. Therefore, if an already finished process (e.g., B) requests for an IO, the CPU is not involved and the IO request is served separately.
Regarding your arithmetic question, if converting a value needs more bits, you can use more bits for it. For instance, if for converting -224, you need more than 8 bits, you can use one more bit.
In reply to Mohammadreza Heidari Iman

Re: Lab 4

by Tarmo Pajusaar -
Hi Mohammadreza,

Thank you for your comment.
I've already submitted my work so there is no take back. However, just to understand, I now wonder that if I/O requests have nothing at all to do with scheduling then when does a process come out from a waiting state? Is my approach stated previously (the corresponding process will stay in waiting state while the OS services its I/O request) wrong? I interpreted the "run time" given for an I/O request as how long it takes to serve it. Outside the affected process, surely, but still affecting scheduling decisions as to when the process can re-enter the ready queue.

Have nice weekend and a happy New Year!
In reply to Tarmo Pajusaar

Re: Lab 4

by Mohammad Hasan Ahmadilivani -
Hi Tarmo,

1- You can update your submitted assignment any time before the deadline (Jan. 2 for Lab 4).
2- I/O requests for sure affect the scheduling. They interrupt the CPU for a running task and the task goes on the waiting list for their request to be served. The task will be ready again when the I/O is served. In the case of this assignment, "estimated run time" for I/O requests means how much time it takes for the task to be ready again.
3- I suppose your interpretation is also the same as what I have written (as far as I understood from your post). However, to make sure, please check your assignment again and resubmit it if needed.

Happy New Year!

Regards.
In reply to Mohammad Hasan Ahmadilivani

Re: Lab 4

by Tarmo Pajusaar -
Hi Mohammad,

Thank you for confirming I'm at or close to the right track.
I’ve updated my work to reflect what I’ve learnt from the discussion. Most importantly, I now consider process B estimated run time 3 ms for Round Robin being valid, not a mistake. Correspondingly, I also consider the post-finish I/O request for process B valid, albeit not affecting the schedule at all.
I additionally updated some explanatory content but these changes are not essential and only serve to clarify my intent.

Unfortunately, Moodle doesn’t seem to allow re-submission. I therefore provided a link to the updated work in the comment to the submission.

Head uut aastat!
In reply to Tarmo Pajusaar

Re: Lab 4

by Edvard Ehiloo -
Hi,

Just to make it clear and understandable. Should we include the I/O requests in the CPU runtime table and make the main process wait until the I/O request is complete? For example, B is running and an I/O request for process B is made. The initial/main B task is put to waiting mode and I/O request is started to be served. The initial/main process B can be continued only after the I/O request is done.

Happy New Year !
In reply to Edvard Ehiloo

Re: Lab 4

by Tarmo Pajusaar -
Hello Edvard,

Since there're only few hours until deadline and it may happen that none of the teaching staff will find time to reply you, I put down here my view on this. Take this with caution.
Basically, I think your statements are right, with a clarification that the I/O requests themselves should not appear in the timetable. I initially indicated them there with a different color just to mark regions where the task had to stay waiting. I removed them later to prevent confusion. However, how you describe the main task scheduling is exactly how I understand it.
Again, my word is not "official" but it may turn out to be better than nothing if you don't get another reply before deadline.

Head uut aastat!
In reply to Edvard Ehiloo

Re: Lab 4

by Mohammad Hasan Ahmadilivani -
Dear Edvard,

Sorry for the late response!
When a process is running (e.g., B) and an I/O request is issued, this process goes off from the run-time table and the next ready task (e.g., C) starts to be run. B will be ready again after the I/O request's run-time is done.
It is okay if you include or not the state (ready/waiting) of the other tasks (that are not under-execution) in the table in parallel with the main task. However, the main running task should be distinct.
If you include all tasks, the table would be more readable for us while reviewing.

Regards.
In reply to Mohammad Hasan Ahmadilivani

Re: Lab 4

by Edvard Ehiloo -
Hello Mohammad,

No problems, not late. Thanks for clarifying the task. Was really helpful and I corrected my assignment.

Best regards,
Edvard Ehiloo