Crisp Reading Notes on Latest Technology Trends and Basics

Archive for June, 2012

Coroutines in C

This is a very readable and understandable article, that I have just rephrased a little. Enjoy reading it …

References

Motivating example

Decompressor

/* Decompression code */while (1) {

c = getchar();

if (c == EOF)

break;

if (c == 0xFF) {

len = getchar();

c = getchar();

while (len–)

emit(c);

} else

emit(c);

}

emit(EOF);

Parser

  • The second routine is a parser
    • This function scans continuous tokens of alphabets as a word
    • The rest of the characters are output individually as tokens.
/* Parser code */
while (1) {
    c = getchar();
    if (c == EOF)
       break;
    if (isalpha(c)) {
      do {
        add_to_token(c);
        c = getchar();
      } while (isalpha(c));
      got_token(WORD);
    }
    add_to_token(c);
    got_token(PUNCT);
}

Putting them together

  • These functions need to be put together. There are two approaches to doing this
  • In the first approach, we create two programs around each of these processes, and send the output of one to the input of the other.
  •  This involves two programs, and is typically a performance overhead.
  • Or one could create two threads, one thread running the decompressor, and the other thread running the parser
  • The decompressor produces a character, and places it into a buffer. The parser reads data from the buffer.
  • The threads co-ordinate by means of a lock or a semaphore.
  • This is still a performance overhead, especially if
  • An efficient way of putting the programs together within a single program is to rewrite one of the routines to output a character at a time, so that it can be used within the loop of another program.
  • The following is the routine to output the decompressed character
    • There are two static variables – replen and repchar, that represent repeated characters.

 UNIX Pipes

POSIX Threads

Rewriting the routines

Per-character Decompressor

int decompressor(void) {
  static int repchar;
  static int replen;
 
  // If repeated characters have not ended, send the character back
  if (replen > 0) {
    replen--;
    return repchar;
  }
 
  c = getchar();
  if (c == EOF)
    return EOF;
  if (c == 0xFF) {
    replen = getchar();
    repchar = getchar();
    replen--;
    return repchar;
  } else
    return c;
}
  • This function can be used to replace the getchar() method in the second function
/* Parser code */
while (1) {
  c = decompressor();
  if (c == EOF)
    break;
  if (isalpha(c)) 
    do {
      add_to_token(c);
      c = decompressor();
    } while (isalpha(c));
    got_token(WORD);
  }
  add_to_token(c);
  got_token(PUNCT);
}

Per-character Tokenizer

  • The following variant of the parser, returns token, if the next character forms a token
  • The actual implementation is more complex
    • The routine returns no token if the current character is alphabetic, and instead adds the token to its internal word.
    • If the next character is non-alphabetic, the internal word is output, as well as the next token.
void parser(int c) {
 
  // The state of whether there is a word being built or not
  static enum {
    START, IN_WORD
  } state;
 
  switch (state) {
 
    // If we are already in the word, and we get a token, we fall through
    case IN_WORD:
      if (isalpha(c)) {
        add_to_token(c);
        return;
      }
      got_token(WORD);
      state = START;
      /* fall through */
 
    // If the state is already Start, if we found a non-alphanumeric token, 
    //   we return that token as well
    //   else, we add to the internal array
    case START:
      add_to_token(c);
      if (isalpha(c))
         state = IN_WORD;
      else
         got_token(PUNCT);
      break;
    }
}

Knuth’s Co-routines

Knuth’s concept is to avoid the caller-callee relationship, and treat the processes as co-operating equals.

  1. Each co-routine gets its own co-location frame, where it gets to store its own local variables, and the return address
  2. When calling a co-routine, the function saves its location on the stack, and jumps to the address specified in the co-routine frame.
  3. Inside the co-routine, local variables are accessed from the co-routine frame, rather than from the stack.
  4. When the co-routine returns, the control returns to its old location, based on the return address saved on the stack as part of the co-routine call.

Co-routines in a stack-based Environment

Co-routines can also be implemented with the current chip architectures with the current compilers

  1. Every local variable needs to be static. This will ensure that all variables get allocated on a separate co-routine frame.
  2. One such variable – state denotes the location from where the co-routine previously returned.
  3. Based on this state, we go-to the previous point, where the computation left off.

A Toy Example

  • A routine to iterate through a list is specified as follows
  • The following is the original “C” function
int function(void) {
  int i;
  for (i = 0; i < 10; i++)
    return i;   /* won't work, but wouldn't it be nice */
}
  • When expressed as a co-routine, the following is the co-routine
int function(void) {static int state = 0;

static int i;

switch(state) {

case 0: goto BEGIN;  break;

case 1: goto LABEL1; break;

}

for( i = 0; i < 10; i++ ) {

state = 1;

return i;

LABEL1:;

}

}

Framework in C, and solution to the problem

Macros to achieve the same effect

  • The following are a good set of macros, that will achieve the same effect
#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=i; return x; case i:; } while (0)
#define crFinish }
  • The co-routine may therefore be coded as
int function(void) {
    static int i;
    crBegin;
    for (i = 0; i < 10; i++)
        crReturn(1, i);
    crFinish;
}
  • The macro crReturn could be simplified even further, as follows
#define crReturn(x) do { state=__LINE__; return x; \
                         case __LINE__:; } while (0)

The Decompressor code

  • The decompressor function may be modified to a co-routine as follows
int decompressor(void) {
  static int c, len;
  crBegin;
  while (1) {
    c = getchar();
    if (c == EOF)
      break;
    if (c == 0xFF) {
      len = getchar();
      c = getchar();
      while (len--)
        crReturn(c);
    } else
      crReturn(c);
  }
  crReturn(EOF);
  crFinish;
}
  • This could be used directly with the parser code.
  • The parser code could continue to be a direct subroutine call.
  • Alternatively, we could convert the Parser code into subroutine code as follows

The Parser Code

void parser(int c) {
  crBegin;
  while (1) {
    /* first char already in c */
    if (c == EOF)
      break;
    if (isalpha(c)) {
      do {
        add_to_token(c);
        crReturn( );
      } while (isalpha(c));
      got_token(WORD);
    }
    add_to_token(c);
    got_token(PUNCT);
    crReturn( );
  }
  crFinish;
}

Scalability of the Model

Multi-threading and Redundancy

In a multi-threaded environment, the above semantics are unlikely to be useful, because of the use of static variables.

The Use of Contexts

The way to solve this is to

  1. Have multiple contexts.
  2. Have an additional argument to each call – the Context itself. One variable in the Context State can store the last exit-point, or the expected entry-point.
  3.  Pass the Context into every call of the subroutine.
  4. All static variables need to dereference the context, instead of being static variables.

The use of Macros

The macros can make it easier to achieve this

Zookeeper Usage in Data-Centers

Overview

What is Zookeeper

Zookeeper is a “Name Server” in the Hadoop suite of products, with the following characteristics.

  1. Names form a hierarchical name-space
  2. It has functionality create, read, update and delete names
  3. It has functionality to send updates to registered listeners on different machines in the same order in which it received them.

The last two features enable it to be used for co-ordination and synchronization.

References

Simple Use Case

External Monitoring Service

Suppose we wanted to use an external monitoring service like Munin

  1. The external program will register a “Zookeeper Watch” to be informed whenever there is a change in the tree location.
  2. The existing services, such as apache may register a node.

For example, the node below represents an Apache server at www32.mydomain.com at port 80.

/services/www/www32.mydomain.com/80
  1. The munin system can periodically get a dump of all services under /services/www .  and load them into its special file – munin.conf
  2. Once this is done, the particular WebServer can be monitored by the Monitoring System.

Why not use a Database

Zookeeper is a superior interface to the database, because of the guarantees made

  1. The watch is ordered with respect to other events, other watches, and other asynchronous replies. The events are all propagated by the client library in the right order.
  2. The client will see the node creation event before it sees the value for the node
  3. The order in which events are seen by the client is the same as the order in which these are being seen by the Zookeeper service.

Usage in Hadoop

Managing Configuration Changes

  • When there are hundreds and thousands of nodes in a cluster, it becomes difficult to push configuration changes to the machines.
  • Zookeeper enables the configuration changes to be pushed.

Implementing Reliable Messaging

  • With Zookeeper, we can implement reliable producer-consumer queues
  • even if a few consumers and some Zookeeper servers fail.

Implement Redundant Services

  • Several identical nodes may provide a service.
  • One of these may elect itself as the leader (using a leader election algorithm), and may start providing the service.

Synchronize Process Execution

  • Multiple nodes can coordinate the start and end of a process or calculation.
  • This ensures that any follow-up processing is done only after all nodes have finished their calculations.

Usage in a Data-Center

Complex Ad-Serving environment

Zookeeper is also useful in a complex Data-Center environment

  • Let us consider the case of a Complex Ad-Serving system. It consists of several components
    • Database for Campaign data and Fiscal transactions
    • Ad-serving engines for serving the best Advertisements for the customers
    • Campaign planners for advertisers to run campaigns and simulations
    • Log collection engines for Data Warehousing, and data planning.
    • Data analytics and modeling systems
    • Fraud detection systems
    • Beacons and fault management systems
    • Failover servers

Bootstrap Configuration

One of the most important uses of Zookeeper in these cases is as a “Bootstrap Server”.

  • It contains the way to contact the “Services”, when all of the services are not running
  • It can store the primary and secondary configurations.

Distributed Service Locator

The Distributed Service Locator allows a way for services to access other services

  • Services may come up, and use “Leader Election” to decide the configurations.
  • They can store their status, which can then be queried.

Distributed System State

Zookeeper is usually used to maintain top-level system states, so that

  • An upto-date directory of which machine is running which service may be maintained
  • This directory may be used by the Monitoring Software to decide which machines should be monitored and how.

Configuration Push

To make configuration changes, and push them to the servers that use them,

  • Zookeeper can pro-actively push the configuration, if a new configuration is created
  • It can also be used to push software onto each of the clusters.

Using Zookeeper for Synchronization in Hadoop

Overview

Centralized Name Server

Both Google (Chubby), and Yahoo (Zookeeper) have been able to implement their service level co-ordinations of their Services and Jobs on top of “Centralized Name Servers”.

These Centralized Name Servers allow a lot of state to be exchanged at a coarse granularity between the co-operating services in a Distributed Environment.

The following are some of the features, where this may help

Configuration Each server / service instance in the system may read a centralized configuration.

This could be used to push a centralized configuration

Status Each server / service could periodically update the status.

This could be used for fault detection and recovery

Synchronization Each server could share its current status

This could be used to help several processes plan and synchronize activities

Synchronization

It is not very obvious that a Name Server could help with Synchronization, but it does. In this article, we discuss how Zookeeper – a Centralized Name Server helps nodes in a distributed system to achieve synchronization.

We discuss two kinds of synchronization primitives

Barrier When “n” workers become available, tasks can be scheduled
Task Queue When job-units become available, they can be picked up by the entities

References

Distributed Barrier

How does it work

A distributed barrier is created and defined as follows

  1. A barrier is instantiated with a name and a size “N”
  2. A thread enters a barrier by executing an enter function
    • The function hangs till there is a critical mass of “N”
    • Then it continues processing
  3. The thread picks up its unit-of-work.
  4. A thread may timeout, and leaves the barrier without picking up the work. In that case, we may need to search for an alternate thread.

How does Zookeeper help

Zookeeper is the common place where the centralized state of the barrier may be kept

  • The synchronization classes on each of the servers/services may use this distributed state to see each others’ state, and decide when to block or unblock.

The steps in the function are

  1. Each thread, when it enters the barrier, creates a node corresponding to itself
  2. Then it waits for the count of the children to reach “N”
  3. Every time there is a new node adding data, all other nodes are informed using a reliable callback.
  4. In each of those callbacks, the Zookeeper state is checked again, and if the critical mass is there, the function will return allowing the thread to continue

Implementation

SyncPrimitive

  • Both Barriers and Locks use the following class definition
    • Watcher is a logical interface that specifies the function – process
    • The constructor instantiates a new Zookeeper instance, and instantiates a mutex
public class SyncPrimitive implements Watcher {

static ZooKeeper zk = null;

static Integer mutex;

String root;

SyncPrimitive(String address) throws KeeperException, IOException {

if(zk == null){

System.out.println(“Starting ZK:”);

zk = new ZooKeeper(address, 3000, this);

mutex = new Integer(-1);

System.out.println(“Finished starting ZK: ” + zk);

}

}

@Override

synchronized public void process(WatcherEvent event) {

synchronized (mutex) {

mutex.notify();

}

}

}

Barrier

  • The Barrier constructor works as follows
    • The name of Zookeeper server, and the path of the Barrier node, as well as the size are sent
    • It creates a root node for the barrier, if no such node existed.
/**
  * Barrier constructor
  *
  * @param address
  * @param name
  * @param size
  */
Barrier(String address, String name, int size)
  throws KeeperException, InterruptedException, UnknownHostException 
{
  super(address);
  this.root = name;
  this.size = size;

  // Create barrier node
  if (zk != null) {
    Stat s = zk.exists(root, false);
    if (s == null) {
      zk.create(root, new byte[0], Ids.OPEN_ACL_UNSAFE, 0);
    }
  }

  // My node name
  name = new 
    String(InetAddress.getLocalHost().getCanonicalHostName().toString());
}
  • To enter a barrier, each thread needs to execute the enter() method
    • Create an ephemeral node in Zookeeper, under the specified name of the node
    • Next, retrieve the number of children under the Zookeeper node
    • If the number of children under a specified node is equal to the barrier size, then we return and the computation can start
    • Else, we block on the mutex.
  • The notify for the mutex comes when there is a Watcher event in the SyncPrimitive.process function specified above
/**
  * Join barrier
  *
  * @return
  * @throws KeeperException
  * @throws InterruptedException
  */

  boolean enter() throws KeeperException, InterruptedException{
    zk.create(root + "/" + name, new byte[0], Ids.OPEN_ACL_UNSAFE,
                    CreateFlags.EPHEMERAL);

    while (true) {
      synchronized (mutex) {
        ArrayList<String> list = zk.getChildren(root, true);

        if (list.size() < size) {
          mutex.wait();
        } else {
          return true;
        }
      }
    }
  }
  • Once the computation finishes, it leaves the barrier by removing itself from the Zookeeper tree
    • The routine first removes the self-node from the Zookeeper tree
    • Then, if there are still nodes to be released, then, we wait for the event of adding or removing children under this node.
/**
  * Wait until all reach barrier
  *
  * @return
  * @throws KeeperException
  * @throws InterruptedException
  */

  boolean leave() throws KeeperException, InterruptedException{

    zk.delete(root + "/" + name, 0);

    while (true) {
      synchronized (mutex) {
        ArrayList<String> list = zk.getChildren(root, true);
        if (list.size() > 0) {
           mutex.wait();
        } else {
          return true;
        }
      }
    }
  }

Producer-Consumer

Producer-Consumer primitives have two operations – produce and consume

The constructor operation is coded as follows

  • The node registers itself under its Internet address
/**
  * Constructor of producer-consumer queue
  *
  * @param address
  * @param name
  */

  Queue(String address, String name)
        throws KeeperException, InterruptedException 
  {
    super(address);
    this.root = name;

    // Create ZK node name
    if (zk != null) {
      Stat s = zk.exists(root, false);
      if (s == null) {
        zk.create(root, new byte[0], Ids.OPEN_ACL_UNSAFE, 0);
      }
    }
  }

The produce operation is specified as follows

  • At the first step, the producer adds a node under the root. This node is labeled /element, and has a suffix, that is automatically and atomically incremented
  • This is done using the flag – CreateFlags.SEQUENCE
  • Note that the Work-Unit itself is specified as the value of the node
  • Since the size of the Work-Units is unbounded, there are no locks
/**
  * Add element to the queue.
  *
  * @param i
  * @return
  */

boolean produce(int i) throws KeeperException, InterruptedException{
  ByteBuffer b = ByteBuffer.allocate(4);
  byte[] value;

  // Add child with value i
  b.putInt(i);
  value = b.array();
  zk.create(root + "/element", value, Ids.OPEN_ACL_UNSAFE,
            CreateFlags.SEQUENCE);

  return true;
}

For the consume operation,

  • Fetch the children, and try to delete the first node in the result
  • If there are no children, wait for an event to see if the lock can be released
/**
  * Remove first element from the queue.
  *
  * @return
  * @throws KeeperException
  * @throws InterruptedException
  */
  int consume() throws KeeperException, InterruptedException{

    int retvalue = -1;
    Stat stat = null;

    // Get the first element available
    while (true) {
      synchronized (mutex) {
        ArrayList<String> list = zk.getChildren(root, true);

        if (list.size() == 0) {
          System.out.println("Going to wait");
          mutex.wait();
        } else {

          Integer min = new Integer(list.get(0).substring(7));
          for(String s : list){
            Integer tempValue = new Integer(s.substring(7));
            if(tempValue < min) min = tempValue;
          }

          System.out.println("Temporary value: " + root + "/element" + min);
          byte[] b = zk.getData(root + "/element" + min, false, stat);
          zk.delete(root + "/element" + min, 0);
          ByteBuffer buffer = ByteBuffer.wrap(b);
          retvalue = buffer.getInt();

          return retvalue;
        }
      }
    }
  }

Routing – Link State Protocols ( Why use them )

This write-up is a top level overview of “Link State Protocols”, and why they are preferred, compared to “Distance Vector Protocols”. I have been wondering about this over the last ten years, and the recent surge in articles on IS-IS allowed some thoughts …

MS-Word Format

Link State Protocols

Mechanism

  1. Each node (router) keeps track of all (physical) links that it owns
  2. This state is advertised to the other routers (switches) periodically through a Link State Advertisement (LSA) message.
    • The Link State message is flooded to every other router in the network
  3. Every router therefore has data for every link in the network.
    • This data is stored in a database called Link State Database
  4. From this data, every router computes the shortest path to every network.
    • This computation is computationally expensive.Based on this, for every network, the next hop is computed
    • The next-hops are stored in a Forwarding Information Base (FIB)
  5. In the data layer, when a router receives a packet,
    • it looks up the next hop, and forwards the packet there.

Comparison to Distance Vector Protocols

Bandwidth to exchange Routing Information

While at an initial glance, it looks like “Link State Protocols” consume excessive bandwidth, because of “Link State Flooding”, a careful analysis shows that

  • Distance vector information, also in its steady state, exchanges the route to all the networks from the current node, with all its neighbors
  • The link state protocol, also does the same thing. Every network is owned by a router, and that data is passed onto every other router by flooding.

So, the byte quantity of data exchanged is the same.

Type of Information Exchanged

Distance Vector Protocols exchange the immediate “Next Hop” information for each of the networks. The paths to each network are computed and hashed at each hop. Hence, there is not too much computation at each node, but all state is not available at a single node.

Link State protocol carries information of the originating source to all the nodes. Hence all the nodes share the same state of the network. But the results of the “path computation”, to each of the network are not transferred. So, each router needs to compute the paths to each of the network.

Points of differences

Distance Vector Link State
Neighbor state of network only Complete network state replicated
Routing paths computed and next-hops exchanged Next hops not computed prior to exchange.

Faster flooding and Convergence

Since the local state of every router is available to all other routers, certain functions can be done better

Under steady state, it can be mathematically proved that there will be convergence, and no loops. This means that we need not be paranoid about disallowing loops in the short term. This allows us to optimize on other characteristics. We may reduce the overall convergence time by focusing on flooding the network with the state change, rather than defensively putting synchronizing conditions

Better Steady-state rerouting

Also, we would be able to use more sophisticated algorithms, while recomputing paths. We may be able to take into account the RSVP reservations on the paths, and build the next hop table, so that the entire network can satisfy the RSVP request.

Controlled Message Sizes

A message in “Distance Vector Protocols” is proportional to the total number of networks in the system. This may require some kind of “Session Based” data exchange between the adjacent routers, as the number of connected networks grows.

A message in “Link State Protocol” is proportional only to the number of links that a router is connected to. Hence, it fits better into a datagram, and can be transferred by the more efficient transport service.

UNIX Signals – Understanding them, and coding for them

Signals are one of the most complex pieces to code for, within the Linux environment. It is difficult to fully get it right, unless one understands a little bit of the internals. In this write up, I summarize a few points from a couple of good ppts on the topic.

Enjoy the perusal …

MS-Word version of this write-up
 
 

Overview

References

What is a signal

A short message sent by the kernel to a process or group of processes

  • Signal number is present as part of a message
  • Parameters related to the message are allowed in POSIX.4

Details

Signal Transmission

  • Signal sending
    • Kernel updates data structures in the Process Control Block (PCB)
  • Signal receiving
    • Kernel forces the process to handle the signal
  • Pending signals
    • Signals that have been sent, but not yet received
    • Processes/threads can block signals – prevent them from being received.

Hints to handle signals

  • The user process declares how it wants to handle a signal using the data structure
    • The action may be SIG_IGN to ignore the signal, or SIG_DFL for the default action
    • If not ignored or defaulted, the handler is execute
struct sigaction {

  void (*sa_handler)();/* handler address, or SIG_IGN, or SIG_DFL */

  sigset_t sa_mask;    /* blocked signal list */

  int sa_flags; /* options e.g., SA_RESTART */

}

 

Sending signals

  • Signals are sent using one of the following system calls
    • info is 0 if sender is a user-process.
    • Info is 1, if sender is the kernel
send_sig_info(int sig, struct siginfo *info, struct task_struct *t);

kill_proc_info(int sig, struct siginfo *info, pid_t pid);

Receiving Signals

  • Handling is done in entry.S , after handling the system call or interrupt. Called from ret_from_intr()
  • The function handle_signal() calls deque_signal() multiple times, till there are no more signals
  • Each signal that is not ignored or defaulted must be caught.

Receiving signals during a System call

  • handle_signal() is called in the kernel mode, while the handlers are present in the user_mode. This can create problems.
  • A blocked call is placed in TASK_INTERRUPTIBLE state.
  • When a signal arrives, it is woken up in the TASK_RUNNING state to execute the signal handler.
  • After this, the process/task has to be placed back in the old state.
  • This is done, if a flag SA_RESTARTABLE is set as part of sa_flags, while registering the signal handler.

Real-time Signals

  • Real-time signals are sent as part of a signal queue, and are dequeued similarly.
  • To send a real-time signal

int sigqueue(pid_t pid, int sig, const union sigval value);

  • When dequeued, the handler function contains the following data structure.
typedef union sigval {

int sigval_int;

void *sival_ptr;

} sigval_t;

Usage of alarm

alarm(2) is a system call in Linux, that sends a signal after the specified time has expired.  Let us discuss various aspects of integrating the alarm system call, as an example.

Usage

In the example below, the alarm system call is supposed to timeout on a slow system call, such as read

if( signal(SIGALRM, sig_alrm) == SIG_ERR )

{
printf(“signal(SIGALRM) error\n”);
exit(1);
}


alarm(10);
n = read( 0, line, MAXLINE );

Premature alarm expiry

Even though the alarm is set of 10 seconds, which should be adequate time to read the data,

  • there may be cases, because of extreme scheduling issues, where the read may not even be executed.
  • In that case, the alarm would expire, and the read function would execute, unprotected by the alarm.
  • To avoid this, use setjmp and longjmp to ensure restartability of application code.
    • setjmp may be used to save the context of the program, prior to the alarm system call.
    • When the signal for alarm expires, longjmp may be used to set the context to that saved
    • This will execute the alarm call prior to the read.
void sig_alrm(int signo)
/* interrupt the read() and jump to
setjmp() call with value 1
*/
{
longjmp(env_alrm, 1);
}

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

{

if( signal(SIGALRM, sig_alrm) == SIG_ERR) {
printf(“signal(SIGALRM) error\n”);
exit(1);
}

if( setjmp(env_alrm) != 0 )

{
fprintf(stderr, “\nread() too slow\n”);
exit(2);
}

alarm(10);
n = read(0, line, MAXLINE);

}

Signal handling within a signal handler

  • One more problem remains with the above scenario.
  • If the program has several signal handlers, and the program is inside one of the signal handlers, when the alarm goes off,
    • The longjmp inside the alarm handler will jump to the setjmp location.
    • This may abort the other handler, or corrupt its data
  • To avoid this, sigsetjmp and siglongjmp need to be used, which will work correctly with signals also.

Restartability within a slow system call

  • As mentioned before, we may be in the middle of a system call such as the read, when this signal handler triggers.
  • This system call then has to be restarted.
  • To allow this, the handler should be registered with the SA_RESTART flag

The modified code

void sig_alrm(int signo)
/* interrupt the read() and jump to
setjmp() call with value 1
*/
{
siglongjmp(env_alrm, 1);
}

void catch_int(int signo) {

}

sigfunc *signal( int signo, Sigfunc *func )
{

struct sigaction act, oact;

act.sa_handler = func;
sigemptyset( &act.sa_mask );
act.sa_flags = 0;

act.sa_flags |= SA_INTERRUPT;

// Fill the full set of signals in the mask

sigfillset(&(act.sa_mask));

if( signo != SIGALRM )

act.sa_flags |= SA_RESTART;

/* any system call interrupted by a signal

* other than alarm is restarted */

if( sigaction( signo, &act, &oact) < 0 )
return(SIG_ERR);
return( oact.sa_handler );
}

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

{

struct sigaction act;

act.sa_handler = catchint;

/* now, SIGINT will cause catchint to be executed */

sigaction( SIGINT, &act, NULL );

sigaction( SIGQUIT, &act, NULL );

act.sa_handler = sig_alrm;

if( sigaction(SIGALRM, &act, NULL) == SIG_ERR) {
printf(“signal(SIGALRM) error\n”);
exit(1);
}

if( sigsetjmp(env_alrm) != 0 )

{
fprintf(stderr, “\nread() too slow\n”);
exit(2);
}

alarm(10);
n = read(0, line, MAXLINE);

}

Re-entrancy

Some re-entrant functions

  • Sometimes the signal handler is called when the main program is in the middle of a function.
  • The same function could get called inside the signal handler as well.
  • In that case, these functions have to be re-entrant.
  • Not all functions are re-entrant

Some re-entrant functions

  • read(), write(), fork()

Some non-reentrant functions

  • malloc() /* The worst offender */
  • scanf(), printf(), strtok() etc

Setting of errno

  • Some signal handlers may call other functions, which may actually set the value of errno.
  • These must be restored when the error handler exits.
  • Otherwise functions could randomly, see their return values changed, if the signal handler was called.

 

Iterative Post-Order Traversal of a Binary Search Tree

Overview

Background

In memory-constrained architectures, it may be necessary to work without a lot of memory. In these cases, we try to execute iterative algorithms instead of recursive algorithms.

Problem Description

To develop an Iterative algorithm to do Post-order traversal of a Binary Tree.

  • Note :- The additional storage should not be proportional to the depth of the tree.
  • In the first cut, an extra Parent pointer may be assumed

Incidentally, this is also an “Amazon Interview Question”

The Algorithm

First Node

The first node in a Post-Order traversal is derived as follows

  1. Start from the Root
  2. If a node has a left child, traverse the left link
  3. Otherwise if the node has a right link, traverse the right link.
  4. Keep repeating this till you hit a leaf
Node *first_child( Node *root ) {

Node *curr = root;

while (1) {

if( curr->left != NULL ) {

curr = curr->left;

continue;

}

if( curr->right != NULL ) {

curr = curr->right;

continue;

}

return curr;

}

}

First Child of SubTree

The above fragment of code can be used for any subtree node (not just the Root)

Next Child

Given an arbitrary node, to find the next child, there are two cases

  1. If the current node is a right sibling of its parent,
  • Both left and right subtrees of the parent have been e xamined.
  • So, next node is the parent
  1. If the current node is a left sibling of its parent
  • The right subtree has not yet been examined, and must be examined before the parent.
  • So the next node is the first post-order child of the right subtree (if it exists)

The code is therefore as follows

Node *next_child( Node *curr ) {

// If node is the right child of the parent

if ( curr->parent->right == curr ) {

return parent;

}

// If node is the left child of the parent

if ( curr->parent->left == curr ) {

if ( curr->parent->right == NULL ) {

return curr;

}

else {

return first_child( curr->parent );

}

}

}

Putting it all together

The root is the last node traversed in a post-order traversal.

The traversal is supposed to end when the child returned is the root node

// Routine to traverse all nodes of the tree

void traverse_all( Node *root ) {

Node *curr = first_child(root);

visit(curr);

while( curr != root ) {

curr = next_child(curr);

visit(curr);

}

}

Further Ideas

Incidentally, the use of the “parent” pointer is extra memory, that should well be avoided.

Unfortunately, to avoid the stack, this was deemed necessary.

We need to look at other possibilities, such as the “Threaded Pointer”, and temporary tree rotation to see if these possibilities will work.

Generating Permutations – An Iterative Approach

Overview

Introduction

In many applications, all permutations of a given array need to be generated. While there is a straight-forward recursive algorithm, the approach does waste a lot of stack. An iterative technique is not straight-forward, but is efficient. ( Believe it or not, this was an Amazon-Seattle interview question in 2003)

In this post, I have described the iterative algorithm, and outlined the pseudo-code. The Djikstra paper on which this is based, has a reasonably clear example. Perhaps the notes here may explain a few things that were assumed in the paper.

References

Explanation of Approach

Inversions

Let us define Inversion of a number, as a function

inv(∏,i) = count of numbers to the right of i, that are less than iEg In the permutation < 6, 3, 8, 1, 4, 7, 2, 5 >,inv(∏,4) = 1 ,

since 2 is the only number to the right of 4, less than 4

Bound on the Inversion values

Note that, for any permutation inv(∏,i) < i, for any i

  • This is obvious, since we account for only numbers 1, 2, …, i-1 , while looking to the right of i.

Inversionless Permutation

A permutation of N digits, that has no inversions is a sequence in ascending order

Eg :- The permutation <0,1,2,3> has an inversion of [0,0,0,0]

Neighboring Inversions

Two inversions are inversions differ in only one position by a value of one.

Eg :- < 0, 0, 1, 1 > and < 1, 0, 1, 2 >are considered neighboring inversions

Neighboring Inversions to Neighboring Permutations

Permutations for Neighbouring inversions can be obtained from one another by swapping exactly one item

  • For example
Consider a permutation of the digits 0, 1, 2, 3The permutations corresponding to the Inversion areInversion                          Permutation

i[0]  i[1]  i[2] i[3]

[   0,    0,    1,    1 ] corresponds to   < 0, 2, 3, 1 >

and

[   0,    0,    1,    2 ] corresponds to   < 0, 3, 2, 1 >

  • There is also a very simple rule to obtain the second permutation from the first
Since the second inversion is formed by increasing i[3] by 1,the second permutation is formed from the first by– moving the number 3 right by one digit.
  • Note that getting a neighboring permutation is a O(1) operation, that involves swapping one number.

Gray Codes

Gray Codes are a way to cycle through a set of available values, so that the adjacent rows differ in at-most one digit. (It is used mostly in Boolean Algebra).

  • Here, we cycle through the inversions as [ ii, i2, …, ij ] , where ijisthe inversion for number j,
    • and hence varies from 0 through (j-1)
  • For the example of Inversions of size 3
    • The inversion sequence according to Gray-Code sequence is as shown below
    • Also shown is the permutation corresponding to these inversions
  Inversion             Permutation[ 0, 0, 0, 0 ]        < 0, 1, 2, 3 >[ 0, 0, 0, 1 ]        < 0, 1, 3, 2 >

[ 0, 0, 0, 2 ]        < 0, 3, 1, 2 >

[ 0, 0, 0, 3 ]        < 3, 0, 1, 2 >

[ 0, 0, 1, 3 ]        < 3, 0, 2, 1 >

[ 0, 0, 1, 2 ]        < 0, 3, 2, 1 >

[ 0, 0, 1, 1 ]        < 0, 2, 3, 1 >

[ 0, 0, 1, 0 ]        < 0, 2, 1, 3 >

[ 0, 0, 2, 0 ]        < 2, 0, 1, 3 >

…                    …

  • Observe carefully how the above permutations obey the rules
  • The Gray-Code generation algorithm is described below
  • The algorithm needs to distinguish between an increasing sequence of values, and a decreasing sequence of values.
    • To encode this, we use positive values when the sequence of values is increasing, and a decreasing set of values, when it is decreasing
    • Also, there needs to be a clear distinction between +0 and -0.
    • To accommodate this, we add one to all the positive values, and decrement one from the negative values. So, the range becomes –N to -1 ( versus –N+1 to 0 ), and N to 1 ( versus N-1 to 0 )

The Algorithm

Gray-Code Generation

So, a sequence of values< 0, 1, 2, 3,  3,  2,  1,  0, 0, 1, 2, 3 >would be encoded as

< 1, 2, 3, 4, -4, -3, -2, -1, 1, 2, 3, 4 >

  • With this encoding, the pseudo-code becomes, as shown above
<next,pos> := get_next_inv(curr,N);// Function to iterate over all digitsfunc get_next_inv( curr:Array, size:int ) : <next:Array,pos:int>

{

int  pos  = size-1;

while(pos > 0) {

<next,cont> = iter(curr,pos,size);

if (!cont) return <next,pos>;

pos–;

}

return <next,pos>;

}

// Function to iterate for a single digit

func iter( curr:Array, i:pos, size:int )

: tuple<next: Array, carry: bool>

if (curr[i] == size ) { curr[i] = -size; return <curr, false>; }

curr[i]++;

if ( curr[i] == -1 ) { return <curr,true>; }

return <curr,false>;

}

Getting the next Permutation

  • Getting the next Permutation involves the following steps
  1. Compute the inversion array from the current permutation
  2. Compute the next inversion and the change using the next_gray_code routine mentioned above
  3. Execute the change on the original permutation, and return the new one.
func next_perm(curr:Array, cinv:Array, size:int): <next:Array, ninv:Array>{

<ninv,pos> = get_next_inv( cinv, size );

next = move_item( curr, pos );

return <next,ninv>;

}

func move_item( curr:Array, pos:int ): <next:Array>

{

next = curr;

exchange( next, pos, pos + sign(curr[pos]) );

return next;

}

Tag Cloud