Disk Scheduling Algorithms

In modern system, the different process can access to the system’s resources simultaneously, such as the storage disk. There will be many pending request for the disk to process. The time required is determined by three factors.

  1. Seek time (the time to move the drive head to the proper cylinder).
  2. Rotation delay (time time to rotate the proper sector under the head.
  3. Actual data transfer time.

The seek time dominate the other two time in most disk, so reduce the seek time can improve system performance substantially. The following are the algorithms for scheduling.

Read more…

Friday, December 10th, 2010 at 00:53

Floppy Disk Controller

A floppy disk controller (FDC) is a device that controls reading from and writing to floppy disk drive. There are a range of chips have been produced for this function, such as µPD765, 8272A, 82078,82077sl & 82077AA. For morden system, a model of FDC has been embed in motherboard chipset.

A FDC can support up to 4 floppy disk drives. It is linked to the system bus and accessed by IO ports. It also connect to a DMA controller, usually connect to channel 2. Floppy disk uses CHS addressing mode. There are always 2 heads and typically it is 80 cylinders and 18 sectors per track. In usually CHS addressing mode, the cylinder and the head start from 0 while the sector start from 1. Asking section number 0 is illegal and this is major source of errors in driver code.

CHS addressing mode: It is the early method of giving the address of data block in the disk. In order to read or write, the driver must move the drive to the right head to right track and the right sector on the disk. This schema is usually used in floppy disk.

LBA addressing mode: logical Block Addressing mode is simply linear addressing schema, The blocks are located by index and start from 0. This schema mornally used in hard disk.

Read more…

Tuesday, October 26th, 2010 at 08:54

Direct Memory Access

Direct Memory Access (DMA) is a feature in modern computers that allow devices to read or write data from or to system momery whithout the interaction with CPU. With the DMA, the CPU initiate the transfer and do other oprations duiring the DMA controller doing the transfer, and CPU will receive an interrupt once the operation has been done. Hence the CPU get freed from the overhead of data transfer.

Two DMA types

Conventional DMA is called third-party DMA (ISA DMA), which means the DMA controllers(third-party component) on the motherboard coordinate the DMA transfers. But these controllers are slow and tied to the old ISA bus, which was abandoned for hard disk interfaces for performance reason. There are very few devices use this type now, only internal floppies, some embeded sound chips, some parallel ports and some serial ports.

The modern one is first-party DMA, which means the preripheral device itself dose the transfer whithout external DMA controller involed. This is also called bus mastering, during the transfer the device take the ownership of the bus. Bus mastring requires PIC bus. Modern IDE/ATA hard disk use this type DMA.

Read more…

Saturday, October 9th, 2010 at 16:48

Volatile variable

Volatile is a type qualifier that tells the complier the value of varible will change at any time,  modified by multiple processes other than the present program. Based on this information, the compiler may refrain from optimizing access to the variable.

Sample code:

int foo;
void bar(void) {
   foo = 0;
   while (foo != 255)
      ;
}

If compile it with optimization option, the complier  will notice that no other code can possibly change the value stored in foo, and will assume that it will remain equal to 0 at all times. The compiler will therefore replace the function body like this:

void bar_optimized(void) {
    foo = 0;
    while (true);
}

However,foo might represent a location that can be changed by other elements of the computer system at any time. The above code will have problem. Whithout volatile, the compiler assumes that only the current program change foo’s value. So add volatile prevent complie to do optimize on foo.

A variable should be declared volatile whenever its value could change unexpectedly. In practice, only three types of variables could change:

1. Memory-mapped peripheral registers

2. Global variables modified by an interrupt service routine

3. Global variables accessed by multiple tasks within a multi-threaded application

Reference:

http://en.wikipedia.org/wiki/Volatile_variable

How to use C’s volatile keyword

Wednesday, September 29th, 2010 at 07:48

ELF PIC

PIC (Position Independent Code) is the instruction codes that execute properly regarless where it resides in the memory image, It is often used for share libraries.

Why position independent code?

In the old days, the codes were position-dependent, that the program was built to be loaded into fixed address. So the operator has to pay attention to avoid the processes those requiring same addresses running at the same time.  So the Position independent code invented. The code can run at any address the  operator chose to load it.

The dynamic address translation obsoleted position-independ code because every process has its own address space. So the programs can build to run at same address space  and  run at same time, the code mapped to the different phisical addresses at backend.

Read more…

Thursday, September 23rd, 2010 at 22:33

Near Call

Near Call is one of call types.  When execute a near call, the processor push the value of EIP register (which contain the offset of next instruction following the CALL instruction) on the stack. Why push the EIP? because the  CALL instruction will branch the processor to the called procedure by change the value EIP to the offset of the called procedure.

The target oprand specifies either an absolute offset in the code segment (an offset from the base of the code segment) or a relative offset (a signed displacement relative to the current value of the instructions pointer in EIP register; this value points to the instruction following the CALL instruction).

For a near call absolute, the absolute is specified indirectly in a generall-purpose register or a memory  location.

For a near call relative, displacement to the next instruction, the  relative offset is generally specified as a label in assembly code. But at the machine code level, it is encoded as a signed immediate value. This value is added to EIP when the CALL executed.

Operand value + EIP =  Called precedure’s absolute address.

Read more…

Monday, September 20th, 2010 at 23:15

Setup TracAccountManager

TrackAccountManager plugin allow users to login trac with  SVN account.  Here is the  manual i got from google about how to setup it on Trac.

Read more…

Thursday, September 16th, 2010 at 21:25

ELF Program Header

Executable and shared object files are programs, systems use them to create dynamic program represetations or process image. Before a program running, the system must load it into the memory and resolve all symbolic reference in the file. Program Header is the primary data structure for creating process image, it holds the information the system need to prepare the program for execution. Executable and shared object files also contain a section table, but it used for programs like nm.

Structure:

Read more…

Tuesday, September 14th, 2010 at 07:31

ELF Relocation

Relocation is the process of associate the symbolic reference with symbolic definition. For example, when a program calls a function, the associate all instruction must transfor control to the proper destination address. In other words, relocatable files must  have information  for modifying their section content.

Relocation table entry structer:

Read more…

Sunday, September 12th, 2010 at 16:29

ELF Special Sections

Various section in ELF are pre-defined and hold program control information. These sections are used by OS  and have different types and attribute for diffrent OS.

Executable files are created from object files and libraries trough linking. The linker resolve the refference among the diffrent object files, adjusct the absolute reference in the object files, and relocates instruction.

Sepecial Sections:

Read more…

Friday, September 10th, 2010 at 18:26