by: George North
439-68-5643
Principles of Operating Systems I
CSCI 4401
Fall 1995
Instructor: M. Rasit Eskicioglu
TABLE OF CONTENTS
What I have learned 3
Problem Description 3
Design using Ada tasking 4
Implementation Subtleties 5
From 1 to 5 Lawyer tasks 5
Judge gains control at start of execution 5
Termination without deadlock 6
Source Code 7
Testing 16
Program Description
What I have learned :
Design using concurrency has given me new insights into the problems that
Computer Science is expected to solve. The concurrency abstraction allows
for simplicity in design. And a concurrent implementation will in many instances
yield a system that out performs a sequential implementation.
Many system specifications lend themselves to solutions that involve concurrent
operations. Ada provides the designer and programmer with many tools that
allow for concurrent implementations. The double benefit of simplicity of
design and higher performance as compared to traditional sequential implementations
leads to serious consideration in applying concurrency to the problem domain.
Any implementation of a system design requires great care and extensive
testing on the part of designers and programmers. This is of even greater
concern whit concurrent systems. The design, and the code it produces, is
very elegant. It can be easy to document and to read. But interaction between
concurrent tasks is subtle. It is difficult to foresee all possibilities.
Extensive testing is important.
Problem : You have been hired by a superior court judge
to help synchronize the cross-examination of the witnesses in a trial. The
Judge wants to take a break if no one wants to ask questions; if there are
lawyers (both from the defense and the prosecution) around who want to ask
question, they MUST synchronize with each other and with the witness so
that (i) only one person is speaking at a time, (ii) each question posed
by a lawyer is answered by the witness, and, (iii) no lawyer asks another
question before the witness is done answering the previous question.
Design - using Ada tasking :
There are three concurrent objects in this design, Judge, Lawyer, Witness.
The Judge is the controlling object. It is the responsibility of the Judge
to: (i) insure that only one Lawyer at a time will ask a question, and (ii)
that the Witness will answer each Lawyer's question before another question
is asked. These requirements are enforced using Ada's accept statement.
Essentially, the Judge sits in a loop containing four accept statements
in order as follows: Question_Start, Answer_Start, Answer_Done,
Question_Done . Each Lawyer task is in a loop which: (i) waits
for the Judge to accept Question_Start, (ii) waits for the Witness to accept
Question, and (iii) then waits for the Judge to accept Question_Done. The
Witness is in a loop which: (i) waits for the Judge to accept Answer_Start,
(ii) accepts a question from a Lawyer, and (iii) then waits for the Judge
to accept Answer_Done.
System requirements are enforced by the order in which the Judge task accepts
messages from Lawyers and the Witness. Subtleties of the design are: (i)
how to allow for from 1 to 5 lawyer tasks, (ii) how to insure that the Judge
task gains control at start of execution, and (iii) how to insure that all
tasks terminate so as to prevent deadlock.
Implementation Subtleties :
At launch time, all tasks become active, the Judge, a Witness, and five
Lawyers. Normal termination will occur will all of these tasks have themselves
terminated. Although five Lawyer tasks are active, it is not necessarily
true that all five will ask questions.
(i) How to allow for from 1 to 5 lawyer tasks.
A task type is used to define Lawyer, and the to allocate an array of Lawyer
tasks. This means that all five lawyer tasks are active at launch. An accept
statement (Lawyer_enters_Courtroom) is used to control execution of Lawyer
tasks. At launch the Bailiff (a procedure named Good_Morning) uses standard
input to ask user for the number of Lawyers, from 1 to 5. A for loop is
then used to start the number of Lawyer tasks needed. In each Lawyer task,
a select statement is used to terminate unneeded tasks.
select
-- Lawyer waits until he can enter the courtroom
or
-- task terminates
end select;
loop while -- there are Lawyers still questioning
accept Question_Start;
accept Answer_Start;
accept Answer_Done;
accept Question_Done;
end loop;
loop while lawyers are still asking questions
-- do some stuff
end loop;
select
-- Lawyer waits until he can enter the courtroom
-- or task terminates
accept Lawyer_enters_Courtroom ...
-- Invariant: a Lawyer will ask a maximum # of questions
loop
-- wait, Judge will tell me when its my turn
-- ask the Witness a question
-- count my questions
-- if this is my last question then exit,
-- else let the Judge know I'm done
end loop;
-- Assertion: loop terminates after lawyer has asked
-- the maximum # of questions. After each
-- question, a counter is incremented by 1,
-- loops continues until
-- count > Max_Num_of_Questions.
-- count me as exited from court
-- announce my exit
-- let the judge know I'm done
or
-- terminate unused lawyer task
end select;
Source Code --
-- Program Assignment # 1
-- Ada Tasking
-- Due: October 28, 1995
--
-- by: George North
-- 439-68-5643
with Text_IO; use Text_IO;
with My_Int_IO; use My_Int_IO;
-- ======================================================================
-- Program: Testify
-- Problem:
--
-- You have been hired by a superior court judge to help
-- synchronize the cross-examination of the witnesses in a trial. The
-- Judge wants to take a break if no one wants to ask questions; if
-- there are lawyers (both from the defense and the prosecution) around
-- who want to ask question, they MUST synchronize with each other
-- and with the witness so that (i) only one person is speaking at a time
-- (ii) each question posed by a lawyer is answered by the witness, and
-- (iii) no lawyer asks another question before the witness is done
-- answering the previous question.
-- ======================================================================
-- Procedure: Testify
-- Functionality: driver procedure for program: Testify
-- Pre-conditions: Standard input device available
-- Post-conditions: Standard output device available
procedure Testify is
-- ===================================================================
-- some global variables
-- ===================================================================
-- assume that there are a maximum of 5 lawyers at a time, and Judge
-- asks for the number of lawyers available when the court starts
-- its daily session
Max_Num_of_Lawyers : constant integer := 5;
subtype Num_of_Lawyers_Type is integer range 0 .. Max_Num_of_Lawyers;
Num_of_Lawyers : Num_of_Lawyers_Type;
Lawyers_Exited_Court : Num_of_Lawyers_Type := 0;
-- ===================================================================
-- needed Task declarations
-- ===================================================================
-- Task : Judge
-- Functionality: Provide a Judge task to control multiple lawyers
-- cross-examining a witness
-- Pre-conditions: Exists both Witness and Lawyer tasks
-- Post-conditions: none
task Judge is
entry Takes_the_Bench;
entry Question_Start;
entry Answer_Start;
entry Answer_Done;
entry Question_Done;
end Judge;
-- ===================================================================
-- Task : Lawyer_Task
-- Functionality: Provide an array of Lawyer tasks, up to
-- Max_Num_of_Lawyers.
-- Pre-conditions: Exists both Judge and Witness tasks
-- Post-conditions: none
task type Lawyer_Task is
entry Lawyer_enters_Courtroom( j : in Num_of_Lawyers_Type );
entry Lawyer_leaves_Courtroom( j : in Num_of_Lawyers_Type );
end Lawyer_Task;
Lawyer : array( Num_of_Lawyers_Type ) of Lawyer_Task;
-- ===================================================================
-- Task : Witness
-- Functionality: Provide a Witness to answer Lawyer questions
-- Pre-conditions: Exists both Judge and Lawyer tasks
-- Post-conditions: none
task Witness is
entry Question( i : in Num_of_Lawyers_Type );
end Witness;
-- ===================================================================
-- body of tasks
-- ===================================================================
task body Judge is
-- Procedure: Call_Court_to_Order
-- Functionality: Print to standard output
-- Pre-conditions: none
-- Post-conditions: none
procedure Call_Court_to_Order is
begin -- Call_Court_to_Order
put( "All rise!" );
New_Line;
put( "CSCI4401, court now in session, Judge George North presiding." );
New_Line;
New_Line;
put( "Would the Witness now take the stand." );
New_Line;
put( "Lawyers, you may proceed ... one at a time please." );
New_Line;
New_Line;
end Call_Court_to_Order;
-- for testing only, used to show which lawyer tasks are still active
procedure active_Tasks is
begin
Put( "Active Lawyers: ");
for k in 1 .. Num_of_Lawyers loop
if Lawyer(k)'callable then
My_Int_IO.put( k, 1 );
put( " " );
end if;
end loop;
put( " - " );
end active_Tasks;
begin -- Judge
-- wait until the bailiff calls court into session
-- accept questions as long as Lawyers remain in court
-- then, adjourn court
accept Takes_the_Bench;
Call_Court_to_Order;
-- Invariant: allow lawyers to take turns asking questions
while Num_of_Lawyers > Lawyers_Exited_Court loop
-- active_Tasks; -- testing only
accept Question_Start;
accept Answer_Start;
accept Answer_Done;
accept Question_Done;
end loop;
-- Assertion: loop terminates when there are no lawyers left to
-- ask questions. Since each lawyer will ask only a
-- finite number of questions the number of lawyers
-- asking questions will eventually reduce to zero.
-- each time a Lawyer asks his last question,
-- Lawyers_Exited_Court is increased by 1. Eventually
-- Lawyers_Exited_Court becomes > Num_of_Lawyers and
-- this loop terminates.
-- this court session is finished
New_Line;
put( "CSCI4401, court now adjourned." );
New_Line;
--
end Judge;
-- ===================================================================
task body Lawyer_Task is
for_Lawyer : Num_of_Lawyers_Type;
-- allow a lawyer to ask a maximum of 15 questions each per day
Max_Num_of_Questions : constant integer := 15;
subtype Num_of_Questions_Type is integer range 0 .. Max_Num_of_Questions;
Questions_Asked : Num_of_Questions_Type := 0;
-- Procedure: Announce_Lawyer_in_Court
-- Functionality: Print to standard output
-- Pre-conditions: none
-- Post-conditions: none
procedure Announce_Lawyer_in_Court is
begin -- Announce_Lawyer_in_Court
put ( "... now entering the courtroom ... Lawyer # " );
My_Int_IO.put( for_Lawyer, 1 );
New_Line;
New_Line;
end Announce_Lawyer_in_Court;
-- Procedure: Announce_Lawyer_out_of_Court
-- Functionality: Print to standard output
-- Pre-conditions: none
-- Post-conditions: none
procedure Announce_Lawyer_out_of_Court is
begin -- Announce_Lawyer_out_of_Court
put ( "... now leaving the courtroom ... Lawyer # " );
My_Int_IO.put( for_Lawyer, 1 );
New_Line;
New_Line;
end Announce_Lawyer_out_of_Court;
begin -- Lawyer_Task
select
-- Lawyer waits until he can enter the courtroom
-- or task terminates
accept Lawyer_enters_Courtroom( j : in Num_of_Lawyers_Type )
do for_Lawyer := j;
end Lawyer_enters_Courtroom;
Announce_Lawyer_in_Court;
-- Invariant: a Lawyer will ask a maximum # of questions
loop
-- wait, Judge will tell me when its my turn
-- ask the Witness a question
-- count my questions
Judge.Question_Start;
Witness.Question( for_Lawyer );
Questions_Asked := Questions_Asked + 1;
-- if this is my last question then exit,
-- else let the Judge know I'm done
if Questions_Asked = Max_Num_of_Questions then
exit;
end if;
Judge.Question_Done;
end loop;
-- Assertion: loop terminates after lawyer has asked
-- the maximum # of questions. After each
-- question, a counter is incremented by 1,
-- loops continues until
-- count > Max_Num_of_Questions.
-- count me as exited from court
-- announce my exit
-- let the judge know I'm done
Lawyers_Exited_Court := Lawyers_Exited_Court + 1;
Announce_Lawyer_out_of_Court;
Judge.Question_Done;
or
-- terminate unused lawyer task
terminate;
end select;
end Lawyer_Task;
-- ===================================================================
task body Witness is
from_Lawyer : Num_of_Lawyers_Type;
-- Procedure: Answer_a_Question
-- Functionality: Print to standard output
-- Pre-conditions: none
-- Post-conditions: none
procedure Answer_a_Question is
begin -- Answer_a_Question
for k in 1 .. 30000 loop null; end loop;
put( "I've answered lawyer # " );
My_Int_IO.put( from_Lawyer, 1 );
put( "'s question." );
New_Line;
end Answer_a_Question;
begin -- Witness
-- Invariant: Witness answers questions
while Num_of_Lawyers > Lawyers_Exited_Court loop
-- the Judge will let me know when to answer a question
-- listen to the question, and remember which Lawyer ask it
-- think for a while, answer the question
-- let the Judge know I;m finished
Judge.Answer_Start;
accept Question( i : in Num_of_Lawyers_Type )
do from_Lawyer := i;
end Question;
Answer_a_Question;
Judge.Answer_Done;
end loop;
-- Assertion: Loop terminates when there are no lawyers
-- left in court. Termination depends on
-- each Lawyer task to terminate.
end Witness;
-- ===================================================================
-- needed Procedures
-- ===================================================================
-- Procedure: Good_Morning
-- Functionality: welcome, ask for number of Lawyers
-- Pre-conditions: uses standard input to ask for # of Lawyers
-- Post-conditions: valid integer range 0 to Num_of_Lawyers_Type
procedure Good_Morning is
begin -- Good_Morning
-- Invariant: from standard input, get the # of Lawyers for today
-- check for errors
loop
begin
put( "Good Morning. " );
put( "How many lawyers will be in court today (1 to 5)? " );
get( Item => Num_of_Lawyers );
New_Line;
exit;
exception -- trap some invalid data ... needs more work
when Others =>
New_Line;
put ( "Not a valid choice." );
New_Line;
put ( "Enter a number between 1 and " );
My_Int_IO.put ( Max_Num_of_Lawyers, 1 );
put ( ", or type 0 to EXIT" );
New_Line;
put ( "Please try again." );
New_Line;
New_Line;
end;
end loop;
-- Assertion: loop will terminate upon entry of valid number for
-- to use for Max_Num_of Lawyers. Zero is a VALID #.
end Good_Morning;
-- ======================================================================
body of main procedure
-- ======================================================================
begin -- Testify
--
-- Bailiff welcomes everyone, call court into session
Good_Morning;
--
-- Lawyer(s) enter the courtroom;
for k in 1 .. Num_of_Lawyers loop
Lawyer(k).Lawyer_enters_Courtroom(k);
end loop;
-- the judge takes over from here ...
-- judge calls court room to order, starts questioning of witness
-- conducts court until all lawyers have asked all questions
Judge.Takes_the_Bench;
end Testify;
-- ======================================================================
Testing --GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:12:48 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? -1 Not a valid choice. Enter a number between 1 and 5, or type 0 to EXIT Please try again. Good Morning. How many lawyers will be in court today (1 to 5)? 6 Not a valid choice. Enter a number between 1 and 5, or type 0 to EXIT Please try again. Good Morning. How many lawyers will be in court today (1 to 5)? 10 Not a valid choice. Enter a number between 1 and 5, or type 0 to EXIT Please try again. Good Morning. How many lawyers will be in court today (1 to 5)? 0 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. CSCI4401, court now adjourned.2. Case for 1 Lawyer enters courtroom ...
GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:15:52 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? 1 ... now entering the courtroom ... Lawyer # 1 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. I've answered lawyer # 1's question. ... now leaving the courtroom ... Lawyer # 1 CSCI4401, court now adjourned.3. Case for 2 Lawyers enter courtroom ...
GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:18:21 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? 2 ... now entering the courtroom ... Lawyer # 1 ... now entering the courtroom ... Lawyer # 2 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 1's question. ... now leaving the courtroom ... Lawyer # 1 I've answered lawyer # 2's question. ... now leaving the courtroom ... Lawyer # 2 CSCI4401, court now adjourned.4. Case for 3 Lawyers enter courtroom ...
GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:22:44 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? 3 ... now entering the courtroom ... Lawyer # 1 ... now entering the courtroom ... Lawyer # 2 ... now entering the courtroom ... Lawyer # 3 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. . . . I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. ... now leaving the courtroom ... Lawyer # 1 I've answered lawyer # 2's question. ... now leaving the courtroom ... Lawyer # 2 I've answered lawyer # 3's question. ... now leaving the courtroom ... Lawyer # 3 CSCI4401, court now adjourned.5. Case for 4 Lawyers enter courtroom ...
GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:25:58 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? 4 ... now entering the courtroom ... Lawyer # 1 ... now entering the courtroom ... Lawyer # 2 ... now entering the courtroom ... Lawyer # 3 ... now entering the courtroom ... Lawyer # 4 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. . . . I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. ... now leaving the courtroom ... Lawyer # 1 I've answered lawyer # 2's question. ... now leaving the courtroom ... Lawyer # 2 I've answered lawyer # 3's question. ... now leaving the courtroom ... Lawyer # 3 I've answered lawyer # 4's question. ... now leaving the courtroom ... Lawyer # 4 CSCI4401, court now adjourned.6. Case for 5 Lawyers enter courtroom ...
GWU/NYU Adaexec v1.1 Macintosh System 7.0 Sun 8 Oct 1995 16:27:48 Console Output from "TESTIFY" Good Morning. How many lawyers will be in court today (1 to 5)? 5 ... now entering the courtroom ... Lawyer # 1 ... now entering the courtroom ... Lawyer # 2 ... now entering the courtroom ... Lawyer # 3 ... now entering the courtroom ... Lawyer # 4 ... now entering the courtroom ... Lawyer # 5 All rise! CSCI4401, court now in session, Judge George North presiding. Would the Witness now take the stand. Lawyers, you may proceed ... one at a time please. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. I've answered lawyer # 2's question. I've answered lawyer # 3's question. I've answered lawyer # 4's question. I've answered lawyer # 5's question. I've answered lawyer # 1's question. ... now leaving the courtroom ... Lawyer # 1 I've answered lawyer # 2's question. ... now leaving the courtroom ... Lawyer # 2 I've answered lawyer # 3's question. ... now leaving the courtroom ... Lawyer # 3 I've answered lawyer # 4's question. ... now leaving the courtroom ... Lawyer # 4 I've answered lawyer # 5's question. ... now leaving the courtroom ... Lawyer # 5 CSCI4401, court now adjourned.