Synchronizing multiple processes

So, I’m at work and my teammate comes over and asks me if I know a solution to synchronize multiple processes such that only one of them can have access to a resource(say a file) at a time. My immediate thought was – a Mutex! But wait, don’t the processes have to share the same address space(which would work in the case of threads spawned by the same process). While thinking about the same, I realized that apt has a similar kind of lock, where it would not let me run multiple apt processes at the same time, because it has a lock on a file. But I had no idea how this was implemented – because for one, the main question that was at the back of my mind was – is a write operation on a file an atomic operation? After some googling, I found the docs and wrote a simple program to demonstrate its use.

#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>

#define ECHO_MSG(x) printf("%s\n", x)

int main(int argc, char *argv[])
{
    const char filepath[30] = "/Users/darthvader/testlock";
    struct flock *new_wt_lock = (struct flock *) malloc(sizeof(struct flock));
    FILE *fp;
    
    memset(new_wt_lock, 0, sizeof(struct flock));
    new_wt_lock->l_type = F_WRLCK;
    new_wt_lock->l_len = 0;
    
    fp = fopen(filepath, "w+");
    if(fp == NULL)
    {
        perror("Error opening file for writing");
        exit(EXIT_FAILURE);
    }
    ECHO_MSG("Attempting to acquire write lock"); 
    if( fcntl(fileno(fp), F_SETLK, new_wt_lock) == -1)
    {
      ECHO_MSG("Unable to acquire lock");
      perror("error");
      exit(EXIT_FAILURE);
    }
 
    ECHO_MSG("Doing random shit...");
    sleep(25);
    ECHO_MSG("Stopped doing random shit");
    
    if(fcntl(fileno(fp), F_UNLCK, new_wt_lock) < 0)
    {
        perror("Error releasing lock");
        exit(EXIT_FAILURE);
    }
 
    ECHO_MSG("Released Lock...Exiting");
}

To test its operation,

$ gcc getlock.c -o getlock

Screen Shot 2013-03-09 at 7.13.45 PM

Open 2 terminals and run the same program.  You will notice that the  latter cannot lock the file. Try it again after the program   exits and it  works like a charm

Screen Shot 2013-03-09 at 7.13.21 PM.

Hope you enjoyed this simple locking solution!

Detecting cycles using topological sort

An interesting and simple way to find the existence of cycles in a directed graph is using Kahns algorithm for topological sort.

typedef struct 
{
	int v; // end vertex
	int w; // weight of edge
} Edge;

int N; // No of vertices
int n_edges; // No of edges

vector< vector< Edge > > adjlist; // Graph represented as an adjacency list
vector< int > isolated_vert; // List of isolated vertices having indegree 0

int indegree[N]; 	// Populate with indegree of every vertex
int cur_vert, sz; 

while(isolated_vert.size() != 0)
{
    cur_vert = isolated_vert[0];
    sz = adjlist[cur_vert].size();

    for(int e = 0; e < sz; e++)
    {
    	/* Remove all outgoing edges */
        indegree[ adjlist[cur_vert][e].v ] -= 1; 
        n_edges -= 1;

	/* If vertex has indegree 0 add to list of isolated vertices */
        if(indegree[adjlist[cur_vert][e].v] == 0) 
        {
            isolated_vert.push_back( adjlist[cur_vert][e].v );
        }
    }
    isolated_vert.erase(isolated_vert.begin());
}
/* Graph still has edges */
if(n_edges > 0)
{
	cout<< "Cycle found" << endl; 
}
else cout<< "No Cycle found" << endl;

The total time complexity is O(|V| + |E|)

Getting blog feeds through email

I like to subscribe to the blogs of my friends and also keep up with various tech blogs across the blogosphere. I was using Google reader or subscribing to blogs individually. Unfortunately, Google reader doesn’t have a send-to-email feature where I can get real time updates sent to my mail and not all blogs have an email subscription feature. So i posted the question on Quora and found this useful website that sends me real time updates from my subscriptions.

More useful vim tips

Go to place in file

:G    End of file

1G  Start of file

<n>G    (or) :n Go the nth line of file

Find and Replace

This is of the form %s/<text to find>/<text to replace>/<options>

%s/foo/bar/g : Replaces all occurrences of  foo with bar

%s/\<foo\>/bar/g : Replaces all EXACT matches of the word foo  with bar

%s/foo/bar/gc : The c option, asks for a confirmation before replacing

SecurIT : A grand conference on security at my alma mater

I was pleased to see that things in my alma mater, Amrita University(Amritapuri) are progressing so rapidly. The SecurIT conference is being conducted from August 17th – 19th. The conference is broadly based on the topic of “The internet of things”. Several eminent researchers will be making their presence there including Andrew S Tanenbaum  of MINIX / Computer Networking fame, Robert Kahn – co-inventor of TCP/IP , Marvin Minsky (AI) – Turing award winner and several other dignitaries. I wish I could be there for this event. If you’re in India, you would be missing something big if you did not make it to the event. This certainly marks a bright future for our university. 

http://www.securit.ws/speakers.html

This conference has been designated by the European Economic Commission as one where you can apply directly to fully funded opportunities to study abroad in European Universities in France, Italy, Germany, Portugal and Spain.

Passing extra parameters to STL sort

While attempting to solve a Quora challenge , I had the necessity to sort a vector of objects with a third parameter as a reference.

My vector looked like

class Topic;
class Query;

vector<Topic> list_topics;

I needed to sort the vector list_topics using a Query object as reference. But traditionally, a comparator function takes in only 2 arguments of the same type as the elements that are being sorted.

bool compareTopics(const Topic t1 , const Topic t2){}; // Traditional comparator
sort( list_topics.begin() , list_topics.end() , compareTopics);

I needed to pass in a third parameter to make it,

bool compareTopics(const Topic t1, const Topic t2, Query query){
// compare here
};

In order to do this, we need to make use of functors i.e an object that can be called like a regular function. To implement this in C++, we need to define a class and implement to () operator function, while passing the extra arguments we need to the class constructor.

class TopicSorter{
    Query query_;
public:
    TopicSorter(Query query){ query_ = query; }
    bool operator()(Topic t1, Topic t2) const {
    return compareTopics( t1 , t2 , query_);
    }
};

Now we can sort the vector of objects

Query query;
sort(list_topics.begin() , list_topics.end() , TopicSorter(query));

Sebastian Thrun on the changing landscape of education

Here is an interview with Sebastian Thrun, where he discusses his ideas and thoughts on the changing landscape of education from the traditional classroom type education in a college to interactive online learning. 

http://youtu.be/75TP3hoPA8U

http://thisweekinstartups.com/blog/sebastian-thrun-of-google-and-udacity-271.html

I am really inspired by his talk. He speaks with the confidence of a true visionary and is clearly out with a mission to change the world where one does not have to shell out huge lumps of money to get a good education. I have registered for a few courses on Udacity, including Peter Norvig’s course and recently registered for the Physics and AI courses. Because I am doing a Masters course in Computer Science in parallel, I am able to contrast the standard classroom education and online education at the same time. The major reason I enrolled in a university in the United States, traveling thousands of miles was not to get a better job or just to certify myself as a Masters student, but to learn from the best teachers out there so that I can improve my knowledge. But even while in a university, one need not get the best a field has to offer. e.g. A university may have great profs in Systems, but not so much for HCI or AI. Now, with Udacity , Coursera , Khan academy and other players in the field providing online classes from the established professors in each field (case in point Sebastian Thrun for AI), one can go to these materials to fill in blank spots. I personally think university education is overrated. In my 4 years of undergraduate education in India, I did not learn much from my coursework. Rather, I learnt most of what I know from online sources. Without these, I would be writing crappy code at some mass recruiting software firm in India. 

My thoughts on some of the major advantages that such a model offers is

  • You can go back and view the same video over and over again till you get the concept. You can also go back and revise concepts you might have forgotten.
  • You can focus on one course at a time, which I feel is one of the best advantages. Most universities try to push a lot of knowledge at once into the brain by making you register for many courses in parallel. In my opinion, different people have different rates of concentration/absorption. For one, I perform much better when focusing on one topic over a long time rather than multitasking with 4 different topics at the same time.
  • Take it at your own pace. This is more useful for people who want to learn something new as a hobby, and may not be able to devote their entire time to it
  • Its fun and engaging, and you can watch it at home , at airport stop overs , on a bus journey sipping soda and lying on a bean bag instead of sitting in silence in a classroom listening to the monotone of the prof.

Thank you, Sebastian Thrun. Thank you, Salman Khan. A big thank you to all those educators out there who have made it their mission to ensure everyone gets a good education irrespective of their social status, background or geography. 

Indenting lines in vim

Vim has always been my primary editor for programming. There was always one part I hated doing the most, indenting lines. I did not know how to indent lines without manually doing it, as my laziness got the better of me. This time, I had to indent a huge block of text and I couldn’t let it be as it was. Here are some ways of indenting in vim.

1. <number of lines> <direction> <indent direction>
e.g. 5jj> indents 5 lines below to the right. jj represents the down direction. kk can be used for the opposite direction. < can be used for indenting to the left. Increasing the number of > or < , repeats the indentation that many times. E.g. >> indents it twice.

2. Indenting using Visual mode
You can use the visual mode to select the text you want to indent and then type ‘>‘ or ‘<‘ to indent the block.

3. Indenting a block between curly braces
If you want to indent an entire text block between curly braces, place the cursor on one of the curly braces and type %>
This is particularly useful for indenting loops and if/switch statements.

Happy indenting!