📄 project1.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<TITLE>OSF Project 1: The Banker's Algorithm</TITLE>
</HEAD>
<BODY background="../../text2.jpg">
<h2>
<CENTER>OSF Project 1:</center>
<center>The Banker's Algorithm</CENTER>
</h2>
<H3>General</H3>
<p> This first project has the following characteristics compared to the remaining three:
<ul>
<li> It involves the least amount of actual coding. All you have
to do is implement <i>one method</i> in <i>one C++ source
file</i>. Everything else is provided.
If you use over 100 lines of code for your implementation,
you probably worked too hard.
<li> It may involve the biggest learning curve if you're
not yet comfortable with a C++ development environment.
I've kept the size small for this reason.
<li> It's end result (a "Banker" class) will be reused as-is in Projects
3 and 4.
</ul>
Everything you need to know is on and around pages 222 and 223 of your Silberschatz book.
But let me provide a little practical background terminology, courtesy of
<a href="http://www.rh.edu/~davec">Dave Clarke</a>...
<H3>Terminology: Deadlock</H3>
Consider the following resolution made in the last century by a town council:
<OL> <LI>Resolved, that this town shall build a new jail.
<LI>Resolved, that the new jail shall be built from material from the old jail.
<LI>Resolved also, that the old jail shall be used until the new jail is finished.
</OL>
Bummer! Each jail requires the same resource (material) at the same time.
It's the classic "Catch 22" scenario.
<p>In operating systems terminology, we'd say the the over-committment of resources
will lead to Deadlock, because, as soon as some of the material is taken away from the
old jail, neither jail will function correctly.
<p> Deadlock is always a possibility when a resource is shared by more than one process.
One of the approaches that may be taken to combat this problem is known as
<i>deadlock avoidance</i>. The major player in this technique is the
<i>Banker's Algorithm</i>. You will be creating your own version
of this algorithm in C++.
<H3>Downloads</H3>
There are three source files required to do this project:
<ul>
<li> Banker.h
<li> Banker.cpp
<li> Project.cpp
</ul>
Subsequent projects will have many more files. So you may want to get in the habit
of downloading everything required via <a href="project1.zip"> zip file</a>.
<h3>
<b><font color="green">Banker</font></b>
</h3>
<p><a href="Banker.h">Banker.h</a>
<br><a href="Banker.cpp">Banker.cpp</a>
<p>
The Banker header file has the following interesting features:
<ul>
<li> Inclusion of < map >, which is the Standard Template Library map template.
This allows us to map Process ID numbers (integral PIDs) to the current
state of resources associated with them.
<li> Definition of four important types of exceptions that you'll need to
throw if unsafe conditions arise. These are:
<ul>
<li> BankerUnsafePidException. A request has been made for a
PID that doesn't exist,
<li> BankerUnsafeContractException. A valid PID
has made a request that overdraws on the
maximum resources for which it contracted.
<li> BankerUnsafeTotalException. An otherwise-OK
request can't be granted right now because there
aren't enough system resources.
<li> BankerUnsafeCommittedException. An otherwise-OK
request can't be granted. Even though the
system resources are currently available, they
are committed. Release of the resources right now
could lead to deadlock depending on the order in
which other PIDs make subsequent requests.
</ul>
<li> The definition of a structure called Resources, which is just a handy
way of grouping three integers. We will use these integers to count
resources. In our case, we'll play with: Files on a file system,
Pages of main memory, and Mutices (semaphores). As far as what you're
required to implement is concerned, these "resources" might as well
be "apples, oranges, and bananas." The Banker's algorithm could be
applied to any arbitrary set of resources.
<li> typdef for ResourcesMap. This is where we actually start using STL
in order to map Processes to the resources associated with them.
<li> Banker class definition.
<ul>
<li> Instance Variables. (For our purposes, there will never
be more than one instance of Banker).
<ul>
<li> RMax remembers how many Files, Pages,
and Mutices are in the system. This
is assigned during construction of
Banker instance, and is immutable.
(i.e., the Max values never change
after they're initially assigned.)
<li> RInUse keeps track of how many Files,
Pages, and Mutices are currently in
use by all processes. This must
be less than or equal to RMax.
<li> RMapMax is an instance of ResourcesMap.
This is where we use STL to remember
the maximum values of Files, Pages,
and Mutices required by each PID.
Values are assigned during openAccount()
method and are thereafter immutable.
So for your purposes (since you're only
writing isSafe), the values in this map
are constants.
<li> RMapInUse is another instance of a ResourcesMap.
We use this other map to remember, for
each PID, what the current allocation of
resources is. For example, the request()
method, which is fully implemented for
you in Banker.cpp, manipulates this
map after it calls your isSafe() implementation.
</ul>
<li> Instance Methods. The only method you're required to implement is
the private method isSafe(). Its whole purpose is
to throw one of the four types of exceptions listed above. HINT:
The order listed above is a good order in which to test for
unsafe conditions. In other words, your code should be
structured as follows:
<ul>
<li>BankerUnsafePidException. First test
to see if the caller sent in a
valid PID. You might want to
plagiarize from closeAccount().
<li>BankerUnsafeContractException. Test
whether iFiles, iPage, iMutex
passed in to isSafe exceeds the
contracted value in RMapMax
for that PID. You might want
to look at code in openAccount(),
which is where RMapMax[iPid] was
set in the first place. That
should make you comfortable with
how to reference data stored in STL.
<li>BankerUnsafeTotalException. The idea
here is pretty simple. If we
add iFiles, iPages, and iMutex
to the values in RMapInUse, we
may exceed the values in RMapMax.
That would be unsafe.
<li>BankerUnsafeComittedException. This
is the hard part. You'll probably
have to read pp. 222-23 about 10
times before you start to feel
comfortable with what to do here.
We'll talk about in class every
week until the project's due.
</ul>
</ul>
</ul>
<h3>
<b><font color="green">Project1</font></b>
</h3>
<p><a href="Project1.cpp">Project1.cpp</a>
<p>
You should not have to make any changes to the Project.cpp file. It has the
following features:
<ul>
<li> Global Variables. There are two global variables call osfLog1 and osfLog2.
They are only used in order to generate comments to a txt file on your system,
useful for debugging. They have nothing to do with the actual operation of the project
(and that's the only reason I would ever allow global variables anywhere...). You
will be required to turn in the output of osfLog1. osfLog2 can be used by you
however you wish.
<li> tryRequest() method. This method provides for the bulk of testing that will
be done on your Banker's Algorithm. It consists of a try/catch block
which makes a request() of the Banker, catches exceptions that you throw
in isSafe(), and prints out results. The tryRequest() method is invoked
by main().
<li> tryMemoryTest(). This method has nothing to do with the Banker per se. It's
an add-on method I provided in order to promote discussion in class about
how memory is managed, particularly with C++ programs. This method
is invoked by main().
Assuming tryMemoryTest()
is invoked with all "true" values, three Banker methods will be invoked, each
of which involves progressively more memory:
<ul>
<li> helloWorld(). This method simply prints a string. The important feature
of this method is that it doesn't reference any internal instance
variables of Banker.
<li> showLimits(). This method prints information stored in the Banker's
instance variables.
<li> request(). This method requires not only instance variables, but
pointers to STL structures that are instantiated during construction
of Banker. The point here is that if the Banker hasn't been
properly constructed, the memory may be corrupt.
</ul>
<li> main(). This method does the following:
<ul>
<li> Initializes osfLog1 and osfLog2.
<li> Constructs a new instance of Banker, and points to the instance with
the variable pBanker (pointer to Banker).
<li> Calls openAccount() for PIDs 0, 1, 2, 3, and 4. These PIDs contract
with the banker for the maximum resources as listed in the
Silberschatz example on p. 222.
<li> Calls tryRequest() for the sequence specified in the Silberschatz
example.
<li> Calls tryRequest() three more times to force Banker to throw all
types of exceptions.
<li> Does some memory testing. This is something I added to promote
discussion in class about the types of protections offered by
an operating system to a C++ program. There are four "memory tests"
as follows:
<ul>
<li> TEST 0. All methods are invoked (three "trues"), because we're invoking the
test routine with a valid Banker instance which has
been properly constructed.
<li> TEST 1. We've deleted pBanker, so all bets are off
about what happens here. But odds are that the
memory for pBanker is still around, and our process
still owns the memory. Our pBanker variable still
points to the correct place even though we've
relinquished the memory via delete. The only thing
that causes my program to crash is the last test,
which invokes STL data structures allocated
within pBanker. So the last flag is set to "false."
In my testing on Windows '95, some of the information
in showLimits() is still correct, and other information
is already corrupted, probably due to reassignment
of the memory for other purposes.
<li> TEST 2. Now I'm really messing with the system. I point
pBanker to an arbitrary, uninitialized chunk of
memory that happens to be the size of pBanker.
Then I invoke the same tests as TEST 1. The difference
now is that all traces are gone of what used to be correct
values for instance variables.
<li> TEST 3. This time I don't even grab a chunk of memory I own.
I arbitrarily point pBanker to a very high number, which
undoubtedly doesn't belong to my process. This time
all tests which access any instance variables will cause
my program to crash (so the last two tests have to be
skipped using "false"). Note, however, that I can
still call helloWorld(), because it doesn't involve
any use of Banker instance memory.
</ul>
The lessons you should take from these memory tests are as follows:
<ul>
<li> Memory is a very fragile thing. Even a robust language
like C++ does not relieve the programmer of the need
for vigilance about constructors, destructors, new,
and delete.
<li> No environment will give consistent results. You may be
able to change some of my falses to trues and still
run the program without a crash; conversely, you may have
to change some of the trues to falses to make the program
run without crashing.
<li> Memory problems might go unnoticed because a program
"gets lucky." Consider TEST 1, when some of the
correct data remained around for a while even after calling
delete. So we can't
even count on a good test procedure to ensure that
our code is free of memory leaks. Often we need to
buy analysis tools like Purify.
<li> Sidenote / soapbox. This is why many programmers
(and managers who know what they are doing) like Java.
Java would spit you
out the first time you tried to execute TEST 1, thereby
saving the software industry millions of dollars per day,
and achieving much better customer satisfaction.
</ul>
</ul>
</ul>
<h3>What to Hand In</h3>
Hardcopies only, please.
<ol>
<li> Complete source code for Banker.cpp, as modified by you to include isSafe() implementation.
<li> A statement about whether your machine / environment was consistent with mine with
respect to true/false values on memory tests. Specifically, tell me:
<ul>
<li> Is your environment less forgiving than mine? I.e., do my values
for true/false cause the program to crash in your environment?
<li> Are you able to get away with setting any of the "falses" to "trues"?
Which ones?
<li> When you do set too many values to "true," what type of failure do you
see? Does the system say "Abort," "SEGV," or what?
<li> Comment on my implementation of the desctructor for Banker. Is it OK?
If not, what should it look like? Why?
</ul>
<li> The standard output of your program with a properly implemented isSafe() method,
and with as many possible "trues" set in Project1.cpp.
<li> The contents of "bankerDebug1.txt".
<li> A statement about whether you were required, in your environment, to make any changes
to Banker.h, Banker.cpp, or Project.cpp in order to make the program work
in your environment.
</ol>
<A HREF="http://www.rh.edu/users/courses.html">Return</a>
to Rensselaer at Hartford Faculty Course Materials Home Page</A>
</BODY>
</HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -