Test 1

Operating Systems

Test 1, 29 February 2012

This test has ten questions; answer at least eight of them.

Up to the first 75 words appearing after a question are taken to be the answer to the question. Words following the 75th word are not part of the answer and will be ignored.

An operating system implements mutexes using interrupt disabling. Is it possible a group of processes (or threads) to find themselves deadlocked entirely through the way they manipulated mutexes? Explain.

Yes, it is. If two data structures A and B each use a mutex to provide mutually-exclusive access, and two threads 1 and 2 each need both data structures, then deadlock could ensue if thread 1 tries to acquire A then B in that order and thread 2 tries to acquire the data structures in the opposite order, and both threads succeed in locking the first data structure they need.

By the by, this question is my gift to you. This question was originally about mutual exclusion and disabled interrupts, but for some reason when I wrote it down I wrote “mutexes” instead of “mutual exclusion” and didn't catch the difference until I started reading the answers. The answer to this question with respect to mutexes is considerably simpler than it is with respect to mutual exclusion.

The answers, approximately verbatim, and in no particular order:
1. Yes, it is possible a group of process can be deadlocked through the way the mutexes are manipulated. This can be explained by the 4 deadlock conditions.
  
  1. A mutex does not share resources.¹ A mutex is either locked or open.
  
  2. A mutex can block allocation request if locked.
  
  3. If resources are not reduced² the mutex, there will be cyclic deadlock.³
  
  4. If a mutex is holding a thread and can hold more than one thread as well as blocking an open mutex will cause deadlock.
  
  1: Share with what?
  
  2: I'm guessing; the word was unintelligible.
  
  3: How?
2. Yes, depending on how and when they disabled and re-enabled interrupts, a process can find itself deadlocked. The mutex disables interrupts then checks to see if the mutex is locked. If the code does not re-enable interrupts before waiting for the mutex to become unlocked,⁴ the process will be waiting forever.⁵ This is because there can be no context switches while interrupts are disabled and therefore the process with the key to the mutex can never call unlock. Therefore the system will be deadlocked.
  
  4: You're suggesting the mutex is not implemented correctly?
  
  5: That's not the same thing as a deadlock.
3. It is possible for a group of processes or threads to be deadlocked in the way they manipulate mutexes. Threads normally compete over mutexes. Mutexes lock and unlock threads so they can all complete their processes. The problem can arise depending on which threads are locked and unlocked. Suppose two threads at the exact same time try to do the same operation⁶ (executing concurrently). Both threads then become locked because both threads are deadlocked waiting for the other.⁷
  
  6: Which operation are they trying to do? A mutex operation? Some other operation?
  
  7: Isn't that just a race condition? How does a race condition lead to deadlock?
4. No, because when the thread or process is done using the critical section the key is given up to the next process/thread. Therefore resources are able to be share, which avoids one of the four deadlock conditions.⁸
  
  8: But what's being shared here? The mutex or the critical section? In either case, what about if there's more than one critical section?
5. Yes, it is possible for processes to be deadlocked through the use of a mutex. A mutex is a data structure to lock a critical section so that only one process (thread) can be in it at a time. During this time, interrupts are disabled.⁹ As interrupts are disabled, nothing can get in that code because it is locked and the key is inside.¹⁰ If the thread shares a resource from outside the mutex and requires it from outside the mutex,¹¹ it cannot get it and thus becomes deadlocked.¹² Any process that requires the process or thread in the mutex is also deadlocked as it cannot reach through the locks.¹³ Any interrupts to bypass the mutex are ignored, perpetuating the deadlock. Another way that the deadlock can be caused through mutexes is that key is returned only when a process leaves, not when context switched out.¹⁴ If the thread is in a mutex and is context switched out through calling another process or a thread the mutex key with that thread and nothing can get in or out of that mutex except? that thread This will deadlock if the second thread needs anything other than the first thread.
  
  9: If interrupts are disabled while a process is in a critical section, then why have mutexes?
  
  10: Is that how disabled interrupts provide mutual exclusion?
  
  11: Do you mean “critical section” instead of “mutex”? If so, what prevents a process in the critical section from accessing resources outside the critical section? If not, what resources could a process need when in a mutex? And what does it mean to be in a mutex?
  
  12: Why can't the thread get the resource? What's preventing it?
  
  13: True, but what happens when the mutex is eventually unlocked?
  
  14: How can a context switch occur if interrupts are disabled?
6. Yes, this is a realistic possibility. Given a group of threads this means context switching.¹⁵ If the interrupts and locking/unlocking aren't carefully handled,¹⁶ especially during context switches, all threads could get stuck, unable to access the mutex to execute, and if there is no way to interrupt it could be stuck in deadlock.¹⁷
  
  15: Oh? Why is that?
  
  16: What does “carefully handled” mean?
  
  17: True, but is that something that can possibly happen? Is there anything in the problem statement that could lead to this possibility?
7. This depends on how the mutexes and interrupt disabling is implemented. Each process or thread has critical sections. These critical sections are what needs to be isolated in order for the process to run safely without deadlock.¹⁸ Using mutexes is one way to do this, but mutexes themselves are critical sections. This is where the combination of interrupt disablers and mutexes can prevent deadlock on the process or threads.
  
  The most useful implementation of this is called a spin lock. This is where the process disables interrupts, checks whether the process is locked, if it is it enables interrupts until it is unlocked and then disables the interrupts again, after completing locks again and re-enables the interrupts. This is done in the lock method and unlock is just setting lock to false.
  
  So the answer is yes, they can find themselves deadlocked if the did not implement the interrupt disabler and mutex correctly.
  
  18: To run safely without deadlock, or without race conditions?
8. Yes, because mutexes are nonsharable¹⁹ and can only be unlocked by the thread that locked it (ownership issues) so if the thread is trying to access a mutex locked by a process/thread that is unavailable because that thread is also trying to access a locked mutex, they will become deadlocked.²⁰
  
  19: What good is a mutex that can't be shared?
  
  20: What happens if the mutex accessed by the second process/thread becomes unlocked?
9. Yes, a group of processes can become deadlocked when a locked mutex blocks before it can re-enable interrupts.²¹ gIn this case the user would have to reload or delete the processes in order to recover from deadlock.
  
  21: A locked mutex blocks what? Itself? That doesn't make sense. A calling thread? That makes more sense, but how does that prevent re-enabling interrupts?
10. Yes. As seen in the last lecture if a group of threads has a circular pattern of interrupt disabling²² it is possible that thread B is waiting on something that A has locked and therefore become blocked but before B blocks it could lock something that A needs once it comes back on.
  
  22: Is it possible to have a circular pattern of interrupt disabling, though? How could such an arrangement occur once the first thread in the cycle disables interrupts?
11. One possibility²³ is if the system contains more than a single CPU. Though one thread on one of the CPUs has interrupts disabled, the others will not.²⁴ However, on a single CPU system disabling interrupts and context switching would prevent threads from deadlocking, as long as the thread ran to completion.²⁵ However, disabling interrupts prevents the operating system from performing important required tasks, so it is not desirable. In effect, a greedy thread/process could turn the system into a sequential processing system, even with disabling interrupts threads can become deadlocked if they do not check for the mutex lock after being unblocked, in effect working up from being blocked and assuming the mutex is no longer locked.²⁶
  
  23: One possibility for what? Deadlock, or no deadlock?
  
  24: So that's what: deadlock or non-deadlock?
  
  25: What is the relation between mutexes and interrupt blocking?
  
  26: This answer is too long.
12. Yes, the implementation can still result in a situation where two or more processes will wait indefinitely for an event that can only be caused by one of the waiting processes. For example, take two processes A and B using two resources X and Y. Suppose process A is blocked and waiting on X,²⁷ and process B blocks and waits on Y.²⁸ When process A tries to lock on Y,²⁹ it must wait for process B to unlock Y.³⁰ Simultaneously process B must wait for process A to unlock X to continue. Because both processes blocked when trying to lock their resources, the unlock() calls cannot be executed, resulting in deadlock.
  
  27: Which means A doesn't yet have X, right?
  
  28: And B doesn't yet have Y.
  
  29: If process A is blocked, how can it try to lock Y?
  
  30: But B doesn't have Y, it's blocked on Y.
13. No, it is not possible for the threads to find themselves deadlocked entirely throughout the way they manipulate the mutexes. Being that a thread can't make a process³¹ due to other threads they will only become deadlocked in system where there are no mutexes.³² In this case mutexes are present because it manipulated it, it can become deadlocked only in certain parts of the system but not entirely. If a thread finds itself to be deadlocked then a simple solution would be to reboot/restart the OS system, in this case it is not entirely deadlocked that way.
  
  31: What does it mean for a thread to make a process?
  
  32: Then what causes the blocking behavior?
14. Yes, there is a group of processes that can get deadlocked entirely because a process may be dependent on other processes in which the deadlock condition will arise.³³ Moreover, disabling interrupts might not work on a group of processes.³⁴ In this case the processes are running and each process is dependent on some other process to complete. So they have a high possibility that the deadlock situation should arise using mutexes is implemented. Starvation problems may also cause to deadlock and have a process is waiting indefinitely for some other process in order if to run.
  
  33: How might the deadlock condition arise?
  
  34: Why not?
15. Yes, a group of processes can be deadlocked. If a context switch occurs in an critical section, then the process could deadlock because interrupts are disabled.³⁵ If process disables interrupts and then switches to another process before it can re-enable them, the second process will finish and not be able to tell the CPU that it is done.³⁶ Or process 1 thinks interrupts are disabled but they aren't.
  
  35: How can a context switch occur if interrupts are disabled?
  
  36: Why not? If the context switch can occur, why can't the process exit the CPU?
16. Yes, if the process or threads are manipulated by a mutex with too few (or many) interrupts disabled³⁷ the system may become deadlocked when they enter the locked function of the mutex.³⁸ Since the mutex itself is a critical section, interrupts must be disabled as soon as the lock is called when re-enabled after a check to see if the mutex is already locked but before waiting for it to unlock (if it is indeed locked) to prevent a potentially infinite wait.
  
  37: Interrupts are either disabled or they're not; there can't be too many or too few disabled.
  
  38: How? The mutex is locked and threads can't enter.
17. Mutual exclusion or mutexes³⁹ allows operating systems to prevent an executable activity from entering a region while other executable activities is in a conflicting region. As it is the case with most computer architectures, interrupt disabling is allowed on selective cases.⁴⁰ By disabling interrupts, exclusion of a critical region can be enforced while the one executable code is in that critical region. All other interrupts are postponed and scheduled to execute once interrupts are once again allowed. Exclusion can be enforced by disabling interrupts.⁴¹
  
  39: These are not the same things. Mutual exclusion is a property, and mutexes are a way mutual exclusion can be achieved.
  
  40: What does this mean? Selective how?
  
  41: What about deadlock?
18. Yes, it is possible. If one thread requires two resources that a second thread requires as well, the first thread cannot hold one resource while the second thread holds the second resource.⁴² When both threads try to allocate the resource they are missing, they will both be blocked, ending up deadlocked as neither finishes. This would be based on the order in which the threads manipulated mutexes.
  
  42: Why not?
19. Mutexes block other processes from continuing⁴³ while the key is being held.⁴⁴ No other program⁴⁵ can move⁴⁶ until the mutex is released by the running process. They are used to protect critical sections and providing mutual exclusion to the running processes. Since the process holding the key releases the key only when it is finished with the critical section, it has everything it needs to complete its process and release the key. Therefore it would not be possible to deadlock entirely based on the mutex.
  
  43: From continuing what? Execution, or locking the mutex?
  
  44: There is no key; that was a metaphor. The mutex is either locked or unlocked.
  
  45: Program or process?
  
  46: Move? What does that mean?
20. No, because a mutex is like a one-thread max policy.⁴⁷ It acts like a lock and key data structure to do mutual exclusions.⁴⁸
  
  47: What is a one-thread max policy?
  
  48: True, but how does that avoid deadlock?
An operating system has a modified round-robin scheduler that simulates priorities while still providing round-robin behavior. Describe an experiment you could submit to the system (that is, you don't have the ability to look at the operating system source code, you can only submit jobs) to demonstrate that the scheduler doesn't support true priorities.

A round-robin scheduler could simulate priorities by varying the quantum size; high-priority processes get bigger quanta. Or high-priority processes could be re-inserted into the ready queue closer to the queue head than lower-priority processes, although one might argue that such a scheduler is no longer round-robin. In either case, the effect is to give high-priority processes more execution time than low-priority processes while still maintaining round-robin behavior.

The lower-priority processes will still run along with the higher-priority processes, and that's the hypothesis the experiment tests. Submit a long, high-priority process and several short, low-priority processes, then examine the order in which the processes end. Assuming all process are compute-bound and spend most of their time executing, the short low-priority processes will terminate before the long, high-priority process, pointing out that the scheduler isn't maintaining strict priority execution order.

The answers, approximately verbatim, and in no particular order:
1. Since round-robin scheduler is a queue order scheduler meaning the first process comes into the CPU runs and then gets evicted and moves to the tail of the queue. Depending on how you want to prioritize the processes, using prioritizing indexes, then you could test this¹ by running a low priority process in the CPU first and then in the round-robin have a lower priority process then the one in the CPU then after that one have a process with the highest priority so it looks like this: [diagram]
  
  If the CPU doesn't take the queue priority next after it then the system doesn't support true priorities, and it will be a traditional round robin.
  
  1: Test what?
2. If the round-robin scheduler is implemented via a queue, jobs are processed FIFO order providing no concept of priority or pre-emption.² Should the round-robin scheduler implement a priority-queue submitting many high priority jobs will starve out low-priority jobs, in effect not providing true round-robin scheduling.³ A tiered priority queue in which processes navigate from highest to lowest priorities after a given quantum of execution would provide priority and reduce starvation while implementing round-robin selection.⁴
  
  A sequence preventing high-priority jobs from completing would be submitting one high-priority job but dozens of low-priority jobs. Without priority pre-emption round-robin is in effect FIFO: H-L-L-L-L-L-L-L.⁵
  
  2: There is pre-emption, otherwise there round-robin scheduling wouldn't be possible.
  
  3: Maybe, but that wasn't the question.
  
  4: Ok, but what's the answer to the question?
  
  5: But the question was about priority.
3. If you submit a job with highest priority to the end (or even the middle) of the queue it will demonstrate that it doesn't support true priorities because even though it will with the lower priority jobs to get to the highest one you submitted, it will take time to do this, it will not tend to the highest priority immediately as true priorities should.
4. If a process has the highest priority, but it takes longer than the interval the eviction algorithm specifies, it will be evicted to the end of the queue. An experiment with a process of the highest priority that takes longer then the giving interval would be evicted to the back of the queue behind many lower priority processes that are included.⁶
  
  6: And the results would be...?
5. You could set up a list of 4 processes in which the priority is set from weak up to strong. You can then set an interrupt after each scheduling that checks the priority of the next process. If the number 4 process does not come out first, then the scheduler doesn't support true priority.⁷
  
  7: Why doesn't that just indicate the high (or strong) priority process doesn't get preferential treatment in the queue? There are other ways of providing priority that don't involve queue manipulation.
6. Submit a set of jobs to the scheduler and let it prioritize them⁸ and being its round-robin behavior. While it is cycling through the processes submit a final job to the scheduler that would have a higher priority than any you submitted before. If the scheduler adds it in front of the highest priority process from the start, it has maintained the priority order but still failed to put the highest priority process next in the CPU. If it does put the new process to the front of the line, it no longer has its processes ordered from high priority to low (this assuming when the new process is put in the queue the process that went first and used to have highest priority is not at the head) next in the CPU.g
  
  8: By what criteria?
7. The experiment would be to submit a certain number of jobs that are numbered and sent in the order of what number they are. Make random numbered processes have a higher priority. A round-robin behavior scheduler is like a queue, priorities won't be reconsidered because it is a strict-ordered queue, which is first in first out data structure.⁹ The output would have the number of jobs in order, even the jobs with the higher priority will be in the right numbered spot.
  
  9: But the question says the round-robin scheduler supports priorities.
8. I would have several processes ???¹⁰ put jobs with the source priority¹¹ with one scheduler. This will not be able to meet all the processor tasks.¹²
  
  10: No idea; the word is unintelligible.
  
  11: What's source priority?
  
  12: Why not? And would you know? Also, to what does “this” refer? What does not meeting all processor tasks have to do with proper priority scheduling?
9. One way to test this is to put in several processes with different priority values but put them in best priority first. When the processes are executed they should adapt their priority¹³ and if the priority values come in lowest to highest order¹⁴ you will know it did not work.¹⁵
  
  13: Adapt their priority to what?
  
  14: How would that be determined?
  
  15: What didn't work?
10. A possible experiment to submit to the system would be to submit jobs that claim to have a much shorter execution time then they truly have.¹⁶
  
  16: And how do mis-stated execution times relate to priorities? And what would the results of the experiment be? And how would that demonstrate simulated priorities?
11. One experiment to submit to the system is to cancel or delete the priorities given.¹⁷ In order to demonstrate the schedule doesn't support the priorities is to make the program¹⁸ cancel the priorities to add on to the experiment,¹⁹ you can manipulate the schedule to crash the system.²⁰ I would create a false round robin scheduler to override the system and not make it work. Writing in another language could demonstrate the scheduler doesn't support true priorities.
  
  17: The priorities given where? And how are they canceled or deleted? And how would that demonstrate a lack of true priorities?
  
  18: You mean “process” and which process do you mean?
  
  19: What?
  
  20: What would crashing the system demonstrate?
12. You could submit a batch file containing programs with different levels on priorities (relative to the function of the system) in a certain order²¹ with some sort of identifying priority²² statement (that give priority level and process Id, assuming you know or have set this Id)²³ and see in what order the programs are executed.
  
  21: What kind of certain order?
  
  22: I guess; the word is unintelligible.
  
  23: This sort of priority statement is part of the batch file? Or something else?
13. One experiment you can do is to submit multiple jobs to the system that vary in time.²⁴ Since it is a round-robin scheduler, a job is removed from the CPU because a shorter job has come²⁵ about and the job²⁶ will be put at the end of the queue. By having the longest job complete it demonstrates that the scheduler doesn't support true priorities.²⁷
  
  24: What's the relation between job time and priority?
  
  25: Wouldn't that be a shortest-job next (SJN) scheduler, assuming SJN schedulers were pre-emptive?
  
  26: Which job? The job removed, or the shorter job?
  
  27: Any (correct) scheduler should have all jobs complete
14. Round-robin scheduling often deals with the waiting time problem.²⁸ On the other hand, priority based scheduling requires the OS respond immediately to the request of the process.²⁹ The modified round-robin scheduler would alter preference of process over other non-critical³⁰ processing but the deadline³¹ of the first may be missed. Again the modified RR scheduler provides some property of priorities but not all the critical ones.
  
  28: What's the waiting time problem?
  
  29: Does it? Even for low-priority processes?
  
  30: I guess; the word was unintelligible.
  
  31: Deadline? Where did that come from?
15. A round-robin scheduler provides response ???³² for long and short running processes. To demonstrate that a round-robin scheduler provides response priorities as described by a round-robin,³³ submit a long-running process and a medium-sized running process.³⁴ The round-robin should perform processor sharing meaning that each process thinks it is getting constant³⁵ service by executing selections of each process going back and forth.³⁶
  
  32: No idea; the word is unintelligible.
  
  33: What does this mean? What is something described by a round-robin?
  
  34: What does comparing run-time vs. size do?
  
  35: I guess; the word is unintelligible.
  
  36: Ok, but does this provide priority behavior?
16. An experiment you could submit the system would be able to check the OS priority increase³⁷ would if the round-robin does not maintain a priority invariant³⁸ then the scheduler is not supporting true probabilities.³⁹
  
  37: I guess; the word is unintelligible.
  
  38: I guess; the word is unintelligible.
  
  39: What might this experiment look like? What hypothesis is it trying to test? What results are expected, and how would they be interpreted?
17. The experiment you could submit to the system is to submit a high priority and a low priority job that return when they put into and out of the CPU, as well as their level of completion after execution stops.⁴⁰ When the jobs are done, if the high-priority job has recorded a time it is removed from the CPU which is incomplete⁴¹ and the low-priority job indicates it entered the CPU before the next time the high-priority job was executed, or finished, you have demonstrated the scheduler does not have true priority.⁴²
  
  40: What is level of completion? When process execution stops, wouldn't the process be done?
  
  41: I guess; the word was unintelligible.
  
  42: But is it always the case that a high-priority process finished before a low-priority job in a true priority-based scheduler?
18. If the operating system is usually round-robin behavior scheduler it is FCFS. In order for it to also use priorities it would have to constantly order the processes as they arrive. To demonstrate this scheduler wouldn't work I would send multiple processes of different and some same priorities to break the machine.⁴³
  
  43: Breaking the machine seems drastic
19. Being that we know that a round-robin scheduler will run processes in FIFO order each for an equal time slice and continue in that order until the processes are complete,⁴⁴ and that utilizing priorities should at least run higher priorities processes first, my experiment would be as follows. Submit a low priority job, followed by a high priority, and then one in the middle. I would then see if the priority simulation at least put them in order of decreasing priority. I would then watch to see the order in which the processes finish execution and repeat the experiment. Due to the nature of round-robin scheduling, I would assume that even if execution order changed, the processes would complete in the same amount of time no matter the order started due to each process getting equal time on the CPU.
  
  44: In what sense, then, can the round-robin scheduler be said to support priorities?
20. Submit several jobs to the system, for example, 3 with “high” priority and then one of “medium” priority. If the RR schedules priorities then we could expect that the three “high” priorities are placed ahead of the “medium” jobs in the queue. Now let us say that the three “high” priority jobs have a quantum of time higher than the quantum value of the scheduler so they will all be exited and pushed to the back of the queue. Now the “medium” priority is at the front, with the “high”s behind it.⁴⁵ If these were true priority these “high”s would be pushed to the front, but because it's a RR scheduler, they executed their time slot now the “medium” job can run before them. Proving that the scheduler doesn't have true priorities.
  
  45: How do you know this from outside the system?
A colleague of yours, noticing the similarity between thread suspend and resume and subroutine call and return, proposes using a stack for organizing thread descriptors in an operating system. Is your colleague's idea practical? Explain.
My colleague's idea not practical, because thread suspend and resume is not like subroutine call and return. Subroutine call and return occurs in strict FIFO order, which makes a stack an ideal data structure for storing run-time frames. However, thread suspend and resume is more general than FIFO order because any of the suspended threads can be resumed, not just the most recently suspended thread. A data structure for holding thread descriptors should provide more or less equal access to any of the descriptors.
The answers, approximately verbatim, and in no particular order:
1. Since threads themselves are usually implemented using a stack,¹ the suggestion has merit. A pop could be used in place of the call subroutine and a push used for return (since the descriptors are simply the threads registers and stack contents).² However, if a thread is suspended and later resumed under different circumstances (which would cause the description to be different) and a pop is not called at the time of suspension and a push at the time of resumption the stack could potentially have 2 different descriptors for the same thread.³
  
  1: Do you mean a run-time stack?
  
  2: Your colleague is interested in a data structure for storing thread descriptors, not execution state.
  
  3: Doesn't a thread have the same descriptor throughout its life?
2. Not really, since thread descriptors operate similarly to process descriptors: every thread would receive its own thread descriptor. Since every thread receives its own descriptor and receives its own set of resources there is no real need to stack the thread descriptors.⁴ This is assuming these threads are no way connected.⁵ This means that the thread wasn't forked from a parent thread sharing resources. This way there is no need to stack thread descriptors, although it wouldn't affect anything if you did.
  
  4: From that point of view, is there any reason to organize thread descriptors in any way at all?
  
  5: They all run in the same process, for example.
3. No, if a thread's descriptor is stored in a stack then that would mean the first resource the thread needs it at the bottom of the stack⁶ and the thread would run backwards,⁷ because the last resource it needs is at the top. I would suggest using a queue, because the resource would still be in the order the thread descriptor wanted then to be called in.
  
  6: Why's that? The thread's resources are stored in its descriptor in any convenient way, and the thread descriptors are stored in a stack, at least according to your colleague.
  
  7: What?
4. The colleague's idea can be practical, depending on the implementation. The operating system needs to keep track of the location of the thread and when it needs to be resumed. This means when a thread resumes it the stack must be found where it was left.⁸ This can be an issue if threads are pushed on top of the stack that need to be resumed.⁹ This could be fixed by giving each thread a stack. Doing so you need to make sure to point to the right stack before storing and resuming threads.
  
  8: What does this sentence mean?
  
  9: What is the issue? It sounds like an ideal arrangement.
5. Yes, it is practical. Using a stack would be helpful because it can keep track of the last thread/process that was running. This helps because we have a reference to the location of each process that was running before.¹⁰ Now in case we need to use its reference or find the location it is easy because the last process running should be put on the top of the stack.¹¹
  
  10: You mean references in the stack?
  
  11: True, but how often would you expect that to be the case in general.
6. [ not answered ]
7. I'm sure it could be done, but it is not an entirely practical way of dealing with thread descriptors. First off, a stack works in LIFO order, so the thread on top of the stack would always be the last one that the operating system put there, which is exactly the opposite order that say a round-robin scheduler would be looking for them,¹² and it would also be tying up whatever resources that a thread is using until it is the resources for the computation.¹³ Like I stated before, I'm sure it could be done, but there are better and easier ways to manage threads.
  
  12: Assuming a round-robin scheduler was in use.
  
  13: How does that work? Wouldn't a thread hold its resources until it's done with them, independent of how the thread descriptors are handled?
8. The idea is not practical due to the use of resources between threads.¹⁴ If a thread descriptor is entered into the stack and requires resources that the suspended thread below it requires, the thread will not be able to proceed and will remain at the top of the queue.
  
  14: The resources between threads are process resources (excpet for the CPU), and they're like global variables.
9. A stack is not practical because threads do not necessarily execute in LIFO order.¹⁵ Using a stack the most recently pushed thread would be first to be popped, should that thread be blocked waiting for another thread it may never complete. A linked list is better to navigate through the thread description blocks because it maintains an order versus all the permutations of threads being placed on a stack.
  
  15: Relative to each other, you mean.
10. No, my colleague's idea is not practical because implementing a stack only gives access to the last thread descriptor that was entered so if you are storing multiple things that you need random access to¹⁶ or need to be organized in any fashion, stacks are not the answer.
  
  16: True, but why would you need random access to thread descriptors. Why isn't your colleague's argument that random access isn't needed persuasive?
11. No, by organizing the thread descriptors using a stack, my colleague will not be able to call and return the desired thread at any time.¹⁷ This is because the nature of a stack only allows the last thread returned to be the next thread called. My colleague would be better of organizing the thread descriptors in a doubly linked-list so that all threads can be called an returned at any time.
  
  17: Do you mean suspend and resume? Because your colleague is arguing that desired threads can be called and returned at any time, hence the stack.
12. I don't think that this would be too practical because a thread is a sequence of executed statements from a program, and if there is a priority between subroutine call¹⁸ a stack can't comply with a FIFO base.¹⁹
  
  18: What does it mean for there to be a priority between subroutine call?
  
  19: What is a FIFO base?
13. No, the colleague's idea is not practical. A thread needs resources such as CPU, execution stack, and process information to execute. You cannot just call or return a thread and have it execute like you would call or return ???²⁰ and have it display.
  
  20: No idea, the word was unintelligible.
14. [ not answered ]
15. No, the colleague's is not practical because that algorithm of stack could possibly override the system.²¹ There are other ways in which to organize thread descriptors. There are similarities on suspend and resume and call and return but they do not work the same way. They work opposite.²² If the colleague's does this thing their system would fail if it is put into a stack. You would not organize that way.
  
  21: What? Override the system? What's that?
  
  22: “Working opposite” means what?
16. No, this idea is not practical. Switching between threads is not just about transferring control from one thread to the next.²³ All this data and calculations the thread has performed to this point must be saved as well,²⁴ which subroutines call and return may not have the ability to provide.²⁵ Storing the thread descriptors in an a stack would be inefficient. Suppose there are 10 threads stored in the stack (in order from 0-9), a stack can only be read from the head or tail so if thread 5 were to be called, I would need its information from the stack, it can't simply read from spot 5.²⁶ The information must be moved to a readable spot first. This is true for any thread descriptor that is not already at a readable spot and moving data this much is expensive and inefficient.
  
  23: It's not? What else is involved in switching between threads?
  
  24: Isn't that what the thread descriptor is for?
  
  25: Why not? Are you saying you can't make a subroutine call within a thread?
  
  26: But wouldn't the subroutine call create a new stack frame in the calling thread's process descriptor?g
17. This is an impractical implementation because data access on a stack is limited and possibly time inefficient. Threads need constant access to their resource²⁷ and each thread has its own descriptors. If a thread is scheduled and the next thread that gets has its descriptor at the bottom of the stack it is inefficient to pop all the other descriptors to get its descriptor.²⁸ Then if the previous thread is resumed its descriptor could (presumably) be at the bottom of the a temp stack. This is impractical, threads need better access to their descriptors.
  
  27: Assuming “constant” means “constant-time access” this isn't true, because threads compete for exclusive access to shared resources, and it's hard (maybe impossible) to provide constant-time access under those conditions.
  
  28: True, but would such a situation ever occur?
18. A stack implementation of threads organized in an stack without enforcing any priority will have the outcome of creating a first come, first served (FCFS) scheduling structure. Stacks do not enforce priority and my colleague's implementation will lead to starvation if a few long running processes need to be popped off the top of the stack for execution.²⁹
  
  29: But if they're on top, why would they need to be popped for execution?
19. No particularly. By using a stack you are assuming that thread D once started will not rely on anything that A or B have done.³⁰ This is because if D is halted it is thrown back onto the stack after C is pulled, creating a sense of deadlock³¹ if the rely too much on each other.
  
  30: Do threads A and B still exist? And how does a stack restrict D’s ability to rely on results produced by A or B?
  
  31: A sense of deadlock? Is that anything like a touch of danger?
20. It is not practical. Threads are a sequence of executed statements that may run simultaneously on the same system. If 2 processes are pushed onto a stack and the first thread³² completes, it cannot terminate until the thread on top of it completes and terminates as well before it can be removed from the stack.
  
  32: Thread or process?
First-come, first serve (FCFS) is the worst way to schedule disk I-O requests. One-way FCFS is a modified FCFS that takes as the next request the first request received that is also in the direction of disk-arm motion. If there are no requests in that direction, the disk-arm reverses motion. Does one-way FCFS improve on FCFS? Explain. Is one-way FCFS better than any of the other disk I-O schedulers? Explain.
One-way FCFS improves on FCFS by cutting down on disk-arm movement, thereby increasing throughput, at a possible cost of reduced responsiveness due to out-of-order request handling.
The answers, approximately verbatim, and in no particular order:
1. Yes, it improves FCFS because disk-arm motion is expensive. Since the modified FCFS doesn't move the arm all the way out if it doesn't need¹ to it saves valuable movement resources. It might be better than shortest seek time since shortest seek time can lead to starvation towards the outside of the disk.²
  
  1: FCFS doesn't do that either.
  
  2: Wouldn't SSTN lead to starvation anywhere on the disk?
2. One-way FCFS is slightly better than pure FCFS. Should disk requests trickle in slowly enough one-way FCFS equals FCFS.³ Also, should a new request come in that is just before where the disk arm is currently positioned, that request will have to wait for the disk arm to complete a total circuit. One-way FCFS is slightly better then shortest seek time next (SSTN) because SSTN can cause starvation, but one-way FCFS can have terrible delay. Scan in one direction then resets the disk arm to the starting position is a bit better then one-way FCFS. Request just behind the disk arm may have to wait but not as long as scanning in both directions.
  
  3: How can that be true, independent of arrival rate? One-way FCFS sweeps back and forth over the disk, while pure FCFS jitterbugs around according to request order.
3. This is a slight improvement to FCFS because it reduces lost time as far as disk arm movement is concerned. Given the case that requests continue to be in same direction. It allows tracking the queue for a better option that FCFS. However, it is still possible to request order could be so “bad” as to force the disk arm to move just as much as an inefficient FCFS, causing no improvement.
  
  Unmodified FCFS would be better than SJNS⁴ because it orders ???⁵ upon arm movement, which reduces lead time. Whereas SJNS moves the arm speculatively⁶ based upon the next shortest job.⁷
  
  4: Not the question.
  
  5: No idea; the word is unintelligible.
  
  6: I'm guessing; the word was unintelligible.
  
  7: You mean shortest seek time, perhaps?
4. One-way FCFS does improve on FCFS in the sense of saving time on unnecessary disk arm movement. FCFS if there is nothing in front of the disk arm the arm will continue to the end before it reverses.⁸ In one-way, it doesn't necessarily have to read the end of the disk before it returns to the opposite direction looking for the next closest task.⁹ One-way FCFS is better than traditional FCFS because the throughput is increased. Although this is better it is still not the most efficient I-O scheduler. I believe that a look circular scan would be the best option. It picks one direction and travels that direction looking for tasks, if no task exists in that direction , then it returns to the start without doing any I-O and starts again and begins searching for the next closest task in that direction. This schedule increase throughput and shortens wait time since it only looking in one direction and not reversing to look in the other.
  
  8: Why is that? FCFS scheduling reacts to queued requests and nothing else.
  
  9: Why not? If FCFS has that behavior, what prevents One-way FCFS from behaving that way too?
5. The one-way FCFS is a potential improvement on a standard FCFS schedule. One way it could be much less efficient is if a request is made on the outermost track while the disk-arm is traveling inward in search of another request that does not presently exist.¹⁰ This situation could be repeated in the reverse (inner request, outward movement) after the previous request was eventually handled, which would make it even less efficient than standard FCFS. That being said it is probably (more often than not) more efficient than FIFO and less potential for starvation than shortest seek time next, but is probably less efficient than a seek scan. The one-way FCFS utilizes the look strategy.
  
  10: Why would a FCFS-based scheduler do that?
6. One-way does improve on FCFS. It keeps disk arm movement to a minimum which makes an efficient scheduler for the OS, and will keep higher priority processes from waiting.¹¹ Whether or not one-way FCFS is better than other I-O schedulers depends on the circumstances. It would be better for a heavily loaded disk than it would be for a lighter load disk. The heavy load would increase throughput and decrease time¹² whereas using it on a lightly loaded disk would do the opposite.
  
  11: Do you mean in general, or specifically for high-priority processes? Wouldn't any form of FCFS scheduling ignore priorities?
  
  12: Throughput usually increases on heavily loaded systems, because there's always something to do. Latency becomes more important than throughput as load increases.
7. Shortest seek time next movement of the arm would lead to starvation problems.¹³ However, to fix this problem, restricting arm movement in one direction by allowing seek scan would eliminate starvation.¹⁴ An ordered queue restricting arm movement in one direction is an improvement on one-way FCFS¹⁵ I-O requests are performed.
  
  13: True, but the question is asking about a modified FCFS scheduler.
  
  14: True again, but not relevant.
  
  15: But that's what One-way FCFS is, isn't it?
8. No, it cannot improve itself just by reversing itself just because there are no requests in that direction. However, FCFS is better then most of the disk I-O schedulers.¹⁶ It is better in the way that it reads if something is there and plays it in the direction of the disk arm motion. Also other disk I-O schedulers cannot reuse their disk arm motion if nothing else is true.¹⁷
  
  16: No, it's the worst possible scheduler that isn't trying to be bad.
  
  17: What?
9. One-way FCFS does improve regular FCFS disk I-O slightly because rather than taking the request 72, 99, 180, 32, 25, 14, 120, 63 in order, it would move somewhat more like the scan scheduling in that say starting on cylinder 80 and moving towards 0, it would process 72 then skip down to 32, 25, & 14 before changing directions, thus taking away some of the head movement involved going straight through. It is still not as efficient as short seek in terms of throughput because it is still jumping around, and wait times would still be considerably higher when compared to look scan, circular scan or look circular scan, which all focus on reducing wait times.
10. One-way FCFS does improve on FCFS. It minimizes the expenditure of resources required to move disk arm about the disk to areas that are not near the current request. It stops the disk arm from skipping jobs that are nearer for other jobs and eliminates that ???¹⁸ first and eliminates the wait and resources used by this unneeded disk travel. This helps to maintain a higher throughput. The sacrifice is possible starvation of jobs in the opposite direction of the disk arm.¹⁹ It gives throughput and disk utilization higher than FCFS, at a risk of starvation. This is better than other disk I-O schedulers such as shortest seek time next in terms of fairness and preventing saturation.²⁰ However, shortest seek time next runs a higher throughput as idle time on the disk and unnecessary movement of the disk arm are decreased as only the nearest request is processed. However, it has at a risk of starving jobs that are far away from the disk's arm current position.
  
  18: No idea; the word was unintelligible.
  
  19: How would they starve, as opposed to possibly being delayed a little longer.
  
  20: What's saturation?
11. One-way FCFS is not better than any other disk I-O scheduler, and improves FCFS. The reason FCFS is good is there is no starvation so every process will be executed. One-way FCFS improves FCFS because it makes the movements of the disk head more efficient and the head moves less in one-way FCFS.²¹ One-way FCFS is not the best because the best scheduler depends on your situation or circumstance, depends on you much information is on your disk.
  
  21: In general, or always?
12. It improves if the one-way FCFS is using a reliable eviction algorithm.²² This should be valid²³ so it could stop processes the first request that comes in and processes another request band on the algorithm. Regular FCFS does not evict processes. Using FCFS in any way is still bad scheduling.²⁴ Entry time is not a good property to execute by.
  
  22: What? What is one-way FCFS evicting?
  
  23: I'm guessing; the word was unintelligible.
  
  24: I'm guessing; the word was unintelligible.
13. FCFS is a first-come first-serve scheduler. Processes²⁵ are executed in the order they enter the machine.²⁶ One-way improves on this by not just taking the first request, but rather the request tin the direction of disk-arm motion. If it isn't there the disk arm switches direction to find the process that is going to it in reverse. This is better cause the requests will be in the order they are going to the disk-arm, rather than the first process in the disk I-O.
  
  25: Disk I-O requests
  
  26: Are issued.
14. Yes, this new FCFS does improve because it cut down on time when the arm doesn't need to extend all the way if there is no request in that same direction.²⁷ But there is a better way when a request is made, the arm will extend to that point but this time it will continue in the same direction.
  
  27: FCFS doesn't do that either.
15. One-way FCFS improves on FCFS because it is restricting the disk-arm movement where FCFS has the partial to jump all over the disk and minimizing arm movement is key. One-way FCFS is better than the shortest seek time next scheduler because it has no starvation issue of never reaching the outer requests, and it is better than FCFS and shortest seek next in that it sets up an ordered queue, however it has poor throughput and this can be solved with a look strategy scheduler that stops when there's no more requests and scans back to the beginning.
16. One-way FCFS does improve on FCFS in that it is faster in processing requests. The FCFS is constantly checking requests from each direction where as the one-way simply processes all request in one direction and then processes all request in the next direction. One-way FCFS is better than SJN processes in that it minimized wait time without allowing large processes to "starve."
17. One-way FCFS improves on FCFS in that it reduces the movement of the disk-arm, increasing throughput. Determining if one-way FCFS is better than other I-O schedulers depends on the disk it would be reading and writing to. On disks that are lighter, one-way FCFS could be better than shortest-seek-time next, assuming that by taking requests properly one-way FCFS reduces starvation.²⁸
  
  28: True, but what does that have to do with disk load?
18. Yes, one-way FCFS is better than FCFS because it reduces the seek time thus it will enhance the performance in which is usually a problem for a regular FCFS algorithm. Going to one-way also helps to reduce seek time because each request is accepted when it is in the same direction of the disk-arm motion. It is better then round robin²⁹ because the new processes don't have to be added in the end but can be accepted if they are in the same direction of disk-arm motion.³⁰ This again helps to reduce the seek time.
  
  29: Round robin? Do you mean circular scheduling?
  
  30: What? Processes?
19. I assume this disk scheduler will ignore the second request received in the direction it is moving until it reaches the destination of the first request, even if the second request is closer.³¹ Yes, one-way FCFS does improve on FCFS because in FCFS if the disk receives three requests first in the center (starting from the left), second all the way to the left and third 3/4 of the way to the right [ diagram ] it will go right then all the way back left, then all the way right. One-way FCFS would first serve request 1, then request 3 then back to request 1. Saving an entire length of the disk in movement. No, this is still less efficient than look-scan scheduling. Look-scan scheduling has the added benefit that it looks at all current requests and goes to the nearest one in the direction it is traveling instead of the first one it received.³²
  
  31: True.
  
  32: That seems like scan; where's the look part?
20. Yes, one-way FCFS does improve on FCFS because it can minimize disk-arm movement, which will increase throughput. However, even though one-way FCFS does improve on FCFS, there are better disk I-O schedulers such as circular scan scheduling or look circular scan scheduling. Using these methods prevent the constant start and stop of the disk head, which can be expensive. These methods also provide short wait times.
The exec system call defined in programming assignment 1 is blocking. Describe the changes needed at the system-call interface (that is, by adding new system calls, or changing the parameters to existing system calls) to have exec be non-blocking. Describe how the new features would be used to perform an asynchronous exec call.
A process making an exec call blocks until the new process's id and the exec-call status can be determined. A non-blocking version of exec would return immediately with a tag value for the calling process. The calling process could then use a new system call, call it execStatus, which accepts a tag value and returns false if the associated new process isn't ready, or returns true, the new process id, and the status if the new process is ready (assuming the exec was successful; if it wasn't the new process id would be undefined and the status would indicate the problem).
The answers, approximately verbatim, and in no particular order:
1. Implement the nonblocking exec system call which executes a new thread that creates a virtual-machine in which to start the execution of the spawned process from the exec call.¹ To prevent the call from blocking the program data would have to be pre-loaded from the disk so that there can be no I-O blocking needed to wait for the disk.² The nonblocking exec system call would take the same input as the assignment 1 exec call. The operating system would have to be thread capable and processes would need to mention thread descriptor blocks to maximize the system.³
  
  1: What?
  
  2: Would preloading prevent blocking, or just make it shorter?
  
  3: What?
2. Since the exec system call now is blocking it means that the requesting process is removed from the ready queue until I-O is done. Assuming all the hardware architecture is the same as assignment 1. Modifying the exec system call to be exec(processID) then it could check if the exec call was successfully by checking the caller's register 0 which holds the status. Then depending on the status you can either ???⁴ executing the current process or if exec as successful then each current process and start executing the new process which id was passed in. This will allow for non-blocking I-O because the requesting process is left unblocked and still executable. This would allow for asynchronous exec calls because no matter what process ID you put into the exec call it will check before it can actually run, assuming there is a method ???⁵ exec call that rest the exec call if fails then exec process ID if pass then exec current ID. This is allowing for the random process execution that could happen.
  
  4: No idea; the word is unintelligible.
  
  5: No idea; the word is unintelligible.
3. [ not answered ]
4. For the exec system call to be non-blocking before it gives the CPU the new program to start running it has to save the current running process's information so it can be added to the scheduler and resumed⁶ when this new program⁷ is done or has finished its allotted time.
  
  6: If the call is non-blocking, what is getting resumed?
  
  7: You mean “process” maybe?
5. Implementing the getSlot, putSlot, and yield system calls would make the execution call non-blocking.⁸ With the yield call, get the current state of the executing thread and save it for execution.⁹ The getSlot and putSlot help with the synchronization of the thread process to allow one process to yield to the other process.¹⁰
  
  8: But they are implemented, and exec is blocking.
  
  9: And then what?
  
  10: Yes, but what does that have to do with the process doing the exec?
6. In order to make exec be non-blocking, we would need to assign IDs to each requester, and then allow the IDs to be queried, resulting in either being granted or denied the system resource that are being request. This allows us to block the requesting ID¹¹ until any resource conflicts are resolved when it can be granted resources and run without issue.¹² This then allows us to manage requester IDs much like processes in the process table while having an asynchronous block call with reduced risk for race conditions.
  
  11: But is that what the question asks for?
  
  12: Ha! You make joke.
7. In order to insure exec never blocks a yield() system call could be made as the first line of the instruction for exec.¹³ This would almost make exec equivalent to an interrupt (as any process currently executing would be blocked, possibly indefinitely). Another less extreme measure would be to write a value to the Halt register.¹⁴ Either of these measures would make exec an asynchronous call but at the cost of stability.
  
  13: But yield is blocking if there's more than one process.
  
  14: Wouldn't that block everything?
8. At the system call interface to make the exec system call be non-blocking I would use abstraction to make all entities¹⁵ look the same.¹⁶ The new feature would be able to perform an asynchronous exec call by treating everything the same way.¹⁷
  
  15: I'm guessing; the word was unintelligible.
  
  16: All what entities look the same. And how does looking the same deal with asynchrony?
  
  17: And how might that work?
9. [ no answer ]
10. A new system call will have to be implemented that determines when it is ok for the next process to start.¹⁸ For example, if false is returned the process cannot begin. If true is returned the process can begin.¹⁹
  
  18: The next process, or the new process?
  
  19: How does this provide non-blocking execs?
11. The new features would have nodes²⁰ that operate in a cycle of exchanging data and computing and at any point in time, all nodes are in the same iteration of this cycle.²¹
  
  There also would be an upper bound on the time it takes to send and deliver message.²²
  
  20: Nodes? What are they?
  
  21: What?
  
  22: This is an unrealistically strong assumption.
12. Exec could be told not to leave the queue²³ once it finished executing, in order for the requesting process to remain executable.²⁴
  
  23: What queue? Perhaps the run queue?
  
  24: Ok, but what details need to be taken care of to bring this about?
13. In order to make the exec be non-blocking, the system call interface would have to be modified so that the ready queue leaves the requesting process executable.²⁵ This new feature will perform an asynchronous exec call by allowing two resources to be allocated synchronously.²⁶ As long as each thread does not hold a resource needed by the other, the asynchronous exec call will execute.²⁷
  
  25: And what might these modifications look like?
  
  26: Sounds tricky; how might two resources allocated synchronously work?
  
  27: Oh.
14. The changes need to have exec be non-blocking is a mutex that doesn't deadlock the system. One new system call could be to have the user or system create a non-blocking program assignment.²⁸ The new features would be used to prevent this non-blocking habit²⁹ in the performance of an asynchronous exec call.³⁰ A buffer could also work for assignment 1 where the exec calls would go through the queue which will prevent the blocking.
  
  28: A non-blocking program assignment. What is that?
  
  29: I'm guessing; the word was unintelligible.
  
  30: But wouldn't you want a non-blocking habit in an asynchronous exec call?
15. By changing the parameters to the yield system call³¹ would allow processes to yield the exec call in order to continue³² and vice versa.³³ This would allow other processes to continue while the exec call also continues its process. A process would make an exec call to another process.³⁴ If there is a third process that has priority, it could yield the executed process. Once complete, the execed process would resume and complete.³⁵
  
  31: What does yield have to do with anything? And yield has no parameters to change.
  
  32: How?
  
  33: What does “vice versa” mean in this circumstance?
  
  34: What would be the effect of making an exec call to another process?
  
  35: That doesn't sound like non-blocking.
16. Changes to be made in the system-call interface.
17. The changes needed at the system call interface could have to allow exec to be running while another exec is running also.³⁶ The addition of another exec system call would solve this problem. With the addition of another exec call (called exec2 for example), the CPU won't go idle³⁷ because while exec call process is waiting for a resource, exec2 can start running a process. A buffer system where exec can copy idle processes would also work.³⁸
  
  36: Not really, because the OS is a critical section (usually).
  
  37: Is that the problem here?
  
  38: Copy idle processes? What is that?
18. To change the exec system call from blocking to non-blocking, the system call interface could instead implement pulling,³⁹ this way the process wouldn't be placed on a wait list. When they⁴⁰ are finished, they would be discovered as being finished by the interface when it returns out to them.
  
  The new features would perform as asynchronous exec call simply because of the fact that they are no longer blocking their processes.
  
  39: Pulling? What's pulling?
  
  40: They who?
19. The system-call would have to be modified in such a way that next requesting process stays in the ready queue (still executable).⁴¹ The seek() method⁴² could be altered to prevent⁴³ this.⁴⁴
  
  When seek is called, then passing the next process off the queue, it would just return and look for the next executable process.
  
  41: Yes, that's true.
  
  42: Seek? Where is there a seek?
  
  43: I'm guessing; the word was unintelligible.
  
  44: I'm guessing; the word was unintelligible.
20. To make exec non-blocking you could add new parameters that could represent another program id.⁴⁵ This way when a process⁴⁶ is executing, it would read another id⁴⁷ and execute that one⁴⁸ before waiting for the other process to end.
  
  45: Another program id? You mean in addition to the one the execing process wants started?
  
  46: Which process?
  
  47: Read another id from where? And what kind of id?
  
  48: Which one?

This page last modified on 2012 March 6.