Midterm Examination 1

Your first midterm examination will appear here. It covers Chapters 1 - 3.

It will be a period-long, closed book exam.

Expectations:

See course goals and objectives
See Objectives at the beginning of each chapter
See Summary at the end of each chapter
Read, understand, explain, and desk-check C programs

See previous exams:

Questions will be similar to homework questions from the book. You will be given a choice of questions. I try to ask questions I think you might hear in a job interview. "I see you took a class on Operating Systems. What can you tell me about ...?"

See also Dr. Barnard's notes. He was using a different edition of our text, so chapter and section numbers do not match, but his chapter summaries are excellent.

Directions:

Read and follow the directions.

Write on four of the five questions. If you write more than four questions, only the first four will be graded. You do not get extra credit for doing extra problems.
Each question is worth 25 points.
Read the entire exam. If there is anything you do not understand about a question, please ask at once.
If you find a question ambiguous, begin your answer by stating clearly what interpretation of the question you intend to answer.
Begin your answer to each question at the top of a fresh sheet of paper. [Or -5]
Please do not staple your sheets together.
Be sure I can read what you write.
Write only on one side of a sheet.
Be sure your name is on each sheet of paper you hand in. [Or -5]

Score Distribution:

Exam Scores

Problem 1 Definitions

List six categories of system calls
Give two examples from each category
Give careful definitions for each term (in the context of computer operating systems):
1. Operating system
2. Process
3. Clustered systems
4. Time sharing
5. User mode vs. kernel mode
6. Virtual machine
7. Kernighan's Law

Warning: A definition that starts "Z is when ...," or "Z is where ..." earns -5 points.

(11 points) Types of system calls (p. 58, Fig. 2.8): process control, file manipulation, device manipulation, information maintenance, communications, and protection

(14 points; 2 points each) Definitions:

Operating system (p. 3) A program that manages the computer hardware, provides a basis for application programs, and acts as an intermediary between the computer user and the computer hardware.

Process (p. 81) Program in execution, a unit of work in a modern time-sharing system.

Clustered systems (p. 16) Two or more individual (computer) systems gathered together to accomplish computational work.

Time sharing (p. 19) The CPU executes multiple jobs by switching among them, but the switches happen so frequently that the users can interact with each program while it is running.

User mode vs. kernel mode (p. 21) Modes of execution of the CPU are controlled by a mode bit. In user mode, the computer system is executing on behalf of the user. In kernel mode, the system is executing on behalf of the operating system.

Virtual machine (p. 76+) Abstract the hardware of a single computer into several different execution environments, creating the illusion that each computing environment is running its own private computer.

Kernighan's Law (p. 85) "Debugging is twice a hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it."

Problem 2 Tricky C Program

Consider execution of the program shown below. Comments and print statements do not necessarily tell the truth.

How many times is the if statement at line 29 executed? Why?
How many times is the if statement at line 35 executed? Why?
How many times is the if statement at line 38 executed? Why?
How many times is the if statement at line 46 executed? Why?
What output is printed to the screen? You may assume all operating systems calls are successful so no fprintf(stderr, ...) statements are executed. Some of the numerical values printed you should know, and some values you cannot know in advance.
(10 of the 25 points) Explain.
Still assuming correct and successful operating systems calls, would it be possible for the output from lines 71 - 78 to be different from what you described in part f)? Explain.

  1 /* Derived from: http://www.cs.cf.ac.uk/Dave/C/node25.html */
  2  
  3 #include <sys/types.h>
  4 #include <sys/ipc.h>
  5 #include <sys/msg.h>
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 #define  MSGFLG (IPC_CREAT | 0666)
 10 #define  MSGSZ     128
 11 
 12 typedef struct msgbuf {   /* Declare the message structure */
 13          long    mtype;
 14          char    mtext[MSGSZ];
 15 } message_buf;
 16 
 17 
 18 void consumer(int msqid, int numberOfMessages);
 19 void producer(int msqid, int numberOfMessages);
 20 
 21 int main()
 22 {
 23     int msqid;
 24     int numberOfMessages = 5;
 25     key_t key = 1236;
 26     pid_t pid;
 27 
 28     printf("In MAIN, get message queue id\n");
 29     if (0 > (msqid = msgget(key, MSGFLG ))) {
 30         fprintf(stderr, "msgget failed\n");
 31         exit(-1);
 32 	}
 33 	
 34     printf("msgget succeeded: msqid = %d. Fork child process ONE.\n", msqid);
 35     if ( 0 > (pid = fork()) ) {  /* fork a child process */
 36         fprintf(stderr, "fork() failed.\n");
 37         exit(-1);
 38     } else if (0 == pid) {
 39         printf("In child process ONE\n");
 40         consumer(msqid, numberOfMessages);
 41         printf("Child ONE is done\n");
 42         exit(0);
 43     }
 44     
 45     printf("In PARENT after ONE.  pid =  %d.  Fork child process TWO.\n", pid);
 46     if ( 0 > (pid = fork()) ) {  /* fork a child process */
 47         fprintf(stderr, "fork() failed.\n");
 48         exit(-1);
 49     } else if (0 == pid) {
 50         printf("In child process TWO\n");
 51         producer(msqid, numberOfMessages);
 52         printf("Child TWO is done\n");
 53         exit(0);
 54     }
 55     
 56     printf("In PARENT after TWO.  pid =  %d\n", pid);
 57 
 58     wait(NULL); /* parent waits for children to complete */
 59     printf("PARENT is done\n");
 60     exit(0);
 61 } 
 62 
 63 
 64 void consumer(int msqid, int numberOfMessages) {
 65     message_buf  receive_buf;
 66     int i = 0;
 67     int ans = 100;
 68 
 69     printf("Child ONE, consumer ...\n");
 70     
 71     while (0 < ans) {
 72         if (0 > msgrcv(msqid, &receive_buf, MSGSZ, 1, 0)) {
 73             fprintf(stderr, "msgrcv failed\n");
 74             exit(-1);
 75         }
 76         ans = receive_buf.mtext[0] - '0';
 77         printf("   Received message %2d: %s --> %d\n", i, receive_buf.mtext, ans);
 78     }
 79 }
 80 
 81 void producer(int msqid, int numberOfMessages) {
 82     message_buf send_buf;
 83     int buf_length;
 84     int i;
 85     char ans[MSGSZ];
 86 
 87     printf("Child TWO, producer ...\n");
 88     
 89     send_buf.mtype = 1;
 90     for (i = 3; i <= numberOfMessages; i++) {
 91         send_buf.mtext[0] = '0' + (i % numberOfMessages);
 92         send_buf.mtext[1] = 0;
 93         buf_length = strlen(send_buf.mtext) + 1 ;
 94     
 95         printf ("Send a message: %s\n", send_buf.mtext);
 96         if (0 > msgsnd(msqid, &send_buf, buf_length, IPC_NOWAIT)) {
 97             printf ("msgsnd failed.  %d, %ld, %s, %d\n", msqid, send_buf.mtype, send_buf.mtext, buf_length);
 98             exit(-1);
 99         }
100     }
101 }

Once

Twice. fork() returns twice, once in the parent, and once in the child. Each parent and child evaluates the Boolean expression once.

Twice, once in the parent, and once in the child.

Twice. The first child created at line 35 exits at line 42. Hence, line 46 is executed in the parent, but not in the first child. Then, fork() returns twice, like the fork() at line 35, having created a second child.
I get
     In MAIN, get message queue id
     msgget succeeded: msqid = 65538. Fork child process ONE.
     In PARENT after ONE.  pid =  38280.  Fork child process TWO.
     In PARENT after TWO.  pid =  38281
     In child process ONE
     Child ONE, consumer ...
     In child process TWO
     Child TWO, producer ...
     Send a message: 3
     Send a message: 4
     Send a message: 0
     Child TWO is done
        Received message  0: 3 --> 3
        Received message  0: 4 --> 4
        Received message  0: 0 --> 0
     Child ONE is done
     PARENT is done
Depending on preemptive scheduling, printing from the first and second child processes could be different.
Lines 35 and 46 create two child processes, in which the functions consumer() and producer(), respectively, are called. We cannot know which of those functions will execute first.
Suppose child ONE happens to call consumer() first, as in my sample run. consumer() blocks at line 72, waiting to receive a message. Eventually, child TWO runs, and producer() sends messages at line 96. producer() sends messages for i = 3, 4, and 5 with string values "3", "4", and "0". Eventually, child ONE runs, and consumer() receives the messages and prints them.

It could be that child ONE and child TWO alternate execution, in which case Send and Received printf lines would alternate. We can make no assumptions about the relative progress of two processes.
Since the mailbox is owned by the operating system, it is entirely possible for other processes to be sending and receiving from the same mailbox. In that case, child ONE could receive messages child TWO did not send, and child TWO could send messages child ONE did not receive.
In an earlier draft of this question, I was going to give you this code, give you output showing child ONE receiving several message before the three sent by the producer(), and asking you to explain how that could be.
More tricky? In general, the number of messages sent by the producer() and the number of messages received by the consumer() do not have to be the same. A slight change to line 91?
That ( (not many students attempted this problem) AND (those who did earned low scores) ) suggests shared memory and fork() may warrent further study before the next exam.

Problem 3 Create and Terminate Processes

What action or event causes a new process to be created?
List at least five actions the operating system must accomplish to create a new process.
Hint: You might answer with high-level pseudo-code.
List at least four actions or events that cause an existing process to terminate.
List at least five actions the operating system must accomplish when it terminates an existing process.
Hint: You might answer with high-level pseudo-code.

Does this sound like Assignment 4? It should.

(4 points) Call to fork()

(7 points) fork() must create a new process:

Assign space for a Process Control Block (PCB) in the memory space of the operating system;

Insert the PCB for the new process in the Ready list;

Assign appropriate values to fields in the PCB;

Allocate memory space for the process;

Copy contents of the memory space of the current process to the memory space allocated for the new process,
OR
Load the memory space for the new process with its executable (probably from disk);

Set the Program Counter in the PCB to the address to which fork() should return,
OR
Set the Program Counter in the PCB to the address at which execution of the new image should begin;

Return to executing the current process at the address to which fork() should return. In principle, fork() could call the scheduler() to pick the next process to run, but in practice, it returns control to the calling process just as any normal function does.

(7 points) Causes of termination include:

The process terminates itself with a call to exit().

The process terminates itself by finishing normally. A well-behaved process always calls exit(), but the operating system must clean up after non-well-behaved processes what finish normally without calling exit().

The process terminates itself by finishing abnormally (crashing). The operating system must clean up after non-well-behaved processes what crash without calling exit().

Another process kill()'s the process in question.

Operating system kill()'s the process in question.

Operating system shuts down or crashes.

(7 points) Essentially, reverse the actions of fork():

Close any open files;

Release memory allocated to this process;

Release any other resources allocated to this process;

Notify any processes that might be waiting to this process to do something (e.g., send a message, terminate);

Remove this PCB from Running, Waiting, or Ready lists;

Mark PCB memory space as available for re-use;

Which process executes next?

A terminating process does not return a value, nor does it report to a user. If it wanted to report, it should have done that before it terminated.

Do not exaggerate the presence of "the user." In many systems, there is no user.

Problem 4 State Diagram for a Process

Besides the Start/Create state and the Stop/Terminated state suggested by Problem 2, list the three most common states of a process.
Draw a UML-like State Diagram showing Start/Create and Stop/Terminated states and the three states you listed in part a).
Show and label transitions (or -2 points) among the five states.
For each of the three states you listed in part a),
- describe what that state represents,
- how/why a process enters that state,
- what happens while it is in that state, and
- how/why a process leaves that state.

(3 points) Ready, Running, Waiting (or Blocked). I/O is one example of a wait state.

(7 points) Figure 3.2, p. 103

(15 points; 5 points each) Running: Represents the process that controls the Program Counter of the CPU
Enters by action of the Scheduler choose it from the ready list
Happens: Its code executes
Leaves to Terminated state when it finishes normally or abnormally
Leaves to Ready state when interrupted by the timer
Leaves to Waiting state by executing an operating system call for a resource which is not immediately available
A Running process cannot be interrupted by another process, because it owns the CPU. No other process has a chance to run.
Ready: Represents a list of processes that have all resources they need to run
Enters from New state when created by fork()
Enters from Running state when interrupted by the timer
Enters from Waiting state when the resource for which it was waiting becomes available (e.g., I/O complete, message received)
Happens: It waits
Leaves to Running state when selected by the Scheduler
Leaves to Terminated state when killed by operating system or another process
A Ready process cannot do anything, since it has no access to the CPU.
Waiting/Blocked: Represents queues of processes waiting for various system resources
Enters from Running state when the running process executes an operating call requesting a resource which is not immediately available. There are circumstances under which a process is moved to a Wait state as a result of an interrupt, but it is much more common to move because of an OS call made by the process itself.
Happens: It waits
Leaves to Ready state when the resource for which it was waiting becomes available (e.g., I/O complete, message received)
Leaves to Terminated state when killed by operating system or another process
A Waiting process cannot do anything, since it has no access to the CPU.

Many students failed to answer directly

describe what that state represents,

how/why a process enters that state,

what happens while it is in that state, and

how/why a process leaves that state.

A process waits for resources, not on them. "Wait for has the general meaning of anticipate/expect something to happen, as in wait for a bus, or wait for the rain to stop before going out, or wait for a letter to arrive. Wait on is in a way serve/act as servant." -- www.english-test.net/forum/ftopic5010.html

Problem 5 Inter-process Communication via Shared Memory

Consider two processes described by this pseudo code:

Process P0			Process P1
	10 int sharedA = 1; 20 . . . 30 sharedA++; 40 . . . 50 printf("P0. A = %d\n", sharedA);			10 int sharedA = 5; 20 . . . 30 sharedA++; 40 . . . 50 printf("P1. A = %d\n", sharedA);

You may assume

Variable sharedA is correctly set up as an integer memory location shared by Processes P0 and P1.
The memory location sharedA is shared by no other processes.
The omitted code fragments denoted by " . . . " contains no references to sharedA.
Processes P0 and P1 run correctly, with no side effects or crashes.
Processes P0 and P1 are two of many processes running on one processor with a timer interrupt-driven process scheduling strategy. That is, any process can be interrupted at any time in its execution and swapped out.

What is printed when these two processes are executed? Give all possible different sets of correct values. Your answer is a set of order pairs (P0 A = ?, P1 A = ?).

Explain.

Hints: This question is about the interplay between shared memory and process scheduling.

Your explanations are more important than your values.

There are several possible values. You must give them all.

Possible pairs of values (P0, P1) include (2, 6), (6, 7), (7, 6), (7, 7), (2, 3), (3, 2), (3, 3), (2, 2), (6, 6), (5, 6), (2, 1).
Case 1 (P0, P1) = (2, 6): P0 runs completely. Then P1 runs completely:
      P0. A = 2
      P1. A = 6
Case 1a (P0, P1) = (2, 6), printed reversed: P1 runs completely. Then P0 runs completely:
      P1. A = 6
      P0. A = 2
Case 2 (P0, P1) = (6, 7): P0 starts and is interrupted at line 20 [A = 1]. Then P1 starts and is interrupted at line 20 [A = 5]. P0 resumes and finishes [A = 6]. P1 resumes and finishes:
      P0. A = 6
      P1. A = 7
Case 3 (P0, P1) = (7, 6): P0 starts and is interrupted at line 20 [A = 1]. P1 runs completely [A = 6]. P0 resumes and completes:
      P1. A = 6
      P0. A = 7
Case 4 (P0, P1) = (7, 7): P0 starts and is interrupted at line 20 [A = 1]. P1 starts and is interrupted at line 40 [A = 6]. P0 resumes and completes [A = 7]. P1 resumes and completes:
      P0. A = 7
      P1. A = 7
Case 5 (P0, P1) = (3, 2): P1 starts and is interrupted at line 20 [A = 5]. Then P0 starts and is interrupted at line 20 [A = 1]. P1 resumes and finishes [A = 2]. P1 resumes and finishes:
      P1. A = 2
      P0. A = 3
Case 6 (P0, P1) = (2, 3): P1 starts and is interrupted at line 20 [A = 5]. P0 runs completely [A = 2]. P1 resumes and completes:
      P0. A = 2
      P1. A = 3
Case 7 (P0, P1) = (3, 3): P1 starts and is interrupted at line 20 [A = 5]. P0 starts and is interrupted at line 40 [A = 2]. P1 resumes and completes [A = 3]. P1 resumes and completes:
      P0. A = 3
      P1. A = 3
Case 8 (P0, P1) = (6, 6): P0 starts and is interrupted at line 20.
P1 starts and is interrupted in the middle of its execution of line 30
P0 resumes and runs to completion
P1 resumes and runs to completion
      P0. A = 6
      P1. A = 6
This is WRONG, under any reasonable interpretation of that these processes should do.
Case 9 (P0, P1) = (2, 2): P1 starts and is interrupted at line 20.
P0 starts and is interrupted in the middle of its execution of line 30
P1 resumes and runs to completion
P0 resumes and runs to completion
      P1. A = 2
      P0. A = 2
Again, this is WRONG.
This is a race condition. The problem is much more interesting if initialization is separate and/or modifications to the shared memory location are more complicated or more diffuse.

Marquette University. Be The Difference.

Marquette | Corliss |