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 (-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 -pa5.tar.gz”.
5. oFinally, download your compressed archive file (-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 (-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 a ention 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