Units 1-4

Question 1

For each of the following system configurations, explain whether it is capable of being concurrent, parallel, both, or neither. Briefly justify each answer.

(a) One processor, two activities
(b) Four processors, two activities
(c) Three processors, five activities
(d) Two processors, one activity

Answer 1

(a) Concurrent, not parallel - take turns to use the processor in pseudoparallel fashion.
(b) Parallel (and therefore concurrent) - two activities can run simultaneously on two of the processors, with two processors idle.
(c) Concurrency is possible by sharing the processors among all the activities. Some parallelism is possible because there are multiple processors but not all activities can be active at once.
(d) Neither concurrent nor parallel because one activity by definition can only be doing one thing at a time.

Question 2

Explain the need for a processor to run in at least two modes, including a supervisor mode.

Answer 2

A processor must mediate between concurrently running processes to prevent errors. The superviser mode is used for privileged instructions, including those involved in performing input/output, and controlling entry/exit from supervisor mode. Control can be exercised over how privileged instructions are executed, and user processes can be prevented from causing certain kinds of system failures or arbitrarily executing sensitive code, because the processor can only perform these instructions when it is in the right mode. This allows policies to be enforced.

Question 3

Explain how the following mechanisms are related:

• entry protocols
• exit protocols
• semaphores

Answer 3

Shared data needs to be protected so that only one process at a time can have access to it. A semaphore is a mechanism designed to protect shared data, through ‘wait’ and ‘signal’ operations which function like an entry and an exit protocol respectively.

A process must execute the entry protocol before using shared data. If another process is already using the data, the entry protocol makes the new process wait. Once a process has finished using shared data, it executes the exit protocol, which alerts waiting processes that they can try to execute the entry protocol again.

Question 4

Give a definition of the term “virtual machine”.

Answer 4

A virtual machine is an abstract computing device that is implemented in software. A virtual machine defines a certain set of instructions and how code and data are organised in the machine’s memory.

Question 5

Name two components of the Java Virtual Machine and state what they do.

Answer 5

Bytecode verifier: checks whether bytecode about to be executed has not been tampered with.

Class loader: loads classes at runtime into the JVM’s memory.

Bytecode interpreter: interprets and executes the code.

Garbage collector: reclaims the memory occupied by unused objects from the heap.

JIT compiler: compiles a sequence of VM instructions into machine code as the sequence is being executed.

Question 6

Briefly state three reasons why concurrent and distributed systems are important.

Answer 6

• Better utilisation of available hardware, software and data.
• Less chance of bottlenecks.
• Improved fault-tolerance.
• Better scalability.

Question 7

Briefly state the main difference between a process and a thread and hence explain the advantages that threads have over processes.

Answer 7

• Process: A program being executed. Has its own set of memory space. Context switches require a substanational amount of data to be stored in order to resume.
• Thread: a lightweight process that shares data between thread instances. Share a common address space. Context switches require less data to be stored. Can be created at will to handle demand.

Question 8

Briefly explain the facilities built into the core Java language to support mutual exclusion.

Answer 8

Mutual exclusion is provided by synchronized access to methods that modify shared data; the synchronized keyword can also be used in the method body to set up a lock before accessing shared data and this approach enables fine granularity of locks.

Question 9

Briefly explain the facilities built into the core Java language to support condition synchronisation.

Answer 9

Conditional synchronisation is provided by Java through a wait/notify mechanism. Threads wait for a condition/lock to come true and then execute the protected code. Once finished, a notification signals the other threads that shared data/protected code can now be accessed again.

Question 10

What does the term thread safe mean when applied to a Java class?

Answer 10

A class is thread safe if it can be executed concurrently by multiple threads without the shared data getting into an inconsistent state.

Question 11

Explain two limitations of the built-in mechanism of ‘monitors’ and how they were addressed by the concurrency utilities introduced by Java 1.5.

Answer 11

Java’s built-in monitors are limited in the sense that they have a single implicit condition variable per lock and there is no possibility of retracting lock acquisition attempts.

The concurrency utilities introduced the Lock and Condition interfaces. The former has a tryLock method that doesn’t block if the lock is not available, and the latter allows the developer to associate multiple explicit conditions to each lock.

Question 12

Explain the terms sequential and parallel systems. Under what circumstances is parallel processing possible?

Answer 12

Sequential system: A system in which each activity must complete execution before another activity can start.

Parallel system: A concurrent system that can really carry out a number of activities simultaneously because it has more than one processor.

Question 13

Is a concurrent system always parallel? Explain your answer.

Answer 13

No. A concurrent system can only be parallel if it has more than one processor. A concurrent system can be psuedo-parallel if it shares processor time between a number of activities but only one activity is actually running at any given time. This appears to the user as if it were a parallel system.

Question 14

In Java, what is the purpose of the Thread method yield()and when might you use it?

Answer 14

The yield method is invoked to indicate that the currently running thread can allow other threads a chance to proceed.

This may be necessary in cooperative multitasking systems in order to force a thread to take a break.

Question 15

Briefly explain the concept of a reentrant lock.

Answer 15

A re-entrant lock can be reacquired by a thread that already holds it.

Question 16

Summarise the main benefits and costs of mobile systems.

Answer 16

**Benefits: **users can communicate and access the distributed system from a wider variety of locations, and share facilities and data. For mobile systems that are wireless there are additional benefits of avoiding the cost and disruption of fixed wiring installation.

Costs: Possibly increased security risk in allowing mobile users to link to a system (wirelessly or not). Mobile components such as laptops are more easily stolen or lost than fixed components. Wireless communications are more vulnerable to interception and lower in bandwidth.

Question 17

What does it mean to say a mobile system is location-aware?

Answer 17

Systems that are location-aware can display locally relevant information or otherwise behave in different ways depending on their physical location.

Question 18

Describe the fetch-execute cycle with reference to the program counter, the CPU, memory, registers and the bus.

Answer 18

Program counter is used to keep track of which instruction is required next from a list of instructions in main memory. The CPU continually fetches the next instruction from memory and places it in the instruction register. It then executes the instruction to completion using registers for storage. Data may also be written to/read from cache main memory, via the bus. The program counter is then updated.

Question 19

Give a definition of the term ‘virtual machine’.

Answer 19

An abstract computing device implemented in software. A virtual machine defines a certain set of instructions and how code and data are organised in the machine’s memory.

Question 20

Explain one advantage and one disadvantage of using virtual machines.

Answer 20

Advantages: Generated virtual machine code is smaller than the corresponding machine code. Can be executed on various platforms without requiring any changes; easier for organisations to develop applications for a wide user base. VMs facilitate the development of applications written in multiple languages and promote the creation of new languages.

Disadvantages: Slower execution speed of the program, compared with compiling it directly to machine code interpreted by the CPU. VMs are also subject to the general issues of backward compatibility problems and to the limitations of the various platforms.

Question 21

Give one benefit and one disadvantage of using a distributed system.

Answer 21

Advantages: More efficient sharing of resources, hardware, software and data. Increased fault-tolerance. Improved scalability.

Disadvantages: If communications links fail or become faulty, some components of the system may become unreachable. Security is potentially more difficult in a distributed system. Introduces new ways in which systems can fail.

Question 22

Are all distributed systems also potentially concurrent? Briefly explain your answer.

Answer 22

Yes. Distributed systems are necessarily concurrent, in that each host (or node) can operate independently and potentially in parallel with other hosts. Each node may be carrying out processing at the same time as one or more other nodes

Question 23

Briefly define the term deadlock in the context of concurrent systems.

Answer 23

A situation in which two or more processes or devices are prevented, for all time, from continuing because each is waiting for one of the other processes, or for a resource that will never become free.

Question 24

Which improved features introduced as part of the Java 1.5 concurrency utilities are useful for avoiding deadlock?

Answer 24

• Lock interface - tryLock() does not block
• Condition interface: ability to assign multiple conditions for each lock
• Atomic variables

(any other suggestions?)

Question 25

An important advantage of Java is that programs written using it can be portable across different platforms.

Java supports a system of thread priorities and a programmer could try to use thread priorities to deal with concurrency issues. Explain why this would be unsatisfactory.

Answer 25

Policies may vary from one virtual machine to another, and the mapping of threads to the underlying platform may vary. Therefore any program logic that relies on priorities set by the programmer will not be platform-independent.

Question 26

What does scalability under contention mean? Give an example.

Answer 26

Scalability under contention is the capacity to maintain a high throughput when multiple threads are trying to use the same resource.

For example, a ticketing system would show scalability under contention if it maintained normal throughput in a situation where the number of customers attempting to order tickets has doubled.

Question 27

Explain why atomic variables help Java programmers achieve scalability under contention.

Answer 27

Atomic variables are lock free, therefore threads do not block because by definition there is no lock to be acquired. If threads do not block, then less time is spent by the JVM in scheduling threads, leaving more time to actually execute them. Atomic variables can therefore not only make the code simpler, but also make it run faster.

Question 28

Explain what a process descriptor is and its purpose. Indicate in your answer two items of information that might be part of a process descriptor and why they are needed.

Answer 28

A process descriptor is a data structure storing information about the context of a process in a form that allows the process to be paused and restarted later.

• unique process identifier
• link to the program’s data (variables)
• start address where the program instructions are located in memory
• a program counter
• current register values
• value indicating the process priority
• events the process is waiting for
• events the process has signalled
• how much time the process may run for
• the process state

Question 29

Explain and compare the terms ‘multitasking’, ‘concurrency’ and ‘parallelism’.

Answer 29

Multitasking and concurrency both refer to the execution of more than one task ‘at the same time’ - this may be using parallelism or psuedo-parallelism. Parallelism is when multiple tasks are actually executing at the same time (using multiple processors), whereas pseudo-parallelism is when tasks appear to be executing at the same time.

Question 30

Explain the differences between the following three potential problems of concurrent systems: deadlock, livelock and starvation. How can communicating processes resolve deadlock in a pragmatic way?

Answer 30

**Deadlock: **a process is prevented, for all time, from continuing because it is waiting for an event that will never happen.

Livelock: a process is continually executing an operation without getting nearer to a condition becoming true.

Starvation: a runnable process is overlooked indefinitely by the scheduler

Deadlock can be resolved by arranging for one of the four conditions for deadlock to not be true (mutual exclusion, hold while waiting, no pre-emption, cycle of processes).

Question 31

Distinguish between pre-emptive multitasking and cooperative multitasking and discuss their relative advantages and disadvantages from the point of view of application programmers.

Answer 31

Cooperative multitasking: applications have to be coded so that they allow other programs to run from time to time. Advantage: programmer doesn’t have to worry about synchronisation. Disadvantage: programmer must release resources at appropriate times to avoid starvation and keep system responsive.

Pre-emptive multitasking: the operating system can require one process to give way to another to allow sharing of resources (provided that the first process is not at a critical point that would make this operation risky). Advantage: Less risk of starvation. Disadvantage: OS does scheduling - overhead. Programmer has to worry about the atomicity of operations on shared data.

Question 32

Coulouris et al identify the following three characteristics of distributed systems:

• Necessarily concurrent
• Possibility of independent failure
• Lack of a global clock

Explain these three characteristics.

Answer 32

Necessarily concurrent: each host (or node) can operate independently and potentially in parallel with other hosts.

Possibility of independent failure: it is possible that one or more hosts may fail, possibly without other parts of the system becoming aware of this; this introduces different sorts of problems from those in non-distributed systems.

Lack of a global clock: each host typically maintains its own value of the current time. Even if all hosts at some initial point had precisely the same value of the current time, over the longer term the equipment that keeps track of time can drift slightly so that the hosts are no longer synchronised.

Question 33

A Java thread can be in a number of different thread states. Describe under what circumstances a Java thread would progress through the following sequence of thread states: New, Runnable, Blocked, Runnable, Waiting, Runnable, Terminated.

Answer 33

• New: new instance of thread created
• Runnable: start() called; thread is either running or waiting for CPU time
• Blocked: waiting to enter a controlled region of code.
• **Runnable: **running/waiting for CPU time
• Waiting: waiting for another thread to perform an action or on some condition becoming true
• Runnable: running/waiting for CPU time
• Terminated: run method has completed

Question 34

Explain two shortcomings of the built-in Java concurrency support which were the motivation for the Java 1.5 concurrency utility libraries.

Answer 34

Java monitors have a single anonymous condition variable instead of an explicit set of condition variables. Impossible to distinguish threads that are waiting for the same lock but on different conditions. Multiple conditions could make programs more efficient because it would not be necessary to notify all threads indiscriminately. Explicit distinct condition variables also make programs easier to understand and hence maintain.

A thread can state for how long it is willing to wait for a notification, but it cannot state for how long it is willing to block when waiting for the lock to become available: once a thread attempts to acquire a lock, there is no ‘backtracking’ and the thread may be blocked indefinitely if there is a deadlock. To help avoid such situations, it would be useful to have a kind of ‘timed blocking’, akin to timed waiting.

Question 35

Briefly define what is meant by a concurrent system and a distributed system.

Answer 35

Concurrent system: A system which may have a number of activities active at the same time and allows all of its active activities to make progress.

Distributed system: A system containing a number of distinct components at different locations, where each component is, in some sense, a computer system itself and the components are linked by a network. The system may demonstrate transparency to varying degrees.

Question 36

For each of the following system configurations, explain whether it is capable of being concurrent, parallel, both, or neither. Briefly justify each answer.

(i) Three processors, one activity
(ii) One processor, three activities
(iii) Three processors, two activities
(iv) Three processors, six activities

Answer 36

i) Neither - multiple activities needed for concurrency/parallelism.
ii) Concurrent - the three activities could share the processor in a psudeo-parallel fashion.
iii) Parallel (and therefore concurrent) - each activity could be running simultaneously on a processor with one processor remaining idle.
iv) Concurrent with some parallelism - up to 3 activies can be active at the same time using 3 processors, but not all 6 activities.

Question 37

Give two benefits of a sequential system.

Answer 37

• Simplicity of design and use.
• Programming is relatively straightforward; no need to think about concurrency.
• Instructions are carried out in a clear, well-defined order.
• If something goes wrong with a sequential program it is relatively easy to trace through the instructions to find the cause.
• The operating system for a sequential system can also be relatively simple.

Question 38

Scheduling policies attempt to achieve various desirable system characteristics. Fairness is one such characteristic. Briefly explain two others.

Answer 38

Responsiveness – indicates whether a system is acceptably fast.

Turnaround – the time a user waits for a process to complete.

Deadline maximisation – maximising the number of achieved ‘deadlines’.

Resource utilisation – keeping the CPU ‘busy’, not over-using resources that are in great demand.

Throughput – achieving the maximum number of processes completed per unit of time.

Robustness – the ability to maintain desirable characteristics under varying system loads.

Question 39

A bank account, account1, has a balance of £0. Two concurrent processes, P1 and P2 both attempt to credit account1 with £5. After the processes have completed these operations, account1 should have a balance of £10, but the balance is only £5.

Explain how this lost update could have happened.

Answer 39

What looks like a simple statement forming one logical operation is actually broken down into several smaller steps (reading the balance value, testing the balance value and then writing the new value). It is possible for the operating system to cause an interrupt between these smaller steps.

P1 could begin executing the crediting method but not yet have written the new value when the system interrupts and P2 also begins executing the crediting method. In this situation, both processes will read the start value as £0 and both will perform the £0+£5 action leaving £5 as the final value.

Question 40

The Java 1.5 concurrency utilities were designed to overcome certain limitations in Java’s built-in concurrency mechanism. State three of these limitations.

Answer 40

Only one anonymous condition variable; impossible to distinguish threads that are waiting for the same lock but on different conditions.

A thread cannot state for how long it is willing to block when waiting for the lock to become available: once a thread attempts to acquire a lock, there is no ‘backtracking’ and the thread may be blocked indefinitely if there is a deadlock.

Java provides poor support for priorities: they mostly depend on the underlying operating system threading model. The application cannot assume that the runnable thread with highest Java priority will be the one scheduled to run next.

Question 41

Write down Java code for a class Q11Thread that extends the class Thread. When an instance of this threaded class is active it simply executes the following two statements:

System.out.print(“hello “);
System.out.print(“world “);

Answer 41

public class Q11Thread extends Thread
 {
     public void run()
     {
         System.out.print("hello ");
         System.out.print("world ");
     }
 }

Question 42

Give a code fragment that will create and activate two instances of a class named Q11Thread.

Answer 42

Q11Thread thread1 = New Q11Thread();
Q11Thread thread2 = New Q11Thread();

thread1. start();
thread2. start();

Question 43

Briefly explain why locks are used in concurrent programming.

Answer 43

Locks are used to ensure mutual exclusion and protect shared resources.

Question 44

If the programmer initialised a semaphore to 0 instead of 1, explain the problem it may cause and if it would be an issue of safety or liveness.

Answer 44

Initialising the semaphore to 0 would mean that there would be no permits available and therefore no process would be able to access the shared resource or critical region.

This would be an issue of liveness as the system would not be able to make any progress.

Question 45

If a programmer forgot to use *semWait *when using a semaphore, explain the problem it may cause and if it would be an issue of safety or liveness.

Answer 45

The shared resource would no longer be protected, and could potentially lead to inconsistent data.

This is a safety issue.

Question 46

If a programmer forgot to use semSignal when using a semaphore, explain the problem it may cause and if it would be an issue of safety or liveness.

Answer 46

It would be possible for a resource to become locked indefinitely and other processes would be prevented from accessing the resource.

This is a liveness issue.