Wednesday, April 28, 2010

My understanding of Thread Sync Objects

Mutexes:
A mutex is a special lock that only one thread may lock at a time. If a thread locks a mutex and then a second thread also tries to lock the same mutex, the second thread is blocked, or put on hold. Only when the first thread unlocks the mutex is the second thread unblocked—allowed to resume execution. GNU/Linux guarantees that race conditions do not occur among threads attempting to lock a mutex; only one thread will ever get the lock, and all other threads will be blocked.

A thread may attempt to lock a mutex by calling pthread_mutex_lock on it. If the mutex was unlocked, it becomes locked and the function returns immediately. If the mutex was locked by another thread, pthread_mutex_lock blocks execution and returns only eventually when the mutex is unlocked by the other thread. More than one thread may be blocked on a locked mutex at one time.When the mutex is unlocked, only one of the blocked threads (chosen unpredictably) is unblocked and allowed to lock the mutex; the other threads stay blocked.

pthread_mutex_t mutex;
pthread_mutex_init (&mutex, NULL);
pthread_mutex_lock (&mutex);
pthread_mutex_unlock (&mutex);

A simple type of deadlock may occur when the same thread attempts to lock a mutex twice in a row.

Locking a fast mutex (the default kind) will cause a deadlock to occur.

Locking a recursive mutex does not cause a deadlock. (those many number of calls to unlock the mutex needs to be made, in order to unlock the mutex, that’s it.)

GNU/Linux will detect and flag a double lock on an error-checking mutex that would otherwise cause a deadlock.The second consecutive call to pthread_mutex_lock returns the failure code EDEADLK.

By default, a GNU/Linux mutex is of the fast kind, the other two types can be created as –

This code sequence illustrates creation of an error-checking mutex, for instance:
pthread_mutexattr_t attr;
pthread_mutex_t mutex;
pthread_mutexattr_init (&attr);
pthread_mutexattr_setkind_np (&attr, PTHREAD_MUTEX_ERRORCHECK_NP); // or PTHREAD_MUTEX_RECURSIVE_NP
pthread_mutex_init (&mutex, &attr);
pthread_mutexattr_destroy (&attr);

pthread_mutex_trylock() : If you call pthread_mutex_trylock on an unlocked mutex, you will lock the mutex as if you had called pthread_mutex_lock, and pthread_mutex_trylock will return zero. However, if the mutex is already locked by another thread, pthread_mutex_trylock will not block. Instead, it will return immediately with the error code EBUSY.

Example:
thread_function()
{
While(1)
{
pthread_mutex_lock (&job_queue_mutex);
do_task()
pthread_mutex_unlock (&job_queue_mutex);
}
}

Semaphores:

Why is the need of Semaphore?
In the example, in which several threads process jobs from a queue, the main thread function of the threads carries out the next job until no jobs are left and then exits the thread. This scheme works if all the jobs are queued in advance or if new jobs are queued at least as quickly as the threads process them. However, if the
threads work too quickly, the queue of jobs will empty and the threads will exit. If new jobs are later enqueued, no threads may remain to process them. What we might like instead is a mechanism for blocking the threads when the queue empties until new jobs become available. A semaphore provides a convenient method for doing this. A semaphore is a counter that can be used to synchronize multiple threads.

Example:
thread_function()
{
While(1)
{
sem_wait(&job_queue_count);
pthread_mutex_lock (&job_queue_mutex);
do_task()
pthread_mutex_unlock (&job_queue_mutex);
}
}
some_other_async_func()
{
pthread_mutex_lock (&job_queue_mutex);
do_some_other_related_task()
sem_post (&job_queue_count);
pthread_mutex_unlock (&job_queue_mutex);
}

Important semaphore details –
semaphore.h
sem_t
sem_init()
sem_destroy()
sem_wait()
sem_trywait()
sem_post()
sem_getvalue()

Condition Variables:
Why do we need that?
Suppose that you write a thread function that executes a loop infinitely, performing some work on each iteration.The thread loop, however, needs to be controlled by a flag: The loop runs only when the flag is set; when the flag is not set, the loop pauses. During each iteration of the loop, the thread function checks that the flag is set. Because the flag is accessed by multiple threads, it is protected by a mutex. This implementation may be correct, but it is not efficient.The thread function will spend lots of CPU whenever the flag is not set, checking and rechecking the flag, each time locking and unlocking the mutex. What you really want is a way to put the thread to sleep when the flag is not set, until some circumstance changes that might cause the flag to become set.

How does condition variable work?
A condition variable enables you to implement a condition under which a thread executes and, inversely, the condition under which the thread is blocked. As long as every thread that potentially changes the sense of the condition uses the condition variable properly, Linux guarantees that threads blocked on the condition will be unblocked when the condition changes.
As with a semaphore, a thread may wait on a condition variable. If thread A waits on a condition variable, it is blocked until some other thread, thread B, signals the same condition variable. Unlike a semaphore, a condition variable has no counter or memory; thread A must wait on the condition variable before thread B signals it. If thread B signals the condition variable before thread A waits on it, the signal is lost, and thread A blocks until some other thread signals the condition variable again.

Important condition variable routines –
pthread_cond_init()
pthread_cond_signal()
pthread_cond_wait()

Semaphore and Condition Variable both are recommended to be used with mutexes for safety and locking features. Whenever your program performs an action that may change the sense of the condition
you’re protecting with the condition variable, it should perform these steps. (In
our example, the condition is the state of the thread flag, so these steps must be taken
whenever the flag is changed.)
1. Lock the mutex accompanying the condition variable.
2. Take the action that may change the sense of the condition (in our example, set the flag).
3. Signal or broadcast the condition variable, depending on the desired behavior.
4. Unlock the mutex accompanying the condition variable.

Tuesday, April 27, 2010

Overview of Certain Buzzwords

Agile :
Agile methods break tasks into small increments with minimal planning, and do not directly involve long-term planning. Iterations are short time frames ("timeboxes") that typically last from one to four weeks. Each iteration involves a team working through a full software development cycle including planning, requirements analysis, design, coding, unit testing, and acceptance testing when a working product is demonstrated to stakeholders. This helps minimize overall risk, and lets the project adapt to changes quickly. Stakeholders produce documentation as required. An iteration may not add enough functionality to warrant a market release, but the goal is to have an available release (with minimal bugs) at the end of each iteration. Multiple iterations may be required to release a product or new features.

Scrum :
Scrum is a “process skeleton” which contains sets of practices and predefined roles. The main roles in Scrum are:

the “ScrumMaster”, who maintains the processes (typically in lieu of a project manager)
the “Product Owner”, who represents the stakeholders, represents the business
the “Team”, a cross-functional group of about 7 people who do the actual analysis, design, implementation, testing, etc.
During each “sprint”, typically a two to four week period (with the length being decided by the team), the team creates a potentially shippable product increment (for example, working and tested software). The set of features that go into a sprint come from the product “backlog,” which is a prioritized set of high level requirements of work to be done. Which backlog items go into the sprint is determined during the sprint planning meeting. During this meeting, the Product Owner informs the team of the items in the product backlog that he or she wants completed. The team then determines how much of this they can commit to complete during the next sprint. During a sprint, no one is allowed to change the sprint backlog, which means that the requirements are frozen for that sprint. After a sprint is completed, the team demonstrates the use of the software.

Scrum enables the creation of self-organizing teams by encouraging co-location of all team members, and verbal communication across all team members and disciplines that are involved in the project.

A key principle of Scrum is its recognition that during a project the customers can change their minds about what they want and need (often called requirements churn), and that unpredicted challenges cannot be easily addressed in a traditional predictive or planned manner. As such, Scrum adopts an empirical approach—accepting that the problem cannot be fully understood or defined, focusing instead on maximizing the team’s ability to deliver quickly and respond to emerging requirements.


Waterfall :
Waterfall methodology is the most structured of the methods, stepping through requirements, analysis, design, coding, and testing in a strict, pre-planned, "all at once" sequence. Progress is often measured in terms of deliverable artifacts: requirement specifications, design documents, test plans, code reviews and the like.

A common criticism of the waterfall model is its inflexible division of a project into separate stages, where commitments are made early on, making it difficult to react to changes in requirements as the project executes. This means that the waterfall model is likely to be unsuitable if requirements are not well understood/defined or change in the course of the project.

Cloud computing :
Cloud computing is Internet-based computing, whereby shared resources, software and information are provided to computers and other devices on-demand, like a public utility.

It is a paradigm shift following the shift from mainframe to client-server that preceded it in the early '80s. Details are abstracted from the users who no longer have need of, expertise in, or control over the technology infrastructure "in the cloud" that supports them. Cloud computing describes a new supplement, consumption and delivery model for IT services based on the Internet, and it typically involves the provision of dynamically scalable and often virtualized resources as a service over the Internet. It is a byproduct and consequence of the ease-of-access to remote computing sites provided by the Internet.


Grid computing :
Grid computing is the combination of computer resources from multiple administrative domains for a common goal. One of the main strategies of Grid computing is to use middleware to divide and apportion pieces of a program among several computers, sometimes up to many thousands. Grid computing involves computation in a distributed fashion, which may also involve the aggregation of large-scale cluster computing based systems. The size of a Grid may vary from being small — confined to a network of computer workstations within a corporation, for example — to being large, public collaboration across many companies and networks.

"The notion of a confined grid may also be known as an intra-nodes cooperation whilst the notion of a larger, wider grid may thus refer to an inter-nodes cooperation".

Grids are a form of distributed computing whereby a “super virtual computer” is composed of many networked loosely coupled computers acting in concert to perform very large tasks. This technology has been applied to computationally intensive scientific, mathematical, and academic problems through volunteer computing, and it is used in commercial enterprises for such diverse applications as drug discovery, economic forecasting, seismic analysis, and back-office data processing in support of e-commerce and Web services.


Weblogic :(specific to my system)
A product of oracle, used for hosting a webpage.
Norkom application (FE) is developed in Java, and is hosted on weblogic.
Now weblogic knows which component/function to call when an event takes place on the FE.
Weblogic also knows which servers it is connected to, like norkomserv.
And since Norkomserv is SOA based, Weblogic knows and translates an event from FE to an API call of norkomserv.

SOA :
A service-oriented architecture is essentially a collection of services. These services communicate with each other. The communication can involve either simple data passing or it could involve two or more services coordinating some activity. Some means of connecting services to each other is needed.

The technology of Web services is the most likely connection technology of service-oriented architectures. Web services essentially use XML create a robust connection.

Service-orientation requires loose coupling of services with operating systems, and other technologies that underlie applications. SOA separates functions into distinct units, or services, which developers make accessible over a network in order to allow users to combine and reuse them in the production of applications. These services and their corresponding consumers communicate with each other by passing data in a well-defined, shared format, or by
coordinating an activity between two or more services

STL :
It provides containers, iterators, algorithms, and functors.
STL Containers : Vector, list, deque(dbl ended queue), queue, set, map, multimap(map with dup entries)
Vector : a dynamic array, like C array (i.e., capable of random access) with the ability to resize itself automatically when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.
list : a doubly-linked list; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time).
deque : a vector with insertion/erase at the beginning or end in amortized constant time, however lacking some guarantees on iterator validity after altering the deque.
queue : Provides FIFO queue interface in terms of push/pop/front/back operations.
set : mathematical set. Implemented using a self-balancing binary search tree.
multiset : a set with duplicate entries.
map : an associative array; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator < style="font-weight: bold;">multimap : a map with duplicate entries.

STL Iterators :
Input iterators (which can only be used to read a sequence of values),
output iterators (which can only be used to write a sequence of values),
forward iterators (which can be read, written to, and move forward),
bidirectional iterators (which are like forward iterators but can also move backwards)
random access iterators (which can move freely any number of steps in one operation).

STL Functors :
The STL includes classes that overload the function operator (operator()). Classes that do this are called functors or function objects. They are useful for keeping and retrieving state information in functions passed into other functions. Regular function pointers can also be used as functors.

STL Algorithms :
A large number of algorithms to perform operations such as searching and sorting are provided in the STL, each implemented to require a certain level of iterator (and therefore will work on any container which provides an interface by iterators).

The Boost Template Library : Wait for more details on this.

FIX protocol interview questions : Part 1 - Admin/Session

Well, I just felt a need that key FAQs in FIX be documented, so that can be used for a variety of purposes, primarily during interviews to gauge a candidate. I have tried to be correct to the max, but do not guarantee it. This is what is best to my knowledge, and its good to cross check things with the FIX site and documentation available there.

1. What is buy side and what is sell side ?
Sell side is the one who earns brokerage.
Buy side is the one who pays brokerage.
buy side (institutions)
sell side (brokers/dealers)

2. What is the latest FIX version in market now?
Its FIX 5.0 SP2.
Something called FIXT.1.1 is also coming.

3. What is FIXML?
FIXML is a structured, validated Extensible Markup Language (XML) derived grammar that is encapsulated within the standard FIX message. This format leaves the FIX session handling intact and minimizes the impact to existing implementations. As an XML-derived language, FIXML messages can be validated by standard parsers and take advantage of a flexible message structure. FIXML is the FIX Markup Language for application messages. It is an XML-derived language, encompassing a series of Document Type Definitions (DTDs) which define the formal representation of FIXML messages. These DTDs will be maintained and versioned in the same manner as the FIX specification. Since FIXML is an XML-based language, it can be parsed/validated by any of the widely available XML parsers, and is positioned to evolve with the XML standard in areas such as datatype validation.

4. What version of FIXML is avlbl now in market ?
Goes hand in hand with FIX version.

5. What is FIXimate?
A tool available on fixprotocol.org to help understand FIX msgs quickly.

6. What is FIXT1.1?
With the release of FIX Protocol version 5.0 in 2006 the FIX Global Technical Committee has introduced a new framework called Transport Independence (TI). Under the TI framework the FIX Session Protocol and the FIX Protocol (the application layer messages) have been separated. This allows FIX Protocol messages to sent via any appropriate transport technology (e.g. MQ, WS-RX, message bus) in addition to the FIX Session Protocol.

7. How does the FIX header look like ?
The first three fields in the standard header are BeginString (tag #8) followed by BodyLength (tag #9) followed by MsgType (tag #35).

8. How does the FIX trailer look like ?
The last field in the standard trailer is the CheckSum (tag #10).

9. Repeating data groups –
Fields within repeating data groups must be specified in the order that the fields are specified in the message definition within the FIX specification document.

10 . Is encryption possible in FIX? More details.
Yes.
The choice of encryption method will be determined by mutual agreement of the two parties involved in the connection. Any field within a message can be encrypted and included in the SecureData field, however, certain explicitly identified fields must be transmitted unencrypted. The clear (unencrypted) fields can be repeated within the SecureData field to serve as an integrity check of the clear data. When encryption is employed, it is recommended but not required that all fields within the message body be encrypted. If repeating groups are used within a message and encryption is applied to part of the repeating group, then the entire repeating group must be encrypted.

11. What is the field delimiter ?
The non-printing, ASCII "SOH" (#001, hex:0x01, referred to in this document as ), is used for field termination. Messages are delimited by the “SOH” character following the CheckSum field. All messages begin with the “8=FIX.x.y” string and terminate with “10=nnn“.

12. What is MultipleValueString data type? When is it used?
String field containing one or more space delimited values.
I have not seen a single scenario where it is used.

13. What are different data types in FIX –
Int, float, char, String, Boolean (Y,N)
Qty, Price, PriceOffset, Amt, MultipleValueSting, Currency, Exchange,
UTCTimeStamp (YYYYMMDD-HH:MM:SS (whole seconds) or
YYYYMMDD-HH:MM:SS.sss (milliseconds) format, colons, dash, and period required)
UTCTimeOnly(HH:MM:SS (whole seconds) or HH:MM:SS.sss (milliseconds) format, colons, and period required.)
LocalMktDate (YYYYMMDD format)
UTCDate : YYYYMMDD date of current GMT
Data : Raw data, always preceded with length field.
(UTC – Universal Time Coordinated also known as GMT)
Month-year : char field in YYYYMM format
Day-of-month : int field with values between 1-31

14. What are sequence numbers?
All FIX messages are identified by a unique sequence number. Sequence numbers are initialized at the start of each FIX session (see Session Protocol section) starting at 1 (one) and increment throughout the session. Monitoring sequence numbers will enable parties to identify and react to missed messages and to gracefully synchronize applications when reconnecting during a FIX session.
Each session will establish an independent incoming and outgoing sequence series; participants will maintain a sequence series to assign to outgoing messages and a separate series to monitor for sequence gaps on incoming messages.

15. More about heartbeats?
The hHeartbeat iInterval is declared by the session initiator using the HeartBtInt field in the Logon message. The heartbeat interval timer should be reset after every message is transmitted (not just heartbeats).

16. Does heartbeat/logon/logout etc msgs have seq numbers?
Like all application messages, even admin msgs have sequence number, including heartbeat. MsgSeqNum is a mandatory field in the standard message header.

17. More about ordered message processing?
The FIX protocol assumes complete ordered delivery of messages between parties. Implementers should consider this when designing message gap fill processes. Two options exist for dealing with gaps, either request all messages subsequent to the last message received or ask for the specific message missed while maintaining an ordered list of all newer messages. For example, if the receiver misses the second of five messages, the application could ignore messages 3 through 5 and generate a resend request for messages 2 through 5, or, preferably 2 through 0 (where 0 represents infinity). Another option would involve saving messages 3 through 5 and resending only message 2. In both cases, messages 3 through 5 should not be processed before message 2.

18. More about Possible Duplicates?
When a FIX engine is unsure if a message was successfully received at its intended destination or when responding to a resend request, a possible duplicate message is generated. The message will be a retransmission (with the same sequence number) of the application data in question with the PossDupFlag included and set to "Y" in the header. It is the receiving application's responsibility to handle the message (i.e. treat as a new message or discard as appropriate). All messages created as the result of a resend request will contain the PossDupFlag field set to “Y”, messages lacking the PossDupFlag field or with the PossDupFlag field set to “N” should be treated as original transmissions.
Note: When retransmitting a message with the PossDupFlag set to Y, it is always necessary to
recalculate the CheckSum value. The only fields that can change in a possible duplicate message are the CheckSum, OrigSendingTime, SendingTime, BodyLength and PossDupFlag. Fields related to encryption (SecureDataLen and SecureData) may also require recasting.

19. More about Possible resend?
Ambiguous application level messages may be resent with the PossResend flag set. This is useful when an order remains unacknowledged for an inordinate length of time and the end-user suspects it had never been sent. The receiving application must recognize this flag and interrogate internal fields (order number, etc.) to determine if this order has been previously received. Note: The possible resend message will contain exactly the same body data but will have the PossResend flag and will have a new sequence number. In addition the CheckSum field will require recalculation and fields related to encryption (SecureDataLen and SecureData) may also require recasting.

20. How can we maintain a 24 hour session, using ResetSeqNumFlag?
What is the process to establish a new set of sequence numbers?

Both sides should agree on a reset time and the party that will be the initiator of the process. Note that the initiator of the ResetSeqNum process may be different than the initiator of the Logon process. One side will initiate the process by sending a TestRequest and wait for a Heartbeat in response to ensure of no sequence number gaps. Once the Heartbeat has been received, the initiator should send a Logon with ResetSeqNumFlag set to Y and with MsgSeqNum of 1. The acceptor should respond with a Logon with ResetSeqNumFlag set to Y and with MsgSeqNum of 1. At this point new messages from either side should continue with MsgSeqNum of 2. It should be noted that once the initiator sends the Logon with the ResetSeqNumFlag set, the acceptor must obey this request and the message with the last sequence number transmitted “yesterday” may no longer be available.

21. What care to be taken before logging off/closing the session?
It is recommended that before sending the Logout message, a TestRequest should be issued to force a Heartbeat from the other side. This helps to ensure that there are no sequence number gaps.

22. More about standard message header?
Following are mandatory fields –
BeginString[8], MsgType[35], BodyLength[9]
SenderCompId[49], TargetCompId[56]
MsgSeqNo[34], SendingTime[52]

23. More about standard message trailer?
CheckSum[10] is the only mandatory field, and it is the last field.

24. How is data integrity maintained?
Using BodyLength[9] and CheckSum[10] fields.
BodyLength is calculated starting from field starting after BodyLenght and
before CheckSum field.
CheckSum is calculated from ‘8= upto SOH before the checksum field.
Binary value of each character is calculated and compared to the LSB of the calculated value to the checksum value.
If the checksum has been calculated to be 274 then the modulo 256 value is 18 (256 + 18 = 274). This value would be transmitted a 10=018 where
"10="is the tag for the checksum field.

25. If there’s no heartbeat for a long time, how can my gateway check if the connection is active or not?
Send a TestRequest, to which the other party must respond with a heartbeat
with same TestReqId.

26. What all msgs you can respond with, when you receive a resend request?
Retransmit the requested msgs in order, with orig seq no, and PossDupFlag=Y
Issue a seq-reset-GapFill with PossDupFlag=Y, to replace the retransmission of admin and app msgs.
Issue a seq-reset-reset with PossDupFlag=Y to force seq no synchronization.

27. Can HeartBtInt be ever zero?
If HeartBtInt is set to zero, then it means, the two parties have agreed to have no hearbeats. But TestReq will still force a heartbeat.

28. Logon msg is responded with Logon[A] only.

29. There are two modes of seq reset msg –
Gap Fill : GapFillFlag=Y
Reset : No GapFillFlag, or GapFillFlag = N.

30. Different Admin MsgTypes –
HeartBeat 0
Logon A
Logout 5
TestRequest 1
ResendRequest 2
SeqReset (2 modes) 4
Reject 3