Unix : System Call for Time

I : stime    allows superuser to set a global kernel variable to a value that gives current time                   
                       
usage    stime(pvalue)                        where pvalue points to a long integer that gives seconds from Jan 1 1970                   
                       
important    clock interrupt handler increments the the kernal variable once a second                   
                       
II : time    retrievs the time as set by stime                   
                       
usage     time(tloc)                        where tloc points to a location in the user process for the return value                   
                       
important    commands such as date use time to determine current time                   


III : times    retrieves the cumulative times that the calling process spent executing in                        
        user mode                   
        kernel mode                   
    retrieves the cumulative times that all zombie children had executes in                         
        user mode                   
        kernel mode                   
                           
usage    times(tbuffer)                       
                           
    struct tms*buffer;        struct tms {    time_t    tms_utime    // user time   
                time_t    tms_stime    // kernel time   
                time_t    tms_cutime    // children user time   
                time_t    tms_cstime    // children kernel time   
                           
    times returns the elapsed time “from an arbitary point in the past”                       
    (usually the boot time)                       
IV : Alarm is used to set an alarm to remind the process of something while it is working on somethings else
Sleep on the other hand also wakes up a process but in that case process is not active. In Alarm system call the process can continue to run     
Example :     42      signal(SIGALRM,wakeup);
                      43      alarm(10);

Example for times:

     18    pt1=times(pb1);   
     19    for(i=0;i less than 3; i++)       
     20       if(fork()==0)
     21          child(i);
     22       
     23
     24    for(i=0;i is less than 3 ;i ++) // why do we need this loop ??

     25           wait((int *)0);
     26    pt2=times(pb2);
     27
     28    printf("\n Parent real %ld user %ld sys %ld",pt2-pt1,
     29                     pb2.tms_utime-pb1.tms_utime,
     30                     pb2.tms_stime-pb1.tms_stime);
     31    printf("\n Parent child user %ld sys %ld",
     32                     pb2.tms_cutime-pb1.tms_cutime,
     33                     pb2.tms_cstime-pb1.tms_cstime);

Function of Clock Interrupt Handler                           
    restart the clock                    c   
    schedule invocation of internal kernel functions    f   
    provide execution profiling                p   
    gather system and process accounting stats        s   
    keep track of time                    t   
    send alarm signals to process on request        a   
    periodically wakeup the swapper process            s   
    control the process scheduling                p   
                           
                    p2as2t    cf   
                    past    coffee   

Code Guru: Gateways 2013

Very tight finish for the first 5 places
 
Parth Vora (I)
Samik Banik(II)
Udhay Raj (III) 

Rank 4-10 in order 
Vivian Ambrose,
Tenzin Chemi,
Talat Ahmed ,
Palak Goyal,
Pramod Das, 
Dharmappa Immannavar,
Bharat Lakkur

Congratulations !!!!


      World War Z

50 by 50 array where 
0 is empty 
1 is soldier
2 is Bullet
3 is Mine

       Level 1 Viewer   
               (Show 0 as space and soldiers as #, bullet as | and mine as * )
       Level 2 Set Army (x1,y1,x2,y2)  
       Level 3 March Past ( make a group of soldiers march in different directions N S E W)
       Level 4 Silver Bullet(when soldiers walk into it they die and bullet can kill umlimited no of soldiers)
       Level 5 Land Mine   (when soldiers step on it all around die)
       Level 6 Moving Bouncing Bullet
       Level 7 Armies, Bullets,Mines (support multiple battalions, mines and bullets)

Inter Process Communication : Part I

If there is one chapter in Design of Unix Operating System (Maurice Bach) you should read then it would be the chapter on IPC.

First time I taught this paper, I hardly understood it well ... second time around I did the coding myself and found some of the topics very interesting. Third time around you realise the clarity in the previous year was quite disconcerting :-)

Ummmm and do I expect students to understand it in first go .. well not really ... but then students are smarter than teachers !!!

I had studied the Dining Philosphers Problem and Locking Problems like "dirty read". I had used applications like OS, Databases, Compilers and Debuggers. I had worked 6 years in Unix Enviorment ....... but alas my concepts were still a bit weak. That is why teaching is such a good thing ... you learn in the process even if the students don't :-)

Some cool things Unix can do :

fork : A process can clone itself !! A ditto copy .... if recursion was difficult to teach then this in a league in itself.

Coding is easy : a=fork(); if (a==0) {// child code} else {// parent code}

but Understanding is another matter ..... what happens in this code
      for(i=0;i<5 a="=0)" ello="" else="" i="" if="" p="" printf="">
       What is the output you expect? How many Hi and Hello and in what order ?

exec: A process is overwritten by an exe in other words "memory is overlayed!!". In the following example first a fork is called (the current process is cloned) .... and then memory is overlayed in the child (using exec) !!

Lets say this app is called forkapp.exe then if we did ps command on another terminal

when code was going to run line 7: you will see two forkapp.exe due to cloning

but after line 7 : you will see 1 forkapp.exe and 1 date due to overlaying

      6    if(fork() == 0)
      7    {    execl("/bin/date","date",0);
      8         printf("Execl failed");
      9         return;
     10    }
           When will line 8 be executed? Why don't we check the return value of execl
        You have seen recursion, where a function calls a function .. what happens here .. any idea

        execl(argv[0],argv[0],0);

semaphore:
      The difficult thing in locking is that we can write a code like

      if (lock_flg==false)
      {      lock_flg=true
            // code to use some resource
       }
      but to implement locking in a multiple process system the risk is that a process p1 after calling the if line and before it calls the assignment line the kernel may give a chance to somebody else (process p2)

     This other process p2 also happens to be executing the same code and he may also check the flag and then set the flag not knowing that process p1 has already intending to lock the same resource.

    Very soon chaos will result with both process using the same resource without realizing that somebody else is also using the same resource (say a printer !!)

      
     Djikstra came up with a clean solution called semaphore (read on wiki)

      semget : create or get an existing semaphore
      semctl : to control semaphore, you can SETALL GETALL IPC_RMID etc
      semop : To increment or decrement a semaphore

We can create an array of semaphore or just a single one and that is a very cool thing because not only we solve Locking problem we also solve the dreadful "deadlock" problem. How Exactly .... you tell me ?
     
 Following Code is the menu:

     22    while (ch!=0)
     23    {
     24       printf("\n 1. Create Semaphore if does not exist");
     25       printf("\n 2. Set All to 1         ");
     26       printf("\n 3. Get All ");
     27       printf("\n 4. P Operation / Decrement / Lock");
     28       printf("\n 5. V Operation / Increment / Unlock");
     29       printf("\n 6. Clean Up");
     30       printf("\n 0. Exit ");
     31       printf("\n\t-----------------------");
     32       scanf("%d",&ch);


      We will create semaphore using semget

     34    if(ch == 1)
     35    {
     36       semid=semget(0X22,2,IPC_CREAT|0777);     37
     38       printf("\n\t Sem Id is %d",semid);
     39       printf("\n setting semaphore");
     40    }

        Here we are creating an array of 2 semaphore

     To set values in the semaphore we use semctl 
     41    if(ch == 2)
     42    {
     43       rval=semctl(semid, 2 , SETALL, r);     44
     45       printf("\n semaphore val is %d %d rval is %d",r[0],r[1],rval);
     46       printf("\n set semaphore");
     47    }
        Q: What is r ?
          To get the values of semaphore we again use semctl
     48    if(ch == 3) // check what is status
     49    {
     50       semid=semget(0X22,2,0777);
     51       printf("\n getting semaphore");
     52       rval=semctl(semid, 2 , GETALL, o);
    53       printf("\n semaphore val is %d %d rval is %d",o[0],o[1],rval);
     54    }

        Q: What is o ?

         To lock we use semop with op set as -1 (line 61)
     55    if(ch == 4) // try to take lock
     56    {
     57       semid=semget(0X22,2,0777);
     58       printf("\n\t If part Sem Id is %d",semid);
     59       printf("\n Process Before Semaphore %d ... Trying to get lock",semid);
     60       sop.sem_num=0; // set the first semaphore
     61       sop.sem_op=-1; // lock
     62       sop.sem_flg=SEM_UNDO;
     63       a = semop(semid , &sop , 1);
     64
     65       printf("\n Process semop %d ",a);
     66       printf("\n Process in critical section");
     67       printf("\n Process Locked ");
     68     }

         To unlock we use semop again but this time we set op to 1
     69    if(ch == 5) // Unlock
     70    {
     71       semid=semget(0X22,2,0777);
     72       sop.sem_num=0; // set the first semaphore
     73       sop.sem_op=1; // unlock
     74       sop.sem_flg=SEM_UNDO;
     75       a = semop(semid , &sop , 1);
     76
     77       printf("\n Process Over is %d ",a);
     78       getchar();
     79    }

          To remove we use semctl again
     80    if(ch == 6) // clean Up
     81    {
     82       semid=semget(0X22,2,0777);
     83       printf("\n getting semaphore");
     84       rval=semctl(semid, 2 , IPC_RMID, 0);
     85    }
     Check the man pages of your installation but you would need to include some header files like the following
       2 #include
      3 #include 
 
      And would also need to declare a few things like
     10    short r[2];
     11    short o[2];
     12    struct sembuf sop;

 Hope you find the blog useful. All the best ....
      
 In part II I will touch on Message Queues and ptrace

Further Reading

Wiki Semaphore
Dining Philosphers Problem
 

Code Guru : Revelation 2013

This time the event saw around 30-40 of the best coders in PG Courses of Computer Science. Winners/Code Gurus were
I. Benjamin Varghese
II. Muffadal Kagda
III. Talat Ahmed

Remaining Top 10 are:
4. Parth Vora – II MCA
5. Samanjana Baidya – IV MCA
6. Udhayaraj R – II MSc
7. Ankita Goyal – IV MCA
8. Vinnas Kuttery – IV MCA
9. Palak Goyal – IV MCA
10. Vivian Ambrose – IV MCA

Congrats, it is not easy to code under pressure when I keep announcing time left and who is leading ... Congratulations to Top 10
Time Limit : 50 minutes
Compiler: Of your choice Help/Textbook/Online all allowed
Questions :

Create a 10 by 10 integer array, 0 Means empty,
Levels
1. Grow Tree (0 means nothing 1 means tree trunk)
2. Grow Tree with leaves (2 means leaf)
3. Tree Spilts after 3 levels
4. Tree further splits after every 3 levels
5. Grow 2 trees at random position
6. Tree has a full canopy of leaves
7. One tree grows under the tree as much as it can but preference for bigger tree
9. Grow a Random Forest of trees

Code Guru : Revelation 2012

Winners: Jayati Jaiswal (I) , Sophia K (II), Shishir (III)

The competition was organized with only a 45 minute coding window. With seniors passing out this year we saw the emergence of 10 new Top Coders. There were 10 questions and Jayati and Sophia completed 7 out 10 in the slotted time

1. Jayati Jaiswal
2. Sophia K
3. Shishir
4. Shreya Rakshit
5. Abdul Kareem
6. Nitish
7. Deepak
8. Talat Ahmed
9. Shashanka
10. Pradeep and Lajith

Code Guru : Gateways 2011

Winners: Jino George (I) , Aditya Gopalkrishnan (II), Raju K (III)

Jino and Aditya were just a few seconds apart and deciding one over the other was nail biting close
Sowmya came fourth. Thanks for all who came and made it a success.
We had MS Computer Science, MCA and M.Sc Computer Science taking part

Questions Were

1. Display Grid 9 by 9 Able to input Food (2 to 9) at any position Able to input Ant (Type 1 and Type 2) at any position

2. Take Shortest Route to Food

3. Two Ants, First Who reaches takes

4. If food is 4 ants can smell only 4 steps away, if 9 then can smell 9 steps away

5. Ant 2 is mightier than Ant 1. He can grab from Ant 1 if he gets chance

6. Keep walking if smell food, once you get food walk out using shortest path

In following set up (Next Sheet)

Ant goes always to closest food source and moves out using shortest path

Final Level
7. Implement Multiple Food Source and Ants

Code Guru : Revelation 2011

Winners: Heena Gupta (I) , Sowmya (II), Aditya G (III)

Other is top 10 in order
Charu J, Jyotsana, Raju K, Boopalan R, Rakesh K, Lakshminarayan, Nibedita S
Questions Were

1. In Zee land , they study Zaths. Some numbers are considered as Zamazing number and some as Zawesome

A number is considered Zawesome if 2109 is found somewhere in the number together

eg. 122312109876

A number is considered Zamazing if 2109 is found somewhere in the number

eg. 12921990982

Write a program to check if an inputted number is Zamazing or Zawesome or not

2. If A thinks of a 4 digit number in which each digit is unique, B takes a guess

eg. A thinks : 7345 B Says 9647 : A says 1 Zing (because 7 is correct but in wrong place) 1 Zong (because 4 is correct and in right place)

eg. A thinks : 7345 B Says 9347 : A says 1 Zing (because 7 is correct but in wrong place) 2 Zong (because 3 and 4 is correct and in right place)

Game is over if B Guesses 7345 and A says 4 Zongs !!!

Assume both numbers have no repetition of digit

Create a game where computer thinks of a 4 digit number and lets users answer with a 4 digit number . Computer should reply how many zings and zongs. Computer should allow user to attempt as many time needed to zolve the puzzle

3. Make a an array of 9 by 12 as shown in sheet 2.

0 means land 8 means rain drops

Make the exact landscape as displayed in the next sheet under Level 1

Level 1: Raindrops fall in each round but they do not go side ways

Level 2: Raindrops try to fall if not possible slide in case gap at lower level. In case 2 drops in contention for slide preference for the one drop which slides right as this is the Northern Hemisphere ??

Level 3: Multiple round of rain should work

Level 4: Make it work in this different landscape, If a drop can fall both left and right it will fall right

Level 5: In case a whole is made at bottom of the land show how the water will flow out

4.Make a variation of Zing Zong (question 2) where user thinks of a number and computer takes guesses

A good algo will solve any 4 digit number in 7 or less guesses