DATA STRUCTURES

POINTS TO REMEMBER

1. Data refers to a set of values which may represent some observation from an experiment ,facts,figures gathered systematically for one or more specific purposes.A data is the single unit of values of certain type that have meaning to its user.

2. A file is collection of related records. A record is a collection of related files.A field holds a particular kind of data.

3. Each entity has certain properties also known as its attributes that describes it.Entity set is a collection of entities of same type that share the same properties or attributes.

4. The key which is chosen to uniquely identify a record is called primary key and other key(s) are known as alternate key(s).

5. Information is defined as the processed summarized or organized data which when used by its recipient helps in taking decisions.

6. Data structure is a logical or mathematical model of a particular arrangement or organization of data.An efficient data structure uses minimum memory space and execution time to process the structure as possible.

7. An array is a finite ordered set of homogeneous elements.In computer memory , array elements are stored in contiguous memory locations. Each element of an array has a fixed and unique index .

8. A linked list is a dynamic data structure containing of nodes where each node is composed of data and a pointer to the next node.

9. A stack is a linear data structure in which all insertions and deletions are restricted only at one end called the top of the stack.A stack is often described as LIFO(Last In First Out).For example stack of coins are above the other. The basic operation performed on stack are 'Push' and 'Pop'.

10.Traversing , searching , insertion, deletion , sorting , merging , copying , concatenation are key operations performed on a data structure.

11. (a)An algorithm is a sequence of steps or instructions required to solve a given problem.(b)The analysis of algorithm is based on how much memory an algorithm needs to solve a particular problem is called the space complexity of an algorithm.(c)Measure of time complexity of an algorithm where we disregard certain terms of a function to express the efficiency of algorithm is called asymptotic complexity.

12. A tree is a multilevel data structure that represents a hierarchical relationship between finite set of individual elements called nodes.

13. A graph is a non linear data structure that consists of set of nodes (or vertices ) and set of edges , with each edge going from one node to another .Each edge in the graph depicts a relationship between pair of nodes.

Symmetric vs Asymmetric Multiprocessing

Symmetric vs Asymmetric Multiprocessing

Asymmetric multiprocessing - In asymmetric multiprocessing (ASMP), the operating system typically sets aside one or more processors for its exclusive use. The remainder of the processors run user applications. As a result, the single processor running the operating system can fall behind the processors running user applications. This forces the applications to wait while the operating system catches up, which reduces the overall throughput of the system. In the ASMP model, if the processor that fails is an operating system processor, the whole computer can go down.

Symmetric mMultiprocessing - Symmetric multiprocessing (SMP) technology is used to get higher levels of performance. In symmetric multiprocessing, any processor can run any type of thread. The processors communicate with each other through shared memory.
SMP systems provide better load-balancing and fault tolerance. Because the operating system threads can run on any processor, the chance of hitting a CPU bottleneck is greatly reduced. All processors are allowed to run a mixture of application and operating system code. A processor failure in the SMP model only reduces the computing capacity of the system.

SMP systems are inherently more complex than ASMP systems. A tremendous amount of coordination must take place within the operating system to keep everything synchronized. For this reason, SMP systems are usually designed and written from the ground up.

SIMD(Single-Instruction Stream Multiple-Data Stream)

A graphical representation of a True, Distributed Memory SIMD architecture

                         

 This architecture is essential in the parallel world of computers. Its ability to manipulate large vectors and matrices in minimal time has created a phenomenal demand in such areas as weather data and cancer radiation research.

The architecture consists of a set of identical processing elements (PEs), capable of performing the same operation on different data sets simultaneously. The SIMD allows for a faster and better way to visualize graphics, rendering them almost flawlessly as well as creating them faster.

SIMD architecture is two fold; True SIMD and Pipelined SIMD: 

• True SIMD
  • Distributed Memory
  • Shared Memory
• Pipelined SIMD

                                                  MIMD(Multiple Instruction stream, Multiple Data stream)

•  MIMD has clearly emerges the architecture of choice for general-purpose mutiprocessors.
•  MIMD machines offer flexibility.
•  With the correct hardware and software support, MIMDs can function as single user machines focusing on high performance for one application, as multiprogrammed machines running many tasks simultaneously, or as some combination of these functions.
•  There are two types of MIMD architectures: distributed memory MIMD architecture, and shared memory MIMD architecture.

Short notes on DMA - DIRECT MEMORY ACCESS

CPU BUS SIGNALS FOR DMA TRANSFER

• The DMA request line is used to request a DMA transfer.
• The bus request (BR) signal is used by the DMA controller to request the CPU to relinquish control of the buses.
• The CPU activates the bus grant (BG) output to inform the external DMA that its buses are in a high-impedance state (so that they can be used in the DMA transfer.)
• The address bus is used to address the DMA controller and memory at given location
• The Device select (DS) and register select (RS) lines are activated by addressing the DMA controller.
• The RD and WR lines are used to specify either a read (RD) or write (WR) operation on the given memory location.
• The DMA acknowledge line is set when the system is ready to initiate data transfer.
• The data bus is used to transfer data between the I/O device and memory.
• When the last word of data in the DMA transfer is transferred, the DMA controller informs the termination of the transfer to the CPU by means of the interrupt line.

INTEL 8251A(USART)....(points to remember)

Block diagram of the 8251 USART (Universal Synchronous Asynchronous Receiver Transmitter)

The 8251 is a USART (Universal Synchronous Asynchronous Receiver Transmitter) for serial data communication. As a peripheral device of a microcomputer system, the 8251 receives parallel data from the CPU and transmits serial data after conversion. This device also receives serial data from the outside and transmits parallel data to the CPU after conversion.





                                        operation between a CPU and the device.

MASTER SLAVE J-K FLIP FLOP(short notes)

CIRCUIT DIAGRAM

Truth Table 

master slave jk flip flop timing diagram

PARALLEL PROCESSING UNIT

 1. Multiprocessor - is a system having two or more processor and it executes more than one  processes.Main feature of multiprocessor is to share main memory or other resources by all processors.In this one master CPU will control all other processors.The other processor maybe co-processor or input-output processors.

The basic characteristics of multiprocessor system are :
1)This system must have more than one processor.All these processor must have nearly identical processing            
capabilities.

2)All these processor must have common shared memory.

3)Processors share all I/O devices or other resources.

4)The interaction among processor at program level must be defined precisely to have a good and efficient design of hardware for a multiprocessor system.

5)The system configuration can be enhanced at required increments at any point of time.


TYPES OF MULTIPROCESSOR 
(A) Rightly Coupled
(B)Loosely Coupled

Rightly coupled shares common memory and each processor has its own local memory where loosely coupled does not have its own shared memory although each processor will have its own local memory.

The processor used in these types of system are specialized to handle different tasks.This system increases the  overall reliability of system, that means if more than one processor fails, their load is being shared by other processor.

Different schemes used for interconnection of processors and memories are : 

1.) Common Bus : This scheme will provide single bus for interconnection of processors and memory.Its is most effective and simple.
The failure of bus system results in total system failure.The performance of overall system is being limited by data transfer of bus.

2.)Multiple Bus Organisation :This system will provide two or more buses for interconnection of processor and memory.This scheme allows multiple data transfer simultaneously.This will increase reliability without increasing the cost too much.

3.)Crossbar Organisation : This scheme provides interconnection of n processor and n memory modules using switch elements.Switch element is having electronic circuit to provide desired path, it supports priority logic to resolve conflicts.
The hardware implementation is complex as compared to multiple bus organisation.

4.)Multistage Interconnection Network : 

FILE ORGANIZATION

DIFFERENT FILE ORGANIZATION

File organization basically refers to the logical arrangement of data, which can be organized in a system of records with co-relation between the fields /columns, in a file system.It refers to the way records are physically arranged on a storage device.

TYPES of file organzation:

1. Heap(unordered) file organization :  the record can be stored where there is storage space available.There  is no fixed order for records.
2. Sorted file organization: the records are stored in sequential order according to the search key of record. 

    -Sequential(SAM)

    -Line Sequential(LSAM)

    -Indexed Sequential(ISAM)

3. Hashed or Direct : with hashed access or direct a portion of disk space is reserved. Records are placed randomly throughout the file.records are accessed by address that specify their disc location.It has an excellent search retrieval performance, but care must be taken to maintain the indexes.

WHAT IS A FILE ?

A file is a collection of bytes stored in secondary storage device, which is generally a disk of some kind.

The collection of bytes may be interpreted, for example , as characters , words , lines , lines , paragraphs and pages from a textual documents ; fields and records belonging to a data base.

It is simply a machine deciphered storage media, where programs and data are stored for machine storage.

METHODS OF ORGANIZING FILES

1. Sequential Organization : a sequential file contains records organised in the order they were entered.The order of records is fixed.The records are stored and sorted in physical ,contiguous blocks within each block the records are in sequence.

Records in these files can be read or written sequentially.Once stored in the file , the record cant be edited i.e cant be made shorter , longer or deleted. However the record can be updated if the length does not change.

New records will appear at the end of the file.