Computer Science

In JavaScript we have the following conditional statements:

• if statement - you would use this statement to execute some code only if a specified condition is true
• if...else statement - you would use this statement to execute some code if the condition is true and another code if the condition is false
• if...else if....else statement - you would use this statement to select one of many blocks of code to be executed
• switch statement - you would use this statement to select one of many blocks of code to be executed

For example: If StatementUse the if statement to execute some code only if a specified condition is true. Syntaxif (condition)

{

code to be executed if condition is true

}

If...else StatementUse the if....else statement to execute some code if a condition is true and another code if the condition is not true. Syntaxif (condition)

{

code to be executed if condition is true

}

If...else if...else StatementUse the if....else if...else statement to select one of several blocks of code to be executed. Syntaxif (condition1)

{

code to be executed if condition1 is true

}

else if (condition2)

{

code to be executed if condition2 is true

}

else

{

code to be executed if condition1 and condition2 are not true

}

else

{

code to be executed if condition is not true

}

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.

Hardware

• 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

Software

• 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)

DataOne of the major requirements of any computer system is the ability to represent and manipulate values ("data").

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.

Data vs. InformationTwo terms common in any discussion of computer systems are "data" and "information". The difference in meaning between these two terms is based on the concept that "information" is "data" which has "meaning" to someone (or something) outside of the computer system.

"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".

1. The IPO(S) ModelA computer system can be thought of as a collection of components which together are capable of 3 operations: Input, Processing, and Output. A fourth operation, Storage, is also required for practical computer systems.

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.

Input:A computer system must include a method for accepting "data" and "instructions" from outside the system.

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

Processing:A computer system must include the ability to change or "transform" data which has been input. These "transformations" typically include (but are not limited to)

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

Output:A computer system must include the ability to send processed data to outside the system in a form that can be used by the "outside world". This "outside world" might be the human "users" of the computer system, but alternatively could be electrical or mechanical controls for automated equipment, or the "inputs" for some other system. Storage:We would not normally consider a collection to be a computer system unless it included some form of memory of previous input or processed data. For example, system composed of an electrical power supply, an on/off switch, a light bulb, and appropriate wiring to connect the other three components would not normally be considered to be a computer system (although it contains IPO elements of a basic form). Replacing the on/off switch with a "toggle button", which would reverse the current on/off "state" of the light, would give us something closer to a computer system.

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.

Deadlock PreventionDifference from avoidance is that here, the system itself is build in such a way that there are no deadlocks.

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.

Deadlock AvoidanceAvoid actions that may lead to a deadlock.

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

Safe State

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.

Banker's Algorithm for Deadlock Avoidance

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.

How do you find if a state is safen process and m resources

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

}

Detection and RecoveryIs there a deadlock currently?

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

Recovery

• 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