COSC 3250 / COEN 4820 Operating Systems
Midterm Examination 1
Wednesday, February 15, 2012

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

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:

  midterm 2000 midterm #1 2005 midterm #2 2005 midterm #1 2007 midterm #2 2007 midterm #1 2008 midterm #2 2008 midterm #1 2009 midterm #2 2009 midterm #1 2010 midterm #2 2010 midterm #1 2011 midterm #2 2011 midterm #1 2012 midterm #2 2012

  midterm #1 2013 midterm #2 2013 midterm #1 2014 midterm #2 2014 midterm #1 2015 midterm #2 2015 midterm #1 2016 midterm #2 2016 midterm #1 2017 midterm #2 2017 midterm #1 2018 midterm #2 2018 midterm #1 2019 midterm #2 2019

  final A 2000 final B 2000 final 2005 final 2007 final 2008 A final 2008 B final 2008 C final 2009 Wed, Fri final 2009 solutions final 2010 final 2011 final 2012 Mon, Fri final 2013 final 2014 final 2015 final 2016 final 2017 final 2018 final 2019

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:

Median: 72; Mean: 71.4; Standard Deviation: 18.3

These shaded block are intended to suggest solutions; they are not intended to be complete solutions.

Problem 1 Definitions
Problem 2 Process Context Switch
Problem 3 Processes and Threads
Problem 4 Interprocess Communication
Problem 5 Tricky C

Give careful definitions for each term (in the context of computer operating systems):

1. Batch system
2. Client-Server computing
3. Clustered systems
4. Process
5. Protection
6. Virtual machine
7. Message passing systems
8. IPC
9. Real-time system
10. Kernel
11. User mode
12. Kernel mode

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

1. Batch system: Typically large, no user present. E.g., overnight accounting runs, daily update of Checkmarq records. Batch mode is an old business data processing mode, still VERY widely used in mainframe business data processing.
2. Client-Server computing: See Sections 1.12.2. Client-server is a master-slave relationship. Client requests, server answers. Which is the master?
3. Clustered systems (p. 16) Two or more individual (computer) systems gathered together to accomplish computational work.
4. Process (p. 81) Program in execution, a unit of work in a modern time-sharing system.
5. Protection: See Section 1.9. Protection controls access to computer system resources. Security defends a system from internal and external attacks.
6. 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.
7. Message passing systems: A mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space. A message-passing facility provides at least two operations: send(message) and receive(message). (Sect. 3.4.2, p. 119) Be careful to avoid circular definitions: "Message passing systems pass messages" counts zero points.
8. IPC: Interprocess Communication: shared memory and message passing. (Sect. 3.4 & 3.5) It is important to know at least some of the TLAs (Three Letter Abbreviations)
9. Real-time system: Typically time-sensitive interaction with external devices, p. 29.
10. Kernel: Part of the OS that is running all the time, core OS processes, p. 6.
11. User mode
12. Kernel mode: User mode and Kernel mode: See Section 1.5.1. User mode is a state of the operating system in which most instructions of user applications are executed. Kernel mode is a state of the operating system in which some critical portions of the operating system is executed. What is it called when a user process makes an operating system call for service? Most operating system code is executed in user mode.

In the context of scheduling and dispatching of processes on a single-core processor,

1. (5 points) What is the purpose of a context switch?
2. (20 points) Describe the steps, in order, taken by a kernel to context-switch between processes.

I have asked this question five times on previous exams, and I announced in class last Friday you should expect a question about the homework.

See Problem 3.2, p. 116. This question foreshadows what you must do in Homework 4

Context switch changes which process holds the CPU. It does not interrupt a running process, nor does it do the work of the scheduler to determine which is the next process to run.

At a high level:

1. Save state of old process on the stack
2. Save Stack Pointer into the Process Control Block of the old process
3. Load Stack Pointer from the Process Control Block of the new process
4. Restore the state

How is control handed over to the incoming process? (or -5)

Think for a moment. Can you write code to save or to restore the Program Counter? No. Why not? In our design, the last instruction executed by the context switch is RETURN, as if from a function call.

Could the use of "kernel" in this question offer a hint for parts of Problem 1?

The code below (Figure 4.14 in our text) uses the Pthreads API:

#include <pthread.h>
#include <stdio.h>

int value = 0;
void *runner(void *param); /* the thread */

int main(int argc, char *argv[]) {
  int pid;
  pthread_t tid; /* the thread identifier */
  pthread_attr_t attr; /* set of attributes for the thread */

  pid = fork();
  if (0 == pid) {  /* Child process */
      pthread_attr_init(&attr);
      pthread_create(&tid, &attr, runner, NULL);
      pthread_join(tid, NULL);
      printf("CHILD : value = %d\n", value);  /* LINE C */
  }
  else if (0 << pid) {  /* Parent process */
      wait(NULL);
      printf("PARENT: value = %d\n", value);  /* LINE P */
  }
}

/*  The thread will begin control in this function   */
void *runner(void *param) {
  value = 5;
  pthread_exit(0);
}

1. (5 points) Describe the action of pid = fork();
2. (5 points) Describe the action of pthread_create(...);
3. (5 points) What is printed at LINE C and LINE P?
4. (10 points) Explain

See problem 4.13, p. 175.

1. See Section 3.3.1. fork() allocates space for a Process Control Block, acquires resources (esp. memory) needed by the process, copies parent's memory to child, puts child on the ready list, returns the PID of the child to the parent, and returns 0 to the child process.
2. pthread_create(...) allocates space for a Thread Control Block, acquires resources (esp. memory) needed by the thread, initializes local memory for the thread, sets the Program Counter of the thread to point to the code for runner, places the thread in the ready list, and returns to the calling process.
3. I get

   CHILD : value = 5
   PARENT: value = 0

4. fork() returns twice, once to the parent process, and once to the child process. We can make no assumptions about which process gets to run first. When it runs, the parent process waits for the child process to finish, whereupon it prints its value, which is 0. When it runs, the child process creates a (sub-)thread. The thread shares the global variable value with its process (the child). The thread changes the child proccess's value to 5 and exits. Meanwhile, the child process itself has been waiting at pthread_join() for the thread to finish, whereupon it prints its value, which is 5. Then the child process terminates, and the parent completes its WAIT(), and prints 0.

The producer-consumer problem is a common example of cooperating processes. A producer process produces information (e.g., a sensor reading) that is consumed by a consumer process (e.g., detect sensor reading out of range). Often, the producer process and the consumer process communication using a bounded buffer.

#define BUFFER_SIZE 10

typedef struct {
   . . .
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

1:
2:
3:
4:
5:
6:
7:
8:
9:

item nextProduced;
 
while (1) {
   /* produce an item in nextProduced */
    while (((in + 1) % BUFFERSIZE) == out)
       ;  /* do nothing */
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
}

1:
2:
3:
4:
5:
6:
7:
8:
9:

item nextConsumed;

while (1) {
    while (in == out)
       ;  /* do nothing */
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    /* consume the item in nextConsumed */
}

You may assume that the machinery for sharing the memory locations for buffer, in, and out has been accomplished correctly by appropriate operating systems calls.

1. Assume that it happens that the Consumer Process happens to be the first to run. Assume that the Consumer Process is allowed to run for about 1000 machine cycles (the exact number is not relevant, but I want to quantify "It gets to run for a long time."). Explain what happens. Your explanation should address
         any changes to any of the shared variables, and
         the flow of control (which statements in the Consumer Process execute).
2. Assume that the Consumer Process eventually is swapped out, and the Producer Process gets its chance to run. Assume that the Producer Process is allowed to run for about 1000 machine cycles (the exact number is not relevant, but I want to quantify "It gets to run for a long time, plenty of time to full the buffer"). Explain what happens. Your explanation should address
         any changes to any of the shared variables, and
         the flow of control (which statements in the Producer Process execute)
3. Your answers to both parts a) and b) should have described a significant waste of computer resources we call "busy waiting." For this part of the problem, assume we have re-started both processes, so they are just ready to start, with the shared memory variable having their values as initialized in the code. Describe one very fortunate sequence of executions which does not suffer from busy waiting. Your answer might take the form:
         ____ process runs until ___
         ____ process runs until ___
         ____ process runs until ___
         etc.
   Your answer should demonstrate clearly that you understand how it would be possible to produce and consume thousands of items with no busy waiting. You are not expected to explain how one could be so fortunate.

See p. 118 in our text.

1. If the Consumer process happens to run first, it will get to its line 4 and find in == out == 0, so the condition in line 4 is TRUE, and the Consumer Process will be in an indefinite loop at lines 4 & 5.
2. If the Consumer Process is interrupted and the Producer process gets its chance to run (you are not responsible for describing how that might happen), the Producer Process fills locations 0, ..., 8 in the buffer. When line 7 fills location 8, line 8 sets in to 9, the condition in line 5 becomes TRUE, and the Producer Process is stuck busy waiting at lines 5 & 6.
3. Any sequence of precesses activations that keep the buffer non-empty and non-full will work. The easiest is
         Produce one item
         Consume one item
         Produce one item
         Consume one item
         etc.

Here's a Tricky C question for you from HW1: Consider the function below. You may assume that K&R's getch() function is available.

#include <ctype.h>

unsigned char EUR[] = {0xE2, 0x82, 0xAC, 0x00}; // UTF-8 string for Euro
unsigned char USD[] = {'$', 0x00};

unsigned long getSymbol(void)
{
	int c;
	char *symbol;
	
	while (isspace(c = getch()))  // Throw out whitespace.
		;
	
	if (c = EUR[0])           // Check for Euro symbol.
	{
		c = getch();
		if (c == EUR[1])
		{
			if (c == EUR[2])
			{
				symbol = EUR;
			}
		}
	}
	else if (c == USD[0])     // Check for dollar sign
	{
		symbol = USD;
	}
	else                      // Fallback.
	{
		symbol = "?";
	}
	// Print the string for the currency symbol we found or '?'.
	printf("Currency is %s\n", symbol);
}

1. the Euro symbol?
2. the dollar sign?
3. some other currency symbol?
4. spaces, carriage returns and tabs, followed by a dollar sign?

Read what the code DOES, not what you think is is SUPPOSED to do! If you try to read the programmer's mind, you get an error message, "None found!"

Depending on how you look at it, there are (at least) three errors here:

1. if (c = EURO[0]) is perfectly valid C, but it probably is not what the programmer intended. It always evaluates to TRUE, in this program since EUR[0] is not NULL.
2. Before if (c == EUR[2]), we probably want another c = getch();
3. Because of 1) and 2), execution can get to the printf() statement without the variable *symbol being initialized. Perhaps we should have initialized char *symbol = "?"; at the top?
4. Nothing is returned.
5. You might observe that you need #include <stdio.h> in order for printf() to link (it will compile fine anyway). I did not worry about that, since you also need a main() from which getSymbol() is called.

Constructs such as char *A and char A[] are equivalent. In some sense, arrays and pointers are (nearly) interchangable.

Soooo..., to attempt to answer the questions:

1. The second nested if-statement does not call getch() to read in the third character of the Euro symbol, so the third if-statement will always be false, and symbol will not be set to the EUR string. Output will be undefined because char *symbol was not initialized.
2. The first if-statement contains an assignment rather than a comparison, and this is always true unless the null character is read from input. The else clause for the dollar sign is therefore never reached, and symbol again does not get set. Output will be undefined because char *symbol was not initialized.
3. Again because of the assignment in the first if-statement, the else clause with the question mark is never reached. Output will be undefined because char *symbol was not initialized.
4. The while loop with isspace() is the only correct part of this function, and it will correctly ignore any whitespace preceding currency symbols. However, for the reasons above, it never ends well.

Did we warn you this was a trick question?

If you did not catch the errors, you got no where. I gave partial credit if you were totally wrong, but clearly confused, since "confused" is a VERY appropriate response to this code. A confused response earned a better partial score than a response suggesting the code ran as was apparently intended. DON'T EVER WRITE CODE LIKE THIS! ! !

I gave 5 of 25 points for the WRONG answers "EUR", "USD", "$", respectively as a form of curving the scores.

By the way, I have heard reports of our Tricky C exam questions showing up as job interview questions. One interviewee responded, "Oh, you must have gotten that from Dr. Bylow's operating systems exam!" She got the job.