※ [本文轉錄自 NTU-Exam 看板 #1KX-CA3O ] 作者: yangchris11 (歪彥) 看板: NTU-Exam 標題: [試題] 103-1 鄭卜壬 系統程式設計 期中考 時間: Wed Dec 10 14:07:04 2014 課程名稱︰系統程式設計 課程性質︰大二必修 課程教師︰鄭卜壬 開課學院：電資學院 開課系所︰資訊工程學系 考試日期（年月日）︰2014/11/19 考試時限（分鐘）：180min 試題 : Systems Programming (Fall,2014) Mid-Term Exam November 19, 2014 ========================================================================== 1. Answer the following questions. (20pts) (a) Where are the following data structures located? User space or kernel space. (4pts) Process control block: Open file descriptor table: File object (i.e.,FILE): V-node (or i-node) table: (b) Compare the difference (including definition and advantages) between advisory locking and mandatory locking. (4pts) Advisory: Mandatory: (c) Explain how file I/O benefits from using standard I/O library's buffer and kernel's buffer cache, respectively. Determine if they can save much in user CPU, system CPU, and clock (or response) time. (4pts) Standard I/O lib: Buffere cache: (d) Define buiult-in and external shell commands, respectively. Why should some commands be built-in or exyernal commands? Built-in: External: (e) The amount of disk space used by a file is integer multiples of disk block size. Explain (A) why the length of a file might be greater than its disk space and (B) why the disk space actually occupied by a file might be geater than its file length. (4pts) (A): (B): 2. Alice wants to write a server allowing people to upload their files via network connection simultaneously. Each connection from a client sends a request to upload a file to the server. Once the connection from a client is accepted by the server, Alice plans to design a loop, which iteratively * reads the data sent by the client via a new connected socket descriptor sock_fd, * writes the client's data to a file, and * synchronize standard C library's buffer or kernel's buffer cache if necessary, assuming that the file descriptor(or file stream) has been set up already. She's got several choices when developing such a program as follows: * I/O models for networking: blocking I/O, non-blocking I/O, multiplexing I/O * File I/O: buffered I/O, unbuffered I/O Buffered I/O: different buffer sizes Unbuffered I/O: character-at-a-time I/O, line-at-a-time I/O * Buffer/disk synchronization: fflush(), fsync() Please help Alice to make decisions. (a) Please specify multiplexing I/O and its advantages. (4pts) (b) Consider I/O models for networking. Which model saves the most in user CPU time? Which model wastes the most in user CPU time? Which model needs longer time to copy the data from the kernel to the process? Explain your answers. (6pts) (c) Please complete the following table for performance comparison between various settings. Assume blocking I/O is adopted as the network I/O model, the file to be uploaded is very large, and the problems of network traffic and system load are ignored here. The file system has 4K-byte blocks. The standard I/O library chooses the optimal size, i.e., 4K bytes, for buffering. In this table, the first line stands for the baseline, which considers the combination of unbuffered I/O, 4K buffer size, and no disk synchronization. A, B, and C are time in seconds. Please fill in the table with >X, <X, or X, where X is A, B, or C. Theymean the time required is much larger than, less than, and close to X, respectively. (13pts) graph : http://ppt.cc/Wi9b 3. Alice plans to develop an encryption program encrypt to encode an input file. The executable file is invoked as follow: $ ./encrypt <plaintext> -o <ciphertext> where <plaintext> is the input file to be encrypted ; <ciphertext> is the encrypted output file. To know what plain texts have been encrypted, the encrypt program logs statistics in the file /alice/logfile. The owner of the directory /alice is Alice; the file /alice/logfile is writable only by Alice. Alice sets the setuid bit on encrypt, ensuring that encrypt run by someone else can update /alice/logfile. (17pts) (a) If only Alice can insert and delete files in /alice, what minimum access rights (i.e.,read, write, and execute) should be used for the directory /alice? Only consider the owner class here. Your answer should be in the form of “rwx”, “r-x”, or the like. (2pts) Owner: (b) If Bob runs the following command successfully: $./encrypt /bob/plaintext -o ciphertext what minimum access rights should be used for the directory /bob? Only consider the other class here. (2pts) Other: (c) There is a security hole in the file encrypt. It's possible for Bob to update Alice's file /alice/testfile, which is writable only by Alice. Why? (3pts) (d) Alice tries to fix the problem mentioned in (c) by checking whether the "real" user can write <ciphertext> before opening it. Here is an excerpt from her code: int fd; if (access("ciphertext", W_OK) < 0) exit(-1); fd = open("ciphertext", O_WRONLY|O_TRUNC); Suppose the file ciphertext is owned and writable only by Bob. It is still possible for Bob to write Alice’s file /alice/testfile, which is writable only by Alice. Why? (4pts) (e) Please help Alice rewrite the excerpt so that access() and open() can be performed atomically. That is, either both of them are performed, or none are performed. Insert your code in Sections A and B. You could declare your own variables in Section A or create your own files if needed. Explain why your code works. (6pts) int fd; // Section A if (access("ciphertext", W_OK) < 0) exit(-1); fd = open("ciphertext", O_WRONLY|O_TRUNC); // Section B 4. Alice plans to write a program score to score students' programs. When issuing the following command, she wants score to call fork() to create three child processes. Each child process calls exec() to execute one program, i.e., prog-i (i=1..3). $ ./score prog-1 prog-2 prog-3 Each child process is asked to first read data from its standard input and then write the result to its standard output. The output will then be sent to score through a pipe. The parent process first writes data to each pipe and then reads the result from the pipe. Alice takes the left model into account, where pfdj (j=1..3) is the file descriptor used by pipe(). The model has three pipelines. It should allow the child processes to send data simultaneously and don't generate any zombie processes. The score program, i.e., score.c, is notcomplete. (28pts) int main( int argc, char *argv[] ) // score.c { int i, pid; // Section A for (i=1; i<argc, i++) { // Section B pid = fork(); if ( pid == 0 ) { // Section C execlp( argv[i], argv[i], (char *) 0 ); } // Section D } // Section E } (a) Fill the following form with the system calls pipe(), dup2(), close(), and wait() to build up the model. Unused file descriptors should be closed. You could declare your own variables in Section A. Sections A~E are the places where you could put your code in score.c. Error handling and data transferring (e.g., read() and write()) can be ignored. (10pts) (b) Deadlock may occur if both of the parent and the clients call fgets() and fputs() to access data via pipe. Please (1) define deadlock, and (2) explain why buffered I/O may lead to a deadlock. (6pts) (1): (2): (c) Deadlock may occur if Alice makes some changes in score.c, including changing fork() into vfork(), changing execlp() into _exit(0), calling read() followed by write() in Section C, and calling write() followed by read() in Section E. read() and write() are used to access data via pipe. Please (1) explain why such changes may lead to a deadlock, and (2) how does the copy-on-write technique speed up the execution of fork()? (6pts) (1): (2): (d) Alice serves as a TA for SP class. She wants each student to run score for submitting his/her program. In this case, only one child process is allowed. The program score not only checks if the output of the student' program prog-1 is correct but also writes the student's score into the file scorefile. Note that the owners of score and scorefile are Alice. The access permission of score is 04755 (octal value); the access permission of scorefile is 00600 (octalvalue). (1) There is a security hole. What is it? (2) Discuss if the problem can be fixed by running prog-1 as the parent and score as the child. The parent reads and then writes data through pipe; the child writes and then reads data through pipe. Explain your answer. (6pts) 5. Please answer the following file-system-related questions. (12pts) (a) How many i-nodes and data blocks will be visited when the file, /home/user/Alice/SP/assignment.c, is opened? Assume all directories and files are one block long. /home/user is a symbolic link pointing to /user; the others are all hard links. Briefly explain your answer. (4pts) (b) Why does any directory always have at least a (hard) link count of 2 ? (2pts) (c) When traversing a directory tree, we often need to know if a file has been visited to avoid a loop. However, each file may have multiple aliases in UNIX. Please give an effective way to detect if a file has been visited or not. (2pts) (d) Under what conditions are a file's contents really removed from a disk? (4pts) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.106 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1418191626.A.0D8.html

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: dyadi (140.112.16.135), 11/08/2017 16:40:32