OS Notes

1.     The minimum number of frames per process (in a demand paged environment) is defined by the computer architecture (or instruction set architecture), whereas the maximum number is defined by the amount of available physical memory.

2.     In any case, we are faced with three major components of the page-fault service time:

1. Service the page-fault interrupt.

2. Read in the page.

3. Restart the process.

3.     The Hardware for demand paging is same as that for paging. Hardware does mapping of logical to physical address plus provides protection and legality of address space.

4.     Number of page faults on a reference string S in LRU is same when S is reversed and LRU is used on it too. Same is the case for optimal page replacement strategy

5.     Dispatcher is looks to see if the desired process to be scheduled by the scheduler is available in memory or not. If not then it swaps out some process and swaps in the desired process.

CN: Aloha vs CSMA

Efficiency Comparison of Aloha and CSMA

In Aloha, a station never senses before transmission.

Collisions are possible in two ways –

1. A station starts transmitting when some frame is already propagating through the
medium.

2. A station transmits when a frame is about to reach that station before it completes its
transmission.

Let K be the no. of frames generated by the system of stations out of which X frames
were transferred successfully, hence,

Aloha - Efficiency = X / K.

Let no. of collisions = a+b

where a= case 1 collisions, b= case 2 collisions
X=k - (a+b).

hence, Aloha - efficiency = [K - (a + b)] / K

Where as in CSMA the medium is sensed, thus now the collisions of case 1 will never
happen in CSMA. Plus such frames will also not be generated in the network system.

hence, CSMA - Efficiency = [K - (a + b)]/ (K - b).
Clearly, [CSMA - efficiency] > [Aloha - efficiency]

CN: CSMA JAMMING SIGNAL

The jam is sent to ensure that all devices on an Ethernet segment know that a collision has occurred and that errors detected by other devices receiving the signal do not mistake this as noise. When a collision occurs both transmitters will detect the collision. Receivers will only detect the collision by receiving the jam signal. Transmitters detect the collision by comparing what is being sent, by what is being received (this is why it is called a "transceiver" because it transmits and receives at the same time). If the received signal differs from the transmit, a collision has occurred, and it sends a jam to notify the receivers to drop the frame and mark it as a collision. The collision is what triggers the backoff timer on the transmitter, not the jam signal. Both transmitters will always detect the collision.

The standard diameter of a 10Mbps Ethernet is 232 bit delay or 23.2 us. Thus the round trip time is 464 bit delay or 46.4 us. The transmitting station, say A, keeps sending the data frame for this period of time. Simultaneously it also receives that data frame. If for the entire duration of 46.4 us it receives what it had sent, then it means that all stations in the network are aware that it (station A) is sending a data frame, and thus hold their transmissions. Thus it is now ensured that no other station will transmit for a next slot time period, and so the station A sends the remaining data of the frame (which includes a 32 bit CRC) in continuation after 46.4 us.

But if station A received, at some point of time, something different from what it was sending then it means that collision has occurred coz some other station also started its transmission before it could have sensed station A’s frame on the channel. Thus the station A now must some how intimate the receiver about the corrupt data it will receive. This intimation is done with the help of JAMMING SIGNAL.

As soon as collision is detected (at worst at the 46.4^th us), the station A aborts transmission and sends a 48 bit jamming signal instead of the remaining data. A jamming signal is a special sequence of repeated “10” bit combination which acts as a CRC not confirming to any valid data possible. And thus the receiver will discard the data.

NOTE: The slot time and round trip time differ by the maximum JAM TIME. For a 48 bit jamming signal,

Slot Time = Round Trip Time + 4.8 us

And since, Round Trip Time = 46.4 us, therefore, Slot time = 51.2 us

ARCHITECTURE: INTERRUPTS SOLVED

INTERRUPTS

1. Hardware Interrupts.
2.  Software Interrupts.
3.   Exceptions.

HARDWARE INTERRUPTS –

They are also called Asynchronous Interrupts, coz they can occur anytime without any knowledge beforehand.

       NMI 

            INTR 

NMI – It can’t be ignored by the system. It is used to handle situations that must be handled without any delay. Example –

Parity Error in Disk
Erroneous Bus Arbitration
Power Failure
Emergency Shut Off, etc

INTR – All I/O devices gain systems attention through this pin on Microprocessor. Example –


     Key Stroke on keyboard
     Mouse Click, etc

SOFTWARE INTERRUPTS –

These are interrupts that are generated due to INT instructions mentioned in the program itself (this is why they are also called Synchronous Interrupts). Corresponding to an INT instruction there is an ISR (Interrupt Service Routine) to which the processor is redirected with the help of IVT (Interrupt Vector Table). The ISR in the end contains an IRET instruction which pops out the flag register values and then restores the previous execution sequence. This is where IRET differs from a simple RET, which does not involve popping of flag values, it just restores the previous execution sequence. Example of s/w interrupts –

INT 33H
INT 34H, etc

EXCEPTIONS –

These are the interrupts that are caused internally in the processor itself. They are caused when a situation arises that can’t be handled by the processor alone.

They are similar to software interrupts in the way that they are just like INT instructions and redirect the control to an ISR through the IVT. But the difference is that they are known to the processor, in other words,  the number “n” of the “INT n” is given by the processor itself and not by the programmer as in case of INT instructions written by him in his program.

Different Types of Exceptions –

Faults
Traps
Aborts

Fault – It occurs before or during the execution of an instruction. The address of the instruction stored in the stack before jumping off to ISR (so as to rectify the fault) is the address of the instruction that was to be or was being executed, so that when the processor resumes, then it could re-execute the instruction after rectification is made by user through the ISR. Example –

Page Fault.

Trap – It occurs after the execution of an instruction, when something unexpected happens that requires the user to handle the exception. Example –

Divide by Zero
Overflow
Single Step Execution or Trace (together with the TRAP Flag)
Breakpoint
Bounds Exception
Invalid Op-code

Abort – It usually occurs due to very serious failures, such as hardware failures or invalid system tables. Because of this, it may happen that the address of the error cannot be found. Therefore, recovering program execution after an abort is not always possible, thereby leaving the only option of terminating or aborting the program that caused such exception. 

MATHEMATICS : CUT SET

1. In a connected graph G, a cut-set is a set of edges whose removal from G leaves G disconnected, provided removal of no proper subset of these edges disconnects G.

A cut-set always "cuts" a graph into two. And hence reduces the rank of the graph by one.

2. If we partition all the vertices of a connected graph G into two mutually exclusive subsets, a cut-set is a minimal number of edges whose removal from G destroys all paths between these two sets of vertices.

3. Every edge of a tree is a cut-set.

4. Cut-sets are of great importance in studying properties of communication and transportation networks. We wish to find out if there are any weak spots in the network that need strengthening by means of additional telephone lines. We look at all cut-sets of the graph, and the one with the smallest number of edges is the most vulnerable.

5. Consider a spanning tree T in a connected graph G and an arbitrary cutest S in G.

Is it possible for S not to have any edge in common with T ?

The answer is NO. Otherwise, removal of the cut-set S from G would not disconnect the graph. Every cut-set in a connected graph G must contain at least one branch of every spanning tree of G.

6. Will the converse also be true? The answer is yes, In a connected graph G, any minimal set of edges containing at least one branch of every spanning tree of G is a cut-set.

7. Every circuit has an even number of edges in common with any cut-set.

8. An edge incident on a pendant vertex is one such example, i.e., an edge incident on a pendant vertex is a branch of every spanning tree, since only that edge is a link to that vertex. Thus such an edge alone in a set is itself a cut set.

Here EF is a branch of every spanning tree and thus taken as a set it becomes the cut set.

                   

9. A cut-set S containing exactly one branch of a tree T is called a fundamental cut-set with respect to T.

Every chord of a spanning tree defines a unique fundamental circuit, every branch of a spanning tree defines a unique fundamental cut-set.

The ring sum of any two cut-sets in a graph is either a third cut-set or an edge disjoint union of cut-sets. Hence, union of any two cut set may not necessarily give a third cut set. (This is just like union of two fundamental circuits, which will either give another circuit or will be just edge disjoint union).

There are two points, each one being converse of another and both are true–

• A chord which forms a fundamental circuit C in a spanning tree of a graph belongs to every fundamental cut set and only those fundamental cut sets which are formed by the branches in C.

• A branch which forms a fundamental cut set F with respect to a spanning tree of a graph belongs to every fundamental circuit and only those fundamental circuits which are formed by the chords in F.

eBay

General Aptitude Topics

I. NUMERICAL ABILITY

QUANTITATIVE APTITUDE

1. SIMPLE EQUATIONS; RATIO PROPORTION AND VARIATION
2. NUMBERS AND NUMBER SYSTEMS
3. PERCENTAGES-PROFIT&LOSS; PARTNERSHIPS; SIMPLE INTEREST; COMPOUND INTEREST
4. AVERAGES; MIXTURES; ALLIGATIONS
5. PROGRESSIONS
6. TIME AND WORK
7. TIME AND DISTANCE
8. DATA SUFFICIENCY
9. DATA INTERPRETATION

REASONING

1. NUMBER AND LETTER SERIES
2. ANALOGIES
3. ODD MAN OUT
4. CODING AND DECODING
5. BLOOD RELATIONS
6. VENN DIAGRAMS
7. SEATING ARRANGEMENTS
8. PUZZLES
9. CLOCKS AND CALENDARS

II VERBAL ABILITY

1. GRAMMAR
2. SENTENCE COMPLETION
3. SYNONYMS
4. ANTONYMS
5. ANALOGIES
6. LOGICAL REASONING

Syllabus for Computer Science and Information Technology (CS)

ENGINEERING MATHEMATICS

Mathematical Logic:

 Propositional Logic; First Order Logic.

Probability: 

Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.

Set Theory & Algebra: 

Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra.

Combinatory:

 Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics.

Graph Theory:

 Connectivity; spanning trees; Cut vertices & edges; covering; matching; independent sets; Colouring; Planarity; Isomorphism.

Linear Algebra:

 Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors.

Numerical Methods:

 LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules.

Calculus:

 Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima & minima.

COMPUTER SCIENCE AND INFORMATION TECHNOLOGY

Digital Logic:

 Logic functions, Minimization, Design and synthesis of combinational and sequential circuits; Number representation and computer arithmetic (fixed and floating point).

Computer Organization and Architecture:

 Machine instructions and addressing modes, ALU and data-path, CPU control design, Memory interface, I/O interface (Interrupt and DMA mode), Instruction pipelining, Cache and main memory, Secondary storage.

Programming and Data Structures:

 Programming in C; Functions, Recursion, Parameter passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps.

Algorithms:

 Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching. Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Basic concepts of complexity classes – P, NP, NP-hard, NP-complete.

Theory of Computation:

 Regular languages and finite automata, Context free languages and Push-down automata, Recursively enumerable sets and Turing machines, Undecidability.

Compiler Design: 

Lexical analysis, Parsing, Syntax directed translation, Runtime environments, Intermediate and target code generation, Basics of code optimization.

Operating System: 

Processes, Threads, Inter-process communication, Concurrency, Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File systems, I/O systems, Protection and security.

Databases:

 ER-model, Relational model (relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B and B+ trees), Transactions and concurrency control.

Information Systems and Software Engineering: 

information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance.

Computer Networks: 

ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs, switches, gateways, and routers. Network security – basic concepts of public key and private key cryptography, digital signature, firewalls.

Web technologies:

 HTML, XML, basic concepts of client-server computing.