DIFFERENCE BETWEEN SEMAPHORE AND MUTEX..

Mutex :

         A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section. Mutexes are typically used to serialize access to a section of re-entrant code that cannot be executed concurrently by more than one thread.

Semaphore :

       A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore). 

Here comes the question,

                    When to use mutex and when to use semaphore?

                    

The producer-consumer problem:

Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.

Using Mutex:

A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.

At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.

Using Semaphore:

A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.

There is misconception that binary semaphore and mutex are same.But they are not.The purpose of mutex and semaphore are different.Just the implementation is similar.

Mutex  is locking mechanism used to synchronize the access to resource.Only one task can acquire the lock.

Whereas Semaphore is a signaling mechanism.

Program to find missing number in a sequence 1 to n...

Algorithm.

step 1: store  the sequence  in the array
step 2: calculate the sum of array;
step: 3: calculate sum of 'n' numbers from 1 to n using the formula n*(n+1)/2;
step 4 : subtract sum of array from sum of n numbers;
        ie  (n*(n+1)/2)-sum of array;
step 5: the difference is the missing number

this approach is better when there is a single missing number...then what about when there are 2 missing numbers...

its very simple
   for the numbers in a sequence the difference will be 1 for every pair
   so find the difference for every pair starting from index 0
   when the difference is greater than 1 then the ( minimum number in pair+1) is the missing             number
   thus we can find more than 1 numbers those are missed from the sequence.

WHAT ACTUALLY HUBS,ROUTERS,GATEWAYS ARE......

One should know about Hubs,Routers,Gateways,Switches and their applications.........

Hubs, Bridges, Switches and Routers are used to build networks. If you are trying to design your own LAN (Local Area Network) at home, then you probably need to know what they do and the main differences between them. I will try to cover all that in addition to some networking details to cultivate the article and provide better understanding of how the internet works. After all, always remember that the internet as you know it is nothing more than a network of networks!

Hubs are used to build a LAN by connecting different computers in a star/hierarchal network topology, the most common type on LANs now a day. A hub is a very simple (or dumb) device, once it gets bits of data sent from computer A to B, it does not check the destination, instead, it forwards that signal to all other computers (B, C, D…) within the network. B will then pick it up while other nodes discard it. This amplifies that the traffic is shared.

There are mainly two types of hubs:

1. Passive: The signal is forwarded as it is (so it doesn’t need power supply).
2. Active: The signal is amplified, so they work as repeaters. In fact they have been called multiport repeaters. (use power supply)

Hubs can be connected to other hubs using an uplink port to extend the network.

OSI Model: Hubs work on the physical layer (lowest layer). That’s the reason they can’t deal with addressing or data filtering.

Switches on the other hand are more advanced. Instead of broadcasting the frames everywhere, a switch actually checks for the destination MAC address and forward it to the relevant port to reach that computer only. This way, switches reduce traffic and divide the collision domain into segments, this is very sufficient for busy LANs and it also protects frames from being sniffed by other computers sharing the same segment.

They build a table of which MAC address belongs to which segment. If a destination MAC address is not in the table it forwards to all segments except the source segment. If the destination is same as the source, frame is discarded.

Switches have built-in hardware chips solely designed to perform switching capabilities, therefore they are fast and come with many ports. Sometimes they are referred to as intelligent bridges or multiport bridges.
Different speed levels are supported. They can be 10 Mb/s, 100 Mb/s, 1 Gb/s or more.

Most common switching methods are:

1. Cut-through: Directly forward what the switch gets.
2. Store and forward: receive the full frame before retransmitting it.

OSI: Switches are on the data link layer (just above physical layer) that’s why they deal with frames instead of bits and filter them based on MAC addresses. Switches are known to be used for their filtering capabilities.

VLANs (Virtual LANs) and broadcast domains: Switches do not control broadcast domains by default, however, if a VLAN is configured in a switch it will has its own broadcast domain.

*VLAN is a logical group of network devices located on different LAN physical segments. However they are logically treated as if they were located on a single segment.

Bridges are used to extend networks by maintaining signals and traffic.
OSI: Bridges are on the data link layer so in principle they are capable to do what switches do like data filtering and separating the collision domain, but they are less advanced. They are known to be used to extend distance capabilities of networks.

In a comparison with switches, they are slower because they use software to perform switching. They do not control broadcast domains and usually come with less number of ports.

Routers are used to connect different LANs or a LAN with a WAN (e.g. the internet). Routers control both collision domains and broadcast domains. If the packet’s destination is on a different network, a router is used to pass it the right way, so without routers the internet could not functions.

Routers use NAT (Network Address Translation) in conjunction with IP Masquerading to provide the internet to multiple nodes in the LAN under a single IP address.

Now a day, routers come with hub or switch technology to connect computers directly.

OSI: Routers work on the network layer so they can filter data based on IP addresses. They have route tables to store network addresses and forward packets to the right port.

Gateways are very intelligent devices or else can be a computer running the appropriate software to connect and translate data between networks with different protocols or architecture, so their work is much more complex than a normal router. For instance, allowing communication between TCP/IP clients and IPX/SPX or AppleTalk.

OSI: Gateways operate at the network layer and above, but most of them at the application layer.

P.S. The term Gateway is used to refer to routers in some articles so beware. In this case, the router has gateway software. And Default Gateway is used to refer to the node (e.g. router) connecting the LAN to the outside (e.g. internet).

Repeaters are simple devices that work at the physical layer of the OSI. They regenerate signals (active hubs does that too).

There is an important rule to obey while using repeaters/hubs to extend a local network and is called the 5-4-3 rule or the IEEE way. The rule forces that in a single collision domain there shouldn’t be more than 5 segments, 4 repeaters between any two hosts in the network and only 3 of the segments can be populated (contain user connections).
This rule ensures that a signal sent over the network will reach every part of it within an acceptable length of time.
If the network is bigger, the collision domain can be divided into two parts or more using a switch or a bridge.

Conclusion

What have been introduced so far are the main traditional devices used to build networks, understanding how they work helps to understand the logic behind networks designing, however, now that technology advance quickly, it is possible to find new products in the market combining two or more of these devices into one.

Examples are:

- Brouter: Works as a Bridge and as a Router.
- IP Switch or MultiLayer Switch (MLS): New switches with routing capabilities, they forward data based on IP addresses, work at the network layer too.

IMPORTANT PROTOCOLS AT DIFFERENT LAYERS.....

Layer 1 protocols (Physical Layer):-
 ADSL Asymmetric digital subscriber line
 ISDN Integrated Services Digital Network RS-232, a serial line interface originally developed to connect modems and computer terminals
 SONET Synchronous Optical NETworking


Layer 2 protocols (Data Link Layer):- ARCnet
 DCAP Data Link Switching Client Access Protocol
 Econet
 Ethernet
 FDDI Fiber Distributed Data Interface
 Frame Relay
 HDLC High Level Data Link Control
 IEEE 802.11
 IEEE 802.16
 LocalTalk
 L2F Layer 2 Forwarding Protocol
 L2TP Layer 2 Tunneling Protocol
 LAPD Link Access Procedures on the D channel
 LLDP Link Layer Discovery Protocol
 PPP Point-to-Point Protocol
 PPTP Point-to-Point Tunneling Protocol
 Token ring

Layer 3 protocols (Network Layer) :-
 ICMP Internet Control Message Protocol
 IGMP Internet Group Management Protocol
 IGRP Interior Gateway Routing Protocol
 IPv4 Internet Protocol version 4
 IPv6 Internet Protocol version 6
 IPSec Internet Protocol Security
 IPX Internetwork Packet Exchange OSPF Open Shortest Path First
 BGP Border Gateway Protocol
 RIP Routing Information Protocol

Layer 4 protocols (Transport Layer) :-
 TCP Transmission Control Protocol
 UDP User Datagram Protocol

Layer 5 protocols (Session Layer) :- 9P Distributed file system protocol developed originally as part of Plan 9
 NCP NetWare Core Protocol
 NFS Network File System
 SMB Server Message

Layer 7 protocols (Application Layer):-

 DNS, Domain Name System
 DHCP, Dynamic Host Configuration Protocol
 FTP, File Transfer Protocol
 Gopher, a hierarchical hyperlinkable protocol
 HTTP, HyperText Transfer Protocol
 IMAP, Internet Message Access Protocol
 IRC, Internet Relay Chat protocol
 ISUP, ISDN User Part
 MIME, Multipurpose Internet Mail Extensions
 NetBIOS, File Sharing and Name Resolution protocol - the basis of file sharing with Windows.
 rsync, a file transfer protocol for backups, copying and mirroring
 SMTP, Simple Mail Transfer Protocol
 SNMP, Simple Network Management Protocol
 SOAP, Simple Object Access Protocol
 Telnet, a remote terminal access protocol TFTP, Trivial File Transfer Protocol, a simple file transfer protocol

Longest Common Subsequence...

Given two Strings X of length m and Y of length n.We have to find longest common sub-sequence(order matters but not necessarily contiguous block) in both the strings
  for example,
                     X=ABCDEF
                     Y=DGHEF
longest sub-sequence  is DEF of length 3 

One naive method is to find all sub-sequences of both the strings individually and compare the subsequences which match .Subsequence with longest length is the required result.
But this method requires exponential time as each string has 2^(length of string) subsequences.
We can use Dynamic Programming to solve this problem.
Let the two strings be ABCDEF and DGHEF

#include<stdio.h>

#include<stdlib.h>

int p=0,maxx=0,a[40];  

int max(int a, int b);  

int lcs( char *X, char *Y, int m, int n ) //returns length of subsequence

{

   int L[m+1][n+1]; //matrix to store lengths of subsequences

   int i, j;

     for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

  

       else if (X[i-1] == Y[j-1])

       {

         L[i][j] = L[i-1][j-1] + 1;

         if(L[i][j]>maxx)        //a[] is array to store postions of matching characters,

                                       p indicates the position

                  {

                        maxx=L[i][j];

                        a[p++]=i-1;

                   }

               }

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

      }

   }

   

   return L[m][n];

}

  

int max(int a, int b)

{

    return (a > b)? a : b;

}

  

int main()

{

  char X[] = "ABCDEF";

  char Y[] = "DGHEF";

  

  int m = strlen(X);

  int n = strlen(Y);

  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

    for(int i=0;i<p;i++)

          printf("%c", X[a[i]]);

    getchar();

  return 0;

}

Explanation :
    m=6,n=5
                    ABCDEF     DGHEF
    for each character of string X(i) compare with all characters of string Y(j)
         and update array L[i][j]
    for example when i=0 and j=0,the elements of array becomes
                      

             
                      when i=0 and j=0 L[i][j] will be assigned 0
                      when i=0 or j=0  L[i]j] will be assigned 0
                      when X[i-1]==Y[i-1],i.e whenever characters of both strings match then L[i][j]=L[i-1][j-1]+1
                      when i=3 and j=1
                                   as is it the first character to be matched ,L[i][j] upto i=3 and j=0 is 0
                                    therefore 
                                  L[3][1] = L[2][0]+1=0+1
                                  length of common subsequence upto D is 1
                Now the becomes as follows

   and a[0] will be assigned with 3
If the characters are not matched then maximum length of  common subsequence upto that character will be assigned to L[i][j]
Thus the process repeats and L[6][5] will be returned as length of longest common subsequence and array a[] contains longest common subsequence