Linux Scheduler

Just few years back(about 2 years), I was reading about linux 2.6 scheduler, the O(1) scheduler. For me it seemed the perfect scheduler(I am no kernel expert or developer, but I keep crossing the kernel domain because of my work), since it was O(1). There were no lookups required. I wondered how much it would effect the performance of my application in the O(1) and the earlier schedulers.

But then it seems, there still problems associated with this scheduler too. The issue that is identified is in the complexity and time cost for calculating the priority for task.

As result of this we have a new scheduler called CFS (Completely Fair scheduler) in Linux 2.6.23

Wait.. it seems we can expect another new scheduler very soon.

References:

The O(1) Scheduler

Completely Fair Schedular

Event Driven Programming

The traditional method of socket programing is multi thread (pthread) or multi process i.e(fork).

But using them requires synchronization, locking and others. People who have used them may realize that some times it becomes a nightmare to trace a problem/crash.

One can still process multiple client request in a single thread, without blocking on the request. This is achieved by using event driven programing.

How to do

1. Use event notifiers such as poll/select/epoll/kqueue

2. Put your connections (i.e the socket file descriptors ) in non-blocking mode.

By doing so you do not wait for the entire data to be written or the entire data to be read at one go. You will read/write in chunk if buffer space or data is available else you can go a head doing other works like process the other client requests, by putting the current connection back into event notifier.

3. Maintain state information, in order to take appropriate action when a event takes place. Unlike the multi threaded, where a single thread as sequential logic.In event driven you will process a connection when a event occurs, for this you need to keep track about the state in which you left it last time.

4. Minimize the use of systems call or your code which can go into blocking, to avoid starvation of other connections.

Advantages

1. It saves the time in context switching, due to threads/process getting scheduling.

2. Saves the trouble of maintaining locking/synchronization (you may still have to use them in event driven programing, but to a small extent)

sqlite3 Quick reference

I always keep forgetting the syntax of sqlite command line queries

Here are some which I use more frequently

1. To see the table names present in the current database

sqlite> .tables

2. To see the databases and files

sqlite> .databases

3. To know the structure of table

sqlite> .schema

4. Create a table

CREATE TABLE dummy (key varchar(250) UNIQUE, value BLOB, pid bigint )

5. To alter a table

sqlite> alter table dummy add key varchar(250);

6. To exit from sqlite shell, this I always keep forgetting.

sqlite> .quit

7. For help

sqlite> .help

8. How to find which process is locking the database
fuser  path_to_sqlite_file

RPM Quick Reference

Following are some most frequently used rpm commands ....

1. How to find, a given file belongs to which rpm package
rpm -qf file name_with_path

2. How to find the files and there paths installed by a particular RPM package
rpm -ql procps-3.2.7-11.1.el5

3. How to find which rpm packages are installed
rpm -qa

4. How to find the version of the package installed
rpm -qa procps
procps-3.2.7-11.1.el5

5. How to query a uninstalled rpm package
rpm -qp the_rpm_package_to_query

6. How to find the files and there path of a uninstalled rpm package
rpm -qpl package.rpm

7. RPM Build from Source rpm

rpmbuild -ba rpm_spec file

rpmbuild -ta tarball

for more rpmbuild options see manpage

8. How to find dependencies of a installed rpm package

rpm -qR gcc-4.1.2-44.el5

SVN Quick Reference

SVN guide

1. checkout code
svn co file:///sourceof thsvnrepository

svn co svn+ssh:///host/sourceoftherepository_from_root

on linux machine I had problem related to permissions for users using svn+ssh://

instead of using the above one can use the following if u donot want to get into permissions problem

svn co svn:///host/sourceoftherepository_related_to_svn_repo

By this method, svn client connects to the svn server (port 3690), rather then using the ssh tunnel. which requires some system level permission handling to the file system.

2. adding a file to repository
svn add new file

3. commit your changes
svn commit file_to_comit -m "Message"

4. Create new branch from main trunk

svn mkdir branchname

svn copy trunk branchname

svn commit branchname -m "new branch"

Resources:
http://artis.imag.fr/~Xavier.Decoret/resources/svn/index.html

http://subversion.apache.org/docs/

http://svnbook.red-bean.com/

http://queens.db.toronto.edu/~nilesh/linux/subversion-howto/

http://blog.tplus1.com/index.php/2007/08/29/how-to-use-vimdiff-as-the-subversion-diff-tool/ - how to use svn with vimdiff

Python Baiscs

In this post we will be learning about some of the basics of python language.

1 How to create .pyc
a. In order to create compiled python code, you need to run this in directory of your python source code.
python -mcompileall .


b. In your python interpreter, execute the following commands

>>> import py_compile
>>> py_compile.compile('test.py')

Vim usefull commands

The other day my colleague asked how to reach to the start of the function in vim editor. For few seconds I could not recollect. How do I do it !!!!!!!. I know it, I use it regularly, but just could not recollect how.
So I thought lets write it down whenever I find some thing useful about vim editor.



1. How to reach start of a function
'{' x2
i.e successively press curly brace ({) twice


2. How to reach start/end of code block enclosed between braces/brackets
shift +5 i.e press ' %'


3. How to enable code folding based on syntax of the programing language used
:set foldmethod=syntax

will fold the code

zo - will open a folded code

zc - will fold a open code

You can set the level folding by

:set foldlevel=1

the depth at which folding to start

4. How to enable line number
:set nu

5. How to hide a buffer
:hide
6. How to see the open files present in buffer
:buffer


7. How to select a particular buffer file from the list of files listed from the above command
:buff num i.e say the file you are interested in is at position 7, then
:buff 7

8. How to split your display window
:sp or
:vs i.e 'sp' will split the view horizontally and 'vs' will split the view vertically

9. To change between different views
ctl+w arrowkey
i.e to change to view area above your current view then, hold ctl key press w then press up arrow key.


10. The most frequently used command is search
/searchstring


11. If you want to search and replace
:%s/search/replace/gc
i.e search is your string to search and replace is the string with which to replace. The 'g' at the end indicates that the search and replace is to be applied on all occurence on that line.

The 'c' at the end will ask for confirmation to replace for every occurrence of the search string. If you do not want to be prompted for confirmation then do not use 'c'.

% indicates to apply it on the entire file.

If you want to search and replace on some section of the file then

:30,60s/search/replace/g

The above command will replace all occurrence of "search" in lines 30 to 60 and replace all occurrence with "replace"

12. Some times you might find that your terminal gets froze or lock when you unknowingly press ctls+s for saving data.
ctl+q
i.e if your terminal view got locked or frozen then press ctl+q to come out of the sleep.

13. vimdiff:

Jumping to diffs

[c

jump backward to previous diff

]c

Jump forward to next diff

Resolving the difference

do

Get the other buffer contents to the current buffer to resolve the difference

dp

Put the current buffer contents to the other buffer to resolve the difference




14. indent the entire file
reach to top of the file
= shift+g (i.e  press "=" and them shift +g)
15.indent the block of document
visual select the block ctl+v
=


There are many more such useful commands available,
the best way to find them out is to google it or :help

Creating and applying Patch

• Create Patch

diff -urN orignalsource updatedsource > file.patch
The above command will create a patch by going recursively through the source and destination.
The option 'N' tells to treat the new files as empty files in the other directory

• Apply Patch

patch --dry-run -p1 < ../file.patch
The above command will run through the patch without applying it and giving information which will be given when the patch would actually will be applied.

patch -p1 < ../file.patch
This would actually apply the patch

C interview questions

1. Bit Fields

struct {
           int b1:5;
  }flag;

The size of this structure will be 4bytes. i.e one integer space is allocated.
In the above example we are using only 5 bits

struct {
         int b1:5;
         int b2:30;
 }flag;

The size of this structure will be 8bytes . i.e 2 integer space is allocated
In the above example we are using in all 35 bits which is more then 4 bytes (4 *8 =32bits), so for 3 more bits we require one more integer



Question:

struct {
        int b1:4;
        int count;
        int b2:5;
} dummy;

What will be the size of dummy?


2. What is the output of the following program

int main()
{
int x;
int y=(10,15);
 x=10,15;
printf("%d %d",x,y);
return 0;
}

3. Now some interesting linked list interview questions

1. Due to some corruption a loop got introduced in a singly linked list. How to find the loop in the linked list
2. Due to some corruption 2 linked lists intersect. How to find the intersection between them.
3. Linked list reversal
4. How to find the center of the linked list
   

Linked list reversal example

#include 
#include 

struct mylnk
{
        int data;
        struct mylnk * next;
};

int populate(struct mylnk ** list, char * srcdata[], int count)
{
        int i;
        struct mylnk * newlist=NULL;
        struct mylnk * newdata;
    #ifdef DEBUG
            printf("%s():%d started.. \n",__FUNCTION__,__LINE__);
    #endif

        *list=newlist;

     for(i=1; i<=count; i++)
    {
        newdata= (struct mylnk *) malloc(sizeof(struct mylnk));
        if(newdata != NULL)
         {
                   newdata->data = atoi(srcdata[i]);
                   newdata->next = NULL;
                   if( newlist == NULL )
                   {
                         newlist =newdata;
                         *list=newlist;
                   }
                   else
                   {
                         newlist->next =newdata;
                         newlist = newlist->next;
                   }
        }
        else
        {
                        printf("Could not allocate memory for link list member");
                        return -1;
        }

   }


        return 0;
}

int display(struct mylnk * lnk)
{
    #ifdef DEBUG
            printf("%s():%d started.. \n",__FUNCTION__,__LINE__);
    #endif
        while(lnk!=NULL)
        {
                printf("Data:%d \n",lnk->data);
                lnk=lnk->next;
        }

    return 0;
}

int printreverse( struct mylnk *lnk)
{
    #ifdef DEBUG
            printf("%s():%d started.. \n",__FUNCTION__,__LINE__);
    #endif

        if(lnk !=NULL)
    {
                printreverse(lnk->next);
        }
        else
        {
                return 0;
        }
        printf("The data is %d \n",lnk->data);

        return 0;
}

int  reverselist(struct mylnk *lnk, struct mylnk ** head)
{

    #ifdef DEBUG
            printf("%s():%d started.. \n",__FUNCTION__,__LINE__);
    #endif

        if(lnk->next !=NULL)
        {
                 reverselist(lnk->next,head);
                 lnk->next->next=lnk;
                 lnk->next->next->next=NULL;
        }
        else
        {
                *head = lnk;
        }

        return 0;
}


int main(int argc, char * argv[])
{

        struct mylnk * linklist=NULL,  * revlinklist=NULL;
    #ifdef DEBUG
            printf("Link list reversal using recursion \n");
    #endif

    populate(&linklist, argv, (argc-1));
    display(linklist);
    //printreverse(linklist);
    reverselist(linklist,&revlinklist);
    display(revlinklist);


    return 0;
}
    

4. You have a very large buffer, in that you have 0's at the begin, after some point in the buffer we have non zero value.
Find the position of non-zero starting value position in the buffer.
There are 2 ways which I can think of, Sequential search and binary search

5. How to make process reload its configuration.



6. Where are static variables placed
Static variables are placed in the data segment of the process.
If there are 2 static variables of same name in different functions,then ?
The variables stored as stags "variable name:function", by the compiler.

7. How to print the return address of calling function from a called function

Gcc has function by calling them you can get the return address from where this function was called from.

For more on these functions: http://gcc.gnu.org/onlinedocs/gcc/Return-Address.html

An sample program for the same is:

#include


int foo()
{
        void *add = __builtin_return_address(0);
        printf("I was called from %x \n",  add);
        return 1;
}

int main()
{

        printf("Return address Testing \n");
        foo();
        return 0;

}

sed

Following is the list of commands that can be used to get your work done using sed.
No doubt there are many online resources available for these but still........

1. Search and replace
sed -e "s/old/new/" file
The above command will search for "old" in "file" and replace it with "new" and dump the output on stdout.

If your sed supports in line processing then
sed -i "s/old/new/" file
in the above case the output would be the file itself

For global search and replace (I am still trying to find out where it is going to be used or how it works ..)
sed -e "s/old/new/g" file
sed -i "s/old/new/g" file

If you want to use back reference, then you can do like this

sed -i -e 's/\(title.*\)/#\1\n title my_linux /' grub.conf

The above will search for a line containing the word 'title', then it will replace the line with

#"the line contain the word 'title' "

add a new line with 'title my_linux'

\1 - gives the first grouped string