Academic Year:

2003/04

Semester:

Winter

Module Title:

Operating Systems

Module Code:

CS4145

Duration of Exam:

3 Hours

Percent of Total Marks:

100

Lecturer:

John Sturdy

Paper marked out of :

100

• Answer 5 questions, at least one from each section

• All questions carry equal marks

There are more points available in the mark scheme than are available for some questions; this means that mentioning more of those points than needed will not get more than the full mark. Thus, there is more than one way to get full marks on some of the questions.

Q1.

a)

Explain how the virtual memory mechanism improved efficiency of the Unix system calls fork and exec. You should mention the work that the system would have to do otherwise, were these optimisations not done.

For fork, the answer must mention copy-on-write (1) and that this requires setting up the translation table for both processes to point to the same frames(1) and to set the data segment to read-only for both(1). It should mention that the memory is then copied one frame at a time, as needed (1) and set to writable in both processes as that happens (1). It should mention that without this, the system would have to copy the whole data segment, and that this is often wasted effort as fork is frequently followed by exec(1).

For exec, the answer must mention demand-paged executables(1). It should mention that the code segment is marked as being paged from the executable file from which it is being run(1), and that it is initially marked as currently paged out(1), and that the page fault mechanism brings pages in as they are needed(1). Because code segments and executable files should both be non-writeable, the file contents should match what is in the memory(1) and so reclaiming frames for re-use when memory is full is cheaper by re-using code segment pages than data segment pages, because they don't need to be written out to backing store before being overwritten(1). If demand-paged executables are not used, the system has to load pieces of program that may never be used(1), which may involve throwing out other data to make way for them(1) and which slows down program start-up.

14 Marks

b)

Explain the parts of the address translation mechanism that are needed to make this work.

Translation table(1) translating addresses page-by-page(1) with presence bit(1) and read-only(1) bit for each page. A different translation table is used for each process(1), but pages shared by more than one process will have corresponding entries in those processes' translation tables(1).

6 Marks

Q2.

a)

You are using a computer for two large tasks at once (both programs written by you), and noticed that the performance suddenly drops drastically. Using system monitoring tools, you find that the CPU is busy less than 5% of the time, but the disk drive is showing a lot of activity. What is likely to be going on?

The tasks between them(1) are occupying more virtual memory(1) than the physical memory available(1) (sometimes called thrashing(1)) and so the system is spending much of its time transferring pages between RAM and backing store(1). For much of the elapsed time(2), in fact by far most of it – about 95%(1) the CPU has nothing to do, because each of the things it might otherwise be doing is waiting for a page to be brought in from backing store(2). Code segment pages can simply be overwritten(1) but as well as bringing in pages from back store, if a frame holding a data page is re-used, its old contents must first be written out to backing store(1).

12 Marks

b)

What are the various things you can try doing about this? Explaining how each of them may help.

You could run the programs one at a time(1), thus reducing the simultaneous memory requirement. You could look at the algorithms(1) used in the programs, to improve their patterns of memory access(1), in particular, ``locality of reference''(1), to reduce the ``working set''(1) i.e the number of pages needed in memory at once, and could also try reducing their overall memory usage(1) by redesigning their data structures(1). You could get more memory for the computer(1). You could try tuning the parameters of the paging system(1).

8 Marks

Q3.

a)

What are the advantages of:

1. multiple processes on a single CPU?

While one process is waiting for i/o(1), another process can be using the CPU (1), and so it is likelier that more of the hardware will be being made good use of at any one time(1). Also, different processes may be keeping different peripherals properly occupied(1).

2. Multiple CPUs in one computer

Higher overall computational throughput(1) which is important for compute-bound applications(1). Parallelized applications can communicate very quickly between their component tasks(1) by using shared memory(1).

4 Marks

b)

What are the differences between processes and threads?

Processes have separate address spaces from each other(1.5) while threads within a process share that processes' address space(1.5). Processes may be reached by (for example) signals from another process while threads cannot be seen from outside(1).

4 Marks

c)

How can data to be transferred from one process to another? (List several ways.)

Pipes(1)

Sockets(1)

Message queues(1)

Shared memory(1)

4 Marks

d)

How can processes synchronise with each other? (List several ways.) What must the implementation of any of these take care about.

Semaphores(1); Monitors(1). The implementation must be uninterruptible(1) to avoid having one process read an ``available'' value from a lock location, then a context switch occurs and another does likewise, then each in turn writes a ``claimed'' value into it..

4 Marks

e)

What extra precautions must be taken to make synchronization work properly on a computer with multiple CPUs?

Ability to read and write memory in one atomic cycle(2) thus preventing a process on one CPU and a process on another from both reading an ``available'' value, and both writing a ``claimed'' value, into a lock location(2)

4 Marks

Q4.

Using C-like pseudocode, sketch implementations of

a)

A program using multiple processes, for example to implement a parallel algorithm efficiently on a machine with multiple CPUs.

10 Marks

b)

A simple shell, capable of reading the names of programs to run and starting those programs in separate processes.

10 Marks

Q5.

a)

Explain how a typical UNIX file system works. How are files connected to their names? What are the data structures involved?

A file system organizes a hardware device such as a disk drive(1) into a hierarchical directory structure(1) in which each directory can ``contain'' files(1) and further directories(1). In fact directories are a special kind of file(1) and files are not contained in directories, but simply pointed to by them(1), via their inode numbers(1), which are unique within that file system. Thus, the same file can appear under multiple names in one or more directories(1) within the same filing system. For each inode number, there is a table indicating where on the disk each part of that file is(1). For large files, this may be a table of tables(1). Each file has a set of permission bits(1). Some files have a bit indicating that they are symbolic links, that is, files which, when read, give the name of a file to be read in place of them(1).

12 Marks

b)

What constants have to be decided on in the design of a new type of file system, and what parameters might be set when you create an individual file system of this type? What factors depend on the underlying disk hardware?

The maximum length of a filename must be decided when designing the file system(1), as must the maximum size of an individual file(1). The size of the filesystem(1), and the number of inodes in it(1), must be decided when creating a specific filesystem. The block size is determined by the disk hardware(1).

5 Marks

c)

What happens if you try to delete an executable file while the program it contains is being run? Why? What underlying mechanism is involved in this?

The file continues to exist until the program exits(1) because it being open for execution means there is in effect an extra link to it(1) and a file is deleted only when there are no longer any links to it(1).

3 Marks

Q6.

Explain in detail (preferably with the timeline) the sequences of events involved in the following Unix operations. You should make it clear what determines when various events happen.

a)

Reading from a disk file

The process calls the OS/library read function(1) which uses the file system(s) to determine what part of the disk is to be read. The disk transaction request is put onto the queue for the relevant disk drive (which may be busy at the time) and the process is suspended(1) and put on the queue of processes waiting for that disk drive, and some other process scheduled since our process cannot continue until it has the data. When the disk drive has fetched a piece of data, it generates an interrupt (1) which the operating system handles. The interrupt handler sets the disk drive in motion for its next job (eventually getting to ours(1)) and returns via the scheduler, which transfers the process whose data has just been fetched, back onto the run queue(1) and eventually the CPU gets round to running it again (1).

6 Marks

b)

Writing to a disk file (you may refer to your answer for part (a) above)

This is similar to reading from the disk(1) but the process need not wait for the data to be written to the disk but can continue processing(1) unless the queue or buffers for things on their way to disk is too long(1). The data will be written to the disk hardware some time later(1).

4 Marks

c)

Reading from the keyboard

The process attempts to read from the keyboard buffer(1) and if there is anything already in the buffer, can take that and procede immediately(1). If there is nothing in the buffer, the process must be suspended and put on the queue for that device(1) and another one scheduled. When the interrupt handler for the keyboard indicates that there is another character available, the character goes into the buffer and any process waiting for it may then be scheduled so that it can go ahead and pick the character up(1).

4 Marks

d)

Writing to the printer

The process writes into the printer buffer(1) and may continue immediately unless the buffer is full(1), in which case it must be put onto the queue of processes waiting for space in the printer buffer(1). Whenever the printer indicates that is is ready for more data, it interrupts the computer, and the interrupt handler takes something from the printer queue and sends it to the printer(1). If in doing so it makes enough room in the buffer for a process to continue, it gets the scheduler to put such processes back onto the run queue(1).

5 Marks

Q7.

a)

Explain the differences between the user and privileged modes of the CPU and MMU.

In privileged mode, some extra instructions are available(1) such as those controlling the MMU(1) and the interrupt system(1). In user mode, only ``application'' type instructions are available(1). In user mode, the MMU arranges address translation for the address space of the current process, while in privileged mode, kernel data is accessible(1). (This needs more work)

7 Marks

b)

How is it enforced that only kernel code runs in privileged modes? What can happen if this fails?

The only way to switch into privileged mode is by an interrupt(1) (including a software interrupt / system call(1)). Interrupts are handled by jumping to a location pointed to by an entry in the interrupt vector(1) and all the interrupt vector entries point into the kernel(1) and only the kernel has write access to the interrupt vector, so no unfriendly access can change it(1), and therefore this continues to be the case. Were it to be possible for user code to gain privileged status, it could circumvent security (1), and were it to be possible to enter privileged mode and jump into the kernel at the wrong point, it would be possible to do, for example, file operations skipping the permissions checks at the start of them(1)

7 Marks

c)

Explain ``sandboxing'' security, as used by Java

A sandbox is a safe program execution environment, in that programs running in it can do only safe operations(1). To allow a sandboxed program to do a variety of useful tasks, but not dangerous ones, it may be allowed to use normal file operations(1) but only on a restricted set of directories(1). For finer control, it may have separate lists of readable and writable directories(1) so it can have its own scratch data but not modify its configuration (such as which directories are inside the sandbox)(1). A sandboxed program may either not be allowed to start other programs, or may have a restricted list of directories containing the only programs it is allowed to start(1).

6 Marks

Q8.

a)

Explain what the major components of a typical operating system are, and how they fit together. List the distinct parts of the kernel.

Kernel(1) including device drivers(1), scheduler(1), and memory manager(1); filing system(s)(1), libraries(1), utilities(1), shell or GUI(1). The kernel is central to the system(1) with the device drivers fitting between it and the hardware(1). The scheduler and memory manager are needed to support user processes(1). Libraries and utilities form further layers on top of all this, and run as normal ``userland'' processes(1).

12 Marks

b)

Which parts can be replaced (or present in multiple versions) without changing the overall design of the system?

Device drivers(1), filing systems(1), libraries(1) and utilities(1).

4 Marks

c)

What is the ``microkernel'' approach operating system design? What are its advantages and disadvantages?

This tries to put outside the kernel everything that does not strictly need to be inside it(1). It is a cleaner design(1) and possibly safer(1) but has more overhead as there are more switches between kernel and non-kernel code(1). (Room for improvement on this!)

4 Marks