This question pertains to i-nodes and zones as implemented in Minix. You may
assume that the system crashes referred to in the question did not occur at
the same time.
* The i-node bit map has been scrambled due to a system crash. Can it be
fixed and how?
* The zone bit map has been scrambled due to a system crash. Can it be
fixed and how?
* What changes could be made to the design and implementation to help
repair the above two bit maps in the case of a system crash?
* What Minix process is chartered with the responsibility of ensuring the
filesystems do not become corrupted? Explain the principles which make
it possible for this approach to work? You will have to discuss the
design of this Minix process for your answer to be correct.
Minix is a Unix-like operating system. Answer each of the following
questions concisely. When asked to justify your answer, please provide as
concise an answer as possible.
* What kind of operating system is Minix. Your answer should be one
sentence or less.
* What are the three (or four) primary layers of the Minix operating
system? What is provided at each layer? Precisely explain how the
different layers interact with one another.
* Can a user process directly access kernel memory? (yes or no) Justify
your answer.
* Can a user process directly call kernel functions? (yes or no) Justify
your answer.
* Tanenbaum claims that operating systems similar to Minix can be
designed to run in a distributed environment. Can Minix as it currently
exists be run in part or in entirety on a Network of Workstations? What
changes would be required to support Minix in a networked environment.
Minix and Unix (and Linux) are two operating systems commonly taught in
universities. Answer each of the following questions in two paragraphs or
less.
* Choosing from your favorite version of Unix (other than Minix) and
Minix, compare the following general areas for both systems by focusing
on policies and design decisions (for this part, a paragraph may be
dedicated to discussing each item):
1. device management
2. process scheduling
3. memory management
4. file systems
* Explain the main difference between Minix user processes and Minix
system tasks from a scheduling perspective. In order for your answer to
be correct, you must precisely explain the difference between how a
user process is handled versus how a system task is handled by the
scheduler. This answer partially overlaps with part (a).
* Suppose you are implementing a network or a parallel version of a
Unix-like operating system. You have a choice between porting your
favorite version of Unix (e.g. Solaris, SGI Irix, or Linux) or Minix.
Explain which OS you would try to get working on the network or
parallel computer and the pros and cons of choosing either operating
system. Your answer will be based primarily and qualitative factors;
however, quantitative factors must be addressed as well.
[This question tests your appreciation of some of the problems faced by an artificial intelligence program in understanding ordinary events. As such, it is intended to allow for differing content in various incarnations of our artificial intelligence courses. You may, of course, apply specific knowledge from the course you took, but you should explain how it is relevant to the specific question. Since the problems faced in understanding the following situation are difficult, you will be graded more on your appreciation of what the problems are than on your ability to tell just how to solve them.] Discuss knowledge representation, information, and control structure mechanisms needed for a computer program to understand the following story: 1. Laura asked, "Who's going to Sally's birthday party?" 2. Bob said, "I'm going to the ball game." 3. Bill said, "I'm bringing this kite." 4. Sue said, "Betty will bring confetti." 5. Sam said, "I'm bringing Mary." 6. Laura said, "Take it back, she already has one." Understanding includes at least being able to answer the following questions: (a) Who will go to the birthday party, and who won't go? (b) Where and why does Bill intend to take the kite? (c) What are the possible reasons for Sam to bring Mary? (d) What are possible reasons for Betty to bring confetti? (e) Who should take what back--and why? (f) Who already has what? (g) Is Mary likely to bring a present? (h) Is confetti likely to bring a present? For each of (a) through (h) individually, discuss specific problems of understanding it poses. If you can, discuss a strategy for meeting that specific problem, and if you can, a computational method that would help think about that problem, and how it might be employed--but you aren't expected to know strategies or methods for all the problems, since they are hard. If you propose a particular technique--chaining or predicate calculus deduction, or some strategy of case-based reasoning, or whatever--then you should either sketch how it would be applied to the specific question (a)-(h) you are discussiong, or sketch some of the difficulties, specific to the question, that would have to be addressed in applying the technique (e.g., would it have to be applied in a particular way?). Since overcoming these difficulties is probably beyond your knowledge at this time, you will be graded mainly on your appreciation of what the difficulties are.
This problem asks you to write pseudocode to determine parameter
passing techniques.
Assuming a block-structured language with static scoping, and
with one type of parameter passing (either by value, by
reference, by value-result, or by name), write a program in clear
pseudocode to determine the type of parameter passing. In other
words, your program should write one of the following messages:
PASS BY VALUE
PASS BY VALUE-RESULT
PASS BY REFERENCE
PASS BY NAME
PASS BY <UNKNOWN>
depending on the parameter transmission technique detected.
Explain the issues involved in choosing data structures for symbol
tables in compilers for block-structured, strongly-typed languages such as
Pascal.
What kind of information must be represented in the symbol table and
how should the table be organized?
For this question, assume that it concerns a high-level block-structured
language with strong typing(e.g. Pascal, PL/1, Algol, etc.).
Consider the following parameter passing techniques:
i) Pass by reference
ii) Pass by value-result
iii) Pass by value
iv) Pass by name
For each of these, tell:
a) What information (e.g. address, value, etc) is transmitted when a
procedure is called;
b) What actions the calling procedure must do to compute the
information in a);
c) What actions the called procedure must do with the information
that it has been sent;
d) What actions must occur when the procedure returns.
How could message passing for a distributed-memory parallel
programming package (e.g., P4, P2, PP) be implemented on a shared-memory
machine such as the Encore?
Answer 2 out of 3 parts of the following question.
1. Describe the following design-related paradigms and
how they impact on software quality and code reusability.
information hiding/encapsulation
abstract data types
objects/classes
2. a) What is the role of conceptual design in
size estimation at the PSP0.1 level using the PROBE
method?
b) How would you assess the quality of a size
estimate made with the PROBE method?
3. a) What are the typical sub phases in the design
process? What criteria can be used to evaluate their
quality?
b) What process is used for evalation?
c) How should design defects and deficiencies be
handled?
d) What impact do they have on the code?
A. Describe the levels in the Personal Software Process
(PSP) hierarchy; how does the individual software engineer
benefit in moving up the levels.
B. Why is it important to develop a coding standard
before developing a line counting standard? What are
some of the criteria to use in evaluating a line counting
standard? Briefly describe the line counting standard you
used for your PSP. What was successful and what was
unsuccessful as you applied it in the PSP projects?
C. What role does line counting play in the levels of
the PSP?
A. Describe the defect classification standard used in the PSP. Do you think it was adequate; what do you think should be changed
B. Describe the defect collection and analysis process in the PSP.
C. What was the typical distribution of defects you observed at the lower levels of the PSP; the upper levels? How do you account for the difference?
D. What mechanisms did you use to reduce your observed defects? Did they work, how do you know?
Describe how to do data flow analysis using a program's control flow graph.
1. For three of the MIMD interconnection schemes, 2-dimensional mesh,
shuffle-exchange, hypercube, binary tree, and cube-connected cycles,
a) give formulae to describe which nodes are connected to which.
b) Give an algorithm for routing messages.
c) Tell what the maximum distance between two nodes is.
d) Discuss what bottlenecks the topology will have,if any.
e) Discuss the cost of the topology.
f) Discuss the expandality of the topology.
2. Define parallel speed-up and efficiency. Choose a parallel algorithm
and topology and compute the order of speed-up and efficiency for the
algorithm on that topology.
Answer the following questions: 1) One key design decision for ATM was whether to use fixed- or variable- length cells. Let us consider this decision from the point of view of efficiency. We can define transmission efficiency as, Number of information octets N = ---------------------------------------------------------------- Number of information octets + number of overhead octets a) Consider the use of fixed-length packets. In this case, the overhead consists of the header octets. Define: L = Data Field size of the cell in octets H= Header size of the cell in octets X = Number of information octets to be transmitted as a single message Derive an expression for N. b) If cells have variable length, then overhead is determined by the header, plus the flags to delimit the cells or an additional length field in the header. Let Hu denote the additional overhead octets required to enable the use of variable-length cells. Derive an expression for N in terms of X, H and Hu. c) Let H=5 and Hu=2. Plot N versus message size for fixed- and variable length cells. Comment on the results. 2) One method of transmitting ATM cells is as a continuous stream of cells, with no framing imposed; therefore the transmission is simply a stream of bits, with all bits being part of cells. Since there is no external frame, some other form of synchronization is needed. This can be the HEC function. The requirement is to assure that the receiver knows the beginning and ending cell boundaries and does not drift with respect to the sender. Draw a state diagram for the use of the HEC to achieve cell synchronization, and explain its functionality.
Given the definition "Individuals who are coworkers have the same manager." and the managerial responsibilities listed below
Sue manages Tom.
Mike manages Jane.
Sue manages Phil.
Phil manages Bob.
Mike manages Bruce.
use predicate calculus and resolution to derive answers to the queries:
a) Are Tom and Phil coworkers?
b) Who are Bruce's coworkers? (Derive all answers to this query).
Begin by using the relations (predicates) Manager(X,Y) and Coworker(X,Y) to represent the information and relationships in this problem. Follow this by derivations of the answers to the queries above.
Given the additional information "Mario and Bruce are coworkers." Discuss what implied information about the coworker/manager relationship must be made exlicit in order to derive answers to the queries:
c) Who are Mario's coworkers?
d) Who is Mario's manager?
Formulate expressions for these implied relationships and derive answers to these queries.
Discuss the role of the Closed World Assumption in deriving answers to the problems above.
A. Suppose you have the data below for four projects. a) Calculate the B0 and B1 values for program size estimation. b) You are developing a new program that you estimate with the PROBE method will be 157 object lines of code. Using the linear regression equation, what do you predict for the total actual LOC when you complete the project? How do we use the UPI and LPI to help us with our estimation?
| Estimated Object LOC | Total Actual LOC | Development Time |
| 114 | 136 | 9.0 |
| 229 | 252 | 24.7 |
| 75 | 83 | 6.9 |
| 150 | 164 | 14.6 |
B. a) Briefly describe two basic review measures and two derived review measures. b) From the following data calculate the DRL for each phase with respect to unit test.
| Phase | Defects Removed/Hour |
| Design Review | 6.8 |
| Code Review | 13.3 |
| Compile | 18.7 |
| Unit Test | 2.4 |
C. Describe what is meant by the term "earned value". How is it used for personal project management?
D. Describe what is meant by a physical and logical line of code. What are the advantages and disadvantages for use of each as a size measure? What is the role of a line counting standard and a coding standard in the PSP?
a) What kind of HCI conflicts might a designer face when
designing computer
systems?
b) What are the main factors that contribute to the
meaningfulness of icons?
c) What are the four main mapping types?
d) What is the difference between static SQL and dynamic SQL.
e) Describe the four types of base tables.
a) Describe five example of how monocular depth cues have been
used to make
object appear as three-dimensional.
b) What are the main advantages of direct manipulation interfaces
in
comparison with command-driven systems? What are the comparative
disadvantages?
c) What will a modeless dialogue box let the user do that a modal
dialogue
box prevent
d) What are the three types of SQL-89 tables?
e) Explain the rules governing temporary table creation in
SQL-92.
a) What are the main differences between the constructive and
ecological
approaches to perception?
b) How have the command driven and direct manipulation been
useful in
understanding the design of information at the interface?
c) Explain the difference between using UNIQUE versus EXIST with
a
subquery.
d) Define the following terms -- Full Outer join, inner join, and
cross
join.
e) What are the limitations to data type when implementing SQL-92
compliant
database using a generic ODBC driver?
a) Take the following grammar for assignment statements and derive FIRST* and FOLLOW sets for each of the nonterminals.
S -> i = E
E -> E + T
E -> T
T -> T * F
T -> F
F -> P ^ F
F -> P
P -> i
P -> ( E )
b) Build a collection of LR(0) configuration sets for the grammar.
c) Which of the following is the grammar: LR(0), SLR(1), LALR(1), or LR(1).
a) Translate the following program fragment into trees, triples, quadruples, or Polish suffix notation. (Include the address calculations. Assume variables SUM and A are of type real, K and N are integer.)
SUM := A[1]; K := 1; WHILE K < N DO BEGIN SUM := SUM + A[K+1]; A[K] := SUM-A[K+1]; K := K + 1; END
b) What optimizations would be appropriate for this code?
c) Give the optimized version of your intermediate form.
d) What are the advantages and disadvantages of the intermediate form you chose?
a) Prove that if a grammar is both left and right recursive in the same nonterminal, it is ambiguous.
b) Take the following grammar for assignment statements and put it in LL(1) form:
S -> i = E | E
E -> T + E | T
T -> T * F | F
F -> i | ( E )
(note: the grammar on the actual exam may be different.)
A. Suppose a software engineer when analyzing her defect data finds that she detects defects in the condition predicates of looping and conditional statements during unit test. This is a frequent, and difficult to find, and fix defect for her. What are some possible causes? Suggest some approaches she could use to detect this defect early in her development cycle, and prevent this type of error from reoccurring?
B. Using the definition of process maturity we discussed in class, show how the PSP and its level structure support the growth of personal process maturity.
C. What is the role of reviews in the PSP? How do we go about designing a PSP review checklist? Calculate the code review yield for a developer who removed 8 defects in code review and allowed 6 to escape to later phases.
From a client/Server prospective, describe the differences between: