I also ask multiple choice questions from the ACM self-assessment tests on Operating Systems and on Concurrency.
-----------------------------------------------------------------
Describe how you would simulate a system with the following
structure:
+<-------------------------------------+
| |
| +<---------------+
| | ^
v ___ +--+ v ___ +--+ |
+---->|||->| |---->+-+-->|||->| |--->+
^ --- +--+ | --- +--+
| CPU | DISK
| v
arrivals departures
a) What information would you need before being able to run
your program?
b) What information would you print out during execution
of your program?
c) What summary information would you like to obtain?
-----------------------------------------------------------------
What are the resources shared by an operating system?
Indicate for each if it is Reusable, Consumable, or both.
-----------------------------------------------------------------
Often an operating system is described as a "Resource Manager".
Specify as many such resources as you can.
-----------------------------------------------------------------
Often an operating system is described as a "Reactive System".
Explain why.
-----------------------------------------------------------------
What is a monolithic kernel, and what is a micro-kernel (or
process-based kernel)?
-----------------------------------------------------------------
What is a Micro-Kernel Operating System Architecture?
What are its adavantages? What its disadvantages?
-----------------------------------------------------------------
What is a monolithic Operating System? and how does it differ
from a Layered Operating System?
-----------------------------------------------------------------
A modern operating system is said to be multitasking,
multithreaded, preemptive, and multiprocessing.
What does it mean?
-----------------------------------------------------------------
Describe what is a Kernel or Supervisor call.
-----------------------------------------------------------------
What is Spooling? Do you think it is a standard component
of operating systems such as Unix and NT?
-----------------------------------------------------------------
In the 60s operating systems started supporting Multiprogramming.
What does it mean?
-----------------------------------------------------------------
Why do computers have (at least) two modes, a user mode and
a kernel mode? How does one go from one mode to the other
and viceversa? Explain in detail then for each of the following
operations indicate if it should be done in user or kernel
mode:
(a) Read the time of day clock
(b) Set the time of day clock
(c) Start an IO operation
(d) Disable interrupts
-----------------------------------------------------------------
What is the distinction, if any, between Interrupts, Exceptions,
and Traps.
-----------------------------------------------------------------
Describe what is a process and indicate how it would be
different if on a system a service is implemented as
a process or as a library (say a DLL in Microsoft).
-----------------------------------------------------------------
a. What happens when a CPU receives an interrupt?
b. Why, in a single processor system, we can use
disabling of interrupts to implement critical regions?
c. How can computers use I/O devices if there are no
interrupts?
-----------------------------------------------------------------
I need to access a database located in LosAngeles.
A friend suggests replicating it in Philadelphia.
Why? What problem(s) will I run into if I follow this advice?
-----------------------------------------------------------------
Explain discrete event simulation. Be sure to indicate
what are events and what is the high level structure of the
simulation program.
-----------------------------------------------------------------
Using what you have learned doing the discrete event
simulation homework, describe:
(a) What is an event.
(b) What are the events in your simulation.
(c) What is the role of the agenda
(d) How did you keep track of time in the simulation.
(e) How did you compute the average queue sizes?
-----------------------------------------------------------------
Process P executes:
A1: X := 1;
A2: Y := 1;
If I change the order of the statements A1 and A2 I get a
process P':
A2: Y := 1;
A1: X := 1;
Is P' equivalent to P? In general, given programs P and P',
what does it mean to say that they are "Equivalent"?
-----------------------------------------------------------------
The state of a task in a multitasking system is described
by a diagram with three states: RUNNING, READY, BLOCKED.
Describe the meaning of each state and each transition.
-----------------------------------------------------------------
Describe as many reasons as you can for a process to become
blocked and explain how processes waiting for a specific
resource are managed.
-----------------------------------------------------------------
Define what is a Process Control Block and give some of the
information it may contain.
-----------------------------------------------------------------
The major distinction between threads and processes centers around:
a. The amount of memory that must be allocated
b. The average number of instructions executed
c. The amount of overhead associated with
creation and context switching.
d. The number of 1/0 requests made
-----------------------------------------------------------------
You have heard that in threads we should be using
threadsafe functions.
A. Give an example of a threadsafe function.
B. Give an example of a function which is not threadsafe.
-----------------------------------------------------------------
Consider busy waiting for entry into a critical section in a
shared memory system. In which scenario (or scenarios) below
would this not be considered an unreasonable approach?
a. When there are few CPU-bound processes in existence
b. When a dedicated processor can be assigned to perform
the busy wait
c. When the expected wait is less than the time needed
to perform a context switch
d. None of the above- busy waiting is always unreasonable
since it does nothing but waste processor cycles.
-----------------------------------------------------------------
We are given tasks T1 and T2. What does it mean to say that
they execute concurrently?
-----------------------------------------------------------------
We are given the following precedence graph:
S1 ------>S2-->+-->S3-------+--->S4
| | ^
v v |
+------->S5-->+-->S6->+--->S7
| | ^
v v |
+--->S8-->+---->S9--->+
a) What is the maximum number of processors
that can be usefully employed to execute concurrently this
program? Explain your result.
b) Assuming that you have only a single processor.
Give a possible legal order in which the statements
S1 through S9 can be executed.
-----------------------------------------------------------------
We are given the following precedence graph:
S1 ------>S2-->+-->S3-------+--->S4
| | ^
v v |
+------->S5-->+-->S6->+--->S7
| | ^
v v |
+--->S8-->+---->S9--->+
Assume that the statements are executed by processes P and Q
as follows:
PROCESS A : begin PROCESS B : begin
S1; S2;
S5; S3;
S8; S6;
S9; S4;
S7;
end end
Declare semaphores and insert P and V operations as required
to make sure that the processes A and B execute the statements
in an order that is consistent with the given precedence
graph.
-----------------------------------------------------------------
Tasks T1 and T2 share the integer variables X, Y initially set to
0.
Task T1 executes: | and T2 executes:
|
X := 0; | Y := 0;
if X > 0 then | while Y < 2 do
X := X + 1; | X := X - 1;
Y := 2; | Y := 1;
What are the possible values of X and Y when these tasks
terminate?
-----------------------------------------------------------------
What is Interleaving? Why is it so important for understanding
concurrent processes?
-----------------------------------------------------------------
Concurrent programming is said to be harder than sequential
programming. Explain why that is so [if you disagree,
give your reasons].
-----------------------------------------------------------------
Give a detailed example of why we need "Mutual Exclusion".
-----------------------------------------------------------------
What is a "Critical Section"? Define it and give an example.
-----------------------------------------------------------------
Process A executes the statements S1; S2;
Process B executes the statements S3; S4; S5;
List at least 6 possible interleavings of these processes.
-----------------------------------------------------------------
Suppose we are given an activity A consisting of atomic actions
b c d and activity B consisting of of atomic actions e f g.
Assume that b c and f g are critical regions with respect to
each other. Show what are all the legal interleavings
of these two activities.
-----------------------------------------------------------------
Process P executes:
A1: X := 1;
A2: Y := 1;
A3: Z := 2;
and process Q executes:
B1: X := 2;
B2: Y := 2;
What are the possible resulting values for X, Y, and Z?
For example, after the execution sequence A1 A2 A3 B1 B2
we obtain [x=2,y=2,z=2].
In the same conditions as above, what should you do if you want
to guaranty that X, Y, Z finish with value, respectively, 1,
2, and 2?
You can change the order of A1, A2, A3; or the order of B1, B2;
or use semaphores; or use spinlocks.
In the same conditions as above, what should you do if you want
that X and Y have both value 1 or both value 2?
-----------------------------------------------------------------
Here is a possible implementation of the lock operation
for a spinlock.
void lock(int &s){
while (TestAndSet(s))
while (*s == 1);
}
Explain in detail what is being done and why. [TestandSet
sets s to 1 and returns the value it had when the
instruction was called].
-----------------------------------------------------------------
Two processes, A and B, execute respectively the code
x := y + z;
w := x * 4;
and
a := w - z;
Apply the Bernstein's conditions in detail to determine if they
can or not be executed concurrently.
-----------------------------------------------------------------
Use the Bernstein's conditions to transform the following
sequential program into an equivalent concurrent program with
maximal concurrency.
x := y+z;
w := y*z;
u := w-3;
v := x+t;
k := x+w;
-----------------------------------------------------------------
What does it mean when we say that we have a Race Condition?
-----------------------------------------------------------------
Process P1 executes the statement X := 7; and process P2
executes the statement X := 11;
where X is a shared variable.
Do we have a race condition? Explain.
-----------------------------------------------------------------
How do you make sure that the two concurrent processes do not
access a shared data structure at the same time?
-----------------------------------------------------------------
We know that a process is not supposed to terminate within
a critical section. Yet processes are know to abort any
place [if nothing else, because of programming errors].
How does the operating system deal with this problem?
-----------------------------------------------------------------
Describe the YIELD instruction and suggest how it can be used
to implement co-routines or non-preemptive operating systems.
-----------------------------------------------------------------
Describe the distinction between "big" and "small" processes,
or, in other words, between "tasks" and "threads". Explain when
you would use one, when the others.
-----------------------------------------------------------------
How do kernel supported threads differ from user threads?
-----------------------------------------------------------------
You have to copy a file, say moo.dat, to foo.dat. We can
read a buffer from moo then write to foo, then read from moo,
then write to foo,.. Alternatively we can overlap the
read and write operations using two threads and alternating
the operations between two buffers. Write such a program in
C (or in pseudo-english). Explain what you are doing,
stressing what each thread does and how they synchronize.
-----------------------------------------------------------------
What is a Tightly-Coupled System? what a Loosely-Coupled System?
-----------------------------------------------------------------
Use the Bernstein's conditions to transform the following
sequential program into an equivalent concurrent program with
maximal concurrency.
x := y+z;
w := y+t;
u := w-x;
v := x+t;
Assuming that each statement is executed in one unit of time,
the sequential program is executed in 4 units of time. How
long will the concurrent program take to execute?
-----------------------------------------------------------------
We have introduced two modules to synchronize concurrent
processes: SPINLOCKS and SEMAPHORES.
(a) Describe them and indicate their advantages, disadvantages.
(b) Why in multiprocessor systems we need special
instructions such as TestAndSet to implement spinlocks?
(c) Why in multiprocessor systems we need spinlocks
to implement mutual exclusion semaphores?
-----------------------------------------------------------------
Implement SPINLOCKs as an abstract class using pseudo-english
(or C++)
-----------------------------------------------------------------
We have introduced an abstract data type to synchronize
concurrent processes: SPINLOCKS.
(a) Describe what it does.
(b) Describe why it uses the TestAndSet instruction
(c) Describe why, in addition to the TestAndSet instruction
it may also disable/enable interrupts.
(d) Describe at least two problems with the use of spinlocks.
-----------------------------------------------------------------
The following code has been suggested to improve the
performance of the lock operation on spinlocks:
PROCEDURE Lock(L : in out SpinLock);
BEGIN
WHILE TestAndSet(L) DO
WHILE (L == 1) DO null;
END;
explain when and why it does so.
-----------------------------------------------------------------
Describe Mutual-Exclusion, Blocking, and Counting
Semaphores. For each give an example of use.
-----------------------------------------------------------------
Define the Readers-and-Writers problem. How did you encounter
this problem in the homeworks?
-----------------------------------------------------------------
The following is code from the Readers-and-Writers problem
discussed in class:
GLOBAL VARIABLES: mutex, wrt : semaphores initialized to 1;
readcount : integer initialized to 0;
READER: ......
p(mutex);
readcount := readcount+1;
if readcount=1 then p(wrt);
v(mutex)
read
p(mutex);
readcount := readcount-1;
if (readcount=0) then V(wrt);
v(mutex);
....
WRITER: .......
p(wrt);
write
v(wrt);
....
Modify this program to make sure that the WRITER has precedence
over the READERs, i.e., if the WRITER is waiting and some READER
is reading, no additional READERs will be allowed to enter the
critical region until the WRITER has entered and gotten out.
-----------------------------------------------------------------
Monitors have been used to create abstract data types that can
be shared by concurrent processes.
Look at the code:
o used as prolog of a monitor procedure
o used as epilog of a monitor procedure
o used to WAIT on a condition within the monitor
o used to SIGNAL a condition within the monitor.
Trace what happens if:
o Process P1 call a monitor operation and within it
executes X.WAIT
o then process P2 calls a monitor procedure and within it
executes X.SIGNAL
o no other process uses this monitor.
-----------------------------------------------------------------
Monitors are abstract data types that can be shared by
concurrent processes. Discuss their implementation in terms of:
a) what happens when a monitor operation is called.
b) what happens when a monitor procedure returns.
c) what happens when a WAIT on a condition is called.
d) what happens when a SIGNAL on a condition is called.
-----------------------------------------------------------------
For monitors:
a. How are they defined?
b. Why are they convenient?
c. Why do they use condition variables?
d. How do condition variables differ from
binary semaphores?
-----------------------------------------------------------------
Monitors are abstract data types that can be shared by
concurrent processes. Here is some information
about their implementation:
Global variables
mutex: Semaphore initialized to 1;
next: Semaphore initialized to 0;
next_count: integer variable initialized to 0;
Prologue Code executed when starting execution of a monitor's
operation:
P(mutex);
Epilogue Code executed when ending execution of a monitor's
operation:
if next_count > 0 then V(next) else V(mutex);
Explain in detail what is going on
-----------------------------------------------------------------
Specify a solution to the Producers-and-Consumers problem
using Monitors.
-----------------------------------------------------------------
Specify a solution to the DINING_PHILOSOPHERS problem [with 4
philosophers] using the CSP language.
Hints: Each philosopher is represented as a process [describe
only one philosopher].
The table with the forks is also represented as a proces.
Look at the monitor solution for this problem. The PICKUP
and PUTDOWN operations are implemented as alternatives in
an alternative command.
-----------------------------------------------------------------
Process P1 sends integers to process P2 using the integer
variable X which is in shared memory. Implement in pseudocode
a monitor with operations PUT and GET that will respectively be
used by P1 and P2.
-----------------------------------------------------------------
Monitors are abstract data types that can be shared by
concurrent processes since their operations are executed in
mutual exclusion. They use Condition variables to allow
a process to sleep if a desired situation is not currently
true [for instance, in a protected buffer, we cannot PUT
when the buffer is full]. Explain the following implementation
for Conditions:
type CONDITION is struct {count: integer := 0;
queue: semaphore := 0;}
procedure WAIT(x : in out CONDITION) {
x.count++;
if (next_count > 0) V(next); else V(mutex);
P(x.queue);
x.count--;}
procedure SIGNAL(x: in out CONDITION) {
if (x.count>0) {
next_count++;
V(x.queue);
P(next);
next_count--}}
In this code next_count (an integer initialized to 0), mutex
(a mutual exclusion semaphore), and next (a blocking
semaphore) are variables global to the monitor. Explain their role.
-----------------------------------------------------------------
Implement as a Monitor an object that will enforce the locking
behavior we have seen in the Readers and Writers problem.
[You will need to implement the operations R_LOCK, R_UNLOCK,
W_LOCK, W_UNLOCK]
-----------------------------------------------------------------
You all know the Dining Philosophers's Problem.
a. How can Deadlock arise? and how can it be avoided?
b. How can Livelock arise? and how can it be avoided?
c. How would you represent the solution of this problem
as a program?
-----------------------------------------------------------------
Conditional Critical Regions (CCR) were introduced to facilitate
the synchronization of concurrent programs. Describe how CCRs can
be implemented using semaphores [the actual implementation is in
the book, you have to describe what the program does and why].
-----------------------------------------------------------------
Specify a solution to the Protected Bounded Buffer Problem
using Conditional Critical Regions. Write the solution in
structured English.
-----------------------------------------------------------------
You are given a concurrent program written, say, in C with calls
to UNIX system services. You run it and it seems to execute
correctly. Yet you know about interleavings and you are afraid
that there might be some underleavings for which the program
would not execute correctly. How would you go about testing your
program? Be as detailed as you can.
-----------------------------------------------------------------
State and explain Amdhal's Law.
-----------------------------------------------------------------
Here is some code from the protected buffer you used in a lab:
typedef struct {
void * q;
pthread_mutex_t mutex;
pthread_cond_t condition;
} pqueue;
void pput(pqueue * fifo, elemtype v) {
pthread_mutex_lock(&(fifo->mutex));
while (queuefull(fifo->q)) {
pthread_cond_wait(&(fifo->condition), &(fifo->mutex));}
put(fifo->q, v);
pthread_cond_signal(&(fifo->condition));
pthread_mutex_unlock(&(fifo->mutex));
}
Give a high-level description of what is done and why.
-----------------------------------------------------------------
We are given a computer system consisting of a CPU and a disk.
We are told that each user request has a compute time of 80
milliseconds and on average generates 10 disk requests.
We are further told that the service time at the disk is 10
milliseconds.
(a) Is this system compute bound or io bound?
(b) What is the maximum number of user requests that can
be satisfied per second?
(c) If we are told that the disk is used 50% of the time,
how many user requests are being satisfied per second?
Explain your answers.
-----------------------------------------------------------------
What would make for a good scheduling policy? Give general
criteria and describe one such policy.
-----------------------------------------------------------------
What is the difference between Load Balancing and Scheduling?
-----------------------------------------------------------------
A low priority process should not be running while a high
priority process is ready. Indicate some instants when the
kernel makes sure that this rule is not violated.
-----------------------------------------------------------------
Little's Law relates the time spent in a queueing system to the
number of jobs in that system. State the law, then show how it
helps us solve the problem:
o Jobs arrive to the printer on the average every two
minutes
o Print jobs have a turnaround time of 10 minutes.
How many jobs are ahead of us when we submit a new job?
-----------------------------------------------------------------
By observing the line at my bank I noticed that there
are on average 20 people in line and that each person
stays about 15 minutes. What is the arrival rate to this
line?
-----------------------------------------------------------------
What is Little's Law?
Can you explain why, when I said "At the bank today
I had to wait 30 minutes, though people were arriving every
5 minutes", somebody said "There must have been ?? people
in line!"
-----------------------------------------------------------------
An operating system can be preemptive or non preemptive.
Explain what it means and what are the advantages of each.
-----------------------------------------------------------------
(a) What is latency?
(b) How can you limit in a non-preemptive
operating system the latency of interrupts?
-----------------------------------------------------------------
We are given the following precedence graph
and we are told that A, C, F take each one unit
of time to complete, while B, D, E take two
units. Assuming that you are given two
processors, construct an execution schedule that
will complete all the jobs as early as possible.
A----->B-+->E
\ /
+--->C
\ \
+->D-+->F
-----------------------------------------------------------------
Explain the distinction between Pre-emptive and Non Preemtive
Scheduling. Be sure to describe the impact that this distinction
has on the performance and ease of programming of multi-tasking
applications.
-----------------------------------------------------------------
In an interactive system with a single disk [see drawing]
the following has been measured:
+<-------------------------------------------+
| +-----------------------------+ ^
| | ---+ +--+ | |
| +-+ | +--->|||--->| |->+ |
| | | | --+ +--+ | ---+ +--+DISK |
+->| |----+->||->| |-+--------------------->+
| | --+ +--+
+-+ CPU
TERMINALS
o Each CPU request generates 36 disk requests
o Service time at the disk is 40 milliseconds
o There are 15 terminals
o Think time is 20 seconds
o The response time is 10 seconds (thus T, in Little's Law,
is 30)
(a) What is the utilization of the disk?
(b) Any idea of how many more terminals you can use
before the disk saturates? [10 EXTRA POINTS!]
-----------------------------------------------------------------
We are given a computer system consisting of a CPU and a
disk. We are told that each user request generates 10 disk
requests. We are also told that the service time at
the disk is 10 milliseconds, the disk utilization is 50%
while the cpu is saturated.
(a) What is the number of user requests being
satisfied per second?
(b) How long does a job spend on the cpu?
(c) What is the minimum response time?
Explain your answers.
-----------------------------------------------------------------
We are given a computer system with the following structure:
---+ +--+ ---+ +--+ ---+ +--+
--->|||-->| |---->|||-->| |---->|||-->| |----->
---+ +--+ ---+ +--+ ---+ +--+
READER CPU PRINTER
The service time for each job is 2 seconds at the reader,
1 second at the CPU, and 3 seconds at the printer.
What is the maximum number of processes that will be
done in a minute? and what will be the utilization of the
printer if the utilization of the reader is only 50%?
-----------------------------------------------------------------
We are given the system
Queue1 CPU1
---+ +-+
--->+-+->| |-->| |----+---+-->
^ | ---+ +-+ ^ |
| | | |
| | ---+ +-+ | |
| +->| |-->| |----+ |
| ---+ +-+ |
| Queue2 CPU2 |
| +-+ +--- |
+<---| |<--| |<-------+
+-+ +---
Disk Queue3
where CPU1 has a service time of 12 seconds, CPU2
has a service time of 15 seconds, and Disk has a
service time of 10 seconds. Assume that each job
will visit a CPU 10 times (and the disk 9 times)
before exiting the system:
(a) What is the least amount of time one job will
take to complete?
(b) What is the average number of jobs completed
per minute?
-----------------------------------------------------------------
We are given the following system
+---+
------+-->|CPU|----+---->
^ +---+ |
| |
| +-----+ |
+<-|DISK |<--+
+-----+
Service time at CPU is 9ms and at DISK is 10ms.
Assuming that each job goes 3 times through the disk
before completing (thus a total of 4 times through the CPU)
(a) Which is the bottleneck? the CPU? the DISK? explain.
(b) How many jobs will be completed per second? explain.
(c) Assuming that your boss wants this system to complete
100 jobs per second and you are free to choose the
service times of CPU and DISK, what values would you choose
for them?
-----------------------------------------------------------------
In describing a system we may use a number of terms:
a) Utilization
b) Response time
c) Turnaround time
d) Throughput
Define each term.
-----------------------------------------------------------------
In an M|M|1 queue system the response time is
ServiceTime/(1 - Utilization)
(a) How can you compute the Utilization if
you are given the Service Time and the
InterArrival Time?
(b) Assume then that you have an M|M|1 system
where the server processes a job in 0.2 seconds
and where 3 jobs arrive each second.
What is the response time in this system?
(c) In a system the utilization is 80%.
We replace its server with one that is twice
as fast. How much better will be the response time
in the new system than it was in the old system?
-----------------------------------------------------------------
What scheduling discipline would you use to improve turn-around
time? Why?
-----------------------------------------------------------------
Write C code to do storage management for (fixed size) segments.
One procedure, INIT, initializes things. One procedure will be
used to ACQUIRE storage, the other to FREE a previously acquired
segment.
Keep a list of the the currently free storage blocks.
-----------------------------------------------------------------
Write in pseudocode procedures to manage variable size blocks
using bit maps.
-----------------------------------------------------------------
Write in C a function "allocate" that manages available storage
in the integer array A. Allocate, given a positive integer
as argument, returns the address of a memory block in A that
has that many free consecutive integer units [or zero if no
such space is available]. Assume that allocate keeps track of
free storage in A using a character array B with '0' for
locations that are free in A and '1' for locations that are
not free in A.
-----------------------------------------------------------------
Write in C procedures which do storage management for
(variable size) segments. One procedure will be used to ACQUIRE
storage, the other to FREE a previously acquired segment.
Keep a list of the the currently free storage blocks and
allocate segments using a first-fit strategy.
Don't forget to merge contiguous free blocks.
------------------------------------------------------------------
Describe how in a paged memory system a virtual address is
converted into a physical address.
----------------------------------------------------------------
When talking of Storage Management we have discussed Internal
and External Fragmentation. Define what they are. Any idea
about how much storage is wasted (i.e. remain unutilized)
because of them?
-----------------------------------------------------------------
Virtual Memory receives substantial support from the hardware.
List what exactly is being supported. Describe, if possible, a
specific computer system.
-----------------------------------------------------------------
Describe 3 reasons for using Virtual memory.
-----------------------------------------------------------------
Describe what is a Virtual memory that is Segmented over Pages.
-----------------------------------------------------------------
You are given a multiprocessing computer system where processors
share main memory. To improve the performance of the system
a cache memory is added to each processor. What problem will
then arise? What technique(s) can be used to avoid it?
-----------------------------------------------------------------
We are given a job that takes 12 seconds to execute on a single
processor. The work done in 10 of these seconds could be executed
in parallel if we were given more processors.
A. How long will it take to execute this program if we have 5
processors?
B. How efficiently are these processors being utilized?
C. Assuming you can have as many processors as you want, how
long will it take you to complete this job?
-----------------------------------------------------------------
(a) What are caches?
(b) What is the cache coherence (consistency) problem?
-----------------------------------------------------------------
We have seen virtual memory addresses grow from 16 bits to
64 bits. Can you give some reasons for this growth?
-----------------------------------------------------------------
What are the respective advantages and disadvantages of Paged
vs Segmented Virtual Memories?
-----------------------------------------------------------------
Virtual Memory receives substantial support from the hardware.
List what exactly is being supported. Describe, if possible,
a specific computer system.
-----------------------------------------------------------------
In a paged virtual memory system we are told that main memory
has a cycle time of 0.6 microsecond; that secondary storage has
an access time of 10 milliseconds. If we want to achieve a
virtual memory cycle time of 1.0 microseconds, what should be the
fault rate of our programs? Explain in detail.
-----------------------------------------------------------------
In a virtual memory system, if we have no fault, we access
a location in time t, and if we have a fault, in time T.
Assume that the probability of fault is p.
(a) Determine the mean time between faults
(b) Determine the average access time to the location
-----------------------------------------------------------------
What is Trashing and how can you prevent it?
-----------------------------------------------------------------
The Virtual Memory of modern operating systems requires
considerable hardware support. Indicate all the kinds
of hardware supports you can think of.
-----------------------------------------------------------------
Define Hard and Soft page faults.
-----------------------------------------------------------------
We have a page fault. We go look for a free frame and we do not
find it. So, to handle the fault, we have first to free a frame
and only then bring in the needed page. What can you do to make
sure that you will always find free frames?
-----------------------------------------------------------------
You are the operating system. You notice that a process has
executed for one second and during that time has had 200
(hard) page faults, where each fault is handled in 10 ms
(thus the effective time of the computation is at least 3
seconds). Would you give more frames to this process? Less?
Why?
-----------------------------------------------------------------
What are the necessary conditions for Deadlocks and why?
-----------------------------------------------------------------
The Ostrich Algoritm deals with Deadlocks. Describe what it is
and why it is not as silly as it seems.
-----------------------------------------------------------------
A problem when using spinlocks is that we may get into
a Priority Inversion situation. Explain in detail what it is
and how you could avoid it.
-----------------------------------------------------------------
In Unix there are a number of mechanisms used to allow
concurrent tasks to cooperate in performing some work.
Describe all the mechanisms you can think of.
For each mechanism indicate:
a. what it is,
b. how it is used,
c. what makes the mechanism particularly useful,
d. what are the problems of the mechanism.
-----------------------------------------------------------------
In Unix suppose that x is an integer in process A.
Process B is the parent of A and B knows A's process id.
Show how B can send an appropriate signal to A and
how A can react by printing out the value of X.
-----------------------------------------------------------------
In Unix a process wants to create a child process that
executes the executable image stored in the file filename.
Write code to achieve this.
-----------------------------------------------------------------
Describe what is non-blocking I/O. Show how a process
may take advantage of non-blocking IO to read concurrently
from two files.
-----------------------------------------------------------------
Describe Blocking and Non-Blocking IO and specify their
advantages and disadvantages.
-----------------------------------------------------------------
Describe synchronous, asynchronous, and non-blocking IO
and specify their advantages and disadvantages.
-----------------------------------------------------------------
Describe the following commands:
(1) netstat
(2) ifconfig
(3) nslookup
-----------------------------------------------------------------
Vnodes in Unix are used to:
a. improve the performance of files
b. improve the reliability of files
c. improve the efficiency of files
d. None of the above
-----------------------------------------------------------------
Describe the use of a Buffer Cache in the Unix file system.
-----------------------------------------------------------------
In Unix when reading and writing to IO devices we may use buffers.
Why? Advantages and disadvantages.
-----------------------------------------------------------------
In Unix when writing to IO devices Unix may use system buffers.
A. What is the purpose of the system buffers?
B. Why are synchronous writes recommended to improve reliability?
C. Why are synchronous writed discouraged to improve performance?
-----------------------------------------------------------------
In Unix, assuming that file pages hold 512 bytes and that inodes
hold 12 direct pointers, read a word at location 234,188.
-----------------------------------------------------------------
Explain how you use the tar and pine commands to send
your homework to the Teaching Assistant and then to receive
his commented reply.
-----------------------------------------------------------------
A process executes
printf("roses");
Then it forks.
Then it executes
printf(" are red\n");
And terminates.
The child just executes
printf("I am the child\n");
and terminates.
What is printed out? Explain.
-----------------------------------------------------------------
In Unix I write a program that executes
printf("Roses are Red");
forks a child and then does other things.
The child executes
char buffer[] = "Violets are Blue";
write(1, buffer, 1+strlen(buffer);
printf("Violets are Blue");
and then does other things.
I look at the output and I find (not necessarily on
separate lines):
Violets are Blue
Roses are Red
Roses are Red
Violets are Blue
and not, as I expected,
Roses are Red
Violets are Blue
Violets are Blue
What happened?
-----------------------------------------------------------------
Write in C and UNIX a program that creates a pipe and
two children.
The first child reads from the terminal a string, writes it to
the pipe, and terminates. The second reads from the pipe, prints
what it obtains to the screen, and terminates.
The main program terminates when both its children have
terminated.
-----------------------------------------------------------------
Write a program in C that attaches to a shared memory segment
containing the data structure
struct S{
char[32] name;
int grade;
} students[32];
prints out the average grade and then detaches the shared memory.
The identity of the shared memory is passed as a command line
parameter to the program.
-----------------------------------------------------------------
You are in Unix, you open an existing, empty file. You seek
location 600K+200, you write there the string "hello".
Describe what are the index and data blocks of the resulting file.
You can assume that pages are 1K bytes and pointers to pages are
4 bytes long.
-----------------------------------------------------------------
Write in C and UNIX a program that creates two children.
The first child prints out its own process id and terminates.
The second process executes a program MOO.
The main program terminates when both its children have
terminated.
-----------------------------------------------------------------
In Unix a parent process opens a file "foo" and then forks two
children. If now the parent and children read from "foo", will
they all read the same information? or what? Give the reason for
the behavior.
-----------------------------------------------------------------
Describe with examples some mechanisms in the Unix shell that
deal with concurrency and with interprocess communication.
-----------------------------------------------------------------
The Unix Shell supports commands such as:
% S1 | S2
Any idea about what it does and how it is implemented?
-----------------------------------------------------------------
Write in C under Unix a program with two processes, a parent and
a child. [Pseudo code will receive partial credit]
The program is called with as command line parameters the names
of two files, filename1 and filename2.
The parent will copy to the child through a pipe p the content
of file filename1. The child will write to file filename2 what
it reads from the pipe p.
-----------------------------------------------------------------
In Unix we can use the command ALARM(T) which will
send a signal to the current process in T seconds.
How do you think this is done by the operating system using the
real time clock?
-----------------------------------------------------------------
Explain the following services of Unix:
signal
pause
kill
alarm
-----------------------------------------------------------------
Show how in Unix alarm and pause can be used to implement the
sleep command. Explain.
-----------------------------------------------------------------
Describe how in Unix we can implement the command Sleep(T) which
will put to sleep the current process for T seconds using the
signal mechanism.
-----------------------------------------------------------------
Discuss signals:
(a) What are signals.
(b) How do you raise a signal.
(c) How do you handle a signal.
(d) Why and how you block signals.
-----------------------------------------------------------------
Explain the difference between Unix IO commands and Standard C
IO commands. Which are portable across operating systems?
-----------------------------------------------------------------
Show how we can use in Unix the popen system service to determine
within our C program if a specific user, say Ikoniak, is currently
logged in our system.
-----------------------------------------------------------------
Unix has the FORK statement. Say in great detail what
it does and some of its possible pitfalls.
-----------------------------------------------------------------
When a Unix process forks, the child process receives
a copy of the address space of the parent.
(a) Indicate some location where the content is different
in the child and in the parent.
(b) Indicate a technique that is used to reduce on average
the amount of memory copied from parent to child.
(c) A problem that the child may have using the printf
command (a Standard C Library function).
-----------------------------------------------------------------
The standard C library function putchar writes to standard output
a single character. Describe what happens (assuming that you are
in Unix) from the moment that you call the function to the moment
that output finally goes to a file denoted by a i-node.
-----------------------------------------------------------------
To keep track of the pages of a file, to each file is
associated an index. You are in a Unix system where the
pages are 1KBytes, and the i-node has 10 direct pointers
1 indirect pointer, 1 doubly indirect pointer, and 1 triply
indirect pointer. Finally, where each pointer is 8 bytes.
Show how you will access the 155,000th byte of the file.
-----------------------------------------------------------------
Describe some mechanisms that exist in UNIX to support
Multitasking:
a. At the Shell level, that is, at the command language
level
b. At the System Services level, that is, at the
application program interface level.
-----------------------------------------------------------------
Describe the aspects of the UNIX file system that you consider
most significant.
-----------------------------------------------------------------
Describe how one can use in UNIX the DUP and CLOSE system
services to pass a pipe as standard output for a child process.
Give the actual C code.
-----------------------------------------------------------------
a) Give the reason why we OPEN files before we read or write to
them.
b) Give an example of the information kept in main memory for an
open file.
c) In NFS the read operation uses as an argument the path of the
file we want to read. Is that different than in Unix? Why?
-----------------------------------------------------------------
In C + Unix write the salient code of a program that
(a) consists of two processes P1 and P2
(b) P1 generates capital letters at random and sends them
one at a time to P2 using a pipe
(c) P2 writes the letters it reads from that same pipe
to the screen one per line
-----------------------------------------------------------------
Write a C (or pseudocode, if necessary) program that
creates a child, sets up a signal handler on SIGUSR1, and
goes to sleep. The child prints "I am here", sleeps 10
seconds, sends a SIGUSR1 signal to his parent, sleeps
10 more seconds, prints "I am gone", exits. The parent's
signal handler just prints "thank you" then exits.
-----------------------------------------------------------------
Write a C (or pseudocode, if necessary) program that
creates a shared memory segment containing a single integer
variable X, prints the value of X, creates a child,
executes a wait, then, when active again, prints out the value
of X.
The child attaches to the same shared memory segment,
writes 7 to X, and exits.
-----------------------------------------------------------------
Write a program in C that attaches to a shared memory segment
containing the data structure
struct S{
char[32] name;
int grade;
} students[32];
prints out the average grade and then detaches the shared memory.
The identity of the shared memory is passed as a command line
parameter to the program.
-----------------------------------------------------------------
Write a C (or pseudocode, if necessary) program that
creates pipes p1 and p2, creates a child, then in a loop,
calls a function FOO that sends a random number in the interval
0..10 through p1 to the child and receives back through p2
a number from the child. The child reads from p1 a number and
writes to p2 the square of that number. Both parent and child
will run forever.
-----------------------------------------------------------------
Implement the function void traspose2(int a[], int n);
which interprets the one-dimensional array a to be an
n by n square matrix and transposes it around the secondary
diagonal ( 1 2 3 4 5 become 25 20 15 10 5 )
6 7 8 9 10 24 19 14 9 4
11 12 13 14 15 23 18 13 8 3
16 17 18 19 20 22 17 12 7 2
21 22 23 24 25 21 16 11 6 1
-----------------------------------------------------------------
We have been using the files csapp.c csapp.h in our homeworks.
In there we find the function
ssize_t rio_readn(int fd, void *usrbuf, size_t n)
to robustly read (i.e. coping with interruptions due to
signals and with the system policies for returning from read)
from fd n bytes into usrbuf. It returns the number of
bytes actually read, or -1 in case of read error. Implement
this function.
-----------------------------------------------------------------
Write the function
int eqr(const char *a, const char *b);
which returns 1 if a is equal to the reverse of b,
returns 0 otherwise. For example eqr("rose","esor")
is 1 and eqr("anna","enna") is 0.
-----------------------------------------------------------------
NFS is a network file system.
(a) Explain what it means to say that NSF is stateless.
(b) Explain how it is possible in NSF to move and use data
between machines with different architectures.
-----------------------------------------------------------------
Write in C (do not worry about syntax errors) a program
where the parent assigns 1 to x, forks a
child that assigns 2 to x, and then (the parent)
prints x. What is printed out? in what order? Explain.
-----------------------------------------------------------------
Give the implementation of a FIFO queue (as a circular buffer)
using C.
-----------------------------------------------------------------
In C define a doubly linked circular list and implement
the Initialization and the Enqueue operations. In
the initialization you should produce a single node
where both the forward and the backward links
point back to this node.
-----------------------------------------------------------------
Given the definition
struct node{
struct node *left;
struct node *right;
char *value;};
implement the function
void traverse(struct node *root)
that prints out the value associated to all the
nodes reacheable from root. Any order will do.
-----------------------------------------------------------------
The ready queue is a priority queue with as elements the ready
processes. Describe at least 3 possible implementations for
priority queues and describe the complexity of the operations
enqueue and dequeue as a function of the ready jobs and,
possibly, of the number of priority levels.
-----------------------------------------------------------------
Implement the function
void get_host_port(char *request, char **host, int *port);
which, given a request of the form
"GET http://hostname[:portid]/[filename] HTTP/1.0"
where [:portid] means that we may or not have a port indication
and [filename] means that we may or not have a file indication,
returns in host a pointer to a pointer to the host id, and in
port a pointer to an integer specifying the port being used.
For example, if request is
"GET http://www.cis.temple.edu:5194/index.html HTTP/1.0"
host will be a pointer to "www.cis.temple.edu" and port a pointer
to 5194. If instead the request is
"GET http://www.nytimes.com/ HTTP/1.0"
then host will be a pointer to "www.nytimes.com" and port a
pointer to 80.
If you want you can use the function
char *strchr(const char *s, int c);
-----------------------------------------------------------------
A possible implementation of the ready queue is as a multilevel
priority queue. That is, assuming that there are n priorities
0, 1, .., n-1, where n-1 is the highest, it keeps at each level a
FIFO of the waiting proceses of that priority. Explain how
you would implement the Enqueue and Dequeue operations on this
ready queue.
[5 extra points for explaining what will be the time complexity
of these operations.]
-----------------------------------------------------------------
Implement the function:
void setbit(unsigned int w, int n);
which, given w and an integer n in the range 0 .. 31
sets the nth bit of w to 1.
-----------------------------------------------------------------
Implement in the language of your choice [or in semi-english
if necessary] a priority queue.
-----------------------------------------------------------------
We want to address the Sectors of a Disk Pack as records 0, 1, 2,
... Unfortunately the pack really has 10 surfaces, 400 cylinders,
and on each track [intesection of cylinder and surface]
it has 40 sectors.
Using C implement the functions:
to_index: surface x cylinder x sector -> record
{It determines the relative position of the physical}
{record identified by surface, cylinder, and sector }
from_index: record -> surface x cylinder x sector
{It determines the surface, cylinder, and sector}
{corresponding to a relative index}
-----------------------------------------------------------------
We are given a disk which on a track has 200 sectors,
where each sector is 1KB. The disk spins at 6000 rpm.
The bus has a data rate of 10MB per second.
(a) What is the average rotational delay on this disk?
(b) Any problem with this bus? and if yes, how would you
deal with it?
-----------------------------------------------------------------
We distinguish the Organisation of a File from its Access
Methods. Define a number of organisations and of access
methods.
-----------------------------------------------------------------
"Stable Storage" is disk memory where read and write operations
are atomic. Unfortunately normally disk memory is not atomic.
The usual disk memory only guaranties that if the read or write
operation does not work, then we will be given an error code.
Show how we can implement stable storage using the usual disks.
-----------------------------------------------------------------
To keep track of the pages of a file, to each file is
associated an index. Describe:
a. What are important features of this index
b. Give at least one detailed example of an index
structure.
-----------------------------------------------------------------
Write in C under Unix a program with two processes, a parent and
a child. [Pseudo code is acceptable and will receive partial credit]
The parent and the child share a memory segment that will
contain space for at least an integer. This memory segment is
created by the parent before forking the child. The parent
will prompt the user and read an integer, then place it in the
shared memory segment. The child will read it from there
and print it to the screen. You can choose the mechanism
the child uses to determine when to read the integer.
-----------------------------------------------------------------
Describe how files are protected in Unix.
-----------------------------------------------------------------
Here is the definition of a person and a bucket:
struct person {
char ssn[10]; // Social Security Number plus a space
char name[26]; // Name plus a space
char grade[3]; // Letter grade with + or - and a space
};
struct bucket {
unsigned int flags; // kth bit 1 iff slot[k] is in use
struct person slot[32];
};
Implement the function:
int bucketAdd(struct bucket *bucketp, struct person *who);
that adds who to the store; return 0 if insert is
successfull, 1, if a person with this social security was
already there (it is not modified), -1 if failure in
finding a free slot for who.
-----------------------------------------------------------------
Implement the function
char *nameval(char *s, char **name, char **value);
which given in s a string like
name1=value1&name2=value2& ..
stores in name and value respectively a pointer to name1
and value1, each terminated with '\0', and returns a pointer
to name2. For example, if s is
"operation=add&ssn=123456789"
then s is modified to
"operation\0add\0ssn=123456789"
^ ^ ^
| | |
*name *value pointer returned by function
-----------------------------------------------------------------
Implement the function
int getHash(char *name, int n)
which, given a string, it returns a value
in the range 0,1, ..,n-1
Use a good hashing algorithm.
-----------------------------------------------------------------
Implement the function:
void binary(unsigned int w);
which, given w prints out the binary expansion of w.
I will accept either the right order or the inverse order.
For example, if w is 37, I will be happy with either
100101 or 101001.
-----------------------------------------------------------------
Implement in C the function
char * dotted(unsigned int ipaddress);
that, given an IP address as a 32-bit unsigned
integer returns its value in the dotted
decimal notation (things like "155.247.71.60").
-----------------------------------------------------------------
Write in C the function:
constant
N = 100;
type
VECTOR = array [1..N] of CHAR;
function BINARY_SEARCH
(A: VECTOR; LOW, HIGH: INTEGER; WHO: CHAR) : INTEGER;
{It returns a position i in A where A[i]=WHO, if there}
{is one; otherwise it returns 0 }
-----------------------------------------------------------------
Write a C program that implements using threads, locks,
and condition variables the following behavior:
GLOBAL: int x = 0;
ACTIVITY 1: ACTIVITY 2:
loop loop
increment x if x is even or decrement x if x is odd;
divisible by 5;
forever forever
-----------------------------------------------------------------
A thread has to execute the following conditional critical region:
when ((x>0)&&(y<7)){
x = x + z - 2;
y = 2*y;
}
Write in C the function moo that implements this thread. Assume that
x and y are global integer variables and z is an integer formal
parameter of moo. Use locks and condition variables to
implement the conditional critical region.
-----------------------------------------------------------------
Explain what is the conditional critical region
when B do S;
Then implement it for threads using condition variables and mutexes.
Explain your code.
-----------------------------------------------------------------
You have to copy a file, say moo.dat, to foo.dat. We can
read a buffer from moo then write to foo, then read from moo,
then write to foo,.. Alternatively we can overlap the
read and write operations using two threads and alternating
the operations between two buffers. Write such a program in
C (or in pseudo-english). Explain what you are doing.
-----------------------------------------------------------------
s is a connected socket, filename is the name of a file.
Write the function
int dumpfile(int s, const char *filename)
that sends to s the content of the file and returns
the number of octets sent over, or -1 if it failed
for some reason.
-----------------------------------------------------------------
Write a function
int readmyline(int s, char *line, int maxn)
which reads from the socket s until either
end of file or carriage return is encountered.
Up to maxn-1 of the first characters read, plus '\0' are
stored in line. The function returns the number of
characters stored in line.
-----------------------------------------------------------------
I execute the statement
n = read(sd, buffer, 100);
When will this statement complete, and what will be its
effect? Think hard about all possible cases (the normal case,
non-blocking behavior, signals, ..)
-----------------------------------------------------------------
Describe in detail, on the basis of messages sent, what
happens when a Client makes a Remote Procedure Call (RPC) to
a Server.
-----------------------------------------------------------------
For RPC people have talked of "at-least once" semantics,
of "at-most once" semantics, and "exactly-once" semantics.
Define each semantics and indicate how it might be
achieved.
-----------------------------------------------------------------
Indicate at least two ways (but not the obvious fact
that they are remote) in which remote procedure calls
differ from normal procedure calls.
-----------------------------------------------------------------
There are problems with remote procedure call.
A. Problems with the parameters of the call.
B. Indicate some of the failures that may occur during the
execution of an RPC.
C. What is meant by AT LEAST ONCE SEMANTICS, AT MOST ONCE
SEMANTICS, EXACTLY ONCE SEMANTICS?
-----------------------------------------------------------------
What is the distinction between a Server and a Service?
Give an example.
-----------------------------------------------------------------
What is the distinction between a Statefull and a Stateless
service?
Give an example and indicate the advantages of each choice.
-----------------------------------------------------------------
For reliability we transmit a '0' as '00000' and a '1' as '11111'.
What is the Hamming distance for these bit vectors?
How many bit errors can we detect?
How many bit errors can we correct?
-----------------------------------------------------------------
(a) What is Forward Error Correction?
(b) What is the Hamming Distance between the following two
bit vectors: 011010001
010110101
(c) How many bit errors can be corrected if we have
a code with minimum Hamming Distance equal to 5?
-----------------------------------------------------------------
Why is a 16 bit CRC considered better than a 16 bit checksum?
-----------------------------------------------------------------
Why is a 16 bit checksum considered better than a 16 bit CRC?
-----------------------------------------------------------------
We are using a communication channel with a bandwidth of 64Khz and
a signal-to-noise ratio of 72 decibels, what will be the maximum
data rate on this channel? Explain your answer.
-----------------------------------------------------------------
On one of my CDs I read that the sound signal has
been sampled using 20 bit numbers on a 20Khz bandwidth.
What will be the datarate required to transmit this
digitized sound? Can you say what should be the decibel
signal-to-noise power ratio of the transmission channel
so that the 20 bit samples are meaningful?
-----------------------------------------------------------------
In data communication and networking one worries about:
(a) Framing
(b) Flow control
(c) Multiplexing
(d) Addressing
(e) Error Control
Define each one of these concepts.
-----------------------------------------------------------------
a. What is flow control and how (and by whom)
it is done in TCP?
b. What is congestion control and how (and by whom)
it is done in TCP?
-----------------------------------------------------------------
Explain the meaning, if any, of the sentence
"TCP and UDP are multiplexed over IP".
-----------------------------------------------------------------
Specify the names of the layers of the OSI network Architecture
and for each specify a standard or a protocol.
-----------------------------------------------------------------
Describe the Sliding Window Protocol.
-----------------------------------------------------------------
What is Unicasting? Multicasting? Broadcasting?
-----------------------------------------------------------------
We are given a communication channel with a bandwidth of
4Khz. We would like to achieve in that channel a data
rate of 128Kbps. How can we do that?
-----------------------------------------------------------------
When we communicate on a data link we want to detect
errors that have occurred in transmission. Describe
one method of error detection.
-----------------------------------------------------------------
You have heard the terms: Error Detection, Error Correction,
Error Recovery. Explain these terms and indicate a technique
used to carry them out.
-----------------------------------------------------------------
A few facts about Ethernet:
(1) What does CSMA/CD stand for?
(2) What is Exponential Backoff?
(3) How big is an Ethernet address (in bits)?
(4) How big is the largets Ethernet packet (in bytes)?
-----------------------------------------------------------------
Ethernet uses a CSMA/CD protocol to share the
communication channel. The size of a frame
in the 10Mbps Ethernet is between 64 and 1518 bytes.
How do you think they came up with such sizes?
-----------------------------------------------------------------
What is a Router and how it differs from a Bridge?
-----------------------------------------------------------------
A vising lecturer observed that routers are bad platforms
for system software development because there is no
memory protection and no pre-emptive scheduling.
a. What is memory protection?
b. What is pre-emptive scheduling?
c. Why the lack of memory protection and of pre-emptive
scheduling makes it hard on systems programmers?
d. Why do you think that such facilities are lacking
in current routers?
-----------------------------------------------------------------
Describe the data structure kept at a router and the algorithm
used to forward to the next router a packet with destination D.
-----------------------------------------------------------------
Describe what is the Backward Learning Algorithm (for
Learning or Adaptive Bridges) and how it operates.
-----------------------------------------------------------------
Why do we use the Distributed Spanning Tree Algorithm
in a system of LANs with Bridges?
-----------------------------------------------------------------
Given the network displayed on the blackboard as A.[It
consists of 3 segments, X, Y, and Z. On X are hosts 1
and 2. On Y is host 3. On Z are hosts 4 and 5. The
bridge A connects X and Y, the bridge B connects
X and Z, and the bridge C connects Y and Z.]
(a) Use the Distributed Spanning Tree algorithm to
derive a Spanning Tree. Indicate which ports
are root and designated ports, and which are
disabled.
(b) Host 1 sends a message to host 4. Then:
(1) Host 1 sends a message to 5: what bridges and
segments are traversed by this message?
(2) Host 3 sends a message to 1: what bridges and
segments are traversed by this message?
-----------------------------------------------------------------
Systems A and B communicate using the Go-Back-N
method. The propagation delay is 10ms, the data
rate is 1Mbps, the packet size is 1KB. N is 10
(i.e. up to 10 packets can be outstanding without
reception of an ACK).
(a) How long will it take A to send 1MB to B?
(b) What is the utilization of the communication channel?
Explain.
-----------------------------------------------------------------
Here is a graph. Indicate all the messages exchanged
when building for it a spanning tree rooted at A.
The message types are 'M' (Message), 'P' (Parent),
'R' (Reject).
+-+ +-+
|A|-----------|B|\
+-+ +-+ \
| | \
| | +-+
| | |E|
| | +-+
| | /
+-+ +-+ /
|C|-----------|D|/
+-+ +-+
-----------------------------------------------------------------
You know about IP addresses.
(a) Can a computer have more than one IP address?
and if so how?
(b) How many IP addresses are there (IP version 4,
the only one we discussed)?
(c) What is the structure of an IP address?
(d) Is the IP address like the Ethernet address
stored in the hardware or is it a software
concept?
(e) What is a subnet mask?
-----------------------------------------------------------------
Convert the following binary IP address to
10110110 11110111 10110100 00100000
(a) Hexadecimal, and
(b) Dotted decimal notation
-----------------------------------------------------------------
What is a routing table and how is it used to route
a packet to the next node.
-----------------------------------------------------------------
In Routing explain the concepts:
(a) Source Independence
(b) Store and Forward
(c) Next-Hop Forwarding
(d) Default routing table entry
-----------------------------------------------------------------
Systems A and B communicate through an intermediate
node C (where store-and-forward is used) using the
stop-and-wait method. On both the links A-C and C-B
the propagation delay is 15ms, the data
rate is 1.5Mbps, the packet size is 1KB. How long will
it take A to send 1MB to B? Explain.
-----------------------------------------------------------------
What is the purpose of the Vector Distance Routing Algorithm?
-----------------------------------------------------------------
What is the difference between Routing Algorithms and Routing
Protocols? Name at least one routing algorithm and one routing
protocol.
-----------------------------------------------------------------
We are communicating on a 50Mbps channel with a satellite
that is 10,000 kilometers high. We send packets that are
25,000 bytes long. We use a stop-and-wait protocol, i.e.
we wait acknowledgement from the previous packet before
sending a new packet.
(a) How efficiently is the channel used?
(b) How long will it take to transmit 200,000 bytes?
-----------------------------------------------------------------
In an IP header we find (among others) the following fields:
Identification, Fragment-Offset, Time-To-Live, Flags.
Indicate what are their purposes.
-----------------------------------------------------------------
A machine A sends messages to machine B using the stop-and-wait
protocol. Assume that the propagation time is 20ms and the
transmission time is 2ms, what will be the utilization of the line?
Explain your answer.
-----------------------------------------------------------------
Two nodes communicate using a Stop-and-Wait policy.
Compute:
(a) The Transmission delay, say, sending b bytes at data rate r.
(b) The Propagation delay, say, sending a packet at distance d.
(c) The Transmission Efficiency.
-----------------------------------------------------------------
You are writing a Client program that communicates
using UDP with a Server. The Server is on host
hocus.pocus.com at port 2345. Specify what the Client program
will do before being able to send the first message to the
Server.
-----------------------------------------------------------------
You are writing a Server program that communicates
using UDP with Clients. Specify what the Server program
will do before being able to receive the first message
from a client.
-----------------------------------------------------------------
We are given a program. That takes 10 minutes on our machine.
We are now given a total of 5 machines. We rewrite the
program so that 2 minutes of the original computation
need to be done sequentially while 8 minutes can be done
concurrently.
(a) What is the resulting Speedup?
(b) How efficiently are we using our computers?
-----------------------------------------------------------------
Describe the OSI Model. Be as detailed as you can within
our constraints of time.
-----------------------------------------------------------------
In the OSI model there is a Presentation Layer. Describe all
the representation issues that you can think of and suggest
some way to make sure that information is faithfully moved
between different computers.
-----------------------------------------------------------------
Two commonly used words when talking of distributed systems are:
Scalability and Transparency. What do they mean?
-----------------------------------------------------------------
Distributed systems are said to be harder to program than
centralized systems. Explain why that is so [if you disagree,
give your reasons].
-----------------------------------------------------------------
At various times in this course we have brought up the issue of
"reliability". Describe some of the topics we have discussed that are
related to "reliability".
-----------------------------------------------------------------
You are in a distributed system and you have three
communicating systems S0, S1, and S2.
On S0 take place, in order, the events
A, B, C,D, E
On S1 take place, in order, the events,
F, G, H, J, K
On S2 take place, in order, the events
L, M, N, 0
We further know that:
A is the sending of a message to S1 received as event F.
B is the sending of a message to S2 received as event N.
G is the sending of a message to S0 received as event C.
J is the sending of a message to S0 received as event D.
K is the sending of a message to S2 received as event O.
L is the sending of a message to S0 received as event E.
M is the sending of a message to S1 received as event H.
a) Write for each event the value of its logical clock.
b) Write in a correct order all these events into a log,
i.e., say which is first, which second, etc.
c) Show two events that are concurrent and two events that
are not concurrent.
-----------------------------------------------------------------
In a distributed system processes want to be able to access a
shared resource in mutual exclusion. Describe the distributed
algorithm for Mutual Exclusion due to Ricart-Agrawala.
-----------------------------------------------------------------
In a distributed system processes want to be able to access a
shared resource in mutual exclusion. This can be achieved in a
Centralized way, in a Distributed way, or in a Semi-Centralized
way.
a. Describe what is meant with these terms.
b. Describe an algorithm for Mutual Exclusion.
-----------------------------------------------------------------
In a homework you have used interprocess communication with
sockets. Explain in detail the following two statements:
(a) s = socket(AF_INET, SOCK_DGRAM, 0);
(b) y = htonl(x);
-----------------------------------------------------------------
You are using stream-oriented sockets.
(a) Explain the distinction between listening sockets
and connected sockets.
(b) Which (if any) of the two kinds are used on the client? which
on the server?
(c) Describe the third kind of socket used in TCP.
-----------------------------------------------------------------
In a distributed system processes want to be able to access a
shared resource in mutual exclusion. Describe the centralized
algorithm for Mutual Exclusion which uses a Resource Manager.
-----------------------------------------------------------------
Compare the problem of mutual exclusion in a tightly coupled
system, to the problem of mutual exclusion in a distributed
system.
-----------------------------------------------------------------
In a distributed system processes we often have a
Manager or Coordinator that oversees the interactions
of the other participants. Describe in detail the Bully
Algorithm that can be used to elect a Coordinator.
-----------------------------------------------------------------
Transactions must be atomic, serializable, and permanent.
What does it mean?
-----------------------------------------------------------------
In the absence of transactionality, show how we can have:
a. A Lost Update
b. A Dirty Read.
-----------------------------------------------------------------
A transaction is supposed to satisfy the ACID properties.
What does that mean?
-----------------------------------------------------------------
Transactions are Started, then Committed or Aborted.
(a) How do we make sure that transactions are serialized?
(b) What are, and give an example of, Cascading Aborts?
(c) What can we do to avoid cascading aborts?
-----------------------------------------------------------------
Explain in detail the purpose of Write-Ahead Logs, Undo-Only,
and how they operate.
-----------------------------------------------------------------
Explain in detail the purpose of Write-Ahead Logs, Undo-Only,
and how they operate. For example, if transaction T, given
objects x, y, z, and w with respectively values 1, 2, 3, and
4 writes 6 to x, 7 to y, 8 to x, 9 to z, 10 to y, and 11 to w
what will be written to the log? what will be done upon
commit? what upon abort?
-----------------------------------------------------------------
We have discussed serialization of transactions. For
example, suppose we have two transactions T1 and T2
that access shared variables a and b:
T1: R1(a) R1(b) W1(a)
T2: R2(a) R2(b) W2(b)
And here are three schedules
H1: R1(b) R1(a) R2(b) W1(a) R2(a) W2(b)
H2: R1(a) R1(b) R2(a) W1(a) R2(b) W2(b)
H3: R1(a) R1(b) R2(a) R2(b) W1(a) W2(b)
Use the Serializability Theorem to show for each
schedule if it is or not serializable.
-----------------------------------------------------------------
Describe in detail the Two-Phase Commit protocol for
transactions. Indicate at least one way in which a
transaction may become blocked.
-----------------------------------------------------------------
Transactions may use Two-Phase Locking (2PL).
(1) What is it?
(2) What is its purpose?
(3) What is Strict Two-Phase Locking (S2PL)?
(4) What is the purpose of S2PL?
-----------------------------------------------------------------
a. Describe in Two-Phase Locking for transactions.
b. Give an argument for why 2PL guaranties serializability.
c. Explain, perhaps by example, why 2PL can give raise to
deadlocks and cascading aborts.
d. What do you do in the case of deadlocks?
e. How can you avoid cascading aborts?
-----------------------------------------------------------------
We are given a transaction that executes the following
operations in sequence
Start R(x) R(y) W(z) W(x) R(u) W(y) Commit
Assuming that we are following a Strict-2-Phase-Locking
Policy, insert appropriate Lock and Unlock commands (things
like L(x) or U(x)).
-----------------------------------------------------------------
We are on a single computer system where transactions
are supported using the Redo-Only method (we are using
strict 2 phase locking). We start with the
integer variables a, b, c, d with values respectively 1, 2, 3, 4.
We carry out the following operations in order:
Store(6 to a), Store(7 to b), Store(9 to c), Store(8 to a),
Store(10 to c), Store(10 to b), Store(11, d).
A. Give the exact content of the Redo-Only log.
B. Indicate what it is done if the transaction is aborted.
C. Indicate what it is done if the transaction is committed.
-----------------------------------------------------------------
In a distributed system access to a shared resource is
mediated by a Coordinator process. Describe an algorithm
for selecting a new Coordinator in case of 'death'
of the current Coordinator.
-----------------------------------------------------------------
Deadlocks are harder to deal with in distributed systems.
a. Describe in detail a method for preventing deadlocks.
b. Justify why it works.
-----------------------------------------------------------------
In a distributed system transactions may become
deadlocked.
a. If we are using a Coordinator to build a Wait-For
graph we may get Phantom Deadlocks. Show an example
of how this may happen.
b. We may use the Chandy-Misra-Haas Algorithm to
detect a distributed deadlock. Demonstrate the
algorithm in the following system when 1 requests a
resource held by 2.
+<-------------------+
/ \
1 2------>4---->5--+--->7
\ /
+---->3----->6
-----------------------------------------------------------------
Machine A sends 256 Byte messages to machine B. Assume
that the distance is 1000 kilometers, the data rate is
1.5 Mbps, what will be:
(a) Transmission Time
(b) Propagation Delay
Explain your answer.
-----------------------------------------------------------------
A phone voice channel is 4KHz. The signal is encoded
using 256 levels (i.e. each sample is represented
with 8 bits). What is the required data rate of the
phone voice channel? Explain how this number is arrived at.
-----------------------------------------------------------------
What is the Internet?
-----------------------------------------------------------------
Describe the use of the ICMP protocol to implement the ping
and the traceroute commands.
-----------------------------------------------------------------
Describe some of the message types and uses of the ICMP protocol.
-----------------------------------------------------------------
Given the network with the specified distances
+-+ 3 +-+ use Dijkstra's Shortest
A | |---------| | B Path algorithm to determine
+-+ +-+ the shortest paths from C
| | to all the other nodes
2 | | 4 and their distances.
+-+ +-+ Give all the steps of the
C | |---------| | D algorithm.
+-+ 11 +-+
-----------------------------------------------------------------
Apply the Vector Distance Algorithm (Bellman-Ford)
for the following graph:
A B C
+-----+----+
/ \ /
/ \ /
+-----+
D E
assuming that each arc has length 1.
-----------------------------------------------------------------
We are using TCP. A client connect to the server and then
closes the connection. How many messages will be sent?
-----------------------------------------------------------------
Here are various statements about the Transmission
Control Protocol. For each statement, indicate if true or false.
(1) It is connection oriented.
(2) It is message oriented.
(3) It is stream oriented.
(4) It is Best-Effort.
(5) It is Half-Duplex
(6) It is a Session Layer protocol.
(7) Between two computers at one time there can
only be one TCP session.
(8) It uses piggy-backed acknowledgements.
(9) It supports up to 256 ports.
(10) It is used to implement the IP protocol.
-----------------------------------------------------------------
We are using TCP. A client connects to a server.
(a) Who performs the active open? who the passive open?
(b) What system calls need to be made by the client
to setup the connection?
(c) What system calls need to be made by the server
to setup the connection?
(d) What is the delay caused by the connection setup
before the client can send any data to the server?
-----------------------------------------------------------------
Temple University has the IP address: 155.247.0.0.
Suppose it decides to partition its 64K host addresses
into 512 subnets.
(a) How many hosts are at most in that whole Temple network?
(b) How many hosts will be in each subnet?
(c) What will be the subnet mask?
(d) If I am given the IP address 155.247.71.142 what
will be the id of its subnet?
(d) What is the class of this IP address?
(e) What is the host id of the given IP address?
-----------------------------------------------------------------
We are using CIDR routing. An ISP owns 6 class C networks, 200.77.0/24,
200.77.1/24, 200.77.2/24, 200.77.3/24, 200.77.4/24, 200.77.5/24.
Another ISP owns 200.77.6/24 and 200.77.7/24.
A. What mask will be used for the first ISP?
B. What mask will be used for the second ISP?
C. Which route will be selected for the address 200.77.6.15 and why.
-----------------------------------------------------------------
Describe what are the class A, B, and C Internet Addresses
and specify for each how many networks are in that class,
and for each network how many hosts.
-----------------------------------------------------------------
I am at home with my PC. I have a modem. I have an ISP.
Describe as well as you can how with my browser I reach
the Yahoo web server. In your explanation try to identify
things like, local loop, POP, ISP, Autonomous System, NAP,
internal and external routing.
-----------------------------------------------------------------
What is the Happened-Before relation on events and
why it is significant?
-----------------------------------------------------------------
Assume that each system A has a public key Kp(A)
and a secret key Ks(A). Show how these keys can
be used to
(a) Allow a system A to communicate in secrecy
with system B.
(b) Allow a system A to authenticate itself to
system B.
(c) Make sure that a message M is not corrupted in
transit (integrity).
-----------------------------------------------------------------
How do we use message digests and encryption to guaranty
message integrity?
-----------------------------------------------------------------
Public key encryption is slow but (perhaps) not breakable.
Secret key encryption is fast but breakable.
Discuss how the use of session keys takes advantage of both
techniques.
-----------------------------------------------------------------
To achieve security we tend to use both public key
cryptography and secret key cryptography and
use timestamps and lifetimes. Why?
-----------------------------------------------------------------
People say that Public Key encryption is more scalable than
Secret Key encryption. Why?
-----------------------------------------------------------------
In a Keberos like system here is an authentication authority S
and systems A and B that share with S, respectively, the
secret symmetric keys K(A) and K(B)). Specify and
explain a protocol through which A and B are authenticated
to each other and are given a session key K.
-----------------------------------------------------------------
Show how A can send to B a message M in a way that guaranties
Authentication, Integrity, and Non-Repudiation. You can assume a
Digest function, say MD5, and the use of a Digital Certificate.
-----------------------------------------------------------------
Systems A and B hold digital certificates from a certificate
authority C.
a. What is a digital certificate?
b. How are they used to allow A and B to communicate in secrecy?
-----------------------------------------------------------------
How do Digital Certificates make safer the distribution of
public keys?
-----------------------------------------------------------------
Some of the distinctions made about Client-Server systems
are:
iterative vs. concurrent
Stateless vs stateful
Describe what they are and some advantages/disadvantages of each.
-----------------------------------------------------------------
Explain how block chaining works and why it makes a block
harder to break.
-----------------------------------------------------------------
You have heard of the n-tier architecture for
distributed systems. Specify the tiers in the
2-tier, 3-tier, 4-tier architectures.
-----------------------------------------------------------------
(a) Explain the acronyms CORBA and ORB.
(b) Describe some ways in which CORBA is much more than RPC.
-----------------------------------------------------------------
What is describe what is the role and some of the services
provided by middleware.
-----------------------------------------------------------------
ingargiola@cis.temple.edu