SCIENCE 131A代做、java设计编程代写

日期：2023-10-04 10:47

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.