辅导COMP 3000、C/C++课程编程辅导
- 首页 >> Algorithm 算法 Carleton University
School of Computer Science
COMP 3000 (WINTER 2022) OPERATING SYSTEMS
ASSIGNMENT 3
Please submit the answers to the following questions in Brightspace by the due time indicated in the
submission entry. There are 20 points in total and 4 bonus points (weight: 0.25).
Submit your answers as a gzipped tarball "username-comp3000-assign3.tar.gz" (where username is your
MyCarletonOne username). Do NOT just submit a file of another format (e.g., txt or zip) by renaming it
to .tar.gz. Unlike tutorials, assignments are graded for the correctness of the answers.
The tarball you submit must contain the following:
1. A plaintext file containing your solutions to all questions, including explanations.
2. A README.txt file listing the contents of your submission as well as any information the TAs should
know when grading your assignment. Without this file, grading will be based on the TA’s
understanding.
3. For each question, where applicable, a C file for your modified version of the provided source code.
This should include all required changes for that question.
4. Diff files showing the modifications, by comparing each submitted C file above and the original: for
example, diff -c 3000pc-fifo.c 3000pc-fifo_modifiedQ7.c > Q7.diff. Avoid moving
around or changing existing code (unless necessary) which may be distracting.
You only need to submit code for the following questions:
Part 3: Q7 (3000pc-fifo), and if you want to attempt the bonus question Part 2: Q4 (3000shell)
You can use this command to create the tarball: tar zcvf username-comp3000-assign3.tar.gz
your_assignment_directory. **Don’t forget to include your plaintext file!!**
No other formats will be accepted. Submitting in another format will likely result in your assignment not being
graded and you receiving no marks for this assignment. In particular, do not submit an MS Word,
OpenOffice, or PDF file as your answers document!
Empty or corrupted tarballs may be given a grade of zero, so please double check your submission by
downloading and extracting it.
Don't forget to include what outside resources you used to complete each of your answers, including other
students, and web resources. You do not need to list help from the instructor, TA, or information found in the
textbook or man pages.
Use of any outside resources verbatim as your answer (like copy-paste or quotation) is not allowed, and will
be treated as unauthorized collaboration (and reported as plagiarism).
Please do NOT post assignment solutions on MS Teams or Brightspace (or other platforms not used in the
course such as Discord) or it will be penalized. Moreover, posting the assignment questions to any external
forums/websites is NOT permitted and will also be penalized/reported.
2
Questions – part 1: Concepts [8]
No code submission for this part.
1. [2] Based on the lecture discussion, explain in your own words why true atomicity is technically
infeasible for the CPU, from the perspective of the ISA. Avoid just pasting slide content as part of
the answer.
2. Why is it recommended to eject (i.e., to tell the system that the disk will be removed) a portable disk,
such as a USB drive or SSD, before disconnecting it from the computer? Let’s ignore potential
physical damages for now.
[2] Mention two reasons, from the file system and data’s perspective.
3. After invoking the fork() system call, there will be the parent process and the child process. Right
after the call, what will be the situation of the following? Use wording such as “shared”, “different
and separate”, “same but separate”, etc.
[1] Content in the address space
[2] File descriptors (and how did you find it out experimentally? – other than doc/manual reading)
[1] Execution context
Questions – part 2: Revisit [3 + 4 BONUS]
The following questions (where applicable) will be based on the original
3000shell.c in Tutorial 3:
Calling an external program explicitly (except for running the entered command) in the code is not allowed.
4. [4 BONUS] Now that we have learned pipes as an IPC mechanism. Inspired by how standard
output redirection in 3000shell is done and how 3000pc-fifo’s pipe is done, try to implement
your own simple shell pipeline also using the vertical bar (‘|’) so that:
You can commandA | commandB
e.g., ls -l | wc -l
- Note that it should not matter if there are spaces around the ‘|’.
- You only need to support two stages, like the example above, but for any two non-interactive
programs with arguments. You do not need to support internal commands, the current output
redirection (‘>’) or the background mode (‘&’). But the original functionality must be preserved.
- To further simplify it, a strawman preprocessing function is provided to save you from dealing with
string manipulation (feel free to modify and use it):
It returns an array of two strings, one for stage 1 and one for stage 2. You can treat each as the
original command line.
So no asking for how to use it…
- Hints: now that you have two programs (stages) to run, you’ll need to fork twice. But make sure not
to end up with four processes (instead of three). As with standard output redirection, you can also
manipulate the file descriptors for the pipeline (before exec’ing anything).
No partial marks for non-working code.
char **split_pipeline(char *buffer)
{
static char *stages[2];
if ((strchr(buffer, '|') != strrchr(buffer, '|')) || (NULL == strchr(buffer, '|')))
return NULL;
char *buffer2 = strdup(buffer);
stages[0] = strtok(buffer2, "|");
stages[1] = strtok(NULL, "|");
return stages;
}
3
5. Can this simple shell pipeline be implemented without pipe(), e.g., by just following how redirection
is done: to dup2() the stdout of stage1 to the stdin of stage2? [1] Briefly explain why (not). [2] How
can you prove your answer without programming (no code changes) but only using commands?
Hint: files in certain file systems can also represent file descriptors.
Questions – part 3: Concurrency [9]
The following questions (where applicable) will be based on the original 3000pc.zip
in Tutorial 6:
Calling an external program explicitly in the code is not allowed.
6. Describe how you can gradually find out the length of the buffer for unnamed pipes just by
manipulating the arguments to ./3000pc-fifo [2]. Hint: you can adjust the arguments in a way
that you will progressively approximate the value. After your attempt, provide this length in bytes [1].
(Although the exact value is expected, a range with an error ±256 bytes is also accepted.).
7. [3] Make minimal changes to 3000pc-fifo so that it:
- Takes as the last command line argument a named pipe (FIFO) that replaces the unnamed one
(pipe(pipefd)), for example: ./3000pc-fifo 100 0 0 /home/student/myfifo
- Uses this named pipe for the producer to write to, whose fd will replace pipefd_write
- Uses this named pipe for the consumer to read from, whose fd will replace pipefd_read
3000pc-fifo should still work the same as before. The file “myfifo” is a FIFO that will be created
by the TA.
8. In 3000pc-fifo, you can see a line “#define WORDSIZE 16” which defines the word size.
Meanwhile, you will also notice that words in the wordlist[] have different sizes. [2] How can you
know in a simple way whether the call write(pipefd_write, word, WORDSIZE) on line 92 actually
writes WORDSIZE bytes or a varying size for each word? You can paste here the corresponding line
from the output of your method. You should not modify the 3000pc-fifo source code.
Note that this question asks for verification, not document/manual reading.
9. [1] In 3000pc-rendezvous, why are the last two arguments of sem_init() set to “1, 1” (line 319)?
School of Computer Science
COMP 3000 (WINTER 2022) OPERATING SYSTEMS
ASSIGNMENT 3
Please submit the answers to the following questions in Brightspace by the due time indicated in the
submission entry. There are 20 points in total and 4 bonus points (weight: 0.25).
Submit your answers as a gzipped tarball "username-comp3000-assign3.tar.gz" (where username is your
MyCarletonOne username). Do NOT just submit a file of another format (e.g., txt or zip) by renaming it
to .tar.gz. Unlike tutorials, assignments are graded for the correctness of the answers.
The tarball you submit must contain the following:
1. A plaintext file containing your solutions to all questions, including explanations.
2. A README.txt file listing the contents of your submission as well as any information the TAs should
know when grading your assignment. Without this file, grading will be based on the TA’s
understanding.
3. For each question, where applicable, a C file for your modified version of the provided source code.
This should include all required changes for that question.
4. Diff files showing the modifications, by comparing each submitted C file above and the original: for
example, diff -c 3000pc-fifo.c 3000pc-fifo_modifiedQ7.c > Q7.diff. Avoid moving
around or changing existing code (unless necessary) which may be distracting.
You only need to submit code for the following questions:
Part 3: Q7 (3000pc-fifo), and if you want to attempt the bonus question Part 2: Q4 (3000shell)
You can use this command to create the tarball: tar zcvf username-comp3000-assign3.tar.gz
your_assignment_directory. **Don’t forget to include your plaintext file!!**
No other formats will be accepted. Submitting in another format will likely result in your assignment not being
graded and you receiving no marks for this assignment. In particular, do not submit an MS Word,
OpenOffice, or PDF file as your answers document!
Empty or corrupted tarballs may be given a grade of zero, so please double check your submission by
downloading and extracting it.
Don't forget to include what outside resources you used to complete each of your answers, including other
students, and web resources. You do not need to list help from the instructor, TA, or information found in the
textbook or man pages.
Use of any outside resources verbatim as your answer (like copy-paste or quotation) is not allowed, and will
be treated as unauthorized collaboration (and reported as plagiarism).
Please do NOT post assignment solutions on MS Teams or Brightspace (or other platforms not used in the
course such as Discord) or it will be penalized. Moreover, posting the assignment questions to any external
forums/websites is NOT permitted and will also be penalized/reported.
2
Questions – part 1: Concepts [8]
No code submission for this part.
1. [2] Based on the lecture discussion, explain in your own words why true atomicity is technically
infeasible for the CPU, from the perspective of the ISA. Avoid just pasting slide content as part of
the answer.
2. Why is it recommended to eject (i.e., to tell the system that the disk will be removed) a portable disk,
such as a USB drive or SSD, before disconnecting it from the computer? Let’s ignore potential
physical damages for now.
[2] Mention two reasons, from the file system and data’s perspective.
3. After invoking the fork() system call, there will be the parent process and the child process. Right
after the call, what will be the situation of the following? Use wording such as “shared”, “different
and separate”, “same but separate”, etc.
[1] Content in the address space
[2] File descriptors (and how did you find it out experimentally? – other than doc/manual reading)
[1] Execution context
Questions – part 2: Revisit [3 + 4 BONUS]
The following questions (where applicable) will be based on the original
3000shell.c in Tutorial 3:
Calling an external program explicitly (except for running the entered command) in the code is not allowed.
4. [4 BONUS] Now that we have learned pipes as an IPC mechanism. Inspired by how standard
output redirection in 3000shell is done and how 3000pc-fifo’s pipe is done, try to implement
your own simple shell pipeline also using the vertical bar (‘|’) so that:
You can commandA | commandB
e.g., ls -l | wc -l
- Note that it should not matter if there are spaces around the ‘|’.
- You only need to support two stages, like the example above, but for any two non-interactive
programs with arguments. You do not need to support internal commands, the current output
redirection (‘>’) or the background mode (‘&’). But the original functionality must be preserved.
- To further simplify it, a strawman preprocessing function is provided to save you from dealing with
string manipulation (feel free to modify and use it):
It returns an array of two strings, one for stage 1 and one for stage 2. You can treat each as the
original command line.
So no asking for how to use it…
- Hints: now that you have two programs (stages) to run, you’ll need to fork twice. But make sure not
to end up with four processes (instead of three). As with standard output redirection, you can also
manipulate the file descriptors for the pipeline (before exec’ing anything).
No partial marks for non-working code.
char **split_pipeline(char *buffer)
{
static char *stages[2];
if ((strchr(buffer, '|') != strrchr(buffer, '|')) || (NULL == strchr(buffer, '|')))
return NULL;
char *buffer2 = strdup(buffer);
stages[0] = strtok(buffer2, "|");
stages[1] = strtok(NULL, "|");
return stages;
}
3
5. Can this simple shell pipeline be implemented without pipe(), e.g., by just following how redirection
is done: to dup2() the stdout of stage1 to the stdin of stage2? [1] Briefly explain why (not). [2] How
can you prove your answer without programming (no code changes) but only using commands?
Hint: files in certain file systems can also represent file descriptors.
Questions – part 3: Concurrency [9]
The following questions (where applicable) will be based on the original 3000pc.zip
in Tutorial 6:
Calling an external program explicitly in the code is not allowed.
6. Describe how you can gradually find out the length of the buffer for unnamed pipes just by
manipulating the arguments to ./3000pc-fifo [2]. Hint: you can adjust the arguments in a way
that you will progressively approximate the value. After your attempt, provide this length in bytes [1].
(Although the exact value is expected, a range with an error ±256 bytes is also accepted.).
7. [3] Make minimal changes to 3000pc-fifo so that it:
- Takes as the last command line argument a named pipe (FIFO) that replaces the unnamed one
(pipe(pipefd)), for example: ./3000pc-fifo 100 0 0 /home/student/myfifo
- Uses this named pipe for the producer to write to, whose fd will replace pipefd_write
- Uses this named pipe for the consumer to read from, whose fd will replace pipefd_read
3000pc-fifo should still work the same as before. The file “myfifo” is a FIFO that will be created
by the TA.
8. In 3000pc-fifo, you can see a line “#define WORDSIZE 16” which defines the word size.
Meanwhile, you will also notice that words in the wordlist[] have different sizes. [2] How can you
know in a simple way whether the call write(pipefd_write, word, WORDSIZE) on line 92 actually
writes WORDSIZE bytes or a varying size for each word? You can paste here the corresponding line
from the output of your method. You should not modify the 3000pc-fifo source code.
Note that this question asks for verification, not document/manual reading.
9. [1] In 3000pc-rendezvous, why are the last two arguments of sem_init() set to “1, 1” (line 319)?