Marquette University logo      

Midterm Examination 1

 

Your first midterm examination will appear here. It covers through Chapter 4.

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

Expectations:

Questions will be similar to homework questions from the book. You will be given a choice of questions, e.g., "Write on four out of five 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.

Homework on your own:

Questions similar to these might appear on exams:

  • Chapter 2: 2.3, 2.8, 2.14, 2.15
  • Chapter 3: 3.2, 3,3, 3.4, 3.5
  • Chapter 4: 4.2, 4.3, 4.4, 4.6, 4.8

Any others are fair game, too.

Question:

Are you trained somewhere that to write in paragraphs? Yes, that is often the preferred means, but in many technical circumstances, including this exam, outlines, enumerations, bullets, and pictures may communicate more effectively. At the very least, you should answer by question parts:

  1.  
  2.  
  3.  

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.
  • 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]
  • 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:

 

 

Problem 1 Structure of an Operating System

Describe the basic structure of an operating system.

Taken from Course Objectives

See Section 1.4, or see the book's Table of Contents:

  • Provides an environment in which programs are executed
  • Manages processes
  • Provides interprocess communication
  • Manages memory
  • Manages file systems
  • Manages mass storage
  • Manages I/O
  • Manages network communications
  • Provides protection and security

You might also mention

  • Layers
  • Bootstrapping
  • Kernel vs. user level
  • User interface, although, what is the UI for an embedded OS?
  • Interrupt handling
  • . . .

Components might be

  • Process manager
  • Interprocess message manager
  • Memory manager
  • File manager
  • Disk manager
  • I/O Manager
  • Protection manager
  • Network manager
  • Interrupt handler
  • User interface

Problem 2 Tricky C

Here is a tricky C program:

#include <stdlib.h>
#include <stdio.h>

#define MAX 127
int i = 23456;

int getNumber(void)
{
	printf ("In getNumber, i = %d\n", i);
	return ++i;
}

void main(int argc, char** argv)
{
    int *array;
    int index = 0;
    int current = 0;
    int j = 0;

    while ( EOF != (current = getNumber()) )  /* EOF has the value -1 */
    {
    	printf ("In while, index, current = %d, %d\n", index, current);
    	if (! index) { array = (int *)malloc(MAX); }
    	array[index++] = current;
    	index &= MAX;
    }
    for (; j < index; j++)
    {
    	printf("%10d: %10d\n", j, array[j]);
    }
}

What does it print? Explain.

When I run it with a particular compiler, I get 
In getNumber, i = 23456
In while, index, current = 0, 23457
In getNumber, i = 23457
In while, index, current = 1, 23458
 . . .
In getNumber, i = 23583
In while, index, current = 127, 23584
In getNumber, i = 23584
In while, index, current = 0, 23585
*** [a] Error -1073741819
Dr. Brylow writes:
Looks like it ought to read and store an arbitrary list of numbers, but it has three major problems: the malloc size is only one fourth of what is intended, the return value from malloc() is not checked against NULL, and most importantly, each successive dynamically allocated block is lost because the pointers aren't being stored anywhere else. Also, it is just badly written, with the last line depending on a fragile property of the MAX constant being one less than a power of 2.

Having a macro named "EOF" does not imply there is a file anywhere. That is bad, confusing programming practice. It violates the Principle of Least Astonishment, but it runs, and you will see worse in the wild.

Several students suggested one of the counters might overflow. Try it. What happens?

Scores on this problem suggest you may need to see tricky C programs on subsequent exams. Be warned.

Problem 3 Processes

Suppose we wish to construct a class Process {...} to encapsulate data and operations for a process

  1. List at least six attributes a class Process should have. For each, give in a pseudo code
    1. Meaningful name
    2. Data type
  2. By what name does our text refer to the set of attributes of our class Process? Explain.
  3. In an object-oriented design, our class Process has a constructor Process( ... ). List the tasks that must be accomplished by the constructor.
  4. What operating system call we have studied is the place from which the constructor Process() logically is called? Explain.
  5. In an object-oriented design, our class Process has a destructor. List the tasks that must be accomplished by the destructor.
  6. Who calls the Process destructor? Explain.

Hint: Some of these questions are discussed in the book and in class, but some are not. In some cases, I am asking you to make an educated guess and justify your guess.

  1. (6 points) See Section 3.1.3
    1. Process state: Implicit by the queue in which PCB is linked
    2. Program counter: Register image
    3. CPU registers: Register images
    4. CPU scheduling information
    5. Pointers to child processes
    6. Pointers to child threads
    7. Memory management information
    8. File management information
    9. Accounting information
    10. I/O management information
    The Process ID is not necessarily an attribute, although it often is. The process is known to the operating system not exactly by its ID, but by a pointer to its PCB,
  2. (3 points) Process Control Block (PCB)
  3. (6 points) Tasks include
    1. Allocate memory for PCB
    2. Initialize most PCB attributes
    3. Allocate memory for code and data
    4. Load memory with executable
    5. Insert PCB into appropriate scheduling queue, probably Ready
    6. Call Scheduler or return to calling process
    The constructor must execute in the address space of the process that calls it, not in its own address space, because its own address space does not exist yet.
  4. (3 points) fork()
  5. (6 points) Undo the work of the constructor, including
    1. Release any resources, including files, locks, semaphores, messages
    2. Especially release process memory
    3. Remove PCB from any scheduling queues and waiting lists
    4. Release PCB memory
    5. Call Scheduler
  6. (5 points) We did not discuss that, but we DID talk about different circumstances under which a process terminates, including
    1. Process finishes. It could call its own destructor
    2. Process finishes, usually with an operating system call to exit(), so exit() should call the process destructor. In this (and most other) case, the Process destructor runs in the address space of the caller, not in the address space of its own object.
    3. Another process (especially an operating system process) can kill(pid) a process, so the operating system call kill() should call the process destructor
    4. In a graceful shutdown, the operating system should terminate all running processes, calling the destructor of each, probably via kill(pid)

A common thread of these problems is that in C, you are responsible for memory allocation and deallocation.

Problem 4 Threads

Suppose we wish to construct a class Thread {...} to encapsulate data and operations for a thread

  1. List at least six attributes a class Thread should have. For each, give in a pseudo code
    1. Meaningful name
    2. Data type
    In addition, include a paragraph of explanation.
  2. In an object-oriented design, our class Thread has a constructor Thread( ... ). List the tasks that must be accomplished by the constructor.
  3. From where is the constructor Thread() logically called? Explain.
  4. In an object-oriented design, our class Thread has a destructor. List the tasks that must be accomplished by the destructor.

Hint: Some of these questions are discussed in the book and in class, but some are not. In some cases, I am asking you to make an educated guess and justify your guess.

  1. Our book does not address this question. A thread is derived from a process in an operating sense, although not exactly in an object-oriented sense. Logically, the PCB should include as an attribute pointers to its constituent threads. Attributes for a Thread include things that differ between threads belonging to the same process, such as
    1. Thread ID, although that may be maintained as a pointer to the thread
    2. Parent process
    3. Thread state: Implicit by the queue in which TCB is linked
    4. Program counter: Register image
    5. CPU registers: Register images
    6. CPU scheduling information
    7. Memory management information
    8. Accounting information
    It is a very interesting question whether data such as control block for open files are shared or individual for threads belonging to the same process

    Book does not give a name, but I'd call it a Thread Control Block (TCB)

  2. Tasks include
    1. Allocate memory for TCB
    2. Initialize most TCB attributes
    3. Allocate memory for data
    4. Load memory
    5. Insert TCB into appropriate scheduling queue, probably Ready
    6. Call Scheduler or return to parent Process
  3. Whomever spawns a new thread. Name depends on the system. Pthreads: pthread_create(); Win32: CreateThread(); Java: constructor Thread()
  4. Undo the work of the constructor, including
    1. Release any resources, including files, locks, semaphores, messages
    2. Especially release thread memory
    3. Remove TCB from any scheduling queues and waiting lists
    4. Release TCB memory
    5. Call Scheduler or return to parent Process
  5. We did not discuss that, but different circumstances under which a thread terminates are probably similar to those under which a process terminates, including
    1. Thread finishes. It could call its own destructor
    2. Process finishes. The process destructor could call the destructor for each child thread.
    3. Process finishes, usually with an operating system call to exit(), so exit() should call the process destructor, which could call the destructor for each child thread.
    4. Another thread (or an operating system process) can kill(tid) a thread, so the operating system call kill() should call the thread destructor

Again, explaining what memory is allocated for what purpose and the deallocation of that memory is key.

How are threads related to processes? How are they different?

Problem 5 Interprocess communication by send() and receive()

Suppose an operating system implements interprocess communication with blocking send and blocking receive primitives.

Case 1: Process Q executing 

     send (P, message);
is blocked until process P executes 
     receive (Q, message);
That is, process Q does not return from its send() operating systems function call until process P returns from its receive() operating systems function call.

Case 2: Similarly, a process P executing 

     receive (Q, message);
is blocked until process Q executes 
     send (P, message);
  1. In case 1, in what schedule state should process Q be placed while it waits for process P to execute its receive()? Explain. Hint: The expected answer is not quite as easy as it might seem.
  2. Given your answer to part a), describe the a sequence of actions by the scheduler by which process P executes its receive(), and process Q eventually ends up in the RUN state.
    1. Process Q is in whichever state you said in part a)
    2. Process P executes its receive()
    3. [You fill in as many steps here as necessary]
    4. Process Q is running
  3. Does this usually work? Give a possible sequence of events in which process Q successfully sends a message to process P, and both are able to continue processing.
  4. Show a scenario (a sequence of send() and receive() by both P and Q) under which deadlock occurs.
    Hint: "Deadlock" here means that P is waiting for Q, and Q is waiting for P, so neither is able to make any progress. We will discuss deadlock in more detail next week.
Problem adapted from Problem 3, Midterm Exam, Spring 2000
  1. "Waiting" is the easy answer. You need to say "Waiting for P to receive()." There is a different wait queue for each resource. -1 if you said "Wait on ..." A servant waits on. A peer waits for. Several students suggested Q waits in the ready queue. That is a wait state, not a ready state
  2. One possible sequence is:
    1. Process Q is in whichever state you said in part a)
    2. Process P executes its receive()

       

    3. The receive() operating system call notices that Q is waiting for P to receive
    4. The receive() call moves Q from the WaitingForPtoReceive queue to the Ready queue
    5. Sometime later, the Scheduler is invoked
    6. Eventually, Q is the process selected by the Scheduler from the Ready list to be made Running

       

    7. Process Q is running
  3. Whether it "usually" works is debatable. Here is one sequence which works:

     

    Process P Process Q
      
    pid Q = ...;
char *message = "Hello";
 . . .
send(Q, message);
 . . .
    		   
    pid P = ...;
char *message;
 . . .
receive(P, message);
 . . .
  4. Here is one sequence that deadlocks:

     

    Process P Process Q
      
    pid Q = ...;
char *message = "Hello";
 . . .
send(Q, message);
 . . .
    		   
    pid P = ...;
char *message = "Hello";
 . . .
send(P, message);
 . . .

    Yes, they are the same. Won't work, will it?

    A process sending a message to itself (or receiving a message from itself) counted, but it probably does not meet the official definition of deadlock we'll meet next week.

  5. Implement a time-out. That is, both send() and receive() might wait for a specified length of time. If the event for which the process was waiting has not occurred, the function returns anyway. Of course, they would not have communicated a message, but they would not be waiting forever in a deadlock.

 

 
  Marquette University. Be The Difference. Marquette | Corliss |