Page 81 - DLIS108_INFORMATION_AND_COMMUNICATION_TECHNOLOGY_APPLICATIONS

VED1
e\L-lovely-eng\comm8-1.pmd IInd 16-9-11 IIIrd 22-12-11 IVth 4-1-12

Information and Communication Technology Applications

many Ps as Vs; this is difficult to keep straight. (A lock is a one-bit semaphore; unlocking it
Notes twice is either an error or has no effect.)
• Monitors: A module or abstract data type that can be visited by only one process at a time.
This solves the mutual exclusion but not the control synchronization. To solve the latter, pro-
cesses which find they cannot continue execute a wait () on a condition variable, which puts
them in a queue for that variable outside the monitor. If a process does something that might
make a given condition true, it does a signal () on that condition, which alerts those in the
queue for that condition. This is still difficult, but less so than semaphores.
• Message passing: The produced item (query, block of data or what not) is sent in a message to
the other process. This provides control synchronization and mutual exclusion in one, and
does not require shared memory, but is less efficient, and in some cases harder to use.
• The sender does a send (), the receiver may or may not do an explicit receive (). There are
many choices to be made here: direct versus indirect naming of the parties involved; synchro-
nous versus asynchronous communication; explicit versus implicit receive (); one-way ver-
sus two-way communication. The language SR has it all.
• Rendezvous (Ada): Two-way message passing with explicit receive. Remote procedure call
(RPC): two way message passing with implicit receive.
• Linda: Implements a very specific shared object type, the tuple, with implicit guards and
mutual exclusion. Orca: allows the user to implement their own shared object types, with
explicit guards and implicit mutual exclusion.

8.7 Other Paradigms

• Paradigms can be classified according to how they access and manipulate the program state.
• Constraint Programming: Define the solution to your problem as a set of restrictions on the
values in it. The system then has to find all the solutions that satisfy the restrictions.
• In practice the search space is too large and too badly structured for this to work.
• There are Two Ways Out: Restrict the domain to something simple: and require the pro-
grammer to structure the search space better by supplying condition-action rules.
• Access-Oriented Programming: Changing a variable causes actions that change other vari-
ables and that propagate to do the work for you.
• Single-Data-structure Languages: Simplify (?) programming by supplying one very power-
ful data type only. They are good for rapid prototyping.
• The sets of SETL provide breadth-first search, the OK/FAIL mechanism depth-first search.
• The SETL oracle function OK sets a choice (backtrack) point and returns TRUE. If a FAIL is
then executed, it returns to the last choice point, clears it, and resumes the OK function, which
now returns FALSE.
• Dataflow Programming: Each operator and function is implemented by a separate processor,
which does its work as soon as the operands are available. This get you optimal fine-grained
parallelism without programmer help. Also, all dataflow languages are single-assignment.
• Functional languages would be ideal dataflow languages but for one problem: They are re-
cursive.
• First Solution: Do dynamic code copying when recursion is needed. This is done by tagging
the variables with an incarnation tag.

76 LOVELY PROFESSIONAL UNIVERSITY