Questions up to 1992

Questions up to 1992

The following are extracted from Computer Science papers at Cambridge. In each case the year the question was set is indicated. I have included a few questions from related areas such as computer architecture and communications and a few from follow-on courses such as Security, Distributed Systems and Computer Systems Modelling to show the context for Concurrent Systems.

PART I

92 Consider the design of operating system facilities to support the input and output of data by user processes. Suppose that there is a dedicated device handler process for each device and that, while the handler transfers a fixed amount of data between memory and the device interface, a user process may request the transfer of an arbitrary amount of data by means of a system call.

Describe how data transfer and synchronisation may be arranged

between the handler and

(a) a system process carrying out a user’s request;

(b) the device.

In each case, outline the data objects, associated operations and synchronising primitives that might be used.

92 Describe the operating system data structures required to support a virtual memory system with both segmentation and paging, and how memory sharing between different processes is implemented.

Describe what operations must be performed by the operating system on an address translation failure and the relative merits of implementing some of these functions in hardware rather than software.

What would be the benefit of implementing both swapping and paging in such a system?

88 Does the ever-increasing availability of real memory do away with the need for virtual memory systems? Distinguish in your answer between the requirements of large timeshared computers and those of single user workstations.

What is the point of using hardware-supported segmentation as well as paging in a virtual memory? Discuss the choices about the size of the segment number field in a virtual address.

88 Describe a hardware method of storage allocation and protection which allows separate concurrent user programs to share library routines in the main store. Estimate the hardware needed and the likely performance reduction. What are the compensating advantages?

89 The following reasons can be given for the use of memory management (relocation and protection) hardware in a computer system:

(a) to provide a larger virtual address space than real memory;

(b) to support the efficient management of real memory by the operating system;

(d) to provide protected sharing of system utilities such as compilers, editors and libraries;

(e) to provide protected sharing of parts of the operating system;

(f) to provide protected sharing of applications subsystems.

For each of the above:

(i) indicate memory management hardware that would meet this requirement;

(ii) discuss the kinds of system for which this requirement would and would not be important.

92 Among the functions of a filing system are path-name resolution, access control, concurrency control and existence control.

A network-based file storage service supports the file abstraction, where a file is an uninterpreted sequence of bytes with a unique identifier.

For each of the four functions listed above, discuss whether it might be located in the service or in the client systems.

92 A file system is required to support random access to files of several tens of megabytes; describe two file structures which would support this efficiently.

For your mechanisms, describe and provide estimates of the costs incurred in accessing random blocks.

How would your two mechanisms cope with the insertion of a new block into the body of the file?

91 Discuss the relative merits of three different methods which can be used to represent a file as a sequence of disk blocks. In each case, what would be a suitable representation for the list of free disk blocks?

How can the algorithm for the allocation of free blocks be tuned for different uses?

91 In a general-purpose filing system the "file" is usually the unit simultaneously of naming, of access control, and of interlock. Discuss the circumstances in which it is suitable to have the same unit for all three, and give examples of each being an unfortunate choice. Under what circumstances might it be desirable to use advisory locks rather than enforced ones?

88 Compare and contrast Access Control Lists and Capabilities as mechanisms for the protection of data.

A user U normally has authority to access files F1 and F2. The user U executes a program P which requires to access file F3. Describe how protection techniques based on (i) Access Control Lists and (ii)

Capabilities may be employed:

(a) to prevent user U from accessing file F3 other than by executing program P;

(b) to prevent program P accessing file F1 when U executes P, whilst allowing P to access F2 when U so require

89 Multi-access operating systems need to provide both protection and sharing. How would the system software, interacting with the hardware, meet the following requirements?

(a) It must be impossible for users to program the line printer directly resulting in interleaved lines of output;

(b) once a user process is running on a processor it must be possible to stop it and let other processes have their turn;

(d) it must be possible for users to execute a shared copy of system utilities such as editors or compilers but impossible for them to corrupt these utilities, the operating system or other users’ code and data;

(e) it must be impossible for one user to login to the system with the identity of another user.

92 Under what circumstances might an operating system’s process scheduler be able to avoid a general process schedule?

How might the priority of processes be made dynamic without a large computational overhead?

A programming language supports lightweight processes which share memory. The operating system on which the language is to run allocates a separate address space to each of its processes. What problems do you foresee with this arrangement?

How could a different operating system design avoid these problems?

91 A function of an operating system is to create the process abstraction. Outline how this is done. How might synchronisation between a process and the hardware be supported? [For example, consider a device handler and the associated device.] How might synchronisation between processes be supported?

91 Outline the design of a scheduler which is required to implement static priorities and time-slicing. Discuss your design choices.

What modifications would you make to support:

(a) a large number of priorities;

(b) multiple threads per virtual address space;

88 The process management subsystem of a multi-access operating system contains a process table with space for a maximum of 100 processes. Each entry in this table is a process descriptor (process base).

Discuss in detail the design options for the process descriptors showing how, for example, process priorities, process scheduling and synchronisation with the hardware might be supported.

89 A distinguished scientist once criticised an operating system named OS/360, alleging that it was wasteful of memory space and that its design was unnecessarily embellished:

For example, OS/360 devotes 26 bytes of the permanently resident date-turnover routine to the proper handling of December 31 on leap years (when it is Day 366). That [function] might have been left to the operator. Source: The Mythical Man-Month (Brooks, 1975)

Contrast and compare the two alternatives for handling extraordinary date calculations (such as leap years): when the operating system handles these, and when the computer operator must handle them. Does your analysis bear out the opinion expressed in the above quotation?

PART II

88 The kernel of a multi-access operating system for a uniprocessor machine is mapped into the address space of every process. Each process occupies a separate address space. The kernel runs almost entirely "in-process" apart from a very small number of dedicated system processes. Processes are scheduled pre-emptively.

(a) Outline the type of facility that might be provided in such a system for communication between processes executing in user mode; i.e. not executing the kernel.

(b) Give a detailed solution for processes accessing a kernel data structure which may be required either for shared reading or for exclusive writing.

89 A language runtime system contains a manager for items of type SEMAPHORE.

(a) If the language offered semaphore operations to the programmer, how would semaphores be declared, initialised and used to achieve:

(i) exclusive access to a shared data structure;

(ii) synchronisation between pairs of processes;

(iii) allocation of multiple instances of a resource?

(b) If the language offered a critical region construct such as:

region v do begin . . . end;

where variable v has been declared as a shared instantiation of some data type, how could the compiler use the semaphore manager to implement this construct? Discuss how synchronisation over the state of the resource protected by the region might be offered in the language and implemented.

91 The requirements for implementing a concurrent system may be stated as follows:

(a) support for separate activities;

(b) support for related activities to work together;

Discuss how these requirements may be met through use of a suitable language system and operating system. Explain why some combinations of language system and operating system will be unable to meet these requirements.

a) Describe how the components of a Remote Procedure Call system relate to the OSI reference model.

b) How does the design of the underlying operating system affect the implementation of an efficient RPC system?

89 The diagram shows the major components of a language level remote procedure call (RPC) system.

For the case where the RPC system uses a request, reply, acknowledge protocol and offers a choice of at most once or exactly once semantics:

(a) explain what happens at points A, B, D and E when the network and both calling and called systems are performing well;

(b) explain how the protocol deals with transient network congestion;

(c) explain how the protocol deals with a crash in the calling system which occurs after a call is made and before the result is received;

(d) explain how the protocol and/or higher levels in the system might handle prolonged network failure or a crash in the called system followed by a restart.

PART III

89 You are designing an airline booking system.

(a) Discuss the facilities you would look for in a language and/or operating system to ensure that an operation such as "book two seats on flight n" could complete correctly.

(b) Explain the additional facilities that would be needed if your system was to automate the booking of seats on a number of connecting flights where all or none of the flights should be booked.

92 Outline the following three approaches to concurrency control in transaction processing systems:

(a) two-phase locking (2PL);

(b) timestamp ordering (TSO);

Say briefly how each of the methods achieves serialisability.

Why are TSO and OCC ostensibly more suitable for implementing a distributed transaction processing system than 2PL?

89 Explain why a transaction of an application program with a database may be regarded both as a unit for recovery and as a unit for concurrency control. Describe briefly two basic approaches by which the scheduler of a Data Base Management System can ensure that the interleaving of operations in concurrently executing transactions cannot lead to inconsistencies in the database. What potential problem(s) of basic Two-Phase Locking does Strict Two-Phase Locking avoid?

91 What are the advantages and disadvantages of a persistent programming language when compared with a relational DBMS for use in database applications? Describe extensions to the compiler and run-time system of a programming language that are required to maintain persistent data values and to support the database programmer.

PART IV CASE STUDIES

92 For the UNIX process state graph given below, describe each transition briefly. Indicate which of the transitions show that UNIX is executed procedurally.

88 UNIX is an old operating system, and since its inception hardware and software techniques have progressed significantly.

Describe which design features are no longer appropriate, still relevant, and now relevant for different reasons.

88 Describe all aspects of how compatible file, device and inter-process input and output are achieved in the UNIX operating system.

What are the good and bad consequences of this generality?

What has been done about the bad consequences in recent versions of UNIX?

89 Explain how UNIX system calls may be used:

(a) to create two processes which read records from a common data file, perform some processing on the records and write results to a common output file;

(b) to create two processes in a pipeline such that one reads units of data from a file, performs some processing on each unit and produces some intermediate output and the other takes that intermediate output, performs further processing and writes a final results file.

For each of (a) and (b) above explain how the system calls are implemented.

91 With reference to the diagram below which shows the basic modular structure of the UNIX kernel, explain briefly:

a) how the buffer cache is used;

b) the UNIX model for achieving dynamic execution of the kernel by processes.

88 Either:

(a) The TRIPOS Operating System disables interrupts whenever critical regions of code are executed. Discuss, with particular reference to TRIPOS message passing, scheduling and storage management, whether this design decision was sensible.

Or:

(b) (i) Describe the relationships between tasks and virtual address spaces in IBM’s MVS operating system and between processes and virtual address spaces in UNIX. What are the advantages and disadvantages of the two approaches?

(ii) A file in the MVS operating system need not occupy a contiguous area of disk. Explain, in general terms only, how the system records where a file’s contents reside on a disk. What are the limitations imposed by this scheme? Are there any advantages?

ARCHITECTURE

91 Use the design of the MIPS R2000 processor to illustrate how instruction execution time can be made to approach one clock cycle.

91 Discuss the approach to provision of support for:

(a) subroutine call and return;

(b) interrupt handling

in the MIPS R2000 processor.

92 The five phases of instruction execution in the MIPS R2000 pipeline have mnemonics: IF RD ALU MEM WB.

(a) Explain what is done in each phase by using the following program fragment as an example. Assume that register 2, $2, contains the address of the start of a data area.

LW $3, 0($2) % load word into $3

LW $4, 4($2)

ADD $5, $4, $3

SW $5, 8($2) % store word from $5

(b) Using the above program, explain why a load delay slot is necessary.

92 A MIPS R2000 virtual address comprises a 20-bit virtual page number and a 12-bit within-page byte offset.

Outline how address translation is performed by the on-chip memory management unit. Explain how a translation lookaside buffer (TLB) entry is set up by an operating system.

Discuss the factors influencing the size of the TLB. Would you expect 64 entries to be sufficient?

89 Many central processing units have features or special instructions which were included because they can be exploited to good effect in or via an operating system. Describe four such features, explaining the consequences for an operating system and for the user of their presence or absence.

SECURITY and PROTECTION

88 Public Key Encryption has been suggested to be a secure means of establishing mutual authentication of two interacting entities on a network.

Starting from the position where neither yet knows the other’s public key, describe carefully how a two-way communication link is set up, identifying at each stage what authenticated information each has gained about the other.

To what extent is this procedure reliant upon the correctness or trustworthiness of an Authentication Server on the network? What advantages does Public Key Encryption have over normal encryption methods?

89 Suppose you are designing the software for a network of banking computers capable of controlling automated cash dispensers and accounts enquiries. Explain how the system and its component parts should be tested.

89 Are there facts about individuals that it is important that government agencies should not know? How difficult is it to stop them from knowing such facts?

COMMUNICATIONS

89 A digital local area network (e.g. Cambridge Fast Ring) is to be used to transmit TV quality video streams in real time. Make notes on the following:

(a) bandwidth requirements per stream;

(b) encoding of the voice and video samples within packets;

(d) limitations of a large system with many users.

88 Describe the operation of a CSMA/CD network.

What are the performance characteristics and how do they change as the speed of transmission is increased or decreased?

89 Describe the basic operation of a CSMA/CD (such as Ethernet) local area network. What is the vulnerable period? How does the effect of the vulnerable period change as the baseband transmission speed is increased or decreased? Comment on the suitability of CSMA/CD for transmission of real-time streams such as telephone traffic.

(a) The quality of service offered by a channel is influenced by the multiplexing strategy used at lower layers. Discuss.

(b) Consider a network composed of hosts and switches interconnected by point-to-point links. Describe the relationship between the multiplexing mechanism used on the links and the technique used for switching. How is this related to processor scheduling?

89 Define the terms coding and multiplexing as applied to communication systems. Give three detailed examples of each, choosing them from different layers of the communications hierarchy.

DISTRIBUTED SYSTEMS

88 You are to advise an international company on the design of a distributed system which will provide both an electronic mail delivery service and a general registration service. A liberal number of dedicated machines are proposed to implement the services, with local disks sufficient to hold both users’ mailboxes and the database to support the services. Principals (e.g. human users, machines, services) are to be identified by a two-dimensional name such as guru@cam. Such names are also to be used for naming groups - lists of principals or other groups.

(a) Define an interface for the mail service.

(b) Define an interface for a registration service which is sufficiently flexible to be used for authorisation, authentication and location.

(d) Describe how you would achieve service availability in the presence of service machine failures.

(e) Outline the approach you would adopt to the consistency of data across the service machines.

89 The heads of all the departments in a certain university have to make a decision. The majority of the heads are hardworking, consistent and loyal, and will make a serious attempt to determine the consensus opinion of their colleagues: once the decision is reached they will carry out the necessary action. It is known, however, that not all of the heads can be trusted. Some will behave in sporadically irrational ways, having cracked under the strain, but others harbour grudges against the university at large and may act with great finesse in ways calculated to disrupt it. Nobody knows which department heads are sound or where suspicion is justified. In this atmosphere of paranoia no central meeting can be arranged. Instead the department heads send individual messages to one another across the newly commissioned university-wide computer network. The computing service is above suspicion, and guarantees that messages sent will be delivered intact, and that the recipient will be able to tell who sent the message. Unfortunately a message can only be sent to one person at once, and can only be forwarded by editing its text into the body of a new message. The computing service charges a flat rate for transmission regardless of message length: university economy guidelines require that any use of the network should be justified.

Design protocols intended to allow the reliable department heads to come to a decision despite the worst endeavours of their incompetent or malicious colleagues. Defend your design by identifying strategies that might be adopted by the unscrupulous to prevent the reliable department heads from reaching the correct consensus, and discuss what happens as the proportion of mavericks in the university grows.

It may be useful to start by considering four departments with at most one traitor.

[reference: Lamport et al., 1982]

91 A client-server style of interaction is to be supported in a distributed system. Discuss the design options for arranging for the operations provided by a server to be invoked by clients. [Hint: you should consider the extent to which distribution transparency can be achieved.]

92 A naming service is to be designed for a large-scale distributed system. Principals such as human users, services and server machines are to be named. The name space should be extensible and amenable to restructuring.

(a) What are the advantages and disadvantages of using pure and impure names?

(b) State and discuss the assumptions you would make about the nature of naming data in such a system.

COMPUTER SYSTEMS MODELLING

91 (a) It is often said that response times are harder to predict than utilisation. Why is this so? Is it important?

(b) Describe and contrast bottleneck analysis and balanced system bounds. When are balanced system bounds more useful?

92 You have 1 Gbyte of keyed records to sort into order using a computer which has 2 Gbyte of available disk and 50 Mbyte of available internal memory. How would you do it and how would the cost depend on the amount of data?

What difference would it make if there were only 5 Mbyte of internal memory?

What difference would it make if the operating system let you have only five files open at a time?

(a) What actions take place at a disk when a block is read or written?

What parameters are needed to specify the performance of a disk?

(b) Consider a Markov chain model for a disk which has a multiple stage server, with one exponential stage for each component of disk access. Assuming a fixed arrival rate with exponentially distributed inter-arrival times, sketch the state diagram of the system.

How realistic is the model? How would you improve it?