Please see attached files for assignment questions and source files.
COMP 346 – Winter 2012
Assignment 3 – page 1 of 2
DEPARTMENT OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING
CONCORDIA UNIVERSITY
COMP 346: Operating Systems
Winter 2012
ASSIGNMENT 3
Due date: Wednesday March 21st before midnight
Theory Questions [50 marks]:
Q.1. Consider the following preemptive priority-scheduling algorithm based on dynamically
changing priorities. Larger priority numbers indicate higher priority (e.g., priority 3 is higher priority
than priority 1; priority 0 is higher priority than priority -1, etc.). When a process is waiting for the
CPU in the ready queue, its priority changes at the rate of α per unit of time; when it is running, its
priority changes at the rate of β per unit of time. All processes are assigned priority 0 when they
enter the ready queue. Answer the following questions:
(a) What is the scheduling algorithm that results when β > α > 0? Explain.
(b) What is the scheduling algorithm that results when α < β < 0? Explain.
Q.2. Somebody proposed a CPU scheduling algorithm that favors those processes that used the least
CPU time in the recent past. For calculating the CPU time of a process in the recent past, a time
window of size τ is maintained and the recent CPU time used by a process at time T is calculated as
the sum of the CPU times used by the process between time T and T- τ. It is argued that this
particular scheduling algorithm (a) will favor I/O-bound programs, and (b) will not permanently
starve CPU-bound programs. Do you agree/disagree with (a) and (b)? Explain.
Q.3. Consider a variant of the round robin (RR) scheduling algorithm in which the entries in the
ready queue are pointers to the PCBs. A malicious user wants to take advantage and somehow
manages to put two pointers to the PCB of his/her process with the intention that it can run twice as
much. Explain what serious consequence(s) it could have if the OS is not aware about the specific
action by the user.
Q.4. Consider the version of the dining philosopher’s problem in which the chopsticks are placed in
the centre of the table and any two of them can be used by a philosopher. Assume that requests for
chopsticks are made one chopstick at a time. Describe a simple rule for determining whether a
particular request can be satisfied without causing deadlock given the current allocation of
chopsticks to philosophers.
Q.5. Consider a system consisting of m resources of the same type being shared by n processes. A
process can request or release only one resource at a time. Show that the system is deadlock free if
the following two conditions hold:
1. The maximum need of each process is between 1 resource and m resources.
2. The sum of all maximum needs is less than m + n.
Programming Questions [50 marks]:
This programming assignment is a slight extension to the classical problem of synchronization – the
Dining Philosophers problem. You are going to solve it using the Monitor synchronization construct
built on top of Java’s synchronization primitives. The extension here refers to the fact that
sometimes philosophers would like to talk, but only one (any) philosopher can be talking at a time
COMP 346 – Winter 2012
Assignment 3 – page 2 of 2
while he/she is not eating. Note that this question is not related to the Q.4 in theory questions in the
previous page.
The source code for this assignment is supplied separately in a zip file. You will need to fill in the
missing code. You have to answer the following questions as part of this assignment:
Note: All code written by you should be well commented. This will be part of the grading scheme.
QP. 1 The Philosopher Class
Complete implementation of the Philosopher class, i.e., all its methods according to the comments in the
code. Specifically, eat(), think(), talk(), and run() methods have to be implemented entirely. Some hints are
provided within the code. Your added code must be well commented.
QP.2. The Monitor
Implement the Monitor class for the problem. Make sure that it is correct, both deadlock- and starvation-
free (Note: this is an important criterion for the grading scheme), uses Java’s synchronization primitives
such as wait() and notifyAll(), and does not use any Java Semaphore objects. Implement the four methods of
the Monitor class; specifically, pickUp(), putDown(), requestTalk(), and endTalk(). Add as many member
variables and methods to meet the following specifications:
1. A philosopher is allowed to pick up the chopsticks if they are both available. It has to be atomic so that no
deadlock is possible. Refer to the related discussion in your textbook.
2. If a given philosopher has decided to make a statement, he/she can only do so if no one else is talking at
the moment. The philosopher wishing to make the statement first makes a request to talk; and has to wait
if someone else is talking. When talking is finished then others are notifies by endTalk.
QP.3. Variable Number of Philosophers
Make the application accept the number of philosophers as a command line argument, and spawn exactly that
number of philosophers instead of the default specified in code. If there is no command line argument, the
given default should be used. If the argument is not a positive integer, report an error to the user and print the
usage information as in the example below:
% java DiningPhilosophers -7.a
“-7.a” is not a positive decimal integer
Usage: java DiningPhilosophers [NUMBER_OF_PHILOSOPHERS]
%
Use Integer.parseInt() method to extract an int value from a character string. Test your implementation with a
varied number of philosophers. Submit your output from “make regression” (refer to Makefile).
Deliverables: Submit your answers to theory questions in PDF or text formats only. For the
programming questions, you must submit the modified source files together with the outputs of
executions and answers to the questions. The solutions to theory and programming questions should
be submitted in two separate archived files (e.g., .zip) via EAS.
C346_PA3_W12/src/common/BaseThread.java
C346_PA3_W12/src/common/BaseThread.java
package
common
;
import
java
.
util
.
Random
;
/**
* Class BaseThread
* Simply one customized base class for many of our own threads
*
* An attempt to maintain an automatic unique TID (thread ID)
* among all the derivatives and allow setting your own if needed.
* Plus some methods for the sync exercises.
*
* $Revision: 1.2 $
* $Last Revision Date: 2010/10/24 $
*
*
@author
Serguei A. Mokhov, mokhov
@cs
.concordia.ca
*/
public
class
BaseThread
extends
Thread
{
/*
* ————
* Data members
* ————
*/
/**
* Preserves value across all instances
*/
public
static
int
siNextTID
=
1
;
/**
* Our Thread ID
*/
protected
int
iTID
;
/**
* TID of a thread to proceed to the phase II
*/
private
static
int
siTurn
=
1
;
/*
* ————
* Constructors
* ————
*/
/**
* Default
*/
public
BaseThread
()
{
setTID
();
}
/**
* Assigns name to the thread and places it to the specified group
*
*
@param
poGroup ThreadGroup to add this thread to
*
@param
pstrName A string indicating human-readable thread’s name
*/
public
BaseThread
(
ThreadGroup
poGroup
,
String
pstrName
)
{
super
(
poGroup
,
pstrName
);
setTID
();
}
/**
* Sets user-specified TID
*/
public
BaseThread
(
final
int
piTID
)
{
this
.
iTID
=
piTID
;
}
/**
* Retrieves our TID
*
@return
TID, integer
*/
public
final
int
getTID
()
{
return
this
.
iTID
;
}
/**
* Sets internal TID and updates next TID on contruction time, so it’s private.
*/
private
final
void
setTID
()
{
this
.
iTID
=
siNextTID
++
;
}
/**
* Just a make up for the PHASE I to make it somewhat tangeable.
* Must be atomic.
*/
protected
synchronized
void
phase1
()
{
System
.
out
.
println
(
this
.
getClass
().
getName
()
+
” thread [TID=”
+
this
.
iTID
+
“] starts PHASE I.”
);
System
.
out
.
println
(
“Some stats info in the PHASE I:\n”
+
” iTID = ”
+
this
.
iTID
+
“, siNextTID = ”
+
siNextTID
+
“, siTurn = ”
+
siTurn
+
“.\n Their \”checksum\”: ”
+
(
siNextTID
*
100
+
this
.
iTID
*
10
+
siTurn
)
);
System
.
out
.
println
(
this
.
getClass
().
getName
()
+
” thread [TID=”
+
this
.
iTID
+
“] finishes PHASE I.”
);
}
/**
* Just a make up for the PHASE II to make it somewhat tangeable.
* Must be atomic.
*/
protected
synchronized
void
phase2
()
{
System
.
out
.
println
(
this
.
getClass
().
getName
()
+
” thread [TID=”
+
this
.
iTID
+
“] starts PHASE II.”
);
System
.
out
.
println
(
“Some stats info in the PHASE II:\n”
+
” iTID = ”
+
this
.
iTID
+
“, siNextTID = ”
+
siNextTID
+
“, siTurn = ”
+
siTurn
+
“.\n Their \”checksum\”: ”
+
(
siNextTID
*
100
+
this
.
iTID
*
10
+
siTurn
)
);
System
.
out
.
println
(
this
.
getClass
().
getName
()
+
” thread [TID=”
+
this
.
iTID
+
“] finishes PHASE II.”
);
}
/**
* Test-and-Set for the iTurn variable.
*
* Use to proceed to the phase II in the correct order.
* Must be atomic.
*
*
@param
pcIncreasingOrder true if TIDs are in increasing order; false otherwise
*
*
@return
Returns true if if the TID of currently running thread matches the turn, ‘false’ otherwise
*/
public
synchronized
boolean
turnTestAndSet
(
boolean
pcIncreasingOrder
)
{
// test
if
(
siTurn
==
this
.
iTID
)
{
// set siTurn = siTurn +/- 1;
if
(
pcIncreasingOrder
==
true
)
siTurn
++
;
else
siTurn
—
;
return
true
;
}
return
false
;
}
/**
* Always assumes the increasing order
*/
public
synchronized
boolean
turnTestAndSet
()
{
return
turnTestAndSet
(
true
);
}
/**
* Allows setting arbitratu turn value. Should be set only before
* the threads are started
*/
public
static
void
setInitialTurn
(
int
piTurn
)
{
siTurn
=
piTurn
;
}
/**
* Default ascending order
*/
public
static
void
setInitialTurnAscending
()
{
setInitialTurn
(
1
);
}
/**
* Descending order
*/
public
static
void
setInitialTurnDescending
()
{
setInitialTurn
(
siNextTID
–
1
);
}
/**
* Calls yield() several (4-40, pseudorandomly) times.
* Next to useless, but helps to mix up the execution of phases.
* Must NOT be atomic.
*/
public
void
randomYield
()
{
// Generate from 5 to 40 yield()’s pseudorandomly
int
iNumYields
=
(
int
)((
new
Random
()).
nextFloat
()
*
35
)
+
5
;
for
(
int
i
=
0
;
i
<
iNumYields
;
i
++
)
yield
();
}
}
// EOF
C346_PA3_W12/src/DiningPhilosophers.java
C346_PA3_W12/src/DiningPhilosophers.java
/**
* Class DiningPhilosophers
* The main starter.
*
*
@author
Serguei A. Mokhov, mokhov
@cs
.concordia.ca
*/
public
class
DiningPhilosophers
{
/*
* ------------
* Data members
* ------------
*/
/**
* This default may be overridden from the command line
*/
public
static
final
int
DEFAULT_NUMBER_OF_PHILOSOPHERS
=
4
;
/**
* Dining "iterations" per philosopher thread
* while they are socializing there
*/
public
static
final
int
DINING_STEPS
=
10
;
/**
* Our shared monitor for the philosphers to consult
*/
public
static
Monitor
soMonitor
=
null
;
/*
* -------
* Methods
* -------
*/
/**
* Main system starts up right here
*/
public
static
void
main
(
String
[]
argv
)
{
try
{
/*
* TODO:
* Should be settable from the command line
* or the default if no arguments supplied.
*/
int
iPhilosophers
=
DEFAULT_NUMBER_OF_PHILOSOPHERS
;
// Make the monitor aware of how many philosophers there are
soMonitor
=
new
Monitor
(
iPhilosophers
);
// Space for all the philosophers
Philosopher
aoPhilosophers
[]
=
new
Philosopher
[
iPhilosophers
];
// Let 'em sit down
for
(
int
j
=
0
;
j
<
iPhilosophers
;
j
++
)
{
aoPhilosophers
[
j
]
=
new
Philosopher
();
aoPhilosophers
[
j
].
start
();
}
System
.
out
.
println
(
iPhilosophers
+
" philosopher(s) came in for a dinner."
);
// Main waits for all its children to die...
// I mean, philosophers to finish their dinner.
for
(
int
j
=
0
;
j
<
iPhilosophers
;
j
++
)
aoPhilosophers
[
j
].
join
();
System
.
out
.
println
(
"All philosophers have left. System terminates normally."
);
}
catch
(
InterruptedException
e
)
{
System
.
err
.
println
(
"main():"
);
reportException
(
e
);
System
.
exit
(
1
);
}
}
// main()
/**
* Outputs exception information to STDERR
*
@param
poException Exception object to dump to STDERR
*/
public
static
void
reportException
(
Exception
poException
)
{
System
.
err
.
println
(
"Caught exception : "
+
poException
.
getClass
().
getName
());
System
.
err
.
println
(
"Message : "
+
poException
.
getMessage
());
System
.
err
.
println
(
"Stack Trace : "
);
poException
.
printStackTrace
(
System
.
err
);
}
}
// EOF
C346_PA3_W12/src/Makefile
# Just a makefile to save some typing 🙂
# Serguei A. Mokhov, mokhov@cs.concordia.ca
# PA3
# Use gmake.
JAVAC=javac
JFLAGS=-g
JVM=java
EXE=DiningPhilosophers
ASMTDIRS := . common
# Lists of all *.java and *.class files
JAVAFILES := $(ASMTDIRS:%=%/*.java)
CLASSES := $(ASMTDIRS:%=%/*.class)
all: $(EXE).class
@echo "Dining Philosophers Application has been built."
$(EXE).class: $(JAVAFILES)
$(JAVAC) $(JFLAGS) $(EXE).java
run: all
$(JVM) $(EXE)
regression: all
@for arg in 3 4 5; do $(JVM) $(EXE) $$arg; done
clean:
rm -f $(CLASSES) #* *~
# EOF
C346_PA3_W12/src/Monitor.java
C346_PA3_W12/src/Monitor.java
/**
* Class Monitor
* To synchronize dining philosophers.
*
*
@author
Serguei A. Mokhov, mokhov
@cs
.concordia.ca
*/
public
class
Monitor
{
/*
* ------------
* Data members
* ------------
*/
/**
* Constructor
*/
public
Monitor
(
int
piNumberOfPhilosophers
)
{
// TODO: set appropriate number of chopsticks based on the # of philosophers
}
/*
* -------------------------------
* User-defined monitor procedures
* -------------------------------
*/
/**
* Grants request (returns) to eat when both chopsticks/forks are available.
* Else forces the philosopher to wait()
*/
public
synchronized
void
pickUp
(
final
int
piTID
)
{
// ...
}
/**
* When a given philosopher's done eating, they put the chopstiks/forks down
* and let others know they are available.
*/
public
synchronized
void
putDown
(
final
int
piTID
)
{
// ...
}
/**
* Only one philopher at a time is allowed to philosophy
* (while she is not eating).
*/
public
synchronized
void
requestTalk
()
{
// ...
}
/**
* When one philosopher is done talking stuff, others
* can feel free to start talking.
*/
public
synchronized
void
endTalk
()
{
// ...
}
}
// EOF
C346_PA3_W12/src/Philosopher.java
C346_PA3_W12/src/Philosopher.java
import
common
.
BaseThread
;
/**
* Class Philosopher.
* Outlines main subrutines of our virtual philosopher.
*
*
@author
Serguei A. Mokhov, mokhov
@cs
.concordia.ca
*/
public
class
Philosopher
extends
BaseThread
{
/**
* Max time an action can take (in milliseconds)
*/
public
static
final
long
TIME_TO_WASTE
=
1000
;
/**
* The act of eating.
* - Print the fact that a given phil (their TID) has started eating.
* - Then sleep() for a random interval.
* - The print that they are done eating.
*/
public
void
eat
()
{
try
{
// ...
sleep
((
long
)(
Math
.
random
()
*
TIME_TO_WASTE
));
// ...
}
catch
(
InterruptedException
e
)
{
System
.
err
.
println
(
"Philosopher.eat():"
);
DiningPhilosophers
.
reportException
(
e
);
System
.
exit
(
1
);
}
}
/**
* The act of thinking.
* - Print the fact that a given phil (their TID) has started thinking.
* - Then sleep() for a random interval.
* - The print that they are done thinking.
*/
public
void
think
()
{
// ...
}
/**
* The act of talking.
* - Print the fact that a given phil (their TID) has started talking.
* - Say something brilliant at random
* - The print that they are done talking.
*/
public
void
talk
()
{
// ...
saySomething
();
// ...
}
/**
* No, this is not the act of running, just the overridden Thread.run()
*/
public
void
run
()
{
for
(
int
i
=
0
;
i
<
DiningPhilosophers
.
DINING_STEPS
;
i
++
)
{
DiningPhilosophers
.
soMonitor
.
pickUp
(
getTID
());
eat
();
DiningPhilosophers
.
soMonitor
.
putDown
(
getTID
());
think
();
/*
* TODO:
* A decision is made at random whether this particular
* philosopher is about to say something terribly useful.
*/
if
(
true
==
false
)
{
// Some monitor ops down here...
talk
();
// ...
}
}
}
// run()
/**
* Prints out a phrase from the array of phrases at random.
* Feel free to add your own phrases.
*/
public
void
saySomething
()
{
String
[]
astrPhrases
=
{
"Eh, it's not easy to be a philosopher: eat, think, talk, eat..."
,
"You know, true is false and false is true if you think of it"
,
"2 + 2 = 5 for extremely large values of 2..."
,
"If thee cannot speak, thee must be silent"
,
"My number is "
+
getTID
()
+
""
};
System
.
out
.
println
(
"Philosopher "
+
getTID
()
+
" says: "
+
astrPhrases
[(
int
)(
Math
.
random
()
*
astrPhrases
.
length
)]
);
}
}
// EOF
Essay Writing Service Features
Our Experience
No matter how complex your assignment is, we can find the right professional for your specific task. Achiever Papers is an essay writing company that hires only the smartest minds to help you with your projects. Our expertise allows us to provide students with high-quality academic writing, editing & proofreading services.
Free Features
Free revision policy
$10Free bibliography & reference
$8Free title page
$8Free formatting
$8How Our Dissertation Writing Service Works
First, you will need to complete an order form. It's not difficult but, if anything is unclear, you may always chat with us so that we can guide you through it. On the order form, you will need to include some basic information concerning your order: subject, topic, number of pages, etc. We also encourage our clients to upload any relevant information or sources that will help.
Complete the order form
Once we have all the information and instructions that we need, we select the most suitable writer for your assignment. While everything seems to be clear, the writer, who has complete knowledge of the subject, may need clarification from you. It is at that point that you would receive a call or email from us.
Writer’s assignment
As soon as the writer has finished, it will be delivered both to the website and to your email address so that you will not miss it. If your deadline is close at hand, we will place a call to you to make sure that you receive the paper on time.
Completing the order and download