Final Test

  1. what is an abstraction?
    a view of an entity (either a process or data entity) that includes only the most significant attributes.
  2. process abstraction
    subprograms used from the early days of programming. called "functions" in C or C++.
  3. data abstraction
    Any representation of data in which the implementation details are hidden (abstracted). Abstract data types and objects are the two primary forms of data abstraction.
  4. two primary features of an abstract data type
    packaging of data with their associated operations, and information hiding.
  5. the purpose of a parameterized abstract data type
    allow an abstract data type that can store elements of any data-type.
  6. what is encapsulation?
    organizing programs into collections of logically related code and data, each of which can be compiled without recompilation of the rest of the program.
  7. why do we need encapsulations?
    large programs need a means to organize groups of subprograms, and to provide partial compilation.
  8. what is a naming encapsulation?
    dividing global names into groupings to avoid name collisions.
  9. three major language features needed by OOP
    abstract data types, inheritance, and dynamic binding of method calls.
  10. CLASS
    an abstract data type
  11. OBJECT
    an instance of a class (a particular variable)
    a class that inherits from another class. a.k.a. SUB-CLASS
    the class from which the derived class inherits
  14. METHOD
    a subprogram that defines an operation on objects
    a call to a method
    the entire collection of methods of an object
    one variable per class (in C++ declared static)
    one variable per object (in C++ not static)
    accept messages to the class (in C++ called with no instance)
    accept messages to an object
    class inherits from more than 1 parent
    can be defined in a class that is able to reference (or point to) objects of the class and objects of any of its descendants
    a method that does not include a definition (it only defines a protocol)
  24. what is the "SHARED inheritance" problem with multiple inheritance?
    if two parents both define a method C, how does it reference one or the other version? also called "DIAMOND inheritance"
  25. What is OBJECT SLICING and when can it occur?
    if objects are stack dynamic, there is a problem with assigning subtypes to each other
  26. static binding of method calls
    static binding is faster
  27. dynamic binding of method calls
    if none are dynamic, you lose the advantages of dynamic binding
  28. Smalltalk
    • the first OOP language
    • everything was an object
  29. C++'s three access controls
    • private -- visible only in the class and friends. Disallows subclasses from being subtypes
    • public -- visible in subclasses and clients (users)
    • protected --- visible in the class and in subclasses, but not clients
  30. C++ method statically vs dynamically bound
    a method can be defined to be virtual, which means that it can be called through polymorphic variables (pointers) and dynamically bound to messages. otherwise it is statically bound.
  31. Java methods statically vs dynamically bound
    • all messages are dynamically bound to methods, unless the method is final (i.e., it cannot be overriden, therefore dynamic binding serves no purpose).
    • static binding is also used if the method is static or private, both of which disallow overriding.
  32. what is a Java INTERFACE?
    • includes only method declarations and named constants.
    • a class that implements a particular interface must supply the method(s) specified in the interface.
    • a class implementing an interface can then call certain method(s) that require the interface.
    • provides some of the things multple inheritance is used for.
  33. what is a Class Instance Record (CIR)?
    • stores the state of an object
    • content is static (known at compile time)
    • allocated memory at run-time when objects (instances of a class) come into existence
    • if a class has a parent, the subclass instance variables are added to the parent CIR
    • access to all instance variables is done as it is in records
    • efficient at run-time.
  34. what is the "vtable" is for?
    • Calls to dynamically bound methods are connected to the corresponding code through a vtable
    • all instances of a given class are bound to the same methods, so we need only one vtable per class at run-time
    • we store a pointer to the correct vtable in each object's CIR when the object is created at run-time
    • method calls can be represented as offsets from the beginning of the vtable
  35. physical concurrency
    multiple independent processors.
  36. logical concurrency
    the appearance of physical concurrency by time-sharing one processor.
  37. thread of control
    the sequence of program points reached as the program executes.
  38. task (a.k.a. process or thread)
    a program unit that that can be in concurrent execution with other program units.
  39. race condition
    when two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race).
  40. liveness
    a characteristic of a task that it will eventually complete its execution.
  41. deadlock
    occurs when all tasks in a concurrent environment lose their liveness. can occur when each task "owns" a recource and each task is waiting on the other task's resource in order to continue.
  42. heavyweight task
    each executes in it's own address space, for protection against other tasks.
  43. lightweight task
    all execute in the same address space for efficiency.
  44. cooperation synchronization
    one task must wait for another task to complete some activity before it can proceed. called producer-consumer problem.
  45. competition synchronization
    two or more tasks must use some resource that cannot be simultaneously used.
  46. semaphore
    • a task synchronization data structure consisting of a counter and a queue for storing task descriptors.
    • simplest, but have a disadvantage.
    • semaphores can be used to implement guards on the code that accesses shared data structures.
    • has a counter and queue of tasks.
    • WAIT method suspends task until a resource unit is available.
    • RELEASE makes another unit of a resource available (gives back a resource).
    • semaphores can be used to implement monitors.
    • monitors can be used to implement semaphores.
    • disadvantage is there is no way to check statically (i.e. in the compiler) for the correctness of their use.
  47. monitor
    • an abstract data type for shared data.
    • put the shared data and its operations in the monitor rather than in the client tasks.
    • the monitor implementation guarantees synchronized access by allowing only one access to the shared data at a time (mutually exclusive access).
    • calls to monitor procedures are implicitly queued if the monitor is busy at the time of the call.
    • a better way to provide competition synchronization than semaphores, because monitor can guarantee synchronized access to the shared data no matter how it is used.
    • semaphores can be used to implement monitors.
    • monitors can be used to implement semaphores.
    • support for cooperation synchronization is very similar as with semaphores, so it has the same problems.
  48. message-passing
    • a general model for concurrency.
    • messages can model both semaphores and monitors.
    • messages are not just for competition synchronization.
    • think of seeing a doctor. most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous.
    • to support concurrent tasks with message passing, a language needs:
    • a mechanism to allow a task to indicate when it is willing to accept messages.
    • a way to remember who is waiting to have its message accepted and some "fair" way of choosing the next message (a message queue).
    • when a sender task's message is accepted by a receiver task, the actual message transmission is called a RENDEZVOUS.
  49. ATOMIC operation
    • an uninterruptable operation.
    • the wait and release semaphore operations must be un-interruptable.
    • once "wait" or "release" starts, the task running it cannot be suspended.
  50. what is one problem with using semaphores for task synchronization?
    no way to check statically for the correctness of their use.
  51. what's one advantage of monitor over semaphore?
    • when used to implement competition synchronization the monitor can guarantee synchronized access to the shared data no matter how the client tasks used the monitor.
    • monitors don't help cooperation synchronization more than semaphores.
  52. how do the methods in a Java Thread work?
    • RUN method -- the thread method that executes when the START method is called to start a thread running.
    • JOIN method -- allows task synchronization. Forces a task to delay until the run method of another task has completed (or until it times out).
  53. exception
    any unusual event, either erroneous or not.
  54. exception handler
    the code unit that processes an exception.
  55. finalization
    • sometimes a subprogram needs to complete some computation regardless of how the subprogram terminates (due to an exception or not).
    • finalization is the ability for the programm to specify such a computation.
  56. continuation
    • where does execution continue, if at all, after an exception handler completes its execution?
    • two alternatives:
    • termination -- terminate the program.
    • resumption -- resume the program somewhere.
  57. exception propagation
    allows a high level of reuse of exception handling code.
  58. why do we have exceptions in programming languages?
    • writing code to check for error returns from subprograms is tedious and clutters the program.
    • encourages programmers to consider many different errors.
    • exception propagation allows a high level of reuse of exception handling code.
  59. what's the difference between an event and an exception?
    event isn't necessarily unexpected.
  60. what's an EVENT DRIVEN program?
    • one in which various parts of the program are executed at unpredictable times, triggered by user interactions (events).
    • litttle or no code executed in an order determined by the program itself.
  61. what is a logic programming language?
    specifies the characteristics of results, not a procedure for producing results.
  62. PROLOG FACT Statements
    • female(shelley)
    • male(bill)
    • father(bill,jake)
  63. PROLOG RULE Statements
    • consequence :- antecedent
    • parent(X,Y) :- mother(X,Y)
    • parent(X,Y) :- father(X,Y)
    • grandparent(X,Z) :- father(X,Y), parent(Y,Z) 
  64. PROLOG GOAL Statements
    • man(fred)
    • father(X,mike)
  65. what are some deficiencies of prolog?
    • the order of attempted matches is nondeterministic and all matches should be attempted concurrently (but aren't).
    • CLOSED-WORLD assumption: the only knowledge is what is in the database.
    • NEGATION problem: anything not stated in the database is assumed to be false
Card Set
Final Test
Study Guide for Final Exam of CISS 445