| |
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. Correct English is always expected.
- 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: 78; Mean: 71.4; Standard Deviation: 18.9
These shaded block are intended to suggest solutions; they are not intended to be complete solutions.
Problem 1 Compare and Contrast
Problem 2 Process Context Switch
Problem 3 Tricky C Program
Problem 4 Process Attributes or Operations
Problem 5 Waiting
Problem 1 Compare and Contrast each pair of terms
(in the context of computer operating systems):
- Protection and Security
- User mode and Kernel mode
- Shared memory and Message passing
- Blocking send and Nonblocking send
- Client-Server computing and Peer-to-peer computing
Hint: "Compare and contrast A and B" questions evoke a standard pattern for an answer:
- Define A
- Define B
- Tell how A and B are similar (that's the "compare" part)
- Tell how A and B are different (that's the "contrast" part)
That's what your answers to each part should look like.
- Protection and Security: See Section 1.9.
Protection controls access to computer system resources
Security defends a system from internal and external attacks
- 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.
- Shared memory and Message passing: See Section 3.4. Be careful to avoid circular definitions: "Shared memory is memory that is shared" counts zero points.
- Blocking send and Nonblocking send: See Section 3.4.2.2. Spell "receive" correctly.
- Client-Server computing and Peer-to-peer computing: See Sections 1.12.2 and 1.12.3. Client-server is a master-slave relationship. Peer-to-peer is a relationship among equals. Was Napster before your time?
Problem 2 Process Context Switch
In the context of scheduling and dispatching of processes,
- What is the purpose of a context switch?
- Describe the steps, in order, taken by a kernel to context-switch between processes.
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:
- Save state of old process on the stack
- Save Stack Pointer into the Process Control Block of the old process
- Load Stack Pointer from the Process Control Block of the new process
- Restore the state
How is control handed over to the incoming process?
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.
Problem 3 Tricky C Program
Here is a slight variation of Dave's Dynamic Linked List program:
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 typedef struct ele {
5 void *next;
6 int num;
7 void *prev;
8 } node;
9
10 node * addToDLL(int num, node *prevptr) {
11 node *nodeptr;
12 nodeptr = (node*)malloc(sizeof(node)); // Allocate new node
13
14 nodeptr->prev = prevptr; // Initialize new node
15 nodeptr->num = num;
16 prevptr->next = nodeptr;
17
18 return nodeptr; // Pointer to new node
19 }
20
21 void printDLLFwd(node *head) {
22 printf("\nPrinting linked list:\n");
23 while(head->next != NULL) {
24 head = head->next;
25 printf(">> %d\n", head->num);
26 }
27 printf(">> %d\n\n", head->num); // tail num field
28 }
29
30 main() {
31 int i;
32 node head;
33 node *nodeptr;
34
35 head.next = NULL; // Initialize the head node
36 head.num = 0;
37 head.prev = NULL;
38 nodeptr = &head; // Initialize to point to the head node
39
40 for (i = 1; i < 4; i++) { // Start at 1 because head contains 0
41 nodeptr = addToDLL(i, nodeptr);
42 }
43
44 printDLLFwd(&head);
45 exit(0);
46 }
- What does this program print? Are you sure?
- Explain why.
- What changes if line 14 and line 16 are interchanged? Explain.
Warning: You may assume this program compiles and runs. Otherwise, be alert.
- See code directory
When I run it, I get
Printing linked list:
>> 1
>> 2
>> 3
>> 3
You could get an infinite loop, printing all kinds of garbage imaginable!
- It starts at 1 and prints "3" twice because line 24 and line 25 are interchanged from Dave's program. Line 24 advances to the next node before printing the contents of the current node.
At line 12, the value returned from malloc() is not checked. Hence, memory allocation could fail, and we'd never know.
A serious difference, and one over which you will trip, is that C does not guarantee that variables are initialized. Dave's example includes a line nodeptr->next = NULL; between line 15 and line 16. Without that, nodeptr->next is un-initialized. For most nodes, that does not matter in this example, because that storage location is soon set to point to the next node in the next call to addToDLL(). However, in the last node (with value 3, in this example), nodeptr->next is un-initialized, and that is the location line 23 is counting on to have the value NULL.
Java and C++ are required to initialize all otherwise un-initialized memory to zero, and many C compilers are "nice" and do the same. It happens that NULL has the value 0, so this code usually works. However, it does not have to work, and many cross-compilers for embedded systems do not zero all memory.
If the un-initialized nodeptr->next field in the last node happens to have non-zero (likely if not set to 0), line 24 will take you who knows where, and you'll continue to interpret whatever garbage happens to be there as a node value and a link to the next node.
Score: -10 if you failed to recognize that nodeptr->next was not initialized. I said this was a tricky C program. I didn't lie.
- No change. Lines 14 - 16 can be written in any order (which means they could be executed in parallel).
It is quite likely there will be a tricky C program on Exam 2.
Problem 4 Process Attributes or Operations
Choose either a) or b)
-
List attributes of a process. For each, give
- a name suggestive of its purpose,
- a likely data type, and
- a description.
- When appropriate, tell what values the attribute might assume.
For example
| Name |
Type |
Description |
Values |
| ID |
integer |
Process identifier |
0 : MAX_INT |
| | | | |
-
List operations on a process. For each, give
- an appropriate name,
- a description of what it does, and
- circumstances under which it might be called.
- When appropriate, tell what parameters might be passed.
Hint: Pseudo-English is fine. I am not looking for near-C code. You do not need to list every possible attribute/operation, but to receive full credit, you should list at least 10 attributes or 6 operations, including the ones without which the operating system will not work.
- See Section 3.1.3, p. 106, or class notes for Chapter 3 PCB
Need to store Registers when switched out? Integer and floating point. Could be stored in stack space?
Need to know process state? Could be deduced from which queue it is in?
- See Section 3.3.
Your O-O training should help you distinguish between operations on a process (methods provided by class Process) from methods called from within a process on other classes. For example, send() and receive() might be operations in a class Message, but probably not methods in class Process. However, send_message_to() or receive_message_from() might belong to class Process.
There is no constructor in the usual sense. fork() is a class method; it is a little like a clone() method, except that it does not return the clone to the parent. fork() is somewhat like a constructor. Perhaps a good design would have a private constructor called by fork(), except that most OO languages require a public constructor.
Getter methods for most attributes.
In principle, setter methods for most attributes. In practice, most attributes are set indirectly, so there should be few explicit setter methods..
kill(), certainly.
wait() is not really a method in class Process. Moving the process to a blocked queue is a side effect of many OS calls the process might make. However, it could be that the OS code effects the move by calling a wait() method, which might belong either to class Process or to class BlockedQueue.
exit() is called by a process. If exit() is a method of class Process, it logically would be called as this.exit(), which certainly can be done, but seems a little odd.
One could design an operating system in which all operating systems calls belong to class Process, but I doubt anyone would consider that a "good" design.
Does this part suggest that class Process is not an especially good fit for "good" object-oriented design?
Problem 5 Waiting
Management of waiting is an essential part of every operating system. The text and I have discussed often the ready and blocked waiting states.
- ready state
- List several ways a process could have gotten into the ready state.
- What is the process waiting for?
- Could the process get "lost" waiting indefinitely? Explain.
- blocked state
- List several ways a process could have gotten into into the blocked state.
- What is the process waiting for?
- Could the process get "lost" waiting indefinitely? Explain.
- What features could an operating system incorporate to deal with the possibility that processes could start to wait for an event that might never happen?
Hint: No, we have not studied that yet. I am asking for your speculation.
- ready: A process can be placed into the ready state by the operating system when it is created, when it is removed from the Run state following a timer interrupt, of from the Blocked state when the resource for which it was waiting becomes available.
CPU
Depends on the scheduling discipline. If there is no preemption and the Running process never gives up the CPU, all ready processes wait indefinitely. If the wait list is a queue, no. Under other disciplines (e.g., priorities) we will study in Chapter 5, perhaps.
- blocked: A running process effectively blocks itself by requesting certain resources from the operating system.
Whatever resource the process requested, for example, to receive a message, to access the hard drive, to receive network traffic, or in response to a page fault.
-5 points if you failed to point out in some way that there are multiple blocked states.
Easily. For example, the process might wait for a message no one ever sends.
- Different strategies (sort of) work for different resources. We will study several throughout the semester. "Aging" is a strategy to adjust priority artificially. Waiting for a message that never arrives may be acceptable, or we may force the process to wait for only a finite amount of time.
A later student asked:
Would another acceptable solution be that the operating system simply not incorporate it and instead use peripherals to generate interrupts (like when a button or a key is pressed / released) as needed? I am in an embedded class right now as well, where we are focusing on timers and interrupts, and was just curious if this answer would fall under the "OS umbrella" category, or if it is not entirely relevant.
Yes, that absolutely counts as an OS strategy. As an OS strategy, I'd call that, "Ignore the problem. Let the users deal with it." It is a VERY common OS strategy. That's what <CRTL> - <ALT> - <DELETE> is for, isn't it? Or just press and hold the [POWER] button?
We probably always should provide a feature such as a button for the user to press as a back-up, but if we can make the OS smart enough to get it right, we'd prefer our OS took care of preventing/avoiding such problems.
Using a timer to interrupt if a wait has been going on for a while is often an excellent way to prevent infinite waits.
IMHO, there is no boundary between hardware and software; there are only "systems," and their users simply expect them to WORK.
Any but the simplest OS cannot function without timers and interrupts. Otherwise, the OS would spend all the CPU time constantly polling, "Has anything happened yet?" Similarly, a good mechanism for handling timers and interrupts is a central mission of any OS.
Yes, there should be MANY connections between your embedded class and this class.
Wait on/for? One waits on a "superior" to provide a service for example, a server in a restaurant. One waits for a peer or a subordinate. In an operating systems context, a server may wait on a client as it services a request from the client, or it may wait for a client to make a request.
Language matters. Use it with care, love, and respect.
| |
