DATA STRUCTURES, ANALYSIS OF ALGORITHMS AND COMPUTATIONAL COMPLEXITY
c -> a -> f -> r -> q
Write a non-recursive function, in the language of your choice, which reverses all of the pointers, for example:
c <- a <- f <- r <- q
The function should return a pointer to the last node in the list (and this node is effectively the new head of the list). An initial call would be:
p = reverse(p);
COMPUTER ARCHITECTURE AND OPERATING SYSTEMS
Readers: Writer:
while (true) { while (true) {
wait(A); wait(B);
readcount++;
if (readcount==1) wait(B);
signal(A);
/* reader reads from the file */ /* writer writes to the file */
wait(A);
readcount--;
if (readcount==0) signal(B);
signal(A); signal(B);
} // end while } // end while
The problem is to consider the effects of the initialization of the semaphores A and B with respect to i) a correct solution and whether the solution guarantees ii) mutual exclusion, iii) no deadlock, and iv) no starvation. The table below has five different initializations and for each initialization answer Yes/No to the previous four questions. Draw this table on your solution paper. Note: The definition of starvation here is that only one process makes progress.
Warning: do NOT guess, just leave blank (+1 point for correct answers, 0 point for blanks, -1 point for incorrect answers).
| A=0,B=0 | A=1,B=0 | A=0,B=1 | A=1,B=1 | A=2,B=1
| Correct Solution: | Y/N | Y/N | Y/N | Y/N | Y/N
| Guarantees Mutual Exclusion: | Y/N | Y/N | Y/N | Y/N | Y/N
| Guarantees No Deadlock: | Y/N | Y/N | Y/N | Y/N | Y/N
| Guarantees No Starvation: | Y/N | Y/N | Y/N | Y/N | Y/N
| |
PROGRAMMING LANGUAGES AND COMPILER DESIGN
b) Demonstrate your understanding of the stages you propose by describing what specific actions you would expect each stage to take during the compilation of the two statements below, which have been extracted from a larger C program.
int Aleph[100], n;
. . .
Aleph[n] = 1 + Aleph[n + 1] * Aleph[n + 1] + zed;
. . .
a) Z -> A
A -> aAa | BbB
B -> bB | a
b) Z -> AaAb | BbBa
A -> e
B -> e
class funny {
private: int x;
public:
funny(int k = 0) {x=k;}
int give_value(void) {return x;}
};
void print_it(funny x, funny *y) {
cout << x.give_value() << " " << y -> give_value() << endl;
}
int main(int argc, char *argv[]) {
funny a(50);
funny *b = new funny(100);
// Two function calls. How are they implemented?
print_it(a, b);
print_it(*b, &a);
return 0;
}
Explain, precisely, what actions need to take place to implement the two function calls to "print_it" in the given C++ program.