finalSprin12

<!doctype html public "-//w3c//dtd html 4.0 transitional//en">

CS 471
Operating Systems

Spring 2013
Final Exam

Time 2 & 1/2 hours

Open Book & Notes

Name:

Unix Login:

All questions are of equal weights.

Question 1:

Consider the following resource allocation graph:

A. If all processes makes no further requests, is the current system state is deadlocked or not? Explain?

B. Describe one possible scenario that may transform the above current system state into a deadlock state.

Question 2:

A. One possible memory management scheme is to allocate a contiguous memory block for each process.

Compare the following two possible allocation schemes:

Best-fit & Worst-fit

B. In virtual memory demand paging scheme, assume that:

1) memory access time is 200 nanoseconds,

2) average overhead page fault time is 8 milliseconds

3) page fault rate is 1% .

What is the effective memory access time?

C. Assume a two dimensional array M [265,256] is stored as one row per one memory page.

How many page faults are generated by the following two programs segments?

Segment 1:

for (j = 0; j <128; j++)
for (i = 0; i < 128; i++)
M[i,j] = 0;

Segment 2:

for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
M[i,j] = 0;

D. Assume we have program size of 9 pages and its reference sequence is:

7 5 4 7 9 5 9 2 1 6

Fill in the missing number of page faults in the following output:

Page Fault Counts:

W OP FF LR MR LF MF RN

2 8 9 9 9 8 8

3 7 7 8 7 9 7

4 7 7 7 7 7 7

5 7 7 7 7 7 7

6 7 7 7 7 7 7

7 7 7 7 7 7 7

8 7 7 7 7 7 7

9 .

E. Can you detect Belady’s Anomaly in the above output? Explain?

Question 3:

A. Write a program with the following description:

filelength <file>

The program prints the length of <file>.

For example:

% ls -l filelength*

-rwxr-xr-x 1 cs471w cs471w 8697 Apr 26 14:05 filelength

-rwxr-xr-x 1 cs471w cs471w 459 Apr 26 14:05 filelength.c

% filelength filelength

8697

% filelength filelength.c

459

B. Consider the following program:

filelock.c

char           *fname;
int count = 6;
int startTime;
main(int argc, char *argv[])
{
      startTime= time(NULL);
      signal(SIGCHLD, handleChild);
      fname = argv[1];
      if (fork() == 0)      Reader(1);
      else if (fork() == 0) Writer(1);
      else if (fork() == 0) Writer(2);
      else if (fork() == 0) Reader(2);
      else if (fork() == 0) Reader(3);
      else if (fork() == 0) Writer(3);
      else while (count > 0) pause();
      printf("ALL DONE\n");
      exit(0);
}
void handleChild(int sig)
{
wait(NULL);
   count-- ;
}
void Reader(int i)
{
     int             MyIndex = i;
     int             fd;
     if ((fd = open(fname, O_RDONLY)) < 0) {
           perror(fname);
           exit(1);
     }
     printf("Reader %d request read lock\n", MyIndex);
     read_lock(fd);
        printf("Reader %d obtained read lock and READING\n", MyIndex);
        sleep(5);
     unlock(fd);
     printf("Reader %d done after %d seconds\n", MyIndex, time(NULL) -startTime);
      exit(0);
}
void Writer(int i)
{
     int             MyIndex = i;
     int             fd;
      if ((fd = open(fname, O_WRONLY)) < 0) {
           perror(fname);
           exit(1);
     }
     printf("Writer %d request write lock\n", MyIndex);
     write_lock(fd);
        printf("Writer %d obtained write lock and WRITING\n", MyIndex);
        sleep(5);
     unlock(fd);
     printf("Writer %d done after %d seconds\n", MyIndex, time(NULL)-startTime);
      exit(0);
}
read_lock(int fd)
{                       /* a shared lock on an entire file */

      if (fcntl(fd, F_SETLKW, file_lock(F_RDLCK, SEEK_SET)) < 0) {
            perror("read_lock");
      }
}
write_lock(int fd)
{                       /* an exclusive lock on an entire file */

      if (fcntl(fd, F_SETLKW, file_lock(F_WRLCK, SEEK_SET)) < 0) {
            perror("write_lock");
      }
}
unlock(int fd)
{                       /* an exclusive lock on an entire file */

      if (fcntl(fd, F_SETLKW, file_lock(F_UNLCK, SEEK_SET)) < 0) {
            perror("write_lock");
      }
}
struct flock   *file_lock(short type, short whence)
{
      static struct flock ret;
      ret.l_type = type;
      ret.l_start = 0;
      ret.l_whence = whence;
      ret.l_len = 0;
      ret.l_pid = getpid();
      return &ret;
}

What is the output the following command:

% filelock filelock.c

Question 4:

A. Write the UNIX commands to create the following directory structure under /home/<user>:

D is a directory, F is file.

B. The following is the typical information kept about a file in UNIX.

Assume the following:

1) A data block pointer = 4 bytes.

2) Number of direct blocks = 10

3) A block size = 4000 bytes.

Calculate the maximum possible file size in blocks.

C. 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): 15 83 37 95 14 65

Head pointer: cylinder 50

Disk Scheduling Algorithm

FCFS

SSTF

C-LOOK

Total Head Movement

D. Consider the following program called mlist (similar to the one we have used at the beginning of this class)

that stores the user login into a file called mlistfile.

int main(void)
{
    int out;
    char *username;
    if ((out = open("mlistfile", O_CREAT | O_WRONLY | O_APPEND)) < 0) {
      perror("mlistfile");
        exit(1);
    }
    if ((username = getlogin()) == NULL) {
        fprintf(stderr, "Who are you?\n");
        exit(1);
    }
    write (out, username, strlen(username));
    write (out, "\n", 1);
    printf("%s: is added to mlistfile\n", username);
}

If the permissions of the mlistfile are:

-rwxr--r-- 1 cs471w cs471w 13 Apr 29 11:03 mlistfile

How to change the permissions of the mlist program to allow any user to store his login name in the mlistfile?

Question 5:

A. The following program scans every port at a give internet host to see if it can connect to that port. This program can be used as a basis to perform a denial of service attack on hosts.

As written, the program is very slow since the connect system call may take up to 2 minutes to return if the connection to the port is not successful.

To speed up this program, modify it to interrupt the connect system call if it took more than 1 second to connect to any port.

int main(int argc, char **argv)
{
     int sockfd;
     struct sockaddr_in servaddr;
     struct hostent *hp, *gethostbyname();
        int portnumber;

        hp = gethostbyname(argv[1]);

        bzero(&servaddr, sizeof(servaddr));
     servaddr.sin_family = AF_INET;
        bcopy (hp->h_addr_list[0], &(servaddr.sin_addr.s_addr), hp->h_length);

     for (portnumber = 1; portnumber < 128000; portnumber++) {

           sockfd = socket(AF_INET, SOCK_STREAM, 0);
           servaddr.sin_port = portnumber;
           if ( ! (connect(sockfd, (SA *) & servaddr, sizeof(servaddr)) == -1))
                     printf ("CONNECTED to port %d\n", portnumber);
           close(sockfd);
        }
}

B. DrWahab digital certificate contains his public key <7,10> and his corresponding private key is <3,10>.

Each of you selects a random symmetric key between 2 and 9.

Send your selected key it to DrWahab encrypted with his public key.

Show your selected key and show the corresponding encrypted value that will be sent to him:

Verify that DrWahab will be able to decrypt the received value and gets exactly the key you selected:

C. Assume that you and DrWahab agree to use XOR to encrypt messages exchanged between you and him.

Assume he send to you a message M = 6.

Show the value of the encrypted message that you will receive from DrWahab that corresponds to M:

Verify that the value you received from DrWahab is indeed the original value 6: