My exams tend to have three to six questions. They are closed book, closed notes. I prefer to ask questions with objective answers. You will have the entire class period to finish the exam. The exam will emphasize the material covered since the last exam. The exam questions are mostly based on the homework and the lecture notes.
There are three levels of understanding. From lowest to highest they are:
Level 1: Able to understand explanations of others
Level 2: Able to solve new problems
Level 3: Able to explain material to others
You need to attain level 2 in order to pass the exam. This means you have read and understood your notes, reviewed your homework, and reviewed previous exams (level 1).
Beyond that, you have invented and solved variations of the problems discussed in class. (Level 2).
To attain Level 3, form a study group and take turns explaining the material to each other. If someone in the group gives a lazy or bad explanation, let him have it!
I tend to give away a lot of information in the review session.
Multi-processing
PCB
Process lifecycle
Scheduling and context switching
Scheduling algorithms
Multi-threading
versus multi-processing
Multi-threading in Java
Cooperative threads: sleeping versus
yieliding
Synchronization in Java
Locking objects
Waiting for object notification
Monitors
Joining threads
Timers
Synchronization problems and mechanisms
Issues
Deadlock
Starvation
Race
conditions
Mechanisms
Hardware
mechanisms
Semaphores
The Bakery Algorithm
Classical problems
Critical
Section
Bounded
Buffer
Readers
and Writers
Dining
Philosophers
I/O
classifying IO devices
device drivers and controllers
PIO (polling vs. interrupt-driven)
DMA
I/O in Java
byte-oriented
vs. char-oriented streams (readers & writers)
filter
streams
file
I/O
pipe
streams
array/String
streams
IPC
Shared Memory
Message Passing
RMI
1. What is a PCB? What information is typically stored in a PCB?
2. Draw a state diagram for a process that shows the transitions between the following states: CREATED, READY, RUNNING, BLOCKED, TERMINATED, SLEEPING. Be sure to label your transitions with the events that cause them.
3. Give examples from everyday life of shared memory communication and message passing. What are the advantages and disadvantages of each?
1. See problems 6.2 and 6.3 in the text.
2. Assume the following processes arrive in top to bottom order at time t = 0:
Process Burst
Time Priority
P1 20 3
P2 2 1
P3 4 3
P4 2 4
P5 5 2
A. Ignoring priorities, compute the average waiting time and average turnaround time for each of the following scheduling algorithms:
1. FCFS
2. SJF
3. RR (time slice = 2 ms)
B. Repeat, this time paying attention to priorities. (Lower numbers indicate higher priority.)
In the preemptive version of SJF, late arriving processes can preempt the current process if their expected burst is shorter than the time remaining on the burst of the current process. Assume P1 and P2 arrive at time 0, P3 arrives at time 1, P4 at time 2, and P5 at time 3.
C. Draw two Gantt charts showing the execution of these processes first assuming SJF, second assuming SJF with preemption.
3. Precisely define the following metrics for evaluating scheduling algorithms:
CPU utilization
Throughput
Turnaround time
Waiting time
Response time
4. Assume the first four burst times of process P were:
B1 = 6, B2 = 8, B3 = 7, B4 = 3
Assuming the predicted first bursts was P1 = 3, compute the predicted second through fifth bursts (P2, P3, P4, P5) using the exponential average formula:
Pn+1 = cBn + (1 - c)Pn
with c = 3/4. Re-compute with c = 1/4. Which one is more accurate?
P1 = 3, P2 = ?, P3 = ?, P4 = ?, P5 =
5. What is the advantage of preemption?
1. What is the advantage of multi-threading over multi-processing?
2. Why should I employ multi-threading in my next application. Describe three benefits.
3. Write a Java program that perpetually prompts the user for a positive integer, n, then responds by saying if n is prime or not. Of course if n is large, it might take the program some time to determine if it's prime. Meanwhile, it should prompt the user for additional numbers. For example:
-> 1023
-> 42
42 is not prime
-> 255
1023 is prime
255 is not prime
->
4A. Write a method that computes the maximum sum of any subsequence of a given array:
class ArrayUtils {
static int max(int[] a) {
// = max of a[i] + ... + a[j] for 0
<= i <= j < a.length
}
// etc.
}
Your method should create slaves to compute the sum of each subsequence. When the slaves have finished, the master picks the largest of these sub-sums.
4B. Assuming an unlimited supply of processors, and assuming each thread runs on its own processor, what is the O runtime of this solution?
1. Assume instances of a particular type of resource provide two types of services:
class Resource {
void service1() { ??? }
void service2() { ??? }
// etc.
}
At most five threads may run service1 at the same time assuming no thread is running service2. Only one thread at a time may run service2.
2. Implement a simple mailbox where threads can leave messages (represented as Java Strings) for each other.
A. Using monitors
B. Using testAndSet
C. Using swap
3. What's wrong with the following proposed solution to the two thread Critical Section Problem:
class MyThread {
int id; // unique id number, = 0 or 1
int turn; // = thread that may enter
critical section next
public void run() {
while(true)
{
while(turn
!= id);
//
critical section
turn
= (id + 1) % 2;
//
remainder section
}
}
}
4. Implement an abstract message handling thread. This thread perpetually removes messages from a queue and passes them to some handler method.
5. Give examples of deadlock, starvation, and a race condition.
6. Assume the definitions of Agent, ProcessAgent, and CPU used in project 2. Implement a manager (doesn't need to be a thread) that allocates the CPU to process agents using the SJF algorithm. If a process agent uses more than twice the predicted burst time, it should be preempted.
1. Is a modem a character or block-oriented IO device? Sequential or random access?
2. Recall the interace for a block-oriented input device:
interface IBlockInputDevice {
int read(byte[] block);
int seek(int num);
void reset();
void open();
}
Provide an implementation of this interface that uses a two dimensional array of bytes as its "device".
3. What are the advantages of DMA over PIO? What is meant by the term "cycle stealing"?
abstract class InputStream {
// overridables:
int avaialble() throws IOException {
return 0; }
void close() throws IOException {}
void mark(int readLimit) {}
boolean markSupported() { return false;
}
void reset() throws IOException {}
abstract int read() throws IOException;
void read(byte[] b, int off, int len) {
for(int
i = off; i < off + len; i++) b[i] = read();
}
void read(byte[] b) { read(b, 0,
b.length); }
long skip(long n) throws IOException {
for(long
i = 0; i < n; i++) if (read() == -1) return i;
return
n;
}
}
abstract class OutputStream {
// overridables
void close() throws IOException {}
void flush() throws IOException {}
abstract void write(int b) throws
IOException;
void write(byte[] b, int off, int len)
throws IOException {
for(int
i = off; i < off + len; i++) write(b[i]);
}
void write(byte[] b) { write(b, 0,
b.length); }
}
10. Implement an extension of InputStream called RandomInputStream. Its read() method generates random bytes. This class also overrides the marking methods.
11. Assume Java didn't provide a ByteArrayOutputStream. Implement your own.
12. Assume two Java files called scores2 and scores2 contain integers between 0 and 100. Write a Java method that creates a file called scores3 that contains all of the numbers in scores1 followed by all of the numbers in scores2. Use a SequenceInputStream to merge scores1 and scores2.
14. Implement an extension of OutputStream called SafeOutputStream that is thread safe.
15. Implement an extension of FilterOutputStream called AddNOutputStream. The write method of this class writes the result of adding its parameter to some number N .
class AddNOutputStream extends FilterOutputStream {
private byte n = 111;
public void setN(byte n) { this.n = n;
}
// etc.
}
Implement an extension of FilterInputStream called SubNInputStream that subtracts N from the byte read and then returns the result:
class SubNInputStream extends FilterInputStream {
private byte n = 111;
public void setN(byte n) { this.n = n;
}
// etc.
}
Write a program that uses these filters.
16. Java has two ways of representing a sequence of objects: List and ObjectInputStream. How can we implement a List backed by an ObjectInputStream? How can we implement an ObjectInputStream backed by a List?
17. Be able to solve problems involving threads communicating through pipes.
1. A reflector is a server that listens for messages of the form:
host port content
where host and port are tokens and content may be any string of subsequent tokens. When a reflector receives such a message it immediately forwards content to the indicated host and port. Reflectors are often used by applets that are only permitted to communicate with servers running on their web server's host. Implement a reflector in Java.