External Searching.docx

External Searching The process of accessing a task or sorting data from external storage (outside main memory) is known as External Searching or External Memory Searching. External memory sources may be a hard disk, a network file server with external storage, or a solid state disk. Data managed from external sources to the main memory has speed as one of the main limiting factors. As such, data has to be organized and accessed in a way that will optimize the ultimate speed of the process. In Internal search , data structure is kept in RAM but External search locates and retrieve records stored in hard disks. B-trees are designed for external searches. B-trees stay in the hard disk. Buffer : a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. I/O buffering The process of temporarily storing data that is passing between a processor and a peripheral. The usual purpose is to smooth out the difference in rates at which the two devices can handle data.

I/O Buffering Unbuffered I/O   



Data transfered from (to) user directly to (from) device (no intermediate storage) Each read or write causes an actual (physical) I/O operation run file manager and device handler for each transfer, could cause very high process switching overheads (when transferring characters for instance - possible to get process switch per character) Not the best way - clearly - any alternatives ?

Buffered I/O      

No direct transfer from (to) user to (from) I/O device Used to smooth peaks in I/O traffic Particularly useful for dealing with scenarios where there is a difference in data transfer rates - linking fast devices to slow ones for instance Also useful for storing data temporarily ... OUTPUT : User's output data transferred to OS output buffer. User continues operation, and is only suspended when the buffer becomes full INPUT : OS reads ahead for user. Read normally satisfied from buffer. User is blocked if buffer is empty

The various I/O buffering techniques are as follows: 1. Single buffering: 

When a user process issues an I/O request, the O.S assigns a buffer in the system portion of main memory to the operation.

2. Double buffering  

An improvement over single buffering is by assigning two system buffers to the operations. A process transfers data to one buffer while operating system empties the other

3. Circular buffer  

Double buffering may be inadequate, if the process performs rapid burst of I/O. When two or more buffers are used. The collection of buffers is called as a circular buffer, with each buffer being one unit in the circular buffer.