辅导 SCIENCE 131A PROGRAMMING ASSIGNMENT 2

日期：2023-10-05 07:48

Sep 2023
COMPUTER SCIENCE 131A
OPERATING SYSTEMS
PROGRAMMING ASSIGNMENT 2
CONCURRENT UNIX SHELL
Introduction
Now that you have implemented a sequential Unix shell (congratulations!) the next step is to
make it more realistic by introducing threads and concurrency. You will be given a completed
solution of PA 1, regardless of whether you finished it or not. This starter code you will need is
available on LATTE. This document is pretty long and was custom designed to help you be
successful with this assignment. Please read it closely. There are various cheat codes (umm I
meant “helpful tips”) in places in the text.
In order to “Meet Expectations”
, you should…
● Fully document your code! This means having Javadoc comments for each class and
method, as well as additional comments to explain convoluted or non obvious lines of
code. When in doubt, more commenting is better!
● Pass the test cases. We will provide you with a list of Junit tests to assess the functionality
of your code, including tests similar or identical to the last PA. YOU WILL HAVE TO
RUN THE TESTS MORE THAN ONCE. We will be running each test roughly 10 times
in order to test for race conditions within your code. If you fail a test during one of those
10 times, then that particular test is considered “failed”. You may fail at most one test
case this way and still receive credit.
● Not violate academic integrity in any way. If you are found to be sharing code, copying
solutions off the internet, or otherwise not submitting your own original work, you will
automatically fail the assignment and may face disciplinary action.
Purpose
This assignment will give you a much clearer idea of how threads and concurrency work. You
will likely experience a race condition, and in debugging that will develop a deeper
understanding of concurrency. In addition, you will have a far greater understanding of how the
shell works, how pipes, foreground and background processing all go together. All of this will
contribute greatly to your understanding of Operating Systems and concurrency which are
important and will be very valuable to you in the future.
Sep 2023
Background
To complete this assignment, you need to have a clear understanding of how threads
work, and how threads can be started and waited upon. A section below reviews some of the key
things you need to know. Concurrent programming will be used in two ways. First, the
Filters of the commands must run concurrently. Next, the users will be able to choose
whether they want to run a command in the foreground or background. Commands running in
the foreground run sequentially to other commands running in the foreground. Commands
running in the background run concurrently to both other background commands and foreground
commands. Even with these implementation changes, from the user perspective, the shell should
behave in the exact same way that it did in PA1.
Desired behavior
In this section we go into a little more detail on how our shell is expected to behave once the
changes have been implemented.
Support of all PA1 Commands
All the commands supported by your shell will be mostly the same as in PA1, so I will not list
them all again here. Here’s just one example, showing our notation: red text is what you
type in and $black text is what your shell displays.
> pwd
/Users/pitosalas
>
Background processing symbol “&”
In this version of your program, whenever an end user types the “&” ampersand at the end of
a command, the REPL loop does not wait for the entire command to complete but it directly
prints out the “>” prompt to accept a new command while the previous ones might still be
running. In other words, the command runs “in background”. This is useful in cases where
you must execute long running commands and you don’t want to wait for the previous
commands to finish before starting another one.
For example, suppose you have a big file of Amazon reviews, and you would like to create a
file with the reviews that contain the phrase “amazing product” and a second file with the
reviews that contain the phrase “bad product”. You can accomplish that by executing the
following commands:
> cat Amazon-reviews.txt | grep amazing > amazing.txt &
> cat Amazon-reviews.txt | grep defective > defective.txt &
>
Note the new symbol, the ampersand (&),as the last character on the line, to indicate that it
should be executed in “background”. Note also that the third > prompt is printed immediately,
even before the previous two commands have completed executing. This is useful because
these two commands will take a while to run and so you can have them running in the
background while you are still able to execute other commands.
Sep 2023
New Command “repl_jobs”
The user should be able to monitor what commands are still running. This could help to avoid
exiting the shell while there are still commands running. To do this you need to create a new
command “repl_jobs” which checks which of the background processes are still alive and
prints a list of the alive processes. For example:
> cat Amazon-reviews.txt | grep amazing > amazing.txt &
> cat Amazon-reviews.txt | grep defective > defective.txt &
> repl_jobs
1. cat Amazon-reviews.txt | grep amazing > amazing.txt &
2. cat Amazon-reviews.txt | grep defective > defective.txt &
>
New Command “kill”
The user should also be able to kill a specified command by providing the number that
“repl_jobs” assigned to it. For example, to kill the second command, user would do:
> kill 1
Killing a process (e.g. kill 1) does not renumber the remaining background process. So if
you type repl_jobs again, in the previous example, there would be one process remaining,
numbered 2.
Important note!
Commands "repl_jobs" and “kill” must be part of your REPL, like the existing exit
command. They are not a new concurrent filter. They can only run as single commands,
cannot be part of any command that involves pipes and do not require any piped input and
piped output. Command “repl_jobs” does not require any arguments and there is a tab
character (“\t”) before the job number.
Java Threads
This is a very brief review of Java Threads. I will not rehash all that we covered in class and can
be found on the slides. I do again remind you that it is always far easier to understand something
if you “play with it” in a simpler “sandbox” environment. This is my personal experience, but
also well supported by research, e.g. Constructivism.
If you are unsure about these concepts, read about threads on the lecture slides/notes, try some of
the toy examples provided in our Public Examples repo, and/or on online resources, before
attempting to complete this assignment.
It might feel like your time should be spent just on solving this PA but in my experience,
investing some time making sure you understand the mechanism pays off handsomely when
doing the assignment.
Recall that when you create and start a thread, you are asking the Operating System to begin
executing your program’s code at the same time as any other thread you have created. They
appear to be running at the same time but as we know of course that because there is just one
CPU, it is the Operating System’s job (and the scheduler in particular) to give each thread a turn
so that none get left behind.
Sep 2023
Threads are generally programmed as either a sub-class of the Thread class, or by implementing
Runnable interface. It is important to understand the difference between the run and start
methods.
Start() will launch the thread. It will return immediately, at which point there are two threads, the
existing one and the new one. Once the thread is launched, the run() method is called from the
thread so the thread can do whatever it needs to do. When the run() method is done, the Thread is
also done.
Tour of the code
You have been provided with a correct solution to PA1, with some enhancements. The
SequentialREPL, SequentialFilter, SequentialCommandBuilder, and
Pipe classes have been replaced by their concurrent counterparts and placed in a new package
concurrent.
Note that you will not be changing the general structure of the code much at all. In fact, you are
only allowed to modify the files in the concurrent package. You cannot modify
ConcurrentPipe. Unlike PA1, you can modify ConcurrentFilter.
● The new ConcurrentPipe is backed by a LinkedBlockingQueue which is a data
structure that is a linked list-based queue which is thread-safe and will block (wait) on
addition and removal operations if necessary. This class has two additional methods that
you should use:
● writeAndWait(String data) will try to place data at the end, having the
invoking thread wait until there’s space in the pipe.
● readAndWait() will try to remove (and return) the first element, having the invoking
thread wait until the pipe is non-empty.
● If the current Thread has been interrupted these methods will throw an
InterruptedException and reset the Thread’s interrupt status.
Poison Pill
A poison pill is a predefined data item which producer processes can use to communicate to
consumer processes that they are done producing. This idea can be applied to the concurrent
pipes and filters design of the Unix shell. In PA1, a consuming filter will know if its producing
filter is done by checking if the input Pipe is empty. However, this no longer works. Therefore,
using the poison pill will be a convenient way for filters to indicate that they have finished
producing all of their output. You should use ConcurrentPipe’s writePoisonPill()
to write a poison pill to a producing filter’s output pipe. If you call readAndWait()on a
consuming filter’s input pipe, null is returned to signify the poison pill has been read.
Sep 2023
Plan of Attack
Starter Kit. For this part, you will not need to change the general structure of the starter code
we gave you much at all. In our code, we have already placed the filters in the concurrent
package (instead of the sequential one as in PA1) and they all have been transformed into
their concurrent counterparts by extending the ConcurrentFilter class (instead of the
SequentialFilter class in PA1). The SequentialCommandBuilder and
SequentialREPL classes have also been replaced by their concurrent counterparts.
To complete this assignment (both Part 1 and Part 2), you do not need to modify any filter class
nor the ConcurrentCommandBuilder class. You only need to modify the
ConcurrentFilter and ConcurrentREPL classes. Please take a moment to go look at
the provided code to make sure you understand!
You should approach this PA as two Parts. In part 1 you will make the Filters concurrent. In part
2 you will introduce “background commands”.
Part 1 – Concurrent Filters
The starter kit code does not allow for concurrent execution of the filters as none of the filters
can be executed as a separate thread. Your task is to allow for (i) filters to be started as threads
and (ii) allow them to run concurrently.
Remember that special care (i.e., code) is needed for multiple threads to run concurrently and not
sequentially. Just because two objects implement the Runnable interface (and hence
represent two threads) does not mean that they will execute ALWAYS in parallel. Your
code determines whether they will execute sequentially or concurrently.
Implementation Hints
Some of the changes and considerations you will need to make are given below. This is not a
complete list, but should include enough to get you started, and thinking about the right pieces of
code to create and change.
● ConcurrentFilter class should implement the Runnable Interface. When and
where will you call the run()method?
● You will need to change the mailboxes for the filters to a data structure that supports
concurrent operations. The LinkedBlockingQueue class is such a structure. Read
about it! Only proceed when you understand what will happen if a thread tries to read
from a blocking queue when it is empty.
● You will have to wait for all (or the last) filter(s) to complete before printing out the " >"
prompt.
● Your REPL loop will have to create all filters before starting any of them (why?)
● As we said above: creating threads != concurrency.
● How can we have sequential code using threads? How can we turn into concurrently
executing code?
● What happens if the threads process at totally different rates (1 : 10000x slower?)
Sep 2023
Your resulting code should behave just like the sequential version that you have completed for
PA 1, and the end user should have no idea that there is a difference- so your concurrently
executing commands should be transparent to the user.
Since we already graded you for this functionality, what will be grading you in this portion of the
assignment is how your code demonstrates your understanding of multi-threading techniques,
and how you go about accomplishing this task.
There is a "correct" way to do it, and you will be graded upon how your understanding of threads
allows you to approach this "correct" ideal. Thus, it is HIGHLY recommended that your code is
clean, well named, well commented, and immediately clear to someone who will determine your
grade in the ten minutes they have to read over it.
Part 2 – Background Commands
After you have completed the above task, the final portion of the assignment is to support a
simple form of background processes. This page from a course about Unix and the Shell can
help you understand what background processes are. After reading through this resource, it is
highly recommended that you play around with background processes on a UNIX console.
Your task now is to allow the end user to run and list the background commands, and to kill any
one of the running background commands, as described earlier in Desired Behavior. You do not
have to provide functionality that allows to suspend a command, or to bring a command from
background to foreground.
● Foreground commands stop the REPL from accepting user input until the command has
finished processing.
● Background commands do not stop the REPL from accepting user input, and continue
running until completion even if the user starts more background commands, or a
foreground command. To start a background command, the user must append an
ampersand (&) to the end of their commands. For example, “cat large-file.txt
&”.
In this version of your program, whenever an end user types the “&” ampersand at the end of a
command the REPL loop does not wait for the entire command to complete but it directly prints
out the “>” prompt to accept a new command while the previous ones might still be running.
Important: Commands repl_jobs and kill must be part of your REPL and not a new
concurrent filter. They can only run as single commands, cannot be part of any command that
involves pipes and do not require any piped input and piped output. The command repl_jobs
does not require any arguments. This is analogous to the existing exit command.
Next, the user also needs to be able to kill background commands using the indices displayed by
repl_jobs. For a command to be killed, every one of its subcommands needs to cease
execution. Stopping the filters should be done by using Java interrupts.
Sep 2023
Recall that just interrupting a Thread does not stop its execution: the interrupt must be properly
handled. Additionally, care must be taken to ensure that the command is killed no matter which
stage of its execution the interrupt is made. Since
ConcurrentPipe.writeAndWait(String data) and
ConcurrentPipe.readAndWait() both throw InterruptedException, you should
utilize them to detect interrupts.
The repl_jobs command must only display background commands that are still running. To
accurately assess whether a command is still running, you must use the Java Thread object’s
isAlive() method.
More information
Grading
There are no hidden unit tests that will be used for grading this assignment. To make sure you do
not have race conditions, run the tests at least 10 times.
Passing many test cases does not mean you will get a high score. The 65 tests in the files other
than REPL_JobsTests.java are the same tests from PA1. Therefore, you can pass all of
them without a correct concurrent solution. Once you are confident that you have a correct
concurrent solution, you should use these to test that your concurrent shell behaves the same as
PA1 (as noted above).
The 4 tests in REPL_JobsTests.java are particular to PA2, but you will also be graded by
eye to determine if you have implemented repl_jobs and kill properly.
Make sure you import and export the Eclipse project properly. The submitted project should have
a structure that looks exactly like the skeleton. An improperly structured project will receive a 0.
The project needs to be renamed FirstnameLastnamePA2 (make sure to use Eclipse’s Refactor >
Rename). The zip file you submit should be named FirstnameLastnamePA2.zip.
You are only allowed to modify the files in the concurrent package. You cannot modify
ConcurrentPipe. Unlike PA1, you can modify ConcurrentFilter.
Sep 2023
Notes on Tests
● To run the tests run AllConcurrentTests.java. Do not run each of the other test
files individually.
● The files will create files to pass into your shell and your shell will output files as part of
the tests. To save all the files that are created over the course of the tests, set
AllConcurrentTests.DEBUGGING_MODE to true. Your code should still work if
it is set to false.
● You may see AllConcurrentTests.java throw an Exception when you have
AllConcurrentTests.DEBUGGING_MODE set to false. This is most likely
because you have left a Java reader/writer object open on a test data file which did not
allow the tests to properly delete the file. To fix this issue, check that you open and close
your reader/writer objects properly in the related Filters.
● UnitTests: For this assignment, your Starter Kit also includes a new set of JUnit tests.
You are allowed to use either the solution we provide to you or your own solution but
make sure you use the new set of JUnit tests.
● Please make sure to include Java Docs for your code as it counts towards your
grade.
Allowed Libraries
You cannot import any additional libraries related to concurrency. The only two classes you
need are Runnable and Thread which are both in the automatically imported package
java.lang.
Remarks
This is an individual assignment. Any sign of collaboration will result in a 0 score for the
assignment. Please check the academic integrity policies in the syllabus of the course.