I seem to recall from my “Advanced” operating systems class, some general problems that need to be addressed when dealing with OS concepts. However I have long forgotten the exact details, hence the true meaning. One was the File Update Problem and the other one was called the Readers and Writers problem. It was used to explain semaphore usage and such. Also there is a certain case where paging algorithms failed miserably and easily deadlocked, rendering said deadlocked hypothetical OS completely useless. Any help here greatly appreciated.
The readers-writer problem is fairly simple. You can have multiple readers at any time, becuase they do change the file. You would only want one writer at a time because they are changing the file. You also don’t really want a reader while there is a writer since everything is changing. But if you allow other readers to jump on while one reader has control of the file, then they con monopolize the file and not allow writers to ever have access.
The classis case where paging failed is where a working files is much larger than the available memory, and the instructions jump around a lot on the file, causing a whole lot of page swaps. Each instruction that should take a clock cycle or two ends up taking magnitudes of time longer becuase it ends up accessing physical memory. Its called thrashing I believe.
The file update problem doesn’t ring any bells, other than the situation for readers-writers.
There are a couple of file update problems, such as the previously mentioned reader/writer problem. Another problem is dealing with linked/shared files, where one user deletes a file, but another user still has a link to the file. Ie. UserA has ~/test/FileA and userB has ~/test/test2/FileA which is a link to userA’s FileA. If UserA deletes the file, UserB should still have a valid link to the file. The file is not deleted, rather UserA’s directory pointer to the file is.
Thank you very much Narile that is exactly what I was looking for.
As for the Readers and Writers problem… Yes, wolfman your description set my heart at ease. In fact I had forgotten the intracacies of the original problem itself. What I was searching for in a problem description though is commonly called priority inversion, as far as priority constrained job queues are concerned. Thanks for the information.
Personally, I prefer the Dining Philosophers Problem. At least it involves food.
Here is a fun one for you, I regularly ask it when I am interviewing canidates for jobs here.
You have a singularly linked list of unknown length, and limited free memory. You discover that due to a small coding error in an insert routine, you might have just created a pointer that links back to a previous node in the list. How do you detect the infinite loop if one exists. Remember that the list is of unknown size. Also assume that you are able to prepare for this eventuality but space is still limited, so an array of the lists contents is not feasable.
Here’s an example of that that comes up from time to time. People often think it would be nice to have a scheduling priority where a process only runs if no other processes are using the CPU, i.e. the process would only get scheduled if it was the only process in the run queue. It can lead to deadlock thus:
Suppose process A has this scheduling priority. Process A acquires a lock on some resource, and before relenquishing the lock it is pre-empted by process B which is scheduled at a higher priority. Process B wants to use the resource that process A has locked. Process B spins the CPU waiting for the resource to become free. Since process B will always be in the run queue (it’s spinning the CPU), process A will never get scheduled, so it can’t release the lock.