2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 1/11 COMP 3430 - Operating Systems Assignment 2 Franklin Bristow and Rob Guderian Winter 2021 Description General submission requirements Question 1: The Marginal At Best Shell ™ Description Task System calls Running your program Script files Assumptions Checking your output Testing Evaluation Code quality and design Implementation Submitting your assignment Advice Debugging Description In assignment 2, you’re going to be working with processes, pipes, and FIFOs. Assignment 2 is due Friday, March 11th, 2022 at 11:59pm CDT (Winnipeg time). General submission requirements 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 2/11 Submissions that violate any of the following will not be evaluated (i.e., you will receive a score of 0 for the assignment): All solutions must be written in C. No other languages are accepted. All solutions must include a working Makefile. Forget how to make a Makefile? Never knew how to make a Makefile? Thankfully, you can go to https://makefiletutorial.com and find some very easy to use basic examples. Your Makefile should contain a clean rule. When is run in your directory, all the temporary files, including the executable should be removed (e.g., rm -f my_prog). All solutions must be compiled by issuing the command make in the directory containing the Makefile. No other build commands are acceptable, even if documented in the README.md. All solutions must include a Markdown-formatted README.md file that minimally describes how to run your submission. Forget how to make a README.md? Never knew how to make README.md? Thankfully, you can go to https://readme.so/ and build a nice, Markdown-formatted README.md with a nice preview and some handy buttons to help you build it. All solutions must run to successful completion. Premature termination for any reason (no obvious output, Segmentation Fault, Bus Error, etc.) is considered to be a solution implementation that does not run. Code that runs for an unreasonably long time (e.g., > 30 seconds) without terminating is also considered to be a solution implementation that does not run. All solutions must compile. Code that does not compile will not be evaluated. Programs must produce no errors when compiled with the flags Note that -Werror prevents your code from being compiled when warnings are present. make clean -Wall -Wpedantic -Wextra -Werror 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 3/11 If these flags are not in your Makefile, your submission will be treated as though it does not compile. Your code must compile and run on a machine on aviary.cs.umanitoba.ca. No late submissions will be accepted. The assignment deadline is enforced electronically. Submissions will not be accepted by e-mail. Reminder: All submitted code will be evaluated using an automated similarity testing tool, alongside commonly available online solutions for problems. Question 1: The Marginal At Best Shell ™ Description “I am very proud of this shell.” Look at him, he’s beaming with pride. (Public Domain) 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 4/11 Operating systems generally come with a shell, some kind of an interface for interacting with the operating system. We’re using command-line shells extensively in this course. When you’re connected to aviary, you’re almost certainly using TCSH (“tee-see-shell”). If you’re using WSL, you’re almost certainly using GNU Bash. If you’re using any recent version of macOS, you’re almost certainly using Zsh (“zee-shell”, but I can’t bring myself to say it, so I always refer to it as “zed-shell”). Almost universally, you can figure out what command-line shell you’re using by running a command: These shells are all interactive, meaning that there’s a “prompt”, where the shell is waiting for you (the user) to type something in (a command). The shell interprets that command, then does the normal fork(), exec(), wait() dance. When the process it fork()ed finishes, the shell prints out that prompt again, patiently waiting for you to enter another command. All of these shells also have the ability to execute scripts — you write a sequence of commands into a text file, and run the shell as a program with that file as an argument: While there still may be some interactivity when running these scripts (prompting you to enter a value), generally these kinds of scripts are non- interactive. A non-interactive invocation of a shell script will just run to completion without ever asking you for input. Task Your job is to implement a non-interactive shell with pipe, redirection, and process substitution support. Your program will be provided with a script, where each line is a sequence of commands that may have pipes (|), redirection operators (< redirect file to standard input and > redirect standard output to file), or process substitution sequences (<(program)). Your program has the responsibility of doing the fork(), pipe(), exec(), wait() dance for all of the commands in the line of the script. So, for example, the command echo $SHELL bash my-script.sh sort -R <(cat /usr/share/dict/words) | head -5 > random.txt 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 5/11 will invoke the sort command with the arguments -R and a “file-like-thing”™ that contains the contents of /usr/share/dict/words, pipe its standard output to the head command (which was invoked with the argument -5), and the head command will have its standard output written to a file named random.txt. The contents of random.txt in this pipeline will be a random selection of 5 words from /usr/share/dict/words. You must implement this pipeline from scratch using the appropriate system calls (e.g., pipe(), mkfifo(), fork(), dup2(), the exec family, and wait()). When working with files in a command pipeline (i.e., redirection operators < and >), you should use the open() and close() system calls. You should not use the I/O functions from the standard library, you’d just be making your life harder. When working with files (reading the script), you can safely use the I/O functions from the standard C library (e.g., fopen, fgets, fclose). You’re also permitted to use the standard string processing functions for deconstructing the command into its components (e.g., strtok, strdup, strchr, etc), though you may consider building a lower-level state machine for parsing the command pipelines. You are permitted to use mktemp (see man 3 mktemp) for implementing process substitution, however process substitution should not actually create a real file, but should be implemented using a FIFO. You are explicitly not permitted to pass your script to another shell and have the other shell do the work. System calls You’ve used fork(), and wait() in assignment 1. You also used execvp(), pipe(), and dup2() in lab 2. Our textbook describes using the exec family of system calls in Chapter 5, and the pipe() and dup2() system calls are described in APUE. Both of these families of system calls are also well documented in the manual pages. In terms of the exec family of system calls, you’re going to want to use either execve() or execvp(), since they both allow you to pass command-line arguments to the program that you’re exec-ing. In terms of pipe() and dup2(): you should read the manual page for dup2() but, in summary, you can use this system call to effectively replace a file descriptor. For the purposes of this assignment, you’re going to need to repeatedly replace STDIN_FILENO and STDOUT_FILENO in the child processes that you create using pipes and the dup2() system call (STDIN_FILENO and STDOUT_FILENO are in unistd.h). 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 6/11 The strategy here is: create a pipe in the parent, create the processes on either side of the pipe in the command sequence, then replace the STD{IN,OUT}_FILENO file descriptors on both sides just before running exec*(). Running your program Your program should take one argument as input, which is the name of the script script it should evaluate. Script files Here is a sample script file that you can use to test your implementation. The sequence of commands increase in complexity as you get further down in the file. The commands above depend on each other (e.g., ln -sf has to be run before head -5 words), so the sequence of execution is important. Assumptions You can make the following assumptions about script files: Each a line in a script file will never have more than 100 characters, each sequence of commands will fit completely on one line (i.e., you don’t have to handle commands that continue onto the next line). Each individual command will be a valid command (e.g., you will never have an individual command that has multiple redirect file to standard in < operators, the name of the program will be an actual program). If a command within a pipeline has redirection operators (>, <), it will only have one of those kinds of operators. In other words, a command won’t have a file redirected to its standard input and redirect its standard output to a file. The only command with the redirect standard input operator < will be the first command, and the only command with the redirect standard output operator > will be the last command. ./tmabsh script.sh touch touched.txt ln -sf /usr/share/dict/words head -5 words > first5words.txt cat /proc/self/status | grep nonvol > nonvoluntaryswitches.txt sort -R < words | head -5 > rand5words.txt sort -R < words | head -5 | sort -d > randsort5words.txt head -5 <(sort -R words) | sort -d > randsort5wordsprocsub.txt 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 7/11 Program names will be separated from their arguments using single whitespace characters. All commands within the script will execute successfully. While I encourage you to check the status code of the child process with wait, you’re explicitly not required to handle a command failing in the middle of the pipeline. Commands within process substitution are simple (i.e., no embedded pipes or redirection, no pipes, no recursive process substitution). Output substitution (e.g., >(cat)) is possible in POSIX shells, but you can safely assume that we will only evaluate your code using input substitution. Checking your output Since these are just regular commands, you can just run each of them in your actual shell and see what the output is. NOTE: Not all shells are created equally, and tcsh does not support process substitution. When you try to do output substitution on tcsh, you’ll get output similar to: You should use bash or zsh instead of tcsh on aviary when you get to the point of testing your implementation of process substitution. Starting bash or zsh on aviary is easy: just type in bash or zsh and press Enter. You can quit bash or zsh and get back to tcsh by typing exit and hitting Enter. Testing Please note that the graders will be using different scripts than the example shown above, but the scripts they are using will be limited to the features described above (e.g., redirection in and out, pipes, and process substitution). With that in mind, we strongly recommend that you write your own test scripts. Some ideas for what to use in your test scripts: Use other programs that redirect I/O (e.g., tee). Read contents from the /proc file system (as in lab 0) and pass them through pipelines in your script. Use other programs that filter I/O (e.g., grep). Whatever you choose to use, you should not be using interactive commands for testing, since none of the scripts the graders will run will be interactive in any way (remember: this is a non-interactive shell). Missing name for redirect. 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 8/11 Evaluation Code quality and design 5 points are awarded for code quality and design. “High quality” is defined as code that follows the standards and best practices that you can find in the “Standards and Best Practices” folder at the root of the Assignments section on UM Learn: Level Description The code is very poor quality (e.g., no comments at all, no functions, poor naming conventions for variables, etc). – The code is low quality, while some coding standards are applied, their use is inconsistent (e.g., inconsistent use of comments, some functions but functions might do too much, code is repeated that should be in a function, etc). This is the maximum level you can earn if the implementation of your program is substantially incomplete. – the code is high quality, coding standards are applied consistently throughout the code base. Implementation The implementation for this assignment is worth a total of 20 points (10 points × 2), and is separated into 3 parts: 1. Command-line parsing and redirection. 2. Piping. 3. Process substitution. Command-line parsing and redirection This part represents the basic implementation of your shell and is worth a total of 5 points. Level Description Parsing and redirection is not implemented at all. 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 9/11 Level Description – The implementation for parsing and redirection is beginning, but incomplete. This might mean that parsing is starting to be implemented, but doesn’t work for most pipelines run by the grader, or redirection doesn’t consistently work. It may also mean that very simple commands with no redirection works, but redirection itself does not work. – The implementation for parsing and redirection is substantially complete, but still incomplete. This might mean that parsing and redirection are substantially complete, but don’t work for all pipelines run by the grader. In other words, simple commands consistently work, but redirection only works sometimes. The implementation of parsing and redirection is complete. Piping General piping represents a slightly more complete implementation of a shell and is worth a total of 3 points. Note: you cannot earn points for piping unless you earn at least 3 points for parsing and redirection. In other words: if your shell does not minimally implement redirection, you cannot earn any points for piping even if it does partially work. Level Description Piping is not implemented at all or you did not earn at least points for parsing and redirection. – Piping is partially implemented. This might mean that it works, but inconsistently with the pipelines the graders use, or only works for a limited number of commands. Piping is completely implemented. Process substitution Process substitution represents a complete implementation of this shell and is worth a total of 2 points. Note: you cannot earn points for process substitution unless you earn at least 1 point for piping. In other words: if your shell does not minimally implement piping, you cannot earn any points for process substitution even if it does partially work. 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 10/11 Level Description Process substitution is not implemented at all or you did not earn at least point for piping. Process substitution is partially implemented. This might mean that it works, but inconsistently with the pipelines the graders use, or that it’s implemented in an inappropriate way (e.g., using temporary files). Process substitution is completely implemented. Submitting your assignment Submissions will be made using the handin command available on all CS UNIX systems. You should be submitting at least the following files: A Makefile. A README.md that includes a summary of how to compile and run your programs (compiling should be “run make”, but you should explicitly tell the grader how to run your program, e.g., what arguments to pass to the program on the command line). Your solution for question 1 (probably just 1 .c file). If your files are in a folder named my_a2, you would run the command: You can see man handin if you need more information. Advice Build this iteratively. In other words, don’t try to get complex command pipelines working as soon as you start. Instead, start with simple commands that take no arguments, then commands that take arguments, then redirection, then pipes, then process substitution. As suggested in Testing above, write scripts that contain these kinds of commands! Make sure that they always work as you’re changing things. Debugging handin 3430 a2 my_a2 2022/3/2 上午6:51 COMP 3430 - Operating Systems file:///C:/Users/12042/AppData/Local/Temp/360zip$Temp/360$13/assignments/assignment2/assignment.html 11/11 Debugging multi-process or multi-threaded C programs is tough! strace can minimally tell you which system calls are being made by which processes and can show you the arguments being passed to the system calls. This can help you figure out why your pipelines are getting stalled or stuck or blocked. strace has a “follow forks” option -f. See man strace for more information about how you can use this. You used strace with -o in lab 1, you should also look at the -e option for strace to limit the kinds of output that it produces instead of trying to filter through everything. You can use your debugger with fork. gdb has options follow-fork-mode and detach-on-fork that you can use to tell gdb which path of the fork it should follow for debugging (i.e., parent or child) and what should happen when a process is forked. You can use the info inferiors command in gdb to show the processes that are part of this process tree. Here are some resources that you can refer to about how to use this feature in gdb: https://sourceware.org/gdb/onlinedocs/gdb/Forks.html https://visualgdb.com/gdbreference/commands/set_follow-fork-mode https://visualgdb.com/gdbreference/commands/set_detach-on-fork https://www.youtube.com/watch?v=IGW8-yeYRgI Jacob says one thing that’s wrong in this video: calling fork() does not “create two processes”. Calling fork() creates one new process: the child. There are a total of two processes in your process group, but you’ve only asked the OS to create one new process. Note: lldb does not have this feature. More precisely, the versions of lldb on aviary, macOS, and WSL do not have this feature. If you really want to get lldb to have this feature, you’re going to have to build llvm from source. Do not recommend.
欢迎咨询51作业君
