Semaphore implementaion using condition variables and mutex

Implementation of semaphore using condition variable and mutex

        To implement a semaphore, we need 3 important functions. A sem_post or up function, sem_wait or down function and sem_init function. At first we have to define a structure with a interger value, mutex of pthread_mutex_t type and  cond of pthread_cond_t type.

------------------------------------------------------

struct semaphore                   

{                                              

  int val;                     

         pthread_mutex_t mutex;

         pthread_cond_t cond;    

}                                            

-----------------------------------------------------

 Now we need three functions:

 --> init(semaphore *s); --contains the initial value of the semaphore.

 --> up(semaphore *s);  --increments the value of val.

 --> down(semaphore *s); -- decrements the value of val and if val is zero it waits for an up()

Code for init()

------------------------------------------------------------------------

void init(semaphore *s, int n)                                                     

{                                                                   

s->val = n;                                

}                                                                  

--------------------------------------------------------------------------

Code for up()

--------------------------------------------------------------------------

void up(semaphore *s)                                    

{                                                                      

pthread_mutex_lock(&(s->mutex));

s->val++;                                        

     pthread_cond_broadcast(&(s->cond));

pthread_mutex_lock(&(s->mutex)); 

}                                                                      

--------------------------------------------------------------------------

Code for down()

----------------------------------------------------------------------------------------

void down(semaphore *s)                                              

{                                                                                      

pthread_mutex_lock(&(s->mutex));                

while(s->val == 0)                                         

                 pthread_cond_wait(&(s->cond),&(s->mutex));

s->val--;                                                           

pthread_mutex_unlock(&(s->mutex));             

}                                                                                     

-----------------------------------------------------------------------------------------

Concurrent Programming - Basics

        Till now we have been using sequential programming which executes a single stream of instructions and operations. Concurrent programming is very much complex than sequential programming. Here several streams of operations executes concurrently. Each sequence of instructions are called threads.

    

        To create thread in C we are including a header file called pthread.h and we can create the thread using

      int pthread_create(pthread_t *thread, pthread_attr_t *attr, void* (*start_routine)(void*), void* arg); 

        We are not required to know the nature of the type pthread_t and pthread_attr_t. So we can say it as type pthread. Third argument is an address of a function which can return anything and accept anything. Fourth argument is the value to the function whose address is in the third argument. Thus we can create different threads of same function which vary in their return type and accept type.

         We have to create the thread inside the main(). As long as the main thread lives, the child thread also lives. So we have to provide a infinite loop at the end of the main().

         When compiling a program we have to link our program to pthread. So compile the program with -lpthread  option.  

Synchronization using mutex

        Mutex is a Mutual Exclusion device. Mutual Exclusion means if there are two events A and B, these two events must not happen at the same time. Mutex has two different states. Locked-->owned by one thread, Unlocked-->not owned by any threads. We can define the mutex variable as a type pthread_mutex.

        For locking: pthread_mutex_lock(&mutex);

        For unlocking: pthread_mutex_unlock(&mutex);

       For initializing:pthread_mutex_init(&mutex, 0);

where mutex is a type pthread_mutex.

Semaphore synchronization

        A more general synchronization mechanism is semaphore. Here we have to include a header file called semaphore.h. sem_wait and sem_post are the two operations similar to mutex lock and unlock. A semaphore should be declared as a type sem_t. On initializing sem_init(sem_t *sem, int pshared, unsigned int value); the first argument is a address of sem object, second is always zero and the third argument is the initial value of the semaphore.

sem_post(&value); -->It increments the value of the semaphore variable.

sem_wait(&value); -->It decrements the value of the semaphore variable. If it is zero them waits for a sem_post() operation to occur.

pthread_join and pthread_exit

        pthread_exit(0) -->A thread uses this to terminate  itself.

      pthread_join(pthread_t t, void** thread_return) --> It makes the main thread to wait until this thread t exits.    

Condition Variables

        Condition variables enables threads to wait until a particular condition occurs. Condition variables are of type pthread_cond_t and has two fundamental functions. They are pthread_cond_wait which has two arguments- address of the condition variable and address of the locked mutex and pthread_cond_broadcast which one argument- the condition variable. pthread_cond_wait release the lock and sleeps the thread until it receives a broadcast message. When it receives a broadcast message, thread reacquires the lock and wakes up.

AVL TREE -The Self Balancing Binary Tree

        AVL Tree is a self balancing binary tree. When an insertion or deletion occurs, it re-balances the tree by checking the height of two child subtrees. Balancing factor of a node is equal to height of the left subtree minus height of the right subtree. If the balancing factor is equal to -1, 0 or 1 then the tree is considered balanced else the tree is rebalanced by calling one or more tree rotations. A simple example for AVL tree is given below.

          Insert a node with data 3 (node 3), which is inserted to the tree as a simple binary tree. Then insert node 2 which is inserted to the left of node 3. Here the function balance() is called  and height of the subtrees are checked. Since the height is not > 1 or < -1 tree rotations are not done here. next the node 1 is inserted. Now the tree becomes unbalanced and rotations are called.

        Now insert node 4 and 5. The balancing factor gives a difference of -2 that is right side the node is not balanced. So again a single rotation is applied.

        Inserting node 6 makes the balanced tree unbalanced. Here node 2 is unbalanced. So a single rotation is called which makes node 4 as the child of parent of node 2, if any element present in the left of node 4, then it is passed to the right child of node 2 and node 2 is passed to the left of node 4. Next node 7 is inserted. At this point the root is balanced. But when we go through each node checking whether it is balanced or not we found that the node 5 is not balanced and single rotation is applied here. Then inserting node 16 then node 15 which makes the tree again unbalanced.

 
        Now the tree is unbalanced and to become balanced we have to apply double rotation. First rotating child and grandchild of the unbalanced node 7 and then rotating the node 7and the new child (node 15) which makes the tree again balanced.

        Insert node 14 which comes to the right of node 7 and the tree becomes unbalanced at node 6. Again a double rotation is called, first rotation is with the child(node 7) and grandchild(node 15) of node 6. Then rotation is with node 6 and with the new child(node 7)

You can find my codes: http://github.com/omalbastin/avl_tree

LogU-Designing the MVC in Rails

 I am only providing some key information that will be helpful in other projects.

Creating the Model

$rails generate model Article
  This will create a model and a database named article. To add rows in the db we have to edit the db/migrate.*.rb file. Then again migrating the database with rake will create a database table with the given fields.

After creating the models we can add data to the db and also check the model in interactive mode my typing
$rails console

Relationship between different db models can be shown by
        >has_one
        >has_many
        >belongs_to
        >has_and_belongs_to_many

Generating the controller

$rails generate controller article
    It generate a controller named ArticleController in app/controller. We can add our template files for the corresponding controller in app/view/articles. We also have to change the route.rb file in config corresponding to the model and controller.

Scaffolding is one of the important feature of rails. Scaffolding helps to create a set of actions and templates that makes it easy to manipulate data for a specific model.

Creating the View
        There is no need to create or generate a view. At the time of  generating the controller a view is also generated. We can add CSS to the file inside app/views/layouts which can be applied to view of each page.

You can find the code in http://github.com/omalbastin/logu
and run it on  http://logu.heroku.com/

LogU - My Blog Application

Rails Framework

        Rails is a web application framework for the Ruby programming language. It is a powerful application which can be used to build web sites quickly and easy to maintain. A framework is a collection of libraries and tools for the development of an application. A good framework provide complete infrastructure to build our application. Rails is a open source, platform independent framework.
    
        Here in rails it has only less codes and using conventions over configuration. It is simple compared to other framework but little difficult to play with all the conventions.

        Rails uses the MVC pattern, which divides the application logic and pass it to three separate entities- Model(data), View(user interface), Controller(all other actions). Changing any of the entity will not affect other entities.

         A user interact with the interface and provide a form submission. The controller receives this input and pass it to the model, model provides the information according to the form and return it to the controller and pass it to the view and it provides the user interface and pass it to the user.
         The three main library that map directly to MVC are 1.Active Record- which handles the database, 2.Action view- which generates the HTML documents and 3.Action Controller that controls the database and application flow.

Installation
        Type in your terminal:

$ sudo apt-get install build-essential libssl-dev libreadline5 libreadline5-dev zlib1g zlib1g-dev
Download ruby and mkdir ~/src && cd ~/src

$wget ftp://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.1-p376.tar.gz
$tar -zxvf ruby-1.9.1-p376.tar.gz
$cd ruby-1.9.1-p376
$./configure && make && sudo make install

$sudo gem install rails
$sudo gem update --system
$sudo gem update rails
$sudo gem install sqlite3-ruby

Creating the Application

$rails new blog
$bundle install

To run the server go to the my_app folder and
$rails server

With the server running, if you open http://localhost:3000/ in your browser, you see the Rails welcome page.

To create  our project database

$rake db:create
Rake is a build language for ruby. By calling rake db:create we are creating database for development environment only. For creating all the databases needed for the rails application  type,

$rake db:create:all
 This will create databases for testing and production environment.

$rails db:migrate
This will connect our rails application to the database.