代做CIS 657编程、代写C/C++程序、c++编程调试

日期：2021-05-09 10:44

Syracuse University CIS 657: Principles of Operating Systems Spring 2021

PA-5: Nachos System Calls for File I/O and

Multi-programming

Total points: 100 pts Due on Apr May 8, 2021 at 11:59 PM

Instructor: Endadul Hoque

Important Reminders

Academic Integrity: Review the academic integrity policy (from the syllabus) and the course honor pledge; you

submitted a signed pledge at the beginning of the semester. For this programming assignment and the future ones,

we will use moss (https://theory.stanford.edu/~aiken/moss/), a system for detecting software similarity,

extensively to detect plagiarism among this semester’s submissions as well as previous years’ submissions (if

applicable). Remember that violating academic integrity policy will significantly jeopardize your grade as you agreed

on the honor pledge.

The first step for success: As with every lab/PA handout/description, I strongly urge you to read every word very

carefully. You may be able to find answers to many questions about each task by carefully reading this document.

FThe late submission policy is not applicable for this PA.

Logistics

1. This lab must be done individually, not in groups.

2. This PA expects that you are already familiar with the Nachos code base and know how to build and run

nachos and execute test programs. All these aspects were covered in the lab on Nachos.

3. For this programming assignment (PA-5), you have to download an archive called student-pa5.tar.gz from

Blackboard. Upon extraction, you will see a directory named student/, which contains nachos/code/ directory.

You have to add to and/or edit the existing Nachos source code.

4. For all the following tasks (Task-1, ...), you have to use the Linux server (lcs-vc-cis486.syr.edu) dedicated

for this course. nachos will not compile and run on a different machine.

6. Unless stated otherwise, you MUST NOT modify/edit/rename/move other existing files under the student/

directory.

7. Unless stated otherwise, you MUST NOT use any additional C/C++ library (e.g., math library) that requires

modification to the compilation commands included in the existing Makefiles.

8. For the following task, you have to use the Linux server (lcs-vc-cis486.syr.edu) dedicated for this course.

You must know how to remotely login to that machine, how to use terminal and how to copy files back and

forth between your computer and the Linux server.

Page 1 of 11

9. For this PA, you have to write a report as well. Your answers must be typed. Only one PDF file is allowed

for submission.

10. Each task explains what you have to do and “? [R-1]” dictates what you have to report about the task.

11. You must follow the submission instructions.

How to obtain the skeleton/source code for this PA?

Obtain student-pa5.tar.gz from Blackboard. Unpack the package to find the skeleton code required for this PA.

The extracted directory is named student/.

$ tar xzf student-pa5.tar.gz

Grading

Please make sure you follow the instructions provided throughout this handout; otherwise your assignment will not

be graded properly. Not following instructions will result in loss of points.

? You must not modify/edit/rename/move other existing files/directories in student/ or in its sub-directories.

? Your solutions must execute on the Linux machine (lcs-vc-cis486.syr.edu), otherwise your solutions will

not be considered for grading.

? You must not change the order of the tasks on your report.

? Your must follow the submission instructions, or it will not be graded properly.

Submission Instructions

You have to submit (a) code and (b) report using Blackboard. Please follow the instructions shown below to prepare

your submission.

Source code

Follow these instructions when you are ready to submit.

1. First clean up your nachos/code/ directory as follows:

$ cd student/nachos/code/

$ cd build.linux/

$ make distclean

# Now clean up test-pa directory

$ cd ../test-pa/

$ make distclean

2. ? Go to (or change directory cd into) your student/ directory. Now student/ should be your current

working directory. To verify your current directory, try this

$ basename `pwd`

student

Page 2 of 11

3. Use your netid to create a compressed archive (<netid>-pa5.tar.gz) of your solution directory. For instance,

if your netid is johndoe, create a compressed archive as follows:

$ cd .. # moving to the parent directory

$ mv student/ johndoe-pa5/

$ tar czf johndoe-pa5.tar.gz johndoe-pa5/

4. To verify the content of your compressed archive, try “tar tvzf <netid>-pa5.tar.gz”.

5. oFinally, download your compressed archive file (<netid>-pa5.tar.gz). You have to submit this package.

Report

? You have to write a report. Your answer must be typed. You can use any typesetting program (e.g., Word, LATEX),

but you have to convert the document to a PDF. Only one PDF file is allowed for submission.

? Mention your full name and SU NetID on the PDF.

? Use Blackboard to submit your PDF.

Use the Blackboard submission link for submitting two files: (a) your code package (<netid>-pa5.tar.gz) and

(b) report (in PDF).

List of Tasks for this PA

1 Implement System Calls for File I/O (40 pts) 4

2 Nachos Multi-programming (60 pts) 5

2.1 Non-preemptive and Preemptive Scheduling (10 pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Preemptive Multi-programming (20 pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 System Calls for Multi-programming (30 pts) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

A Some Useful Links 11

o All the tasks must be done on the lcs-vc-cis486.syr.edu, because nachos will not compile

and run on a different machine.For example, if your implementation fails test cases, we will look into your implementation and

grade both implementation and testing holistically.

Page 3 of 11

Task 1 Implement System Calls for File I/O (40 pts)

You may want to revisit PA-4 and your solution to refresh memory on how to implement a system call.

For this task, you have to implement the following system calls that the Nachos user programs can utilize for file I/O

operations. [Hint: It is recommended that you implement these syscalls in the same order presented below.]

1. int Create(char *name): This system call creates a Unix file with the name given by the parameter “name”,

and returns 1 if successful, and -1 if not, to the user program.

Implement another function that extracts the file name from the user program memory so that you can re-use

the name extraction function for other Nachos system calls,

call to implement this Nachos system call in

exception.cc. (See the documentation of Unix/Linux open() syscall)

[Hint: Implement this system call first. The Nachos Open() system call implementation is very similar. ]

2. OpenFileId Open(char *name): This system call opens the Unix file “name” and returns an “OpenFileId”

(aka, a file descriptor) if the file (“name”) exists. This OpenFileId can be used to read from and write to the file.

If the file doesn’t exist, Open() returns -1 to the user program to indicate an error.

call to implement this Nachos system call in

exception.cc. (See the documentation of Unix/Linux open() syscall)

Hint: You don’t have to maintain a separate mapping between Nachos OpenFileIds and Unix file

descriptors. Instead you can simple return the same file descriptor that the Unix open(...) syscall

returns.

3. int Write(char *buffer, int size, OpenFileId id): Utilize your implementation of Write() from

PA-4 and extend it so that it can now write to an already open Unix file (specified by id) as well as print out to

the screen. This function returns the number of bytes actually written or -1 on failure.

call to implement this Nachos system call in

exception.cc. (See the documentation of Unix/Linux write() syscall)

4. int Read(char *buffer, int size, OpenFileId id): This system call reads size bytes from the open

file (specified by id) and stores them into buffer. On success, it returns the number of bytes actually read from

the file (note: it can be 0 too), and on failure, it returns -1.

For this task, implement only the case for reading from a file; you don’t have to implement the case for reading

from ConsoleInput (i.e., keyboard input).

call to implement this Nachos system call in

exception.cc. (See the documentation of Unix/Linux read() syscall)

5. int Close(OpenFileId id): Close the file specified by id. It returns 1 on success and -1 on failure.

call to implement this Nachos system call in

exception.cc. (See the documentation of Unix/Linux close() syscall)

What to report for Task 1?

Try the list of tasks below in the order and provide answer/screenshot as stated.

Do not forget to re-build nachos if required and run it from build.linux/

[R-1] (4 × 5 = 20 pts) For each system call mentioned above, provide at least one screenshot of your implementation.

Your screenshots should be legible. Therefore, if the implementation of a system call requires more

than one screenshots, please provide them and mark them appropriately. [Hint: There should be at least 5

screenshots.]

Page 4 of 11

[R-2] ((1 + 1 + 1) × 4 = 12 pts) Build the test programs in test-pa/ if needed. Build nachos in build.linux/.

test-pa/ includes four test files for the file systems calls: file-test0.c, file-test1.c, file-test2.c

and file-test3.c.

Explain what should be the results of running each of these test programs, file-test0.c, file-test1.c,

file-test2.c and file-test3.c. Explain what features of the file system calls are tested with each

test program. Run these test programs with Nachos. Provide a screenshot of the output of running each

program, and provide your explanations. Some of these programs are expected to create some local files.

Make sure to include a screenshot of each file along with the program output.

[R-3] (8 pts) Write a new test program file-test4.c of your own to test the returned values of calling Read()

and Close(). For each of these system calls, your program should demonstrate one success case and

one failure case. Your program should print out the appropriate messages on the screen as shown

below:

? For Read():

– Print “Read(): Successful: read x bytes”, where x is the value returned by Read() on

success.

– Print “Read(): Failed: returned y”, where y is the value returned by Read() on failure.

? For Close():

– Print “Close(): Successful: returned x”, where x is the value returned by Close() on

success.

– Print “Close(): Failed: returned y”, where y is the value returned by Close() on failure.

Your file-test4.c should printout the returned values (i.e., integers) as shown above. Refer to file-test3.c.

Your file-test4.c needs to have a similar function to convert an integer (i.e., positive, 0, negative) to a

string.

Do not forget to edit test-pa/Makefile for this new file-test4.c as you did in PA-4. Otherwise

you will not be able to compile this new test program.

Your report should include:

1. (3 pts) Explain why we can’t simply use printf() functions or other Unix I/O system calls to print

out those outputs from Nachos user programs.

2. (4 + 1 = 5 pts) Provide screenshots of your file-test4.c and the output of running this test

program

Task 2 Nachos Multi-programming (60 pts)

Task 2.1 Non-preemptive and Preemptive Scheduling (10 pts)

Preliminary Requirements for this task

? Replace your current version of threadtest.cc in your Nachos directory with the one located at

student/extra/threadtest.cc

? Turn off the timer device by commenting out this line alarm = new Alarm(randomSlice); inside the

Kernel::Initialize() function located in kernel.cc of your Nachos directory. Simply use “//”. By turning

the timer device off, you will be able to see more predictable outputs.

? Compile nachos in build.linux/

Page 5 of 11

What to report for Task 2.1?

Try the list of tasks below in the order and provide answer/screenshot as stated.

Do not forget to re-build nachos if required and run it from build.linux/

? [R-1] (1 pt) Run the command ./nachos -K. You should see the same output as below.

prompt> ./nachos -K

*** thread 0 looped 0 times

*** thread 0 looped 1 times

*** thread 0 looped 2 times

*** thread 0 looped 3 times

*** thread 0 looped 4 times

*** thread 1 looped 0 times

*** thread 1 looped 1 times

*** thread 1 looped 2 times

*** thread 1 looped 3 times

*** thread 1 looped 4 times

*** thread 2 looped 0 times

*** thread 2 looped 1 times

*** thread 2 looped 2 times

*** thread 2 looped 3 times

*** thread 2 looped 4 times

*** thread 3 looped 0 times

*** thread 3 looped 1 times

*** thread 3 looped 2 times

*** thread 3 looped 3 times

*** thread 3 looped 4 times

^C

Cleaning up after signal 2

prompt>

Provide a screenshot of your output.

? [R-2] (1 + 3 = 4 pts) Notice that kernel->currentThread->Yield(); in void SimpleThread(int which)

is commented out (see threadtest.cc). Uncomment (delete ‘//’) to activate the line and recompile

Nachos and run it with the same command ./nachos -K. Provide a screenshot of the output. Explain

why this output is different from the previous one in ? [R-1] of Task 2.1.

? [R-3] (1 + 4 = 5 pts) Activate the Timer Device: Now turn on the timer device by activating line alarm =

new Alarm(randomSlice); in Kernel::Initialize() of kernel.cc. Recompile Nachos and run it

with the same command ./nachos -K. The output looks like: (The order of these lines in your output may

differ)

prompt> ./nachos -K

*** thread 0 looped 0 times

*** thread 1 looped 0 times

*** thread 2 looped 0 times

*** thread 3 looped 0 times

*** thread 0 looped 1 times

*** thread 1 looped 1 times

*** thread 3 looped 1 times

Page 6 of 11

*** thread 0 looped 2 times

*** thread 1 looped 2 times

*** thread 2 looped 1 times

*** thread 3 looped 2 times

*** thread 0 looped 3 times

*** thread 1 looped 3 times

*** thread 2 looped 2 times

*** thread 3 looped 3 times

*** thread 1 looped 4 times

*** thread 2 looped 3 times

*** thread 3 looped 4 times

*** thread 0 looped 4 times

*** thread 2 looped 4 times

^C

Cleaning up after signal 2

prompt>

Notice that after activating the timer device, the output should look different from the previous one.

Provide a screenshot of your output. Explain why this output is different from the one you observed when

the timer was disabled (in ? [R-2] of Task 2.1).

Task 2.2 Preemptive Multi-programming (20 pts)

The current version of Nachos can run only one user program at a time. To enable Nachos load and run multiple

programs concurrently, we need to overcome the following three limitations.

? First Limitation: Nachos must be able to accept multiple user program names.

? Second Limitation: Nachos must be able to create an individual thread for each user program.

? Third Limitation: Nachos must be able to load multiple programs and create address space for each program

in the main memory.

For this task, you have to resolve the First and Second limitations. However, to resolve the third limitation, a

new implementation addrspace.cc and addrspace.h have been provided in “student/extra/”. These new

addrspace.[cc|h] files implement a simple contiguous memory management scheme that can load multiple

programs in the memory without overwriting. Use the diff command to see the differences between the new

addrspace.[cc|h] and the original files. With these new addrspace.[cc|h] files, the memory management (a

solution to the third limitation) is done for you. You have to replace the original addrspace.[cc|h] with the new

version located in student/extra/.

Do not forget to replace the original addrspace.[cc|h] with the new version located in student/extra/

before working on this task

Task 2.2.1 (7 pts) Overcoming the first limitation

Recall that the distribution version of Nachos runs a user-level program from the main thread. See RunUserProg ()

in threads/main.cc. By default, Nachos can read only one user program name that is provided after the -x flag.

No matter how many you specify with multiple -x flags, it can only remember and handle one user program.

Page 7 of 11

What to report for Task 2.2.1?

Try the list of tasks below in the order and provide answer/screenshot as stated.

Do not forget to re-build nachos if required and run it from build.linux/

? [R-1] (4 pts) Modify threads/main.cc so Nachos can take many user programs via multiple -x flags (e.g.,

“./nachos -x ../test-pa/prog1 -x ../test-pa/prog2”).

[Hint: Do not hard code the user program names. Do not hard code or limit on how many -x flags can be

provided. The number of -x flags can vary. You can utilize the List class (lib/list.[cc|h]) provided in

nachos/code/, instead of implementing your own list type data structure or using a data structure from the

C++ STL library]

Provide a screenshot of your edits in main.cc. Explain what have you changed/inserted.

? [R-2] (2 pts) At this stage, if you test your implementation, you will not observe multiple user programs running

concurrently, because you haven’t resolved the second limitation yet.

Then how to test? You have to comment out the RunUserProg(userProgName); line of the main(...)

in the threads/main.cc and add some extra printing code to see if nachos prints out the provided user

program names correctly. Then test your implementation. An example output is shown below. Provide a

screenshot of your output

prompt>./nachos -x ../test-pa/prog1 -x ../test-pa/prog2

Program [0] = ../test-pa/prog1

Program [1] = ../test-pa/prog2

^C

Cleaning up after signal 2

? [R-3] (1 pt) Now (a) turn off or remove those print out messages you added in the previous step ? [R-2]

of Task 2.2.1 and (b) uncomment the RunUserProg(userProgName); line in main.cc. In other words,

you are reverting the changes you made in ? [R-2] to test your implementation. Provide a screenshot of

your code.

Don’t miss this step (? [R-3] of Task 2.2.1, otherwise the following task(s) will not work properly.

Task 2.2.2 (13 pts) Overcoming the second limitation

What to report for Task 2.2.2?

Try the list of tasks below in the order and provide answer/screenshot as stated.

Do not forget to re-build nachos if required and run it from build.linux/

? [R-1] (1 pt) Revisit threads/main.cc. Which block of code in main.cc creates the address space to run a user

program when you run “./nachos -x ../test-pa/prog1”?

? [R-2] (1 + 1 = 2 pts) Carefully study the Fork(·) function defined in thread.[cc|h].

1. What is the role of the first argument of the function Fork(·)?

2. If we use a pointer to the function RunUserProg(·) as the first argument of Fork(·), what will be

the effect?

Page 8 of 11

? [R-3] (6 pts) Carefully consider all the exercises above. With the new addrspace.[cc|h] files, Nachos can

load multiple user programs in the main memory whenever you create an address space for each program

to be executed (dictated by the multiple “-x” flags). The RunUserProg() function in main.cc shows an

example on how to create an address space for one user program. It loads the executable file in the code

segment and executes the user program. Notice that the AddressSpace::Execute() function never

returns. Recall that the current Nachos can only run one user program thread at a time.

To load and run multiple user programs, your task is to create a new thread for each user program.

Modify main.cc so it creates a user-level thread for each program specified by each -x flag. Provide one

or more screenshots of your implementation/edits in threads/main.cc.

[Hint: Study carefully how threadtest.cc creates multiple threads. Pay aention to the first argument of

Fork(·) and think about which function pointer should be the first argument to run a user program.]

? [R-4] (2 pts) Re-build nachos and test programs in test-pa/. Run nachos with command

“./nachos -x ../test-pa/prog1 -x ../test-pa/prog2”. Your nachos must be able to run all user

programs provided in the command line. Provide a screenshot of the output.

? [R-5] (2 pts) Re-build nachos and test programs in test-pa/, if necessary. Run nachos with command

“./nachos -x ../test-pa/write -x ../test-pa/prog1 -x ../test-pa/prog2”. Your nachos

must be able to run all user programs provided in the command line. Provide a screenshot of the output.

Task 2.3 System Calls for Multi-programming (30 pts)

At this stage, your nachos can execute multiple user programs provided in the command line arguments (using

multiple -x flags). In this task, you are going to implement some additional system calls (Exec() and Join()) that

user programs can use to spawn new processes. (In Nachos, Exec() is a combination of Unix fork() and exec()

whereas Join() is similar to Unix waitpid()).

[Hint: It is recommended that you implement these syscalls in the same order presented below.]

1. SpaceId Exec(char* path_to_exec_name): this syscall takes one string argument that is the path to the

filename of a user program. The way Exec() creates threads is similar to what you did for the -x flag in

Task 2.2.2. When a user program calls Exec(), Nachos kernel creates a new thread and a new address space for

the executable filename given as the argument. This new thread should execute the user program loaded into

the address space. (Recall RunUserProg()).

On success, Exec() needs to return a SpaceId (defined in userprog/syscall.h) of this new thread, which

can be used as the argument of Join(). SpaceId for each thread must be unique but not necessarily random.

On failure, however, Exec() returns -1.

Hint: For SpaceId, think about creating a pid for each Thread. You must make sure that each pid is

unique but not necessarily random.

2. int Join(SpaceId id): This system call helps the caller thread (say, Thread A) running the user program

join another thread (say, Thread B, running a different program) specified by the argument “id”.

On success, Thread A will stay blocked inside the Join() function while Thread B is alive and will return

from Join() once Thread B has finished its execution; in this case, Join() should return 0.

On failure, Join() should return -1.

Hints

Hints on how to implement Join(): READ CAREFULLY

SpaceId is an integer; so given a SpaceId, you have to find out the corresponding thread object. You

Page 9 of 11

have to implement the lookup mechanism by using a data structure, say, a thread table or a thread

list. (You can utilize the Nachos List class that you used in Task 2.2.1)

Inside Join(), the caller thread (Thread A) needs to be associated with the to-be-joined thread (Thread

B) so that Thread B can wake up Thread A when Thread B is about to finish. After the successful

association, Thread A calls Thread::Sleep() to get itself blocked. However, if it fails, Thread A

should not be blocked and Join() should return with -1.

[Check the comment before Thread::Sleep() implementations. You should notice that it expects the

interrupts to be disabled when called. Check line 86 in threads/synch.cc for how to call Sleep() and

look at the surrounding code on how to disable and enable interrupts.]

When Thread A wakes up, it assumes that Thread B has finished and therefore it can safely return 0

from Join().

When Thread B is finishing its execution, Thread B must wake up all the threads that have previously

joined it. In our example, Thread A has joined Thread B, and therefore Thread B must wake up

Thread A.

By now, you may have realized that you need another mechanism, say a waiting-list, for each thread to

keep track of which threads are waiting for this thread to finish.

When Thread A wants to associate itself with Thread B, Thread A simply adds itself to the Thread

B’s waiting-list. The terminating thread (i.e., Thread B), in turn, can wake up each thread in its waiting

list by using “Scheduler::ReadyToRun()”. You have to implement this “waking-up” logic inside

“Thread::Finish()”.

What to report for Task 2.3?

Try the list of tasks below in the order and provide answer/screenshot as stated.

Do not forget to re-build nachos if required and run it from build.linux/

? [R-1] (6 pts for Exec() + 10 pts for Join() = 16 pts) For each system call mentioned above, provide at least one

screenshot of your implementation. Your screenshots should be legible. Therefore, if the implementation

of a system call requires more than on screenshots, please provide them and mark them appropriately.

Points for the screenshot(s) of each system call are specified along with the description of the

system call (see the syscalls in Task 2.3)

? [R-2] (14 pts) Build your nachos and the test programs in test-pa/, if necessary. There are three programs:

prog3.c, prog3b.c and prog4.c. prog3 is for testing Exec(), prog3b is for testing both Exec() and

Join() together, and prog4 is called by the other two and is not intend to be executed directly.

1. (3 pts) Explain what these user program, prog3.c, prog3b.c and prog4.c, do.

2. (2 + 3 = 5 pts) Run the excutable of prog3 test program as ./nachos -x ../test-pa/prog3.

Provide a screenshot of your output. Explain the output. A sample output is shown below:

prompt> ./nachos -x ../test-pa/prog3

Hello from prog4

Hello from prog3. Child process id: 2

Exit system call made by ../test-pa/prog3

Hello from prog4

Page 10 of 11

Hello from prog4

Hello from prog4

Hello from prog4

Bye from prog4

Exit system call made by ../test-pa/prog4

^C

Cleaning up after signal 2

prompt>

Note that you may have different id for the child process. But it is expected that prog3 should not wait

for prog4 to finish as shown above.

3. (2 + 4 = 6 pts) Run the excutable of prog3b test program as ./nachos -x ../test-pa/prog3b.

Provide a screenshot of your output. Explain the output. A sample output is shown below:

prompt> ./nachos -x ../test-pa/prog3b

Hello from prog4

Hello from prog4

Hello from prog4

Hello from prog4

Hello from prog4

Bye from prog4

Exit system call made by ../test-pa/prog4

Hello from prog3b. Child process id: 2

Exit system call made by ../test-pa/prog3b

^C

Cleaning up after signal 2

prompt>

Note that you may have different id for the child process. But it is expected that prog3 must wait for

prog4 to finish as shown above.

Appendix A: Some Useful Links

1. A Road Map Through Nachos by Thomas Narten – http://www.cs.kent.edu/~javed/class-OS10S/nachosroadmap.pdf

2. MIPS instruction set – https://inst.eecs.berkeley.edu/~cs61c/resources/MIPS_help.html and

https://www.dsi.unive.it/~gasparetto/materials/MIPS_Instruction_Set.pdf

Page 11 of 11