<!doctype html public "-//w3c//dtd html 4.0
transitional//en">
CS 471
Operating Systems
Spring 2010
Final Exam
Time 2 & 1/2 hours
Open Book & Notes
Name:
Unix Login:
Each Question is 20
points.
Question 1
A. Fill in the number of page faults in the following matrix, assuming the
following page reference string:
5 6
1 0 1
6 0 8
6 2
|
Working set size Page Replacement Algorithm |
1 |
2 |
10 |
|
Optimal |
|
|
|
|
Random |
|
|
|
|
FIFO |
|
|
|
|
LRU |
|
|
|
|
LFU |
|
|
|
|
MFU |
|
|
|
Question 2
A. Explain the meaning of s in the following
listing of the passwd file:
% cd /usr/bin
% ls -l passwd
-r-sr-sr-x 1 root sys 27228 Aug 16
2007 passwd
Answer:
B. Consider the following access matrix.
1.
Is
it possible for D1 to access the laser printer? Explain.
Answer:
2.
Is
it possible for D1 to access F2? Explain.
Answer:
Question 3
In
class we discussed the concepts of Blocking
and Nonblocking I/O:
Blocking
- process suspended until I/O completed
Nonblocking
- Returns quickly with count of bytes read or written
To
set a file descriptor fd to
Nonblocking we use the following system calls:
val = fcntl (fd, F_GETFL, 0);
fcntl (fd, F_SETFL, val | O_NONBLOCK);
Consider
the following 6 programs:
ServerX and ClientX, where X = 1, 2, 3.
Fill
in the following matrix with one of the following choices:
·
DD
= Definite Deadlock, the client and server are deadlocked
·
PD
= Possible Deadlock, the client and server may reach a deadlock state.
·
NC
= Normal Chatting, a message typed by
one “immediately” is seen by the other.
·
EC
= Erratic Chatting, a message typed by one “eventually” will be seen by the
other.
|
Clients Servers |
1 |
2 |
3 |
|
1 |
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
int
main(void)
{
int len, listenfd, connfd;
struct sockaddr_in servaddr,
cliaddr;
char buff[512];
int nread;
listenfd = socket(AF_INET,
SOCK_STREAM, 0);
bzero(&servaddr,
sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr =
htonl(INADDR_ANY);
servaddr.sin_port =
htons(10123);
bind(listenfd, (SA *) &
servaddr, sizeof(servaddr));
listen(listenfd, 0);
len = sizeof(cliaddr);
connfd = accept(listenfd, (SA *) & cliaddr,
&len);
ChatX(connfd);
}
int
main(int argc, char **argv)
{
int sockfd;
struct sockaddr_in servaddr;
struct hostent *hp,
*gethostbyname();
char buffer[512];
int nread;
sockfd = socket(AF_INET,
SOCK_STREAM, 0);
bzero(&servaddr,
sizeof(servaddr));
hp = gethostbyname(argv[1]);
bcopy(hp->h_addr,
&(servaddr.sin_addr.s_addr), hp->h_length);
servaddr.sin_family = AF_INET;
servaddr.sin_port =
htons(10123);
if (connect(sockfd, (SA *) & servaddr,
sizeof(servaddr)) < 0) {
perror("connect
error");
exit(-1);
}
ChatX (sockfd);
}
Void Chat1(int
sockfd)
{
int nread;
char buffer[512];
for (;;) {
nread = read(0, buffer, 512);
if (nread == 0) exit(0);
write(sockfd, buffer, nread);
nread = read(sockfd, buffer,
512);
if (nread == 0) exit(0);
write(1, buffer, nread);
}
}
void Chat2(int
sockfd)
{
int nread;
char buffer[512];
for (;;) {
nread = read(sockfd, buffer,
512);
if (nread == 0) exit(0);
write(1, buffer, nread);
nread = read(0, buffer, 512);
if (nread == 0) exit(0);
write(sockfd, buffer, nread);
}
}
void Chat3(int
sockfd)
{
int val, nread;
char buffer[512];
val = fcntl (sockfd, F_GETFL, 0);
fcntl (sockfd, F_SETFL, val | O_NONBLOCK);
val = fcntl (0, F_GETFL, 0);
fcntl (0, F_SETFL, val | O_NONBLOCK);
for (;;) {
nread = read(0, buffer, 512);
if (nread == 0) exit(0);
write(sockfd, buffer, nread);
nread = read(sockfd, buffer,
512);
if (nread == 0) exit(0);
write(1, buffer, nread);
usleep(1000);
}
}
Question 4
A. Calculate
the total head movement for servicing the following request Queue
according to the specified disk I/O scheduling algorithms.
Request Queue
(cylinder range 0-100): 83 37
14 24 65
Head pointer: cylinder 0
|
Disk
Scheduling Algorithm |
FCFS |
SSTF |
C-LOOK |
|
Total
Head Movement |
|
|
|
B. The following is the
typical information kept about a file in UNIX.
Assume the following:
·
A
data block pointer = 10 bytes.
·
Number
of direct blocks = 10
·
A
block size = 1000 bytes.
Calculate the maximum possible file size
in blocks.
Answer:
C.
To
keep track of the free disk blocks, one method is to use a Bit
vector where
Bit [i] = 0 means block i is occupied.
Assume a word length of 32 bits and the
prefix of the bit map is: 003
What is the index number of
the first empty block?
Answer:
Question 5
The following is an example of a general
directory structure.
A.
Draw
the director structure rooted at Q5 after executing the followingcommands:
% pwd
/home/cs471w/public_html/spring10/final
% mkdir Q5
% cd Q5
% mkdir D1 D2
% cd D1
% echo HI > F1
% echo BY > F2
% cd ../D2
% touch F3
% mkdir D3
% cd D3
% ln –s /home/cs471w/public_html/spring10/final/Q5/D1 F4
% ln F4/F1 F5
Answer:
B.
What
is the output of the following two statements:
% cat /home/cs471w/public_html/spring10/final/Q3/D2/D1/F5
Answer:
% cat /home/cs471w/public_html/spring10/final/Q3/D2/D3/F4/F2
Answer:
C.
Consider
the following three programs:
Q5R.c
int
main(int argc, char **argv)
{
int fd;
fd =
open("Q5file", O_RDONLY);
read_lock(fd);
printf("Q5R");
while
(1) sleep(20);
unlock(fd);
}
Q5S.c
int
main(int argc, char **argv)
{
int fd;
fd =
open("Q5file", O_RDONLY);
read_lock(fd);
printf("Q5S");
lseek(fd, 5, SEEK_SET);
read(fd,
buf, 5);
write(1,
buf, 5);
while
(1) sleep(20);
unlock(fd);
}
Q5W.c
int
main(int argc, char **argv)
{
int fd;
fd =
open("Q5file", O_WTONLY);
write_lock(fd);
printf("Q5W");
while
(1) sleep(20);
unlock(fd);
}
Assume
the contents of Q5file is: 0123456789
Fill
in the following matrix with the output of each program, assuming we have 4
open windows and in each window we execute one program as follows:
1st raw: execute Q5R then Q5R, Q5S and Q5W
2nd raw: execute Q5S then Q5R, Q5S and Q5W
3rd raw: execute Q5W then Q5R, Q5S and Q5W
If
no out is produced, enter: nothing
|
|
Q5R |
Q5S |
Q5W |
|
Q5R |
|
|
|
|
Q5S |
|
|
|
|
Q5W |
|
|
|