Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COMP604 Operating Systems
Assignment 3
Deadline: 25 October 2024, 5:00pm
This is an individual assignment. You must submit your own work and you are solely responsible for your submission. Make sure you understand what are required for each question. There are 4 questions in this assignment.
This assignment will contribute 30% towards the overall course marks.
Question 1: Read-Write Semaphore (Max Mark: 30 / 100)
This question requires you to implement Read-Write semaphores for xv6.
Two files – semaphore.h and semaphore.c are provided for you as a reference design for semaphore implementation in xv6. A structure representing a semaphore is defined in semaphore.h. There are three functions associated with the semaphore – initsema(), downsema() and upsema(), that initialize, decrement and increment a semaphore respectively. The code for these functions is provided in semaphore.c. Study them in conjunction with the lecture slides to make sure you understand them. You may want to compile them with the xv6 kernel and see how it works with the user program sematest.c provided for you. In order to do so, add the function provided in sys_sematest.c to sysfile.c and make sematest() a system call for xv6 in the usual way. Then compile xv6 with make qemu CPUS=1 and run sematest. Running xv6 on a single CPU prevents the displayed messages from being garbled.
Task: Implement Read-Write Semaphore that can be used to solve the Reader/Writer problem as discussed in class. In semaphore.h there is already an empty struct rwsemaphore. There are also five associated function prototypes:
void initrwsema(struct rwsemaphore *rws);
int downreadsema(struct rwsemaphore *rws);
int upreadsems(struct rwsemaphore *rws);
void downwritesema(struct rwsemaphore *rws); void upwritesema(struct rwsemaphore *rws);
You will need to design an appropriate struct rwsemaphore, and implement these five functions in semaphore.c. Your struct rwsemaphore should be defined using the semaphore in semaphore.c. That is, do not use the xv6 locks. Note that you do not need to wake up the waiting threads/processes in the same order as semaphores are requested.
There is a function called sys_rwsematest() in sys_sematest.c. Make rwsematest() a system call like sematest() above. A user test program has been provided in rwsematest.c. It makes use of this system call. The test program conducts three tests – read lock test, write lock test, and read & write lock test. You will need to work out from this program what the correct output of each test should be.
Capture your test output and paste it into a document. Then explain why this output shows that your implementation is correct.
Submission Requirement: Clean up (remove) all the object files and executable files using the command make clean (in the directory where the Makefile is located). Then, in the parent directory of xv6-riscv, run the tar command to archive the whole xv6- riscv directory (with its sub-directories including user, kernel, and mkfs). Name this tar file q1-.tar where is your student ID.
The code you added/modified should be documented with appropriate comments.
Submit both this tar file and the document showing the test program outputs and your explanations to Canvas.
Question 2: File System (Max Mark: 15 / 100)
A simple file system has the same structure as the one in Task 10.2. First, there is an inode bitmap, which marks whether each corresponding inode is allocated (1) or free (0). There are 16 inodes. Each allocated inode has contents consisting of three fields. The first field is either f (file) or d (directory). The second field a either points to a single data block or is -1 which indicates that the files is empty. Note that in this limited file system, each file or directory can only occupy a single data block. The third field is a reference count for files. For directories, it indicates the number of directories within this directory.
Task: Answer the questions in each of the following cases.
(1) Consider the state of the file system below:
inode bitmap 1000100110010001
inodes [d a:0 r:4] [] [] [] [f a:-1 r:1] [] [] [d a:15 r:2]
[d a:22 r:2] [] [] [f a:-1 r:3] [] [] [] [f a:-1 r:1]
data bitmap 100000000000000100000010
data [ (.,0) (..,0) (m,7) (a,8) (g,11)] [] [] [] [] [] [] []
[] [] [] [] [] [] [] [(.,7) (..,0) (m,15) (e,11)]
[] [] [] [] [] [] [(.,8) (..,0) (r,4) (w,11)] []
Question: List all the files and directories that are currently in this file system.
(2) Consider the state of the file system below:
inode bitmap 1000100010000101
inodes [d a:0 r:4] [] [] [] [d a:19 r:2] [] [] []
[d a:9 r:2] [] [] [] [] [f a:-1 r:2] [] [f a:-1 r:2]
data bitmap 100000000100000000010000
data [(.,0) (..,0) (g,8) (w,4) (m,13) (z,13)] [] [] [] [] []
[] [] [] [(.,8) (..,0) (s,15)] [] [] [] [] [] []
[] [] [] [(.,4) (..,0)] [] [] [] []
Question: What error do you find in this file system? How could a check-and-repair program such as fsck find such errors? Could it be corrected automatically?
(3) Consider the state of the file system below:
inode bitmap 1000100010000101
inodes [d a:0 r:4] [] [] [] [d a:19 r:2] [] [] []
[d a:9 r:2] [] [] [] [] [d a:-1 r:2] [] [f a:-1 r:1]
data bitmap 100000000100000000010000
data [(.,0) (..,0) (g,8) (w,4) (m,13) (z,13)] [] [] [] [] []
[] [] [] [(.,8) (..,0) (s,15)] [] [] [] [] [] []
[] [] [] [(.,4) (..,0)] [] [] [] []
Question: What error do you find in this file system? What should a check-and- repair program such as fsck do when encountering such a problem?
(4) Consider the state of the file system below:
inode bitmap 1000100010000101
inodes [d a:0 r:4] [] [] [] [d a:19 r:2] [] [] []
[d a:9 r:2] [] [] [] [] [f a:-1 r:2] [] [f a:-1 r:1]
data bitmap 100000000100000000010000
data [(.,0) (..,0) (g,8) (w,4) (m,13) (z,13)] [] [] [] [] []
[] [] [] [(.,8) (..,0) (s,15)] [] [] [] [] [] []
[] [] [] [(.,4) (..,3)] [] [] [] []
Question: What error do you find in this file system? Is there sufficient information in the file system to correct such a problem? If so, which piece of information is needed?
(5) Consider the state of the file system below:
inode bitmap 1000100010000101
inodes [d a:0 r:4] [] [] [] [d a:19 r:2] [] [] []
[d a:18 r:2] [] [] [] [] [f a:-1 r:2] [] [f a:-1 r:1]
data bitmap 100000000100000000010000
data [(.,0) (..,0) (g,8) (w,4) (m,13) (z,13)] [] [] [] [] []
[] [] [] [(.,8) (..,0) (s,15)] [] [] [] []
[] [] [] [] [] [(.,4) (b,0)] [] [] [] []
Question: What error do you find in this file system? Is there sufficient information in the file system to correct such a problem? If so, which piece of information is needed?
Submission Requirements: Put your answers to the above questions in an MS Word file (.doc or .docx) or a plain text file (.txt). Name this tar file q2-
Question 3: RAID (Max Mark: 15 / 100)
A Python program called raid.py that is provided simulates a RAID similar to what you have done in Task 11.2
Task: Provide tabulated results and answer the questions for each of the following parts.
(1) Use the timing mode of raid.py to obtain the following
(a) Total time for 100 random reads to the RAID with 4 disks at levels 0, 1, 4, and 5. You may use a range of 1000 and assume left-asymmetric RAID-5. Show the command and simulator outputs.
(b) As above but for 100 random writes. Show the command and simulator outputs.
(c) Tabulate the results obtained above.
(d) Based on the results you obtained, answer the following questions
(i) How do the read and write timing results compare across these four RAID levels? Which arrangement is the most efficient for reading and which one for writing.
(ii) Give reasons why the relative performances across RAID levels are as you tabled.
(2) Tabulate the timing results of 100 random writes to left-asymmetric RAID-5 for 4, 5, 6,7 and 8 disks. Show the commands and simulator outputs.
Answer this question: Based on your results, how does the performance scale as the number of disks increases? Give plausible reason(s) for this observation.
Submission Requirements: Put your answers to the above questions in an MS Word file (.doc or .docx) or a plain text file (.txt). Name this tar file q3-
Question 4: Files in xv6 (Max Mark: 40 / 100)
In Unix/Linux, there is a system call named lseek() (accessed through the standard C library) that repositions the offset of an open file for reading and writing. Look at the man page of lseek to understand more.
Task: Implement a lseek() system call for xv6-riscv. This system call is a lot more restricted than the Linux version. The function prototype is int lseek(int fd, int offset);
where fd is the file descriptor, and the file offset is set of offset bytes. Offset is always computed from the beginning of the file. It returns the resulting offset location in bytes if successful. Otherwise, it should return -1.
Note that if the offset is larger than the size of the file, then the offset location will be set to the end of the file and this value is what should be returned. This is different from the behaviour of the lseek() in Unix/Linux.
Write your own user program filetest (in a file filetest.c) to test your lseek() system call. It should take two arguments, the first one is a text file name and the second is an integer (the offset). Make sure that it test for the case where the offset is larger than the file size. Otherwise, it should read a few characters from the file and print them out to show that the offset has been set correctly.
Chapter 8 of the xv6 book contains useful information.
Submission Requirements: Clean up (remove) all the object files and executable files using the command make clean (in the directory where the Makefile is located). Then, in the parent directory of xv6-riscv, run the tar command to archive the whole xv6- riscv directory (with its sub-directories including user, kernel, and mkfs). Name this tar file q4-.tar where is your student ID. Submit this file to Canvas.
The code you added/modified should be documented with appropriate comments.