Lists and Queues
The operating system uses lists and queues extensively. One of the most common usages of these structures is to hold in an orderly manner the control blocks that represent the tasks that are in various stages of execution. (A task can run, it can wait for an external event such as an input/output operation, or it can be ready to run but held because its priority is not high enough). The control blocks are moved in and out of these stages. Discuss how you would implement these structures. Would you use lists or queues? Please consider aspects of efficiency and robustness.
Lists as described by Mouratidis (2004) is “Sequence of elements whose order is significant, Elements can be added and removed anywhere in the list” and Queues are defined like “A restrictive form of list that obeys a First-in-first-out (FIFO) rule e.g. the queue at the bus stop!” (Mouratidis, 2004). So we find both are data structures which maintain a list, both have significant order but the key difference is that the List allows elements to be added and removed from any location whereas the Queue has just one entry point and an exit point. Apart from the simple Queues, there is another important data structure known as Priority Queue, “The ADT Priority Queue keeps track of numerical costs of the objects it holds” (Chvátal, n.d.) which is used more commonly by the Operating Systems.
Considering these attributes we can easily measure the pros and cons of each approach. Where List is flexible, Queue is fast and where the List requires keeping address map of each of its element, the Queue can do away with only two pointers i.e. to the starting element and the ending element.
An operating system has mission of managing computer resources on behalf of processes (tasks). So it must know the status of the processes and resources. Various status tables are maintained for this purpose. Our concern is to see the most efficient and robust implementation of a Process Table. The main purpose of this data structure is to maintain,
- Process identification data
- Processor state data
- Process control data
OS then uses the Process control information to schedule process state, maintain process structure information, interprocess communication information, process privileges and accounting information. (Callari, n.d.)
Having considered the type of data and its uses a process table is more efficient to be implemented using a Priority Queue ADT (Downey, n.d.) which is not a simple FIFO but it keeps a priority along with an element stored in it. Since remove operation retrieves the item with highest priority it suits perfectly to cater the requirements of high priority OS tasks. The limited but useful interfaces, connected elements and fast retrieval of a Priority Queue make it ideal candidate for implementation of a Process Table.
References
Mouratidis, Haris, 2004, Data Structures and Algorithms Lecture 4: Stacks, Queues. [Online] http://www.dcs.shef.ac.uk/~haris/DSA/Lecture_Week_4_lists.ppt [December 3, 2006]
Chvátal, Vašek, n.d., The abstract data type Priority Queue. [Online] http://www.research.rutgers.edu/~chvatal/notes/pq.html [December 3, 2006]
Callari, Franco, n.d., Process Control Blocks. [Online] http://www.cim.mcgill.ca/~franco/OpSys-304-427/lecture-notes/node7.html [December 3, 2006]
Downey, Allen B., n.d. Queues and Priority Queues. [Online] http://www.ibiblio.org/obp/thinkCS/cpp/english/chap20.htm
