How to create doubly linklist using template in c++

First create list.h file and put this code in list.h

#include "list.h"
#include
using namespace std;

template<> class Lnode
{
public:
T data;
Lnode<> *next;
Lnode<> *prev;

};


template<> class List
{
public:
void add( T data );
void display();
T remove();
Lnode<>* head;
List()
{
head = new Lnode<>();
head->next = NULL;
head->prev = NULL;
}
};

template<> void List<>::add( T data )
{
Lnode<> *p;
p = new Lnode<>();
p->data = data;
p->next = head->next;
p->prev = head->prev;
head->next = p;
}

template<> T List<>::remove()
{
T data;
Lnode<> *node;

if (head->next == NULL)
{
cout << "ERROR: `remove' called with empty list.\n"; exit(1); } node = head->next;
data = node->data;

head->next = node->next;
head->prev = node->prev;
delete node;

return data;
}

template<> void List<>::display()
{
T data;
Lnode<> *node;

while(head->next!= NULL)
{

head=head->next;
cout <<>data;
cout << "\n"; } }

Next create linklist_template.cpp and put this code in linklist_template.cpp.

#include "list.h"
#include
using namespace std;

int main()
{
List<> list1;
List<> list2;

list1.add( 5 );
list1.add( 25 );
list1.add( 35 );
list1.add( 45 );
list2.add( 2.7 );

list1.display();

cout << list1.remove();
cout << "\n";
cout << list1.remove();
cout << "\n";
cout << list1.remove();
cout << "\n";

l

return 0;
}

kernel 2.6 scheduling time complexity o(1)

The highest priority level, with at-least ONE task in it, is selected. This takes a fixed time ( say t1 )

The first task ( head of the doubly-linked list ) in this priority level is allowed to run. This takes a fixed time ( say t2 )

Total time taken for selecting a new process is t = t1 + t2 ( Fixed )

The time taken for selecting a new process will be fixed( constant time irrespective of number of tasks )

Deterministic algorithm !!



Kernel 2.4 had Global runqueue. All CPUs had to wait for other CPUs to finish execution.

An O(n) scheduler.
In 2.4, the scheduler used to go through the entire “ global runqueue” to determine the next task to be run.

This was an O(n) algorithm where 'n' is the number of processes. The time taken was proportional to the number of active processes in the system.

This lead to large performance hits during heavy workloads.

Manual boot in GRUB

From the GRUB command-line, you can boot a specific kernel with a named initrd image as follows:

grub$ kernel /bzImage-2.6.30

grub$ initrd /initrd-2.6.14.2.img

grub$ boot

Message display : Uncompressing Linux... Ok, booting the kernel.

Ajax (Asynchronous Javascript + XML)

Brief history

Ajax is only a name given to a set of tools that were previously existing.
The main part is XMLHttpRequest, a server-side object usable in JavaScript, that was implemented into Internet Explorer since the 4.0 version. In Internet Explorer it is an ActiveX object that was first named XMLHTTP some times, before to be generalized on all browser under the name XMLHttpRequest, when the Ajax technology becomes commonly used. The use of XMLHttpRequest in 2005 by Google, in Gmail and GoogleMaps has contributed to the success of this format. But this is the when the name Ajax was itself coined that the technology started to be so popular.

Why use Ajax?

Mainly to build a fast, dynamic website, but also to save resources.
For improving sharing of resources, it is better to use the power of all the client computers rather than just a unique server and network. Ajax allows to perform processing on client computer (in JavaScript) with data taken from the server.
The processing of web page formerly was only server-side, using web services or PHP scripts, before the whole page was sent within the network.
But Ajax can selectively modify a part of a page displayed by the browser, and update it without the need to reload the whole document with all images, menus, etc...
For example, fields of forms, choices of user, may be processed and the result displayed immediately into the same page.

What is Ajax in depth?

Ajax is a set of technologies, supported by a web browser, including these elements:

• HTML and CSS for presenting.
• JavaScript (ECMAScript) for local processing, and DOM (Document Object Model) to access data inside the page or to access elements of XML file read on the server (with the getElementByTagName method for example)...
• The XMLHttpRequest object is used to read or send data on the server asynchronously.

Optionally...

• DOMParser may be used
• PHP or another scripting language may be used on the server.
• XML and XSLT to process the data if returned in XML form.
• SOAP may be used to dialog with the server.

The "asynchronous" word, means that the response of the server while be processed when available, without to wait and to freeze the display of the page.

How does it works?

Ajax uses a programming model with display and events. These events are user actions, they call functions associated to elements of the web page.
Interactivity is achieved with forms and buttons. DOM allows to link elements of the page with actions and also to extract data from XML files provided by the server.
To get data on the server, XMLHttpRequest provides two methods:
- open: create a connection.
- send: send a request to the server.
Data furnished by the server will be found in the attributes of the XMLHttpRequest object:
- responseXml for an XML file or
- responseText for a plain text.

Take note that a new XMLHttpRequest object has to be created for each new file to load.

We have to wait for the data to be available to process it, and in this purpose, the state of availability of data is given by the readyState attribute of XMLHttpRequest.

States of readyState follow (only the last one is really useful):

0: not initialized.
1: connection established.
2: request received.
3: answer in process.
4: finished.

The XMLHttpRequest object

Allows to interact with the servers, thanks to its methods and attributes.

Attributes

readyState	the code successively changes value from 0 to 4 that means for "ready".
status	200 is OK 404 if the page is not found.
responseText	holds loaded data as a string of characters.
responseXml	holds an XML loaded file, DOM's method allows to extract data.
onreadystatechange	property that takes a function as value that is invoked when the readystatechange event is dispatched.

Methods

open(mode, url, boolean)	mode: type of request, GET or POST url: the location of the file, with a path. boolean: true (asynchronous) / false (synchronous). optionally, a login and a password may be added to arguments.
send("string")	null for a GET command.

Building a request, step by step

First step: create an instance

This is just a classical instance of class, but two options must be tried, for browser compatibility.

if (window.XMLHttpRequest) // Object of the current windows { xhr = new XMLHttpRequest(); // Firefox, Safari, ... } else if (window.ActiveXObject) // ActiveX version { xhr = new ActiveXObject("Microsoft.XMLHTTP"); // Internet Explorer }

Or exceptions may be used instead:

try { xhr = new ActiveXObject("Microsoft.XMLHTTP"); // Trying Internet Explorer } catch(e) // Failed { xhr = new XMLHttpRequest(); // Other browsers. }

Second step: wait for the response

The response and further processing are included in a function and the return of the function will be assigned to the onreadystatechange attribute of the object previously created.

xhr.onreadystatechange = function() { // instructions to process the response }; if (xhr.readyState == 4) { // Received, OK } else { // Wait... }

Third step: make the request itself

Two methods of XMLHttpRequest are used:
- open: command GET or POST, URL of the document, true for asynchronous.
- send: with POST only, the data to send to the server.

The request below read a document on the server.

xhr.open('GET', 'http://www.xul.fr/somefile.xml', true); xhr.send(null);

Inside the Linux boot process

The process of booting a Linux system consists of a number of stages. But whether you're booting as standard x86 desktop or a deeply embedded PowerPC target, much of the flow is surprisingly similar. kernel decompression, the initial RAM disk, and other elements of Linux boot.

In the early days, bootstrapping a computer meant feeding a paper tape containing a boot program or manually loading a boot program using the front panel address/data/control switches. Today's computers are equipped with facilities to simplify the boot process, but that doesn't necessarily make it simple.

Let's start with a high-level view of Linux boot so you can see the entire landscape. Then we'll review what's going on at each of the individual steps. Source references along the way will help you navigate the kernel tree and dig in.

When a system is first booted, or is reset, the processor executes code at a well-known location. In a personal computer (PC), this location is in the basic input/output system (BIOS), which is stored in flash memory on the motherboard. The central processing unit (CPU) in an embedded system invokes the reset vector to start a program at a known address in flash/ROM. In either case, the result is the same. Because PCs offer so much flexibility, the BIOS must determine which devices are candidates for boot. We'll look at this in more detail later.

When a boot device is found, the first-stage boot loader is loaded into RAM and executed. This boot loader is less than 512 bytes in length (a single sector), and its job is to load the second-stage boot loader.

When the second-stage boot loader is in RAM and executing, a splash screen is commonly displayed, and Linux and
an optional initial RAM disk (temporary root file system) are loaded into memory. When the images are loaded, the
second-stage boot loader passes control to the kernel image and the kernel is decompressed and initialized. At this stage, the second-stage boot loader checks the system hardware, enumerates the attached hardware devices, mounts the root device, and then loads the necessary kernel modules. When complete, the first user-space program (init) starts, and high-level system initialization is performed.

That's Linux boot in a nutshell. Now let's dig in a little further and explore some of the details of the Linux boot process.

System startup

The system startup stage depends on the hardware that Linux is being booted on. On an embedded platform, a bootstrap environment is used when the system is powered on, or reset. Examples include U-Boot, RedBoot, and MicroMonitor from Lucent. Embedded platforms are commonly shipped with a boot monitor. These programs reside in special region of flash memory on the target hardware and provide the means to download a Linux kernel image into flash memory and subsequently execute it. In addition to having the ability to store and boot a Linux image, these boot monitors perform some level of system test and hardware initialization. In an embedded target, these boot monitors commonly cover both the first- and second-stage boot loaders.

In a PC, booting Linux begins in the BIOS at address 0xFFFF0. The first step of the BIOS is the power-on self test (POST). The job of the POST is to perform a check of the hardware. The second step of the BIOS is local device enumeration and initialization.

Given the different uses of BIOS functions, the BIOS is made up of two parts: the POST code and runtime services. After the POST is complete, it is flushed from memory, but the BIOS runtime services remain and are available to the target operating system.

Commonly, Linux is booted from a hard disk, where the Master Boot Record (MBR) contains the primary boot loader. The MBR is a 512-byte sector, located in the first sector on the disk (sector 1 of cylinder 0, head 0). After the MBR is loaded into RAM, the BIOS yields control to it.


Stage 1 boot loader

The primary boot loader that resides in the MBR is a 512-byte image containing both program code and a small partition table (see Figure 2). The first 446 bytes are the primary boot loader, which contains both executable code and error message text. The next sixty-four bytes are the partition table, which contains a record for each of four partitions (sixteen bytes each). The MBR ends with two bytes that are defined as the magic number (0xAA55). The magic number serves as a validation check of the MBR.

The job of the primary boot loader is to find and load the secondary boot loader (stage 2). It does this by looking through the partition table for an active partition. When it finds an active partition, it scans the remaining partitions in the table to ensure that they're all inactive. When this is verified, the active partition's boot record is read from the device into RAM and executed.

Stage 2 boot loader

The secondary, or second-stage, boot loader could be more aptly called the kernel loader. The task at this stage is to load the Linux kernel and optional initial RAM disk.
The first- and second-stage boot loaders combined are called Linux Loader (LILO) or GRand Unified Bootloader (GRUB) in the x86 PC environment. Because LILO has some disadvantages that were corrected in GRUB, let's look into GRUB. (See many additional
resources on GRUB, LILO, and related topics in the Resources section
later in this article.)



The great thing about GRUB is that it includes knowledge of Linux file systems. Instead of using raw sectors on the disk, as LILO does, GRUB can load a Linux kernel from an ext2 or ext3 file system. It does this by making the two-stage boot loader into a three-stage boot loader. Stage 1 (MBR) boots a stage 1.5 boot loader that understands the particular file system containing the Linux kernel image. Examples include
reiserfs_stage1_5 (to load from a Reiser journaling file system) or e2fs_stage1_5 (to load from an ext2 or ext3 file system). When the stage 1.5 boot loader is loaded and running, the stage 2 boot loader can be loaded. With stage 2 loaded, GRUB can, upon request, display a list of available kernels (defined in /etc/grub.conf, with soft links from /etc/grub/menu.lst and /etc/grub.conf). You can select a kernel and even amend it with
additional kernel parameters. Optionally, you can use a command-line shell for greater manual control over the boot process.

With the second-stage boot loader in memory, the file system is consulted, and the default kernel image and initrd image are loaded into memory. With the images ready, the stage 2 boot loader invokes the kernel image.

Kernel

With the kernel image in memory and control given from the stage 2 boot loader, the kernel stage begins. The kernel image isn't so much an executable kernel, but a
compressed kernel image. Typically this is a zImage (compressed image, less than 512KB) or a bzImage (big compressed image, greater than 512KB), that has been
previously compressed with zlib. At the head of this kernel image is a routine that does some minimal amount of hardware setup and then decompresses the kernel contained within the kernel image and places it into high memory. If an initial RAM disk image is present, this routine moves it into memory and notes it for later use. The routine then calls the kernel and the kernel boot begins.



When the bzImage (for an i386 image) is invoked, you begin at ./arch/i386/boot/head.S in the start assembly routine (see Figure 3 for the major flow). This routine does some basic hardware setup and invokes the startup_32 routine in ./arch/i386/boot/compressed/head.S. This routine sets up a basic environment (stack, etc.) and clears the Block Started by Symbol (BSS). The kernel is then decompressed through a call to a C function called decompress_kernel (located in ./arch/i386/boot/compressed/misc.c).
When the kernel is decompressed into memory, it is called. This is yet another startup_32 function, but this function is in ./arch/i386/kernel/head.S.

In the new startup_32 function (also called the swapper or process 0), the page tables are initialized and memory paging is enabled. The type of CPU is detected along with any optional floating-point unit (FPU) and stored away for later use. The start_kernel function is then invoked (init/main.c), which takes you to the non-architecture specific Linux kernel. This is, in essence, the main function for the Linux kernel.

With the call to start_kernel, a long list of initialization functions are called to set up interrupts, perform further memory configuration, and load the initial RAM disk. In the end, a call is made to kernel_thread (in arch/i386/kernel/process.c) to start the init function, which is the first user-space process. Finally, the dle task is started and the scheduler can now take control (after the call to cpu_idle). With interrupts enabled, the pre-emptive scheduler periodically takes control to provide multitasking.

During the boot of the kernel, the initial-RAM disk (initrd) that was loaded into memory by the stage 2 boot loader is copied into RAM and mounted. This initrd serves as a temporary root file system in RAM and allows the kernel to fully boot without having to mount any physical disks. Since the necessary modules needed to interface with
peripherals can be part of the initrd, the kernel can be very small, but still support a large number of possible hardware configurations. After the kernel is booted, the root file system is pivoted (via pivot_root) where the initrd root file system is unmounted and the real root file system is mounted.



The initrd function allows you to create a small Linux kernel with drivers compiled as loadable modules. These loadable modules give the kernel the means to access disks and the file systems on those disks, as well as drivers for other hardware assets. Because the root file system is a file system on a disk, the initrd function provides a means of bootstrapping to gain access to the disk and mount the real root file system. In an embedded target without a hard disk, the initrd can be the final root file system, or the final root file system can be mounted via the Network File System (NFS).


Init

After the kernel is booted and initialized, the kernel starts the first user-space application. This is the first program invoked that is compiled with the standard C library. Prior to this point in the process, no standard C applications have been executed.

In a desktop Linux system, the first application started is commonly /sbin/init. But it need not be. Rarely do embedded systems require the extensive initialization provided by init (as configured through /etc/inittab). In many cases, you can invoke a simple shell script that starts the necessary embedded applications.

Steps for Kernel Compilation – 2.6.30

The following steps are a guideline to recompile the kernel. I have tested it today on my debian installation and i hope that it should work fine on all systems. If there are any mistakes please let me know. Remember to be a root to do the following steps. But before beginning with the following steps you need to have gcc­version­2.95­3. To install this version see the steps are

1. Step­-1

Download the kernel source code from the internet . You have to pick up the 2.6.30 kernel version. The format of the file is in tar format so you would have to untar it. You can create your own directory to untar it but i would advise to keep the kernel source in /usr/src/. After copying the tar image of the kernel, untar it by issuing the command tar – xvf linux­kernel­2.6.30.tar

2. Step-­2

Now is the time to configure the options that we have to keep in our new kernel. So go in the source code directory which would be something like /usr/src/linux­kernel­2.6.30 and key in the command make menuconfig. For running menuconfig you should have ncurses library installed, which can be done by installing libncurses package from your synaptic package managers. The make menuconfig would look something like as under:­

3. Step – 3

Selection of modules – Now we have to select the modules. Make sure that in the Processor type and features­> symmetric multiprocessing support is disabled. Selected and deselected of items is done using space bar. You can read the details of an item using inbuilt context sensitive help. Just place your cursor at the command and press ?. You would then see the context sensitive help. It causes lot of problems so remove it. After deselect this you can go back by pressing escape. Also now go to the device drivers­>character devices and deselect Direct rendering manager. This also causes a lot of troubles because of hardware incompatibility.
After these two things you can come back to the main menu by pressing escape. Here select file systems and select ext3 to be loaded as inbuilt and not a module. These changes are sufficient and rest is your own wish. After selecting and deselecting the packages, press escape again and again until it asks you to save. So say yes as the screen under.

4. Step­-4

Running makefile – Now after saving the menuconfig file, key in the command make. This would compile all the modules and all files in two stages and create configuration files.

5. Step­-5

Making Modules – After make is done now key in the command make modules_install. This command installs all the modules for the kernel in /lib/modules/2.6.30.

6. Step­-6

Now the bzImage of the kernel is created which is the bunzipped compressed image. Copy this image to boot directory by the following command cp /arch/i386/boot/bzImage /boot/vmlinuz­2.6.30.

7. Step­-7

Now is the time to create a RAMFS i.e. initrd which loads the filesystem in memory. so to get that key in the command as mkramfs ­o /boot/initrd.img­2.6.30 2.6.30.

8. Step­-8

Now type the command grub update on command prompt.

9. Step­-9

Congratulations. You can boot into the new kernel now.