Computer Science

A computer system can be divided into 5 components:

1. Hardware
2. Software
3. Data
4. Procedures
5. Personnel

In studying Computer Systems' Architecture, only the first 3 of these are of direct interest.

• Processor
  • a.k.a. CPU / Central Processing Unit
  • Components:
    1. ALU / Arithmetic Logic Unit: arithmetic & Boolean logic operations
    2. CU / Control Unit: instruction processing sequencing and control
    3. Interface Unit: (internal) bus structure
  • Alternate View
    1. Execution Unit: instruction circuits (including ALU)
    2. Control Unit: instruction retrieval, sequencing, and EU sub-circuit selection
    3. Registers: limited, quick-access data "containers" and "flags"
    4. Internal Bus Interface
• Input & Output Devices
  • Actual electrical or electro-mechanical IO devices (e.g. keyboards, printers, video monitor) will not be considered as significant in our study of Computer Systems' Architectures.
• Input & Output InterfaceExternal Bus Structurecollection of "wires" that carries power and signals between different computer componentsChannelseparate, special purpose IO processor connecting an IO device to the CPU (or "main memory"); may perform signal conversion, timing control, buffering, etc.Communicationsdirect/indirect connection to other computer systems based on pre-agreed upon "protocol" (shared rules for how communication is to take place
• Storage / Memory
• • (Main) Memory / Primary Storage addressed cellseach containing a binary patternunits:byte(typically 8 "bits") - characterword(typically 32 "bits" but many different sizes are found on different computer systems) - basic numeric unit; basic unit of data transferKbytes210 bytes (1024)Mbytes220 bytes (1,048,576)Gbytes230 bytes (1,300,109,824)usage:
    • "active" data and instructions (i.e. instructions and data currently being processed
    • John vonNeumann & stored program concept vs. Babbage's engine with separate data and instruction stores
  RAM vs. ROMROM is non-modifiable (by normal computer operation)
• (Secondary) Storage
  • long-term (inactive) data and program storage
  • examples: disk, tape, CD
  • units: typically stored in "blocks" of multiple words/bytes (physical records)
• REGISTERSMAIN MEMORYSECONDARY STORAGESPEEDvery fastfastslowDURATIONvery short-termshort-term (while program is active)long-termPOWER DOWN EFFECTdata lostRAM- data lost; ROM - data maintainedmaintainedSIZE OF UNIT TRANSFERREDbit, byte, or wordbyte or wordphysical record most commonALU ACCESSyesindirect onlyno

• System Software
  • Operating System
  • Utilities (may be built into OS or external programs)
• Application Software
  • Application tools: word processors, spreadsheet managers, etc.
  • Corporate applications: in-house systems e.g. inventory management
• High-level vs. Machine-level Software
  • High-level: "source" instructions in a language such as COBOL
  • Machine-level: binary patterns with no immediate human meaning
  • High-level instructions must be converted into Machine-level instructions before they can be processed by a "processor"; this conversion is a one-to-many process
• Instruction Classes
  • data transfer (copying data)
  • data transform (modifying data)
  • instruction flow control (changing the default sequence)

In general, digital computers (the only type considered in this course) represent values as patterns of "off" and "on" signals. Each value requires a different pattern (or, at least, a pattern which is different from any other value of the same type). Different types of values generally are represented using different "encoding schemes". An "encoding scheme" specifies how many "off" and "on" signals are required for each value, and provides a unique pattern of signals for each possible value.

"Information" is "data" which has meaning. The most common task of a computer system (especially when the input source and the output destination are the same) is to transform data into information. In fact, this is sometimes used as the basis for alternative definitions of a computer system .

The concept of "meaning" can be difficult. Generally, we think of "meaning" as implying that something with intelligence exists for which the "data" has meaning. When the output of a computer system is the automated control of some other system (as in CAD, Computer Aided Manufacturing), we end up debating, the unresolved question of what is meant by "intelligence".

Note that the IPO(S), Input-Process-Output(-Storage), model is applied to at least two different areas:

1. the collection of "equipment" that makes up a computer system
2. the "actions" that a computer system is capable of performing.

Power or energy sources required to enable operation of the computer system are not "inputs".

• selecting subsets of the data
• counting and accumulating totals of selected data values
• re-arranging the sequence or "format" of data

For the purposes of this course memory (or "storage") will be considered to be an essential element of any computer system.

• ignore the problem altogether ie. ostrich algorithm it may occur very infrequently, cost of detection/prevention etc may not be worth it.
• detection and recovery
• avoidance by careful resource allocation
• prevention by structurally negating one of the four necessary conditions.

Make sure atleast one of the 4 deadlock conditions is never satisfied.

This may however be even more conservative than deadlock avoidance strategy.

• Attacking Mutex condition

• never grant exclusive access. but this may not be possible for several resources.

• Attacking preemption

• not something you want to do.

• Attacking hold and wait condition

• make a process hold at the most 1 resource at a time.
• make all the requests at the beginning. All or nothing policy. If you feel, retry. eg. 2-phase locking

• Attacking circular wait

• Order all the resources.
• Make sure that the requests are issued in the correct order so that there are no cycles present in the resource graph.

  Resources numbered 1 ... n. Resources can be requested only in increasing order. ie. you cannot request a resource whose no is less than any you may be holding.

Think of it as a state machine moving from 1 state to another as each instruction is executed.

Safe state is one where

• It is not a deadlocked state
• There is some sequence by which all requests can be satisfied.

To avoid deadlocks, we try to make only those transitions that will take you from one safe state to another. We avoid transitions to unsafe state (a state that is not deadlocked, and is not safe) eg.

Total # of instances of resource = 12

(Max, Allocated, Still Needs)

P0 (10, 5, 5) P1 (4, 2, 2) P2 (9, 2, 7) Free = 3 - Safe

The sequence is a reducible sequence

the first state is safe.

What if P2 requests 1 more and is allocated 1 more instance?

- results in Unsafe state

So do not allow P2's request to be satisfied.

When a request is made, check to see if after the request is satisfied, there is a (atleast one!) sequence of moves that can satisfy all the requests. ie. the new state is safe. If so, satisfy the request, else make the request wait.

Max[n * m]

Allocated[n * m]

Still_Needs[n * m]

Available[m]

Temp[m]

Done[n]

while () {

Temp[j]=Available[j] for all j

Find an i such that

a) Done[i] = False

b) Still_Needs[i,j] <= Temp[j]

if so {

Temp[j] += Allocated[i,j] for all j

Done[i] = TRUE}

}

else if Done[i] = TRUE for all i then state is safe

else state is unsafe

}

One resource of each type (1 printer, 1 plotter, 1 terminal etc.)

• check if there is a cycle in the resource graph. for each node N in the graph do DFS (depth first search) of the graph with N as the root In the DFS if you come back to a node already traversed, then there is a cycle. }

Multiple resources of each type

• m resources, n processes
• Max resources in existence = [E1, E2, E3, .... Em]
• Current Allocation = C1-n,1-m
• Resources currently Available = [A1, A2, ... Am]
• Request matrix = R1-n,1-m
• Invariant = Sum(Cij) + Aj = Ej
• Define A <= B for 2 vectors, A and B, if Ai <= Bi for all i
• Overview of deadlock detection algorithm,

  Check R matrix, and find a row i such at Ri < A.

  If such a process is found, add Ci to A and remove process i from the system.

  Keep doing this till either you have removed all processes, or you cannot remove any other process.

  Whatever is remaining is deadlocked.

  Basic idea, is that there is atleast 1 execution which will undeadlock the system

• through preemption
• rollback
  • keep checkpointing periodically
  • when a deadlock is detected, see which resource is needed.
  • Take away the resource from the process currently having it.
  • Later on, you can restart this process from a check pointed state where it may need to reacquire the resource.
• killing processes
  • where possible, kill a process that can be rerun from the beginning without illeffects

I'm sure you can do but:

• do you have any scuba diving qualifications/experience
• what kind of technology were you working on
• Do you know a guy in the business.

with a diploma in engineering, I'm pretty sure you can do anything with some sort of engineering based profession you want to.

if you make it your goal. yes you can.