4-1 Discuss how you would wish to allocate processes in the systems that were described in the introduction, for example:

A process dedicated to each source of external event: each sensor, each actuator. One or more processes to handle network communication. If a separate process is used to perform calculations on the gathered data then a buffering scheme and synchronisation will be needed.

Many arrangements are possible, see the UNIX case study for one example. One per active user (terminal line in the first instance). One to manage each independent device. One or more associated with memory management. One or more associated with any network connection. System services may have dedicated processes e.g. filing. Users may be allowed to create more processes dynamically.

A full answer should specify the function of each process and the points at which it must synchronise with client requests, device events, buffer access etc.

The point to make here in addition to the previous discussion is that you don’t want to sit and wait while your document is paginated or your mail is fetched. You want to get on with many things in parallel.

This is discussed in detail at the start of Chapter 27.

One process per compiler phase. If there are fewer processors than phases the system’s scheduler will automatically carry out the organisation.

4-2 How would you simulate one processor per process in a uniprocessor and a shared memory multiprocessor?

By being able to multiplex processes on a processor transparently. The basic mechanism is to save the state a process has built up on a processor when the process must relinquish the processor. The state can be restored on the (or a) processor when it becomes available.

4-3 List everything that might be considered part of the state of a process. Which of these items must always be in main memory and which could be swapped out to backing store when the process was not running?

The items in Section 4.3 are not intended to be comprehensive for every possible system. use a local system’s process state descriptor as an example. See the UNIX and NT case studies.

It is essential to be able to record that an event has occurred or a signal has been sent to a process while a process is swapped out. Associated with this is the state change from blocked to runnable.

Other aspects of process state such as register contents and open files are only needed when the process is to run.

4-4 Design a method of implementing synchronisation between a peripheral and a single process which is dedicated to managing it.

One dedicated process - the process descriptor can be used. The interrupt service routine knows which process to inform that the event has occurred. it can be programmed to record the event and change the process state.

How does the interrupt service routine know where to record that the event has occurred? The peripheral may have taken work from a transaction record, indicating which process is awaiting completion of the task. The descriptor of this process could be used as above.

Here we have the general case that any number of processes may be awaiting some event. The requirement may be that all should be made runnable and the first to be scheduled succeeds on obtaining, for example, a buffer made free by a transfer of its previous contents to disc.

We need event objects so that processes may indicate that they are awaiting some specific event and the event causer may signal the event.

4-5 Design a data structure which implements the representation of the processes known to an operating system. You should consider whether your system has a significant number of dedicated system processes and, if so, whether they will be held separately from user processes. What operations would you expect to provide at the interface of a process management module?

One possible structure was outlined in Section 4.5. Various alternatives are possible. Linked lists could be set up through a pool of descriptors. Separate lists could be held for blocked and runnable processes. Several run queues could be maintained either according to a fixed priority scheme, a dynamic priority scheme or according to recent behaviour, such as the most recent reason for blocking.

4-6 When does a general schedule need to be carried out in a multi-access system?

When the current process blocks.

When it is in a compute-bound phase it will use up its time slice. It may then be scheduled round robin with other processes behaving similarly or a multilevel queue arrangement might be used. A lower priority queue has a longer time slice. If you use up your timeslice at one level you drop a level.

Section 4.6 sketched how priority could be associated with different reasons for blocking.

One per separate user task, others for managing system resources.

One for each communication in progress (data from several separate communications might be arriving interleaved). Others to respond to new communications.

One for each client with work in progress. Others ready to respond to new clients. Others to manage storage devices.

The additional requirement is that media streams must be serviced periodically at rates appropriate for the particular medium. Synchronisation between different streams may be required (e.g. talking head). A fixed allocation of priorities with pre-emption is not suitable, for example, a video stream might be given high priority to achieve the required throughput. It is necessary for a voice stream to be given time regularly, even if it assigned a lower priority than video.

4-7 How does scheduling for real-time systems differ from scheduling for multi-access systems?

For many real time systems it is possible to work out a schedule in advance. For example, it may be known that a certain process is periodic with period 20 units of time and it must run for 4 units of the 20. Other processes are specified similarly. The normal working schedule can be precomputed. Alarm conditions cause special catastrophe procedures to be invoked.

4-8 What approaches can be taken to scheduling for shared memory multiprocessor systems?

This question will also be relevant later when we discuss the freeing of processes that are blocked on a semaphore or condition queue.

The basic issue is whether we should attempt to schedule co-operating processes at the same time on different processors, for example the threads of a process. Should the application be able to specify which threads should run together? Or should the kernel be kept simple and provide the least possible mechanism?

4-9 Recall the layered communications software described in Chapter 3. Consider the situation when several user processes have made requests for network input or output. How might the layers be executed by processes? How might synchronisation between user-level processes and the arrival or transmission of data at the network be arranged? Where might network buffers be located with respect to the ISO layers? Why would it be a bad idea to have a process execute each of the ISO layers?

A good paper to read on this general area is:

Clark D D, "The structuring of Systems Using Upcalls" ACM 10^th SOSP and Operating Systems Review 19(5), Dec 85.

The point is made in the paper that communication is initiated both top down and bottom up. Procedural invocation is often set up for top down invocation but not for bottom up - this is achieved by an asynchronous signal mechanism. The client should be given a choice between this and an upcall mechanism. Clark suggests that each layer could comprise a number of modules that can be invoked procedurally top down or bottom up.

This is an example of the need for a multi-threaded service, so that threads can work on behalf of different clients but can access shared system data.

Although each layer provides a service for higher layers it is not a good idea to dedicate processes to providing layer functions. This would involve too much context switching overhead.

We assume that a pool of buffers is available for use by applications and incoming data. In Chapter 6 we introduce the idea of mapping to avoid copying. A similar idea could be used here. An application could request some number of pages from a buffer pool which could be mapped into the process address space and mapped out again on transmission. We do not assume buffer areas associated with each layer - layers in general add or remove headers and possibly trailers.

4-10 For a given modular operating system structure, what is the minimum set of dedicated, resident system processes that can be used? How does the rest of the operating system get executed in this case?

It depends on the type of system. Assuming a general purpose system, there must be a process that is permanently resident in memory that can organise the bringing in and swapping out of other processes.

There must be a process that is ready to respond to the or a user coming on line.

Associate processes with each system function and have services invoked by message passing.

For both of the approaches indicated above, discuss where a separate address space could be used for protection purposes. Assume that the system provides a mechanism for a process to make requests of the operating system. We have studied one such mechanism in Section 3.3.2. We shall expand on this in Part II.

The book does not emphasise hardware-enforced protection domains. This is a topic which might best be treated in a later course on special architectures. The trend has been towards software-enforced protection through type-checking in modular programming languages.

In outline, at one extreme a separate hardware-protected protection domain could be provided for every service. Architectures vary as to whether domains are considered to be self-standing or to be "in process". A domain switch would be needed on every service call. A capability architecture would be needed to support this.

Less general hardware support is achieved by the provision of rings of protection, for example, Multics was designed to have 64 but was built with 8. In this case, the OS and utilities may run "in-process" but may have varying degrees of protection associated with them. In a conventional system we have two rings or domains and it is common to provide the OS "in-process" as a single protected domain. With this model the OS occupies part of the address space of every process but is still protected.

An alternative approach is to use separate address spaces more liberally and to provide a mechanism for invoking a service in one address by a client occupying another. An OS could be provided in this way or could be subdivided into separate services.

4-11 In what circumstances might it be advantageous to use several threads of control within a single process?

If the process has several distinct tasks to perform or the same task on behalf of different clients.

4-12 Section 4.9 introduced a process management module and pointed out that, as this module implements the process abstraction, it cannot itself be implemented in terms of processes.

Within an operating system, the interface operations of the process management module may be called as simple procedures. In Section 4.4, for example, we saw the WAIT (event) operation invoking the BLOCK (process) operation.

In Section 4.10 it was mentioned that an operating system might be executed by a set of system processes taking users’ requests or might instead be executed "in process". For both of these models of execution, discuss how the invocation of process management can be incorporated into the model. (The problem to address is, if you are executing the operating system yourself, what happens when you block yourself?).

The question relates to the creation of an abstraction. We create the process abstraction, perhaps at the lowest layer of a system as in THE, or in a process management module. Above this level, or outside this module, all execution is carried out by processes. Below the level, or within the module, the process abstraction cannot be used. We have to contrive to execute the required code without the benefit of the abstraction.

4-13 What aspects of the state of a process are of concern to an operating system and a language system?

The OS is concerned with the allocation to a process of any resource that it manages. For example, the OS is concerned with the pages of physical memory that are allocated to a process. It is not concerned with the fine-grain representation of process state within those pages. That is the concern of the language run-time system.

4-14 Discuss how a sequential programming language can be used to implement a concurrent system. What assistance would you expect from a library package and operating system? What are the advantages and disadvantages of using a concurrent programming language?

Either separate tasks are programmed as separate programs executed by separate OS processes or the sequential language is augmented by library calls to support multiple threads of control within the program.

In the first case, it is necessary for communication between the components to be supported by the OS. This may mean that the system is not portable.

In the second case the underlying OS may be incapable of seeing more than one thread of control per program. We explore these issues throughout Part II.

4-15 What is the essential difference between co-routines and processes? If a concurrent program is to run on a uniprocessor machine, what advantages are there in using a language which supports processes? When might co-routines offer an advantage?

You program the scheduling of co-routines yourself; either the language system or the OS schedules processes. If you use co-routines you cannot respond to an event immediately. If you use language-level-only processes you still can’t. If you use language level processes known to the OS, and the OS supports pre-emptive scheduling and process priority you can arrange immediate response.

Co-routine switching incurs very little overhead. It might be that your application does not require immediate response to events; or it might be the case that pre-empting the processor on an interrupt is bad for some application areas; for example, a high speed network might interrupt the processor too often from work which has a deadline for completion.

Co-routines and language level processes run to voluntary suspension, so within a single OS process there can be no interference between them. They can maintain the consistency of data structures shared between them.

4-16 What are the potential problems of using a language-level "threads package" when the operating system sees only one process? Why might such a scheme be inappropriate for a shared memory multiprocessor?

Synchronous I/O (blocking system calls): the OS sees the whole process as blocked.

Response to events: the OS cannot schedule some specific thread when an event occurs.

The separate language level threads cannot run simultaneously on the processes of a multiprocessor.

4-17 What are essential requirements for real-time response to be achieved?

Note that real-time does not necessarily mean "very fast". It must be possible to bound the delay (that is, to know the maximum possible delay) between an event occurring and the associated (possibly user-level) process running.

Different application areas have different characteristics. Pre-emptive scheduling must be an option so that alarms can be serviced immediately they occur.

4-18 What is meant by a static specification of processes in a programming language? How would you expect a static approach to be reflected in the syntax of a language?

Processes are created at compile time rather than run time. You may be given syntax to create a "process" module or to bind a number of processes to a module.

A common approach is to use a special kind of procedure call, often called "fork" which causes a child process to be created to run in parallel with the parent. The parent continues, the child executes the called procedure. On return from the procedure the child may explicitly or implicitly "join" with the parent, that is, be deleted.

The child’s identifier may be returned to the parent when the child is created. The parent might be able to make system calls with this identifier as argument to request information on the child or control it.

4-19 You are working in an environment where application developers need to be able to use different scheduling algorithms. Which thread architecture would be most suitable and why?

A user thread package would be appropriate, at least during application development. Kernel threads are usually scheduled according to the operating system's scheduling policy. If a scheduler activation scheme is used we have both application-level scheduling and kernel threads.

4-20 Are there any disadvantages arising from using only kernel threads in an application?

Assume a scheduler activation scheme is not available. Kernel threads are more expensive (in context switching) than user threads (although less expensive than processes). If the application generates a large number of user threads it may be better not to make every one a kernel thread. Any thread that potentially makes a blocking system call should have a separate kernel thread.

4-21 Discuss the pros and cons of multiplexed threads compared with scheduler activation.

Multiplexed threads puts the responsibility on the programmer to decide how user threads should be mapped onto kernel threads. This is difficult to get right.

Scheduler activations involves cooperation between the operating system and the runtime system to keep a given number of threads in the ready state for the OS to schedule. If a thread blocks the runtime system is informed and replaces it with a runnable user thread. The runtime system may then implement whatever scheduling policy it wishes.

4-22 Discuss why soft real time requirements, such as those that involve dynamically arriving continuous media, might best be met with a combination of user and kernel threads.

The application needs some kernel threads, plus the ability to allocate high priority to them, so that they may be scheduled immediately their event occurs. As discussed above in 4-20, it is best not to use a large number of kernel threads and some lower priority application activities may best be left as user threads. A scheduler activation scheme allows this decision to be avoided.