The thread system in Modula-3 uses mutexes and condition variables to control concurrency. An alternative scheme would be to use message passing. Each message-passing channel would be an object with two methods: send (message: REFANY) and receive (): REFANY plus an initialisation method. Calling send would append the argument to a (fixed-length) FIFO queue of data which would be collected by the thread calling receive. The thread would block if receive were called when the queue was empty or if send were called when the buffer was full. Write an interface, Message, defining a suitable opaque object type with init and send methods, and write a further interface MessageInternal revealing the receive method. [8 marks] Write an implementation exporting to both of these interfaces supplying the concrete revelations of the types and providing appropriate default methods. [12 marks] 3 [TURN OVER CST.97.3.4 4 Compiler Construction Consider the following grammar for expressions () and commands (). ::= i | n | - | * | ( ) ::= i := | if then | if then else | repeatwhile | ; | { } Show that there are syntactic ambiguities between (a) the minus (-) and exponentiation (*) operators, (b) the if-command and the if-then-elsecommand, and (c) the if-then-else-command and the repeatwhile-command. [4 marks] Define, in a programming language notation of your choice, a recursive descent parser that will construct the abstract syntax tree for an input stream conforming to the above syntax for commands. You may assume the existence of a function lex() that will yield an integer representing the next lexical token from the input stream, and the functions mk2(op,x), mk3(op,x,y) and mk4(op,x,y,z) that will construct abstract syntax tree nodes with a given operator and one, two or three operands. You should assume that exponentiation is right associative and more binding than subtraction which is left associative. The command following then should be the longest possible and the command before repeatwhile should be the shortest possible. [12 marks] Briefly outline how you would modify your parser if the command to the left of repeatwhile was changed to be the longest (rather than the shortest). [4 marks] 5 Data Structures and Algorithms You are given two sets of numbers Xi and Yj , where i and j run from 1 to N. Devise an algorithm to find the M largest values of Xi ?Yj . This algorithm should not be quadratic in N, though it is permitted to be quadratic in M. You should regard N as being of the order of 20,000 and M as being of the order of 1,000. [20 marks] 4 CST.97.3.5 6 Data Structures and Algorithms Describe and justify Kruskal's algorithm for finding the minimum spanning tree of an undirected graph. [6 marks] Suppose that all edges longer than some given L were omitted from the graph, for example as a result of not calculating them at all. Would the algorithm still give the correct result? Would you be able to tell if it had not? If it yielded a tree would it be guaranteed to be the best one? Justify your answers and consider the problem of finding a minimum spanning tree for 1,000,000 points in a plane rectangle where there is an edge between every pair of points and the cost of the edge is the Euclidean distance between the two points. [14 marks] 7 Structured Hardware Design A smart card is the size and shape of a credit card, but contains a microprocessor, a RAM, a ROM and some amount of non-volatile storage. The only connections to the card are five gold-plated contacts for power, ground, clock, data and reset. Write a few sentences about each of the following: (a) Design partition: i.e. how should the circuitry of the card be structured? [5 marks] (b) Testing: i.e. how will the component(s) of the card and the completed card be tested before shipping? [5 marks] (c) Product customisation: i.e. how will the card be different in different application markets (banking, authentication, casino, cellular phone etc.)? [5 marks] (d) Uniqueness: i.e. how would the card be customised or differentiated on a percard basis for individual users? [5 marks] 5 [TURN OVER CST.97.3.6 8 Operating System Functions A computer is equipped with a CPU with a 32-bit virtual address space, a 32-entry TLB with access time 10ns and 32 Mbyte DRAM with access time 100ns. Its secondary storage is provided by an IDE hard disc with transfer rate 1 Mbyte/s, and which rotates at 3600 revolutions per minute and has an average seek time of 10ms. The computer uses demand paged virtual memory with 1 kbyte pages. (a) Explain the function of the TLB with the aid of a diagram. [4 marks] (b) Design a page table structure which the operating system can use to implement virtual memory on this system and describe how a virtual address is translated using it. Are there any drawbacks of your approach? [4 marks] (c) What is demand paging? Briefly describe a policy which the operating system can use to share the available physical memory between competing processes. [3 marks] (d) Calculate the effective memory access time for the system if virtual memory is managed using the scheme described in your answer to (b), if page tables are kept locked in memory, the probability of finding a translation in the TLB is 98%, and the probability of a page fault is 10?6 . Exclude operating system overhead from your calculation, and briefly explain your answer. [9 marks] 9 Computation Theory Explain the action of a Turing machine, and show how the progress of a computation may be tracked by maintaining a record of the configuration at each time t. Prove that a computation which enters the same configuration twice will not terminate. [8 marks] Suppose you are given a Turing machine T having r states and k symbols. It is known that in a particular computation the head moves on the tape so that it is never more than l squares from its starting point. Calculate a bound on the number of configurations that the machine may enter during the computation. [4 marks] State a precise form of the unsolvability of the HALTing problem for Turing machines. Assuming this result, show that it is not possible to compute a bound on the distance of the head from its starting position during HALTing Turing machine computations. [8 marks]

Transcribed Image Text:

1This is called: A program unit that can be in concurrent execution with other program units a. A subprogram A thread b. c. A library file d. An event 2Which of the following would not be true when "sharing data"? a. Variables declared outside of main are shared. b. Object allocated on the heap may be shared (if pointer is passed). c. Variables on the stack are private: passing pointer to these around to other areas can cause problems. d. Shared variables can be better read and written without synchronization. 3Two kinds of synchronization are a. Priority synchronization b. Cooperation synchronization c. Competition synchronization d. Primitive synchronization 1This is called: A program unit that can be in concurrent execution with other program units a. A subprogram A thread b. c. A library file d. An event 2Which of the following would not be true when "sharing data"? a. Variables declared outside of main are shared. b. Object allocated on the heap may be shared (if pointer is passed). c. Variables on the stack are private: passing pointer to these around to other areas can cause problems. d. Shared variables can be better read and written without synchronization. 3Two kinds of synchronization are a. Priority synchronization b. Cooperation synchronization c. Competition synchronization d. Primitive synchronization

Answer rating: 100% (QA)

For the first part of your question lets define the interfaces Message and MessageInternal in a pseudocode manner interface Message method init method sendmessage REFANY interface MessageInternal meth... View the full answer