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!

Advertisements

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|)

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));