Final

Part of materials for 22C:50, Spring 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Name: ________________________________________________

ID Number: ___________________

Please write your answers in the space provided! Make sure your name is in the same form as it appears on your University ID card! Illegible and excessively long answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam is worth 1/5 of the final grade (20 points; allocate 4-5 minutes per point).

Background: Assemblers, linkers and relocating loaders, taken together, convert the symbolic representation of the contents of memory to numerical form. For each symbol in the original source of a program, one or the other of these finishes the job of fixing the final value that will land in memory before the program begins execution. Of course, recall that the assembly process always begins at relocatable zero unless the origin is explicitly set.
For this problem assume that the following file, ext.eal, has already been assembled to produce object code in ext.obj:
```
	    INT SA
	    INT SB
	SA:
	SB  =   #10
```
A Problem: Assume that the following EAL code is assembled, linked with ext.obj, and loaded. For each line in the following code that actually places a value in memory, identify the component of the programming system that is most likely to fix the final value. Do not comment on lines that place nothing in memory.
```
(2.0)	    EXT SA      ______________

	    EXT SB      ______________

	SC  =   10      ______________

	SD:             ______________

	    W   SA      ______________

	    W   SB      ______________

	    W   SC      ______________

	    W   SD      ______________

	    W   SC+SD   ______________
```
Background: A Unix program can call exit(stat) to terminate. Normally, stat is zero, but nonzero values are typically used to signal errors or failures. A Unix program can call wait(&stat) to wait for its child process to terminate; the stat argument indicates why the process terminated and it includes the low 8 bits of the stat value passed to exit() by the terminated process.
All standard Unix utilities use exit() to indicate success or failure. For example, rm indicates whether it successfully deleted the file, and cc indicates successful error-free compilation.
In many Unix shells, the && delimiter between two shell commands causes the second command to execute only if the first command returned an exit status of zero indicating normal termination. All commands between the && and the end of line will be skipped if the command returns a nonzero exit status indicating failure.
Part A: Extending the EBNF grammar for MP5sh to support the && feature documented above, we'd have to add just one new rule and one new nonterminal name. Give that rule:
```
	<script> ::= { <line> } <EOF> 
	<line> ::= # { <anything> } <EOL>

(0.8)	<line> ::= ____________________________________________________
	<command> ::= <progname> { <argument> } <EOL> 
	<progname> ::= <nonblankstring> 
	<argument> ::= <nonblankstring> 
```
Part B: Obviously, adding support for && to your solution to MP5 requires a slightly more complex parser, because we added a production rule. Does it require changes to the lexical analyzer? If yes, what new lexeme type must be added?
```
(0.8)	________________________________________________
```
Part C: Write a shell script using this feature that deletes the file f, then deletes the file g, but only if f was successfully deleted. Finally, your script should output success, but only if both deletions worked.
```
(0.8)	________________________________________________
```
Part D: You've been given the problem of writing an if program that can be called from any Unix shell. It should return success if its arguments evaluate to true, and failure if its arguments are undefined or false. All tokens in the argument list should be separated by blanks. Obviously, you'll have to write an expression evaluator. One major part of the language processing job, however, has already been almost completed by the program that called your program. What is it?
```
(0.8)	________________________________________________
```
Part E: Write code that outputs equality if 49 times 72 is the same as 56 times 63, using the built-in echo and your if commands, along with the features of the shell discussed in previous parts of this question:
```
(0.8)	________________________________________________
```
Background: The fictional On-a-Shoestring Software Corp offers a new operating system called OASOS, featuring a marginally novel file system structure. This file system is just like Unix, except:
- I-nodes are one sector in size (4K bytes, or 1K 32-bit words).
- linearized sector numbers are 32-bit quantities.
- The first 8 words (32 bytes) of an i-node hold administrative data including the file size.
- For small files, the remaining bytes of the i-node hold the file itself.
- For larger files, the remaining words of the i-node hold the 32-bit disk addresses of the sectors of the file.
- For extraordinarily large files, the i-node holds the disk addresses of index sectors holding addresses of data sectors.
Your boss has just suggested that you write code for OASOS that allows a user program to open a disk file so that the open file becomes a segment of the program's virtual address space. Once a file is opened this way, read and write operations to that segment become direct accesses to the file.
Part a: Your bosses proposal will work for large (and larger) files. What information do you copy into the page table entries for the segment that represents an open "larger file"?
```
(1.0)	________________________________________________

	________________________________________________
```
Part b: This proposal has a near fatal flaw if it is applied to small files. What is the root cause of this flaw?
```
(1.0)	________________________________________________

	________________________________________________
```
Background: Somehow, you've managed to fix the OASOS file system so that users can open files as segments of running programs. If two or more programs open the same file, they share the memory segment representing that file. Other than these shared segments, the virtual address space of each program is entirely private.
Part a: Suppose your program opens, as a segment, an object file holding the code for a function. Assume your program then executes a call instruction to the first location in that segment. The result is a complete failure! Your program bombs out with a "bus trap" error message. Why?
```
(1.0)	________________________________________________

	________________________________________________

	________________________________________________
```
Part b: Your program builds a binary tree in a segment it shares with another program. Every time the other program tries to follow a pointer in this tree, it bombs out with a "bus trap" error message. Why?
```
(1.0)	________________________________________________

	________________________________________________

	________________________________________________
```
Background: As you already know, OASOS uses virtual memory with one address space per process. Initially, no pages are allocated to a process, so all the entries in the page table are marked as totally-invalid. Reading or writing a totally-invalid page raises an exception.
The allocate(addr,size) system service changes the markings on pages from totally-invalidd to invalid-but-allocated. The pages involved begin with the page containing the virtual address addr and run up to the page containing the address addr+size. Reading from an invalid-but-allocated page raises an exception. Writing an invalid-but-allocated page causes it to become a valid-read-write page with an associated page-frame.
The deallocate(addr,size) system service changes the markings on pages in the addressed range from valid-read-write, valid-read-only or invalid-but-allocated to totally-invalid.
Part a: What part of the system actually allocates page frames to user processes.
```
(1.0)	________________________________________________

	________________________________________________
```
Part b: What system data structure does the allocate() service manipulate.
```
(1.0)	________________________________________________

	________________________________________________
```
Part c: The deallocate() service described above does one more thing for each page that was marked valid-read-only or valid-read-write. What thing?
```
(1.0)	________________________________________________

	________________________________________________
```
Part d: The set of system services given above is incomplete! You can infer that there is one more system service from the given set of states of pages. What must this service do?
```
(1.0)	________________________________________________

	________________________________________________
```

Background: Suppose your heap runs from addresses 50 to 80 (decimal) inclusive. Addresses are word addresses, so don't worry about bytes.

Part a: Show the initial breakdown of the heap for the binary buddy system:

	 _____________________________________________________________
(1.0)	|                                                             |
	|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
	50                  60                  70                  80

Part b: Show the initial breakdown of the heap for the Fibonacci buddy system:

	 _____________________________________________________________
(1.0)	|                                                             |
	|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
	50                  60                  70                  80

Background: Your C++ program running on a Unix (or Linux) system opens a C++ output. When you open this stream, all the operating system knows is that you opened a file (the system knows nothing about C++, after all; that's just a compiler and a library of pre-compiled support functions).
Part a: What object is allocated on the heap of the user process?
```
(1.0)	________________________________________________

	________________________________________________
```
Part b: How is this connected with an entry in the open file table of the process?
```
(1.0)	________________________________________________

	________________________________________________
```
Part c: What object is allocated in the operating system kernel's heap?
```
(1.0)	________________________________________________

	________________________________________________
```
Part d: How is the open file table entry connected to this kernel object?
```
(1.0)	________________________________________________

	________________________________________________
```