課程名稱︰系統程式設計
課程性質︰大二必修
課程教師︰鄭卜壬
開課學院：電資學院
開課系所︰資訊工程學系
考試日期（年月日）︰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)