Time wait state
http://dev.fyicenter.com/Interview-Questions/Socket-4/Explain_the_TIME_WAIT_state_.htmlTCP keep alive
Tuesday, May 26, 2009
Monday, May 25, 2009
What is the difference between SO_REUSEADDR and SO_REUSEPORT?
SO_REUSEADDR allows your server to bind to an address which is in a TIME_WAIT state. It does not allow more than one server to bind to the same address. It was mentioned that use of this flag can create a security risk because another server can bind to a the same port, by binding to a specific address as opposed to INADDR_ANY. The SO_REUSEPORT flag allows multiple processes to bind to the same address provided all of them use the SO_REUSEPORT option. From Richard Stevens (rstevens@noao.edu): This is a newer flag that appeared in the 4.4BSD multicasting code (although that code was from elsewhere, so I am not sure just who invented the new SO_REUSEPORT flag). What this flag lets you do is rebind a port that is already in use, but only if all users of the port specify the flag. I believe the intent is for multicasting apps, since if you're running the same app on a host, all need to bind the same port. But the flag may have other uses. For example the following is from a post in February: From Stu Friedberg (stuartf@sequent.com): SO_REUSEPORT is also useful for eliminating the try-10-times-to-bind hack in ftpd's data connection setup routine. Without SO_REUSEPORT, only one ftpd thread can bind to TCP (lhost, lport, INADDR_ANY, 0) in preparation for connecting back to the client. Under conditions of heavy load, there are more threads colliding here than the try-10-times hack can accomodate. With SO_REUSEPORT, things work nicely and the hack becomes unnecessary. I have also heard that DEC OSF supports the flag. Also note that under 4.4BSD, if you are binding a multicast address, then SO_REUSEADDR is condisered the same as SO_REUSEPORT (p. 731 of "TCP/IP Illustrated, Volume 2"). I think under Solaris you just replace SO_REUSEPORT with SO_REUSEADDR. From a later Stevens posting, with minor editing: Basically SO_REUSEPORT is a BSD'ism that arose when multicasting was added, even thought it was not used in the original Steve Deering code. I believe some BSD-derived systems may also include it (OSF, now Digital Unix, perhaps?). SO_REUSEPORT lets you bind the same address *and* port, but only if all the binders have specified it. But when binding a multicast address (its main use), SO_REUSEADDR is considered identical to SO_REUSEPORT (p. 731, "TCP/IP Illustrated, Volume 2"). So for portability of multicasting applications I always use SO_REUSEADDR.
What exactly does SO_REUSEADDR do
This socket option tells the kernel that even if this port is busy (in the TIME_WAIT state), go ahead and reuse it anyway. If it is busy, but with another state, you will still get an address already in use error. It is useful if your server has been shut down, and then restarted right away while sockets are still active on its port. You should be aware that if any unexpected data comes in, it may confuse your server, but while this is possible, it is not likely. It has been pointed out that "A socket is a 5 tuple (proto, local addr, local port, remote addr, remote port). SO_REUSEADDR just says that you can reuse local addresses. The 5 tuple still must be unique!" by Michael Hunter (mphunter@qnx.com). This is true, and this is why it is very unlikely that unexpected data will ever be seen by your server. The danger is that such a 5 tuple is still floating around on the net, and while it is bouncing around, a new connection from the same client, on the same system, happens to get the same remote port. This is explained by Richard Stevens in ``2.7 Please explain the TIME_WAIT state.''.
Wednesday, May 20, 2009
Citrix learning
1. http://citrix.skillport.com/ ( try to get username and password for it)
2. http://mycitrite/C15/E-Learning%20Courses/default.aspx : site has the details on how to request for access:
I need to get username and passowrd for mycitrite
3. How to reset mycitrite password
4. Mylearning : https://rod.sumtotalsystems.com/citrix/app/management/LMS_LearnerHome.aspx?FromLogin=1
Tuesday, May 19, 2009
Interview question
1. use of volatile
2. storage class in c programming
3. code optimizations
SIMD, loop unrolling, parallelizing, pipelining
4. Radix tree
5. Spin lock and mutex
Monday, May 18, 2009
Other Imp interview questions
1. How to allocate memory in 2d or 3d array
2. Redix tree : imp for networking interview ..... used to store and search IP based Host
3. Read about thread
4. How to find max subset of sum of these number in one pass (0 , -1 , 5 , 3 ,-2 , 7, -9, 1)
2. Redix tree : imp for networking interview ..... used to store and search IP based Host
3. Read about thread
4. How to find max subset of sum of these number in one pass (0 , -1 , 5 , 3 ,-2 , 7, -9, 1)
Interview Question
Latest Interview question by Brocade communication
1. Why do we need to send MSS to other side?
2. What is value of syn in finla ack of 2-way handshake?
3. if r1 and r2 router r connected to hub and some host on hub sends packet to some network then it reaches to both router then how do router decide that one on these 2 router have to f/w this packet to other router?
4. HTML call flow, content length.
5. DNS call flow
6. if we write yahoo.com and what will happen?
7. Black widow archecture.
1. what is reentrant code ?2. what is spin lock , bottom half , semaphore , mutex , tasklet (difference between them )?3. what is virtual memory and why we need it?4. find the mid node of singly link list in one pass ?5. reverse singly and doubly link list ?6. delete a node from lik list if u know only the address of node to be deleted ?7. 8, ,5,3 and measure 4 liters water problem ?8. if u have 10 number from 1 to 10 and array of 9 then how to find missing element in one pass ? (n(n+1)/2) 9. MSS how to get value of mss ? default 536 ? could be different for sender and reciver for same connection ?10. psedo header of TCP and UDP ?11. count the number of bits set in number (n = n & n-1);12. check if number is power of 2 or not ?13. change xth bit from integer ?14. what is mobile ip?15. what is priority inversion and priority inheritance and priority celling ?16. segmentation and fragmentation ?17. why tcp is three way handshak why not two way ? (as in ace of two way its diffciult to know if its a new SYN or retransmited SYN )18. Routing protocols ? 19. slow start and congestion avoidence ?20. mirror image of binarry tree ?21. create binarry tree form normal tree ?22. serching and sorting algo ?23. how to find loop in a singly link list ?24. IPC machenism ?25. fork and exec ?26. static , volatile , static function , union , register , address of registar variable (compile defined in gnu c if u try to get address of register variable then it will ignore register request)28. What is DMZ ?29. difference b/w switch and router ?30. IGMPv1 and IGMPv2 ?31. Tcp timers , keepalive , prove management etc.32. TCP connection setup ?33. function pointer ?34. what is finate state machine ? 35. how to check if character used in some string and other string is not same and that too in a single PASS ? ex "neeraj" & "jenar" should be same ? (and assign prime number to each character and add if sume is same then character are same)36. difference betwen normal os and RTOS (in rtos we can preempt kernel and know worst time of execution )37, how rtt is calculated in tcp ?38. trce route and path mtu discovery ?39. os scheduling algo ?
40. Write Addition of two numbers using Bitwise operators.
---------------------------------------------------------------------------
Lnode *reverse_list( Lnode *head )/********************************/{ Lnode *rhead = NULL, *head1;
while ( head != NULL ) { head1 = head->next; head->next = rhead; rhead = head; head = head1; }
return rhead;}
An alternative version:-----------------------
Function `reverse_list_r()' is a recursive version of `reverse_list()'.
This alternative uses `accumulator recursion', a form of recursion much used in functional language programming.Again, two lists are involved in the processing -- the original list, and the accumulating reverse-list. (The actual work of reversingthe list, and the recursion, takes place in the subsidiary function, `reverser()'.)
Lnode *reverse_list_r( Lnode *head )/**********************************/{ return reverser( head, NULL );}
Lnode *reverser( Lnode *head, Lnode *rhead )/******************************************/{ Lnode *head1;
if ( head == NULL ) return rhead; else { head1 = head->next; head->next = rhead; return reverser( head1, head ); }}
/***Discourse for Ex. K.3.2 (142--1998)===================================
----------------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end
----------------------------------------
56. Write a program to remove duplicates from a sorted array.
ANS. int remove_duplicates(int * p, int size) { int current, insert = 1; for (current=1; current < size; current++) if (p[current] != p[insert-1]) { p[insert] = p[current]; current++; insert++; } else current++;
return insert;
} -------------------------------------------
reverse with single parameter
4. node * reverse (node * n) { node * m ;
if (! (n && n -> next)) return n ;
m = reverse (n -> next) ; n -> next -> next = n ; n -> next = NULL ; return m ; }-------------------------------
Bit-manipulation* 1. Reverse the bits of an unsigned integer.
* 2. Compute the number of ones in an unsigned integer.
3. Compute the discrete log of an unsigned integer.
* 4. How do we test most simply if an unsigned integer is a power of two?
5. Set the highest significant bit of an unsigned integer to zero.
6. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
Hints and Answers
1. #define reverse(x) \ (x=x>>16(0x0000ffff&x)<<16, x="(0xff00ff00&x)">>8(0x00ff00ff&x)<<8, x="(0xf0f0f0f0&x)">>4(0x0f0f0f0f&x)<<4, x="(0xcccccccc&x)">>2(0x33333333&x)<<2, x="(0xaaaaaaaa&x)">>1(0x55555555&x)<<1)
2. #define count_ones(x) \ (x=(0xaaaaaaaa&x)>>1+(0x55555555&x), \ x=(0xcccccccc&x)>>2+(0x33333333&x), \ x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x), \ x=(0xff00ff00&x)>>8+(0x00ff00ff&x), \ x=x>>16+(0x0000ffff&x))
3. #define discrete_log(h) \ (h=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16), \ h=(0xaaaaaaaa&h)>>1+(0x55555555&h), \ h=(0xcccccccc&h)>>2+(0x33333333&h), \ h=(0xf0f0f0f0&h)>>4+(0x0f0f0f0f&h), \ h=(0xff00ff00&h)>>8+(0x00ff00ff&h), \ h=(h>>16)+(0x0000ffff&h)) If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2….. But this macro does not work out log2(0) which does not exist! How do you think it should be handled?
4. #define power_of_two(x) \ ((x)&&(~(x&(x-1))))
5. (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero #define zero_most_significant(h) \ (h&=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16))
Graphics---------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end ----------------------------------Kruskal's Algorithm (spanning tree)The steps are: The forest is constructed - with each node in a separate tree. The edges are placed in a priority queue. Until we've added n-1 edges, Extract the cheapest edge from the queue, If it forms a cycle, reject it, Else add it to the forest. Adding it to the forest will join two trees together. Every step will have joined two trees in the forest together, so that at the end, there will only be one tree in T. We can use a heap for the priority queue. The trick here is to detect cycles. For this, we need a union-find structure. --------------------------------------------------------------
Basic Slow-StartThe algorithm begins in the exponential growth phase initially with a congestion window size (cwnd) of 1 or 2 segments and increases it by 1 Segment Size (SS) for each ACK received. This behavior effectively doubles the window size each round trip of the network. This behavior continues until the congestion window size (cwnd) reaches the size of the receiver's advertised window or until a loss occurs.When a loss occurs half of the current cwnd is saved as a Slow Start Threshold (SSThresh) and slow start begins again from its initial cwnd. Once the cwnd reaches the SSThresh TCP goes into congestion avoidance mode where each ACK increases the cwnd by SS*SS/cwnd. This results in a linear increase of the cwnd.-----------------------------------------------------------
Hi,
carti wrote:> Can anyone who knows well explain with example> of what is spinlock?> ...
> Something like the following it says.> > spinlock like a semaphore but has no process list. And when> a process finds a lock closed by another process, its "spins"> around repeatedly, executing a tight instruction loop until the lock> becomes open.> > I dont especially understand what is spinning and executing a> right instruction loop.
Spinlock (aka busy lock) is when a thread repeatedly tests for acondition. Eg. Look at the following C code -
1. while (lock == 1) continue; /* tight loop */ 2. lock = 1; 3. /* critical section goes here */ 4. lock = 0;
When executing this code the thread waits for some other thread toset lock to zero. When lock is zero, the thread enters the criticalsection.
A tight loop is a loop with a very small body. Spinning is the slangfor repeatedly executing a tight loop that effectively does nothing(like line 1 above).
Note: a race condition exists between lines 1,2. There exists thepossibility that more than one thread can enter the critical section atthe same time. This is because, the "test" to check "lock == 0" and the"set" "lock = 1" operations are not atomic. Atomic test-and-set supportfrom the hardware helps in preventing this. See the 'membar' (memorybarrier) instruction on Alpha architectures for how atomic test-and-setis implemented in hardware.
Spinlocks have the following features - 1. eats CPU - you are constantly checking lock status 2. you cannot hold this lock for long without degrading performance the rule of thumb goes that spinlocks are fine upto 150 iterations of your (while) loop. 3. on a lot of CPU architectures (esp ones that implement atomic test-and-set instructions), spinlocks are cheap to create. 4. can be implemented without kernel support
Semaphores are different in that while waiting to obtain a lock, athread is 'put to sleep' and does not consume any CPU cycles. Thethread is woken up (by the kernel or the threading library) when thelock becomes available. Creating/using semaphores is expensive becausethe kernel/threading library has to setup/maintain some internal datastructures, so its best to use them in cases where you have to wait along time to obtain a lock.
HTH,
- Raja------------------------------------------------------------------
Mutex & semaphore
There synchronization semantics are very different:
mutexes allows serialization of access to a given resource i.e. multiple threads wait for a lock, one at a time and as previously said, the thread owns the lock until it is done, most importantly only this particular thread can unlocks it.a binary semaphore is a counter with value 0 and 1, a task blocking on it until any task does a sem_post. The semaphore advertise that a resource is available, and it provides the mechanism to wait until it is signaled as being available.As such one can see a mutex as a token passed from task to tasks and a semaphore as traffic red-light (it signals someone that it can proceed).
There is a lot of confusion around these two concepts. They permit the same kind of feature i.e. synchronization but as I explained with different semantics.
Semaphores are usually more expensive to use than mutex, but they provide you sometimes more reliability. For example, let’s say you have two threads, thread A and thread B trying to serialize access to resource R.
The mutex way would be;
step 00 – create a lock objectstep 01 – A request the lockstep 02 – B request the lockstep 03 – A grab the lockstep 04 – A uses Rstep 05 – A release the lockstep 06 – B grab the lockstep 07 – B uses Rstep 08 – A request the lockstep 09 – B release the lockstep 10 – A grab the lock
Q: What happens if thread B returns between step 7 and step 9 ?A: step 10 may never occurs …
In this scenario there is no way to recover, the mutex is an opaque object and you are stuck in a deadlock situation. If you are using C++, you may get over it using RAII, but if you use plain C, well that’s harder.
With semaphores things are a little bit different, you can make step 10 happen even if your thread leaves early. You need an external actor of course (a monitoring thread for example) that upon thread completion may resume the work flow.
Since people are confused by semaphores or misuse them more frequently, here are a few examples on how to use them.
Serializing access using a semaphore
Note that when using a binary semaphore to serialize access to a resource, you need to initialize it with the value 1, meaning resource available.
Requesting the lock is done by calling sem_wait() on it, and releasing the lock is done by calling sem_post():
// thirst get a semaphore and initialize it with the value 1sem_init( … )…
// lock the resourcesem_wait( …)
… do some stuff …
// release the resourcesem_post( … )
The consumer / producer model
if you initialize the semaphore withe the value 0 and call sem_wait on it, the semantic is different, you are waiting for some one to signal you that there is some job to do.In this scenario, the semaphore is not used to serialize access to a particular resource, it is used as signaling mechanism.A consumer is waiting for a consumer to signal him that some data is available or that there is work to do.
very simple and effective, that’s why semaphore are used so frequently for producer/consumer work flows.
// thirst get a semaphore and initialize it with the value 0sem_init( … )…
while( true ){// wait for some job to dosem_wait( …)
… work hard on it …}
// yep there is no sem_post here: the producer, that gives this task// work to do is supposed to be the one calling sem_post()
check your platform semaphore implementation, sem_post(), sem_wait() and sem_init() are the API to use POSIX semaphores.
Your platform API may be different, but the concepts are the same.
Enjoy and share.-------------------------------------------------------
Priority inversion
http://www.netrino.com/Embedded-Systems/How-To/RTOS-Priority-Inversion
--------------------------------------------------------
good interview questions
http://www.techinterviews.com/programming-puzzles-riddles-and-interview-problems-------------------------------------------------------
puzzels
http://gurmeetsingh.wordpress.com/puzzles/---------------------------------------------------------
1. Why do we need to send MSS to other side?
2. What is value of syn in finla ack of 2-way handshake?
3. if r1 and r2 router r connected to hub and some host on hub sends packet to some network then it reaches to both router then how do router decide that one on these 2 router have to f/w this packet to other router?
4. HTML call flow, content length.
5. DNS call flow
6. if we write yahoo.com and what will happen?
7. Black widow archecture.
1. what is reentrant code ?2. what is spin lock , bottom half , semaphore , mutex , tasklet (difference between them )?3. what is virtual memory and why we need it?4. find the mid node of singly link list in one pass ?5. reverse singly and doubly link list ?6. delete a node from lik list if u know only the address of node to be deleted ?7. 8, ,5,3 and measure 4 liters water problem ?8. if u have 10 number from 1 to 10 and array of 9 then how to find missing element in one pass ? (n(n+1)/2) 9. MSS how to get value of mss ? default 536 ? could be different for sender and reciver for same connection ?10. psedo header of TCP and UDP ?11. count the number of bits set in number (n = n & n-1);12. check if number is power of 2 or not ?13. change xth bit from integer ?14. what is mobile ip?15. what is priority inversion and priority inheritance and priority celling ?16. segmentation and fragmentation ?17. why tcp is three way handshak why not two way ? (as in ace of two way its diffciult to know if its a new SYN or retransmited SYN )18. Routing protocols ? 19. slow start and congestion avoidence ?20. mirror image of binarry tree ?21. create binarry tree form normal tree ?22. serching and sorting algo ?23. how to find loop in a singly link list ?24. IPC machenism ?25. fork and exec ?26. static , volatile , static function , union , register , address of registar variable (compile defined in gnu c if u try to get address of register variable then it will ignore register request)28. What is DMZ ?29. difference b/w switch and router ?30. IGMPv1 and IGMPv2 ?31. Tcp timers , keepalive , prove management etc.32. TCP connection setup ?33. function pointer ?34. what is finate state machine ? 35. how to check if character used in some string and other string is not same and that too in a single PASS ? ex "neeraj" & "jenar" should be same ? (and assign prime number to each character and add if sume is same then character are same)36. difference betwen normal os and RTOS (in rtos we can preempt kernel and know worst time of execution )37, how rtt is calculated in tcp ?38. trce route and path mtu discovery ?39. os scheduling algo ?
40. Write Addition of two numbers using Bitwise operators.
---------------------------------------------------------------------------
Lnode *reverse_list( Lnode *head )/********************************/{ Lnode *rhead = NULL, *head1;
while ( head != NULL ) { head1 = head->next; head->next = rhead; rhead = head; head = head1; }
return rhead;}
An alternative version:-----------------------
Function `reverse_list_r()' is a recursive version of `reverse_list()'.
This alternative uses `accumulator recursion', a form of recursion much used in functional language programming.Again, two lists are involved in the processing -- the original list, and the accumulating reverse-list. (The actual work of reversingthe list, and the recursion, takes place in the subsidiary function, `reverser()'.)
Lnode *reverse_list_r( Lnode *head )/**********************************/{ return reverser( head, NULL );}
Lnode *reverser( Lnode *head, Lnode *rhead )/******************************************/{ Lnode *head1;
if ( head == NULL ) return rhead; else { head1 = head->next; head->next = rhead; return reverser( head1, head ); }}
/***Discourse for Ex. K.3.2 (142--1998)===================================
----------------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end
----------------------------------------
56. Write a program to remove duplicates from a sorted array.
ANS. int remove_duplicates(int * p, int size) { int current, insert = 1; for (current=1; current < size; current++) if (p[current] != p[insert-1]) { p[insert] = p[current]; current++; insert++; } else current++;
return insert;
} -------------------------------------------
reverse with single parameter
4. node * reverse (node * n) { node * m ;
if (! (n && n -> next)) return n ;
m = reverse (n -> next) ; n -> next -> next = n ; n -> next = NULL ; return m ; }-------------------------------
Bit-manipulation* 1. Reverse the bits of an unsigned integer.
* 2. Compute the number of ones in an unsigned integer.
3. Compute the discrete log of an unsigned integer.
* 4. How do we test most simply if an unsigned integer is a power of two?
5. Set the highest significant bit of an unsigned integer to zero.
6. Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
Hints and Answers
1. #define reverse(x) \ (x=x>>16(0x0000ffff&x)<<16, x="(0xff00ff00&x)">>8(0x00ff00ff&x)<<8, x="(0xf0f0f0f0&x)">>4(0x0f0f0f0f&x)<<4, x="(0xcccccccc&x)">>2(0x33333333&x)<<2, x="(0xaaaaaaaa&x)">>1(0x55555555&x)<<1)
2. #define count_ones(x) \ (x=(0xaaaaaaaa&x)>>1+(0x55555555&x), \ x=(0xcccccccc&x)>>2+(0x33333333&x), \ x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x), \ x=(0xff00ff00&x)>>8+(0x00ff00ff&x), \ x=x>>16+(0x0000ffff&x))
3. #define discrete_log(h) \ (h=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16), \ h=(0xaaaaaaaa&h)>>1+(0x55555555&h), \ h=(0xcccccccc&h)>>2+(0x33333333&h), \ h=(0xf0f0f0f0&h)>>4+(0x0f0f0f0f&h), \ h=(0xff00ff00&h)>>8+(0x00ff00ff&h), \ h=(h>>16)+(0x0000ffff&h)) If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2….. But this macro does not work out log2(0) which does not exist! How do you think it should be handled?
4. #define power_of_two(x) \ ((x)&&(~(x&(x-1))))
5. (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero #define zero_most_significant(h) \ (h&=(h>>1)(h>>2), \ h=(h>>2), \ h=(h>>4), \ h=(h>>8), \ h=(h>>16))
Graphics---------------------------------------
25. Reverse a linked list.
Ans: Possible answers -
iterative loop curr->next = prev; prev = curr; curr = next; next = curr->next endloop
recursive reverse(ptr) if (ptr->next == NULL) return ptr; temp = reverse(ptr->next); temp->next = ptr; return ptr; end ----------------------------------Kruskal's Algorithm (spanning tree)The steps are: The forest is constructed - with each node in a separate tree. The edges are placed in a priority queue. Until we've added n-1 edges, Extract the cheapest edge from the queue, If it forms a cycle, reject it, Else add it to the forest. Adding it to the forest will join two trees together. Every step will have joined two trees in the forest together, so that at the end, there will only be one tree in T. We can use a heap for the priority queue. The trick here is to detect cycles. For this, we need a union-find structure. --------------------------------------------------------------
Basic Slow-StartThe algorithm begins in the exponential growth phase initially with a congestion window size (cwnd) of 1 or 2 segments and increases it by 1 Segment Size (SS) for each ACK received. This behavior effectively doubles the window size each round trip of the network. This behavior continues until the congestion window size (cwnd) reaches the size of the receiver's advertised window or until a loss occurs.When a loss occurs half of the current cwnd is saved as a Slow Start Threshold (SSThresh) and slow start begins again from its initial cwnd. Once the cwnd reaches the SSThresh TCP goes into congestion avoidance mode where each ACK increases the cwnd by SS*SS/cwnd. This results in a linear increase of the cwnd.-----------------------------------------------------------
Hi,
carti wrote:> Can anyone who knows well explain with example> of what is spinlock?> ...
> Something like the following it says.> > spinlock like a semaphore but has no process list. And when> a process finds a lock closed by another process, its "spins"> around repeatedly, executing a tight instruction loop until the lock> becomes open.> > I dont especially understand what is spinning and executing a> right instruction loop.
Spinlock (aka busy lock) is when a thread repeatedly tests for acondition. Eg. Look at the following C code -
1. while (lock == 1) continue; /* tight loop */ 2. lock = 1; 3. /* critical section goes here */ 4. lock = 0;
When executing this code the thread waits for some other thread toset lock to zero. When lock is zero, the thread enters the criticalsection.
A tight loop is a loop with a very small body. Spinning is the slangfor repeatedly executing a tight loop that effectively does nothing(like line 1 above).
Note: a race condition exists between lines 1,2. There exists thepossibility that more than one thread can enter the critical section atthe same time. This is because, the "test" to check "lock == 0" and the"set" "lock = 1" operations are not atomic. Atomic test-and-set supportfrom the hardware helps in preventing this. See the 'membar' (memorybarrier) instruction on Alpha architectures for how atomic test-and-setis implemented in hardware.
Spinlocks have the following features - 1. eats CPU - you are constantly checking lock status 2. you cannot hold this lock for long without degrading performance the rule of thumb goes that spinlocks are fine upto 150 iterations of your (while) loop. 3. on a lot of CPU architectures (esp ones that implement atomic test-and-set instructions), spinlocks are cheap to create. 4. can be implemented without kernel support
Semaphores are different in that while waiting to obtain a lock, athread is 'put to sleep' and does not consume any CPU cycles. Thethread is woken up (by the kernel or the threading library) when thelock becomes available. Creating/using semaphores is expensive becausethe kernel/threading library has to setup/maintain some internal datastructures, so its best to use them in cases where you have to wait along time to obtain a lock.
HTH,
- Raja------------------------------------------------------------------
Mutex & semaphore
There synchronization semantics are very different:
mutexes allows serialization of access to a given resource i.e. multiple threads wait for a lock, one at a time and as previously said, the thread owns the lock until it is done, most importantly only this particular thread can unlocks it.a binary semaphore is a counter with value 0 and 1, a task blocking on it until any task does a sem_post. The semaphore advertise that a resource is available, and it provides the mechanism to wait until it is signaled as being available.As such one can see a mutex as a token passed from task to tasks and a semaphore as traffic red-light (it signals someone that it can proceed).
There is a lot of confusion around these two concepts. They permit the same kind of feature i.e. synchronization but as I explained with different semantics.
Semaphores are usually more expensive to use than mutex, but they provide you sometimes more reliability. For example, let’s say you have two threads, thread A and thread B trying to serialize access to resource R.
The mutex way would be;
step 00 – create a lock objectstep 01 – A request the lockstep 02 – B request the lockstep 03 – A grab the lockstep 04 – A uses Rstep 05 – A release the lockstep 06 – B grab the lockstep 07 – B uses Rstep 08 – A request the lockstep 09 – B release the lockstep 10 – A grab the lock
Q: What happens if thread B returns between step 7 and step 9 ?A: step 10 may never occurs …
In this scenario there is no way to recover, the mutex is an opaque object and you are stuck in a deadlock situation. If you are using C++, you may get over it using RAII, but if you use plain C, well that’s harder.
With semaphores things are a little bit different, you can make step 10 happen even if your thread leaves early. You need an external actor of course (a monitoring thread for example) that upon thread completion may resume the work flow.
Since people are confused by semaphores or misuse them more frequently, here are a few examples on how to use them.
Serializing access using a semaphore
Note that when using a binary semaphore to serialize access to a resource, you need to initialize it with the value 1, meaning resource available.
Requesting the lock is done by calling sem_wait() on it, and releasing the lock is done by calling sem_post():
// thirst get a semaphore and initialize it with the value 1sem_init( … )…
// lock the resourcesem_wait( …)
… do some stuff …
// release the resourcesem_post( … )
The consumer / producer model
if you initialize the semaphore withe the value 0 and call sem_wait on it, the semantic is different, you are waiting for some one to signal you that there is some job to do.In this scenario, the semaphore is not used to serialize access to a particular resource, it is used as signaling mechanism.A consumer is waiting for a consumer to signal him that some data is available or that there is work to do.
very simple and effective, that’s why semaphore are used so frequently for producer/consumer work flows.
// thirst get a semaphore and initialize it with the value 0sem_init( … )…
while( true ){// wait for some job to dosem_wait( …)
… work hard on it …}
// yep there is no sem_post here: the producer, that gives this task// work to do is supposed to be the one calling sem_post()
check your platform semaphore implementation, sem_post(), sem_wait() and sem_init() are the API to use POSIX semaphores.
Your platform API may be different, but the concepts are the same.
Enjoy and share.-------------------------------------------------------
Priority inversion
http://www.netrino.com/Embedded-Systems/How-To/RTOS-Priority-Inversion
--------------------------------------------------------
good interview questions
http://www.techinterviews.com/programming-puzzles-riddles-and-interview-problems-------------------------------------------------------
puzzels
http://gurmeetsingh.wordpress.com/puzzles/---------------------------------------------------------
Good example
For example, here's how you'd ensure that a structure is packed tightly (i.e. no padding between members) in MSVC:
#pragma pack(push, 1)struct PackedStructure{ char a; int b; short c;};#pragma pack(pop)// sizeof(PackedStructure) == 7Here's how you'd do the same thing in GCC:
struct PackedStructure __attribute__((__packed__)){ char a; int b; short c;};// sizeof(PackedStructure == 7)The GCC code is more portable, because if you want to compile that with a non-GCC compiler, all you have to do is
#define __attribute__(x)
Whereas if you want to port the MSVC code, you have to surround each pragma with a #if/#endif pair. Not pretty.
For example, here's how you'd ensure that a structure is packed tightly (i.e. no padding between members) in MSVC:
#pragma pack(push, 1)struct PackedStructure{ char a; int b; short c;};#pragma pack(pop)// sizeof(PackedStructure) == 7Here's how you'd do the same thing in GCC:
struct PackedStructure __attribute__((__packed__)){ char a; int b; short c;};// sizeof(PackedStructure == 7)The GCC code is more portable, because if you want to compile that with a non-GCC compiler, all you have to do is
#define __attribute__(x)
Whereas if you want to port the MSVC code, you have to surround each pragma with a #if/#endif pair. Not pretty.
Sunday, May 17, 2009
Todays Points
Pragmas :
A preprocessor directive that is not specified by the ISO standard. Pragmas often control actions of the compiler and linker. A pragma always begins with a number sign (#). The one I regularly use is #pragma pack(1) where I'm trying to squeeze more out of my memory space on embedded solutions, with arrays of structures that would otherwise end up with 8 byte alignment.
Subscribe to:
Posts (Atom)