# Help with Operating Systems Theory (CPU Scheduling, and Java Synchronization using monitors)

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
(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

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

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.

package
common
;

import
java
.
util
.
Random
;

/**

* 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

extends

{

/*

* ————

* Data members

* ————

*/

/**

* Preserves value across all instances

*/

public

static

int
siNextTID
=

1
;

/**

*/

protected

int
iTID
;

/**

* TID of a thread to proceed to the phase II

*/

private

static

int
siTurn
=

1
;

/*

* ————

* Constructors

* ————

*/

/**

* Default

*/

public

()

{

setTID
();

}

/**

* Assigns name to the thread and places it to the specified group

*

*
@param

*
@param

*/

public

(
poGroup
,

String
pstrName
)

{

super
(
poGroup
,
pstrName
);

setTID
();

}

/**

* Sets user-specified TID

*/

public

(
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
()

+

+

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
()

+

+

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
()

+

+

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
()

+

+

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

*/

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

Pages (275 words)
Standard price: \$0.00
Client Reviews
4.9
Sitejabber
4.6
Trustpilot
4.8
Our Guarantees
100% Confidentiality
Information about customers is confidential and never disclosed to third parties.
Original Writing
We complete all papers from scratch. You can get a plagiarism report.
Timely Delivery
No missed deadlines – 97% of assignments are completed in time.
Money Back