Scope
This article primarily discusses about the linkage types with a C++ perspective, at the same time giving an insight as to how the things differ from the C language.
Introduction
Identifier names are used in C++ to refer to various types, their instances and constructs like namespaces, templates, references etc. Linkage determines the portions of the program/translation units in which an identifier can be referenced, in other words its visibility. Linkage are of three kinds: internal linkage, external linkage and no linkage.
Linkage Types
Internal Linkage : A name having internal linkage type denotes an identifier which can be referenced using names declared in the same scope or in other scopes of the same translation unit. In other words internally linked identifiers are unique to a tranlation unit. The following kinds of identifiers have internal linkage.
Note 1: Some listings put members of unnamed namespace in internal linkage category but it's not implied. To quote comment [82] in Article 7.3.1.1 in the C++ standard - "Although entities in an unnamed namespace might have external linkage, they are effectively qualified by a name unique to their translation unit and therefore can never be seen from any other translation unit"
Note 2: Inline functions in C are of file scope whereas they have external linkage by default in C++.
External Linkage : A name with external linkage can be referred to from every translation unit of the program. The following kinds of identifiers have external linkage.
No Linkage : Names with no linkage are visible only in the scope in which they're declared. Such names include local objects, local classes, and other local types. Put differently, any name that has neither external linkage nor internal linkage has no linkage. Some exceptions to local declarations are entities declared with the extern keyword.
Linkage for functions and objects
The tabular representations below capture various scenarios resulting in varied linkage types for the functions and objects.
* The name has internal linkage if previously declared with internal linkage in a visible declarationStorage class specifier File scope (C) or namespace scope (C++) Block scope Class scope (C++ only) auto invalid invalid invalid extern external linkage, possibly internal linkage* external linkage, possibly internal linkage* invalid register invalid invalid invalid static internal linkage invalid external linkage none external linkage, possibly internal linkage* external linkage, possibly internal linkage* external linkage
Reversing the order of redeclaration with a different storage specifier leads to undefined results. To be more specific an identifier declared as extern before declaring it as static. In such a scenario the compiler does not complain, but results are also not defined.
* The name has internal linkage if previously declared with internal linkage in a visible declarationStorage class specifier File scope (C) or namespace scope (C++) Block scope Class scope (C++ only) auto invalid no linkage; automatic storage invalid extern external linkage, possibly internal linkage*; static storage external linkage, possibly internal linkage*; static storage invalid register invalid no linkage; automatic storage invalid static internal linkage; static storage no linkage; static storage external linkage; static storage none external linkage, except that const objects in C++ have internal linkage; static storage no linkage; automatic storage no linkage; same storage duration as the enclosing object
References
[1] Linkage in C and C++
[2] informIT - C++ Reference Guide (Linkage Types)
[3] C++ Standard
Tuesday, March 25, 2008
Linkage Types - C++
Thursday, March 20, 2008
Database Normalization
Introduction
The process by which an exiting database schema is modified to organise the data in an efficient, non-redundant manner is called Normalization. The primary goal of the process is to reduce data redundancy across tables and ensure that the data dependencies are meaningful, so that the data is logically stored and consumes less space. The process was first put forward by Edgar F Codd in his paper A Relation Model of Data for Large Shared Data Banks. Describing in generic terms the process decomposes the original non normalized table into two or more relations such that they convey the same meaning as the original table.
Problems addressed by normalization
Just to highlight various problems that can be faced while designing a database let's presume that we are to maintain the online library for the Browser Library Store. We will be needed to have a track of information pertaining to various books, publishers and authors. Initially we consider a single table for the purpose with fields such as Title, ISBN, Author, AuthorBio, Subject, Publisher, Price, Pages. Now using this schema for our database, can lead to various inconsistencies and anomalies. Storing unrelated group of information in a single table results in multiple records having same information, as in having same author for multiple books in this case leads to repeating the author information over these records. An improper/missing updating of any of the records leaves the database in an inconsistent state and can lead to false query results. This phenomenon is known as updating anomaly.
We won't be able to enter any information pertaining to author or publisher without a book being housed in our library or even cannot have multiple entries per book as we are having ISBN as the primary key here. This is known as insertion anomaly.
Similarly we can't delete record for any of the books from our library without deleting the author information, the scenario better known as the deletion anomaly.
Ideally, we should design our database so as to avoid these inconsistencies and anomalies, by normalizing the tables and enforcing referential integrity between them.
What are normal forms
A set of guidelines laid down by the database community for ensuring that the databases are normalized. The normal forms describe the degree of strictness of a table. The lesser the degree of normalization for a table, the greater are the chances of it having logical inconsistencies and data anomalies. The process tends to slow down the data retrieval, since data which may have been retrievable from one record in an non normalized design may have to be retrieved from several records in the normalized form. Therefore the rule of the thumb says that normalize while it doesn't have a measurable effect on performance. A typical database is normalized up to the third normal form, where in some cases may require the schema to consider higher degree of normalization. Lets take a look at what each of these normal forms has to offer us.
First Normal Form
The first normal form should be the simplest one to conform to. This rule calls for eliminating repeating groups in individual tables and creation of separate table for each related set of data. Each set of related data is further identified with a primary key. This requires values in each table to be atomic. In the example alluded to above, we have non atomic column author, which could be further broken into fields like first name, last name for better retrieval. Similarly there could be a subject field which needs to be atomic. We could achieve 1NF conformance by breaking down the original table into separate tables with related data. So we end up creating new tables namely Book, Author, Publisher, Subject and some tables to establish relations between them, which are all in 1NF.
| ISBN Number | Title | Price | PublisherID |
|---|---|---|---|
| 0321194871 | Exceptional C++ | $79 | 1 |
| 2119487103 | Introduction to Database System | $126 | 2 |
| 2342395603 | Exceptional C++ Style | $89 | 1 |
| 4545323233 | Inside C++ Object Model | $66 | 3 |
The information for the author, subject and publisher are taken out of the original table and the entire related set of information is moved to separate tables. The relation between the Book table and the Publisher table is modelled using the primary key of 'many' as the foreign key of the 'one' in the relation. Since the books and authors, books and subjects have many to many relationship the same is to be modelled as a separate tables.
Author Table
| AuthorID | First Name | Last Name | AuthorInfo |
|---|---|---|---|
| 1 | Herb | Sutter | One of the most prominent C++ experts. |
| 2 | Stanley | Lippman | Architect with the Visual C++ development team at Microsoft |
| 3 | Chris | Date | Specializing in relational database technology |
The author table contains the information about the author with AuthorID as the primary key.
| PublisherID | Name | Address | City | State | Zip | Phone |
|---|---|---|---|---|---|---|
| 1 | Addison-Wesley | 75 Arlington Street, Suite 300 | Boston | MA | 02116 | 201-767-5021 |
| 2 | Prentice Hall | Upper Saddle River | New Jersey | New Jersey | 07458 | 800-677-7377 |
| 3 | Sams Publishing | 800 East 96th Street | Indianapolis | Indiana | 46240 | 800-889-3358 |
Subject Table
| SubjectID | Name |
|---|---|
| 1 | C++ |
| 2 | Database |
In order to establish the relationship between the books, authors and subject we'll consider two more tables viz. BookAuthor table and BookSubject table.
BookAuthor Table
| ISBN Number | AuthorID |
|---|---|
| 0321194871 | 1 |
| 2119487103 | 3 |
| 2342395603 | 1 |
| 4545323233 | 2 |
This table models the many to many relationship between books and authors. A book may have more than one authors, similarly an author may have penned a number of books.
BookSubject Table
| ISBN Number | SubjectID |
|---|---|
| 0321194871 | 1 |
| 2119487103 | 2 |
| 2342395603 | 1 |
| 4545323233 | 1 |
The relationship between books and subjects is again many to many as a book may be covering more than one subjects, similarly a subject may have a number of books on it.
The only drawback of such normalization process is that we might need to use joins for even a simple cross table query.
The article will be updated soon...
Wednesday, March 19, 2008
Double-Checked Locking Pattern
Scope
This post is meant to discuss the overview of the Double-Checked Locking pattern, and discuss any alternative means to address te thread-safety issue with the Singleton pattern. Its presumed that we all are aligned as to what the singleton pattern is all about.
Introduction
Double-Checked Locking is a pattern in its own sense which is designed to add efficient thread safety to initialization of shared resources. It saves us of the overhead associated with applying various synchronization techniques to atomize the initialization of these shared resources. An example would be Gamma Singleton, where to have synchronized creation of the single instance of an object we need to acquire a lock before proceeding to initialize. The locking though is an overhead each time except when the resource is actually being initialized. The DCLP optimization proposes to check the lock hint (locking condition) in an unsafe way before proceeding to lock
The pattern itself is not perfect and might fail for varied reasons on uniprocessor or multiprocessor architectures. In the remaining article we'll discuss the attempt of DCLP to make a Singleton thread safe, concluding with a mechanism to address the issue.
Issue with Gamma Singleton
The traditional Gamma approach to implement a Singleton is based on intializing a static pointer on heap on its first access, and returning the exisiting instance if already created. This is done by checking the instance member say mInstanceP for NULLness before actual creation. This suffices in most single threaded environments, but then you might bump into interrupts or multi-threaded access to your singleton instance. Making the access thread safe seems to be relatively easy. All you need to do is to acquire a lock before testing for nullness, but this would be pretty expensive for each access to your singleton as acquiring locks is a heavy operation. DLCP comes to your rescue here.
Double-Checked Locking Pattern in action
The DCLP proposes to resolve the problem faced by the above method by first checking a lock hint/condition which determines whether our singleton is already setup, if not then proceed to aquire lock. It then again checks for the condition so as to initialize the instance and the conditional variable. The second condition here is essential to prevent the race condition where multiple threads execute in parallel. The threads will queue up at lock and when they finally acquire the lock they'll find the instance as already initialized, hence will skip the same.class Singleton
{
public:
static Singleton *getInstance (void)
{
// First check
if (mInstanceP == 0) {
// Ensure serialization
// (guard constructor acquires mLock)
Guard
// Double check.
if (mInstanceP == 0)
mInstanceP = new Singleton;
}
return mInstanceP;
// guard destructor releases mLock.
}
private:
static Mutex mLock;
static Singleton *mInstanceP;
};
Where the Double-Checked Locking pattern gives way!
There are several scenarios in which the DCLP might not behave in accordance to the 'observable behavior' mandated by the language standards.
Consider the initialization of the singleton instance using the expression
mInstanceP = new Singleton;
The compilers internally are free to breakup the expression into steps/instructions. The above expression can be broken down as 1) Allocate raw memory 2) Initialize the Singleton object by calling its constructor 3) Assign the address of the instance to mInstanceP member variable.
These instructions in order to give the desired result should be executed in an acceptable order, but its totally upto the compilers to determine the execution order or optimize to merge the instructions to execute. This optimization might fail in certain scenarios like parallel processing of multiple instructions. Since the language does not provide any constructs to mandate the constraints for instruction execution order, we have little in our hands we can do.
We can intersperse the execution statements with temporaries but then again the compilers are smart enough to phase them out during dependency analysis.
Another scenario where DCLP fails is their portability to hardware platforms that have nonatomic pointer or integral assignment semantics. Such scenarios are possible on systems where memory addresses cross alignment boundaries, thereby requiring two fetches from memory for each access. In this case, it may be necessary to use a separate wordaligned integral flag instead of using a non aligned instance pointerthe instance pointer.
Yet another problem arises if an aggressive optimizer caches the conditional variable say in a register and does away with the second conditional check. This problem can however be resolved using the volatile keyword at the cost of some lost optimization.
References
[1] DCL Pattern - Schmit & Harrison
[2] Dev C++ Article - Why DCLP isn't 100% thread safe
[3] C++ and The Perils of Double-Checked Locking: Part I
[4] C++ and The Perils of Double-Checked Locking: Part II
Tuesday, March 18, 2008
Multithreading - An Introduction
Introduction
To begin with a short definition we’ll introduce the technique as a programming paradigm to allow a program to perform multiple tasks concurrently. With the ever increasing speed of the CPUs, longer instruction pipelines and better compiler optimizations and given limitations of the hardware peripherals we needed a technique similar to preemptive multitasking (It is a the feature that allows your computer to run two or more programs concurrently) employed for processes (A program in execution is called a process) to be applicable at thread (A thread is a dispatch able unit of executable code which shares the address space, resources and kernel objects of a process) level to allow it to perform multiple tasks simultaneously. This lead to the advent of multithreading. In this technique we can have more than one thread of execution of a single process scheduled by the CPU to perform an independent task.
How is multithreading achieved?
Multithreading on a single processor system generally occurs by time slicing, wherein the processor switches between different threads and this happens fast enough to give the end user an illusion of simultaneity. On a multiprocessor or multi-core system, now coming into general use, threading can be achieved via multiprocessing wherein different threads and processes can run literally simultaneously on different processors or cores. Many known multithreading standards exist as of now. Win32 Multithreading is the standard on Windows platform, other multithreading standards do exist like OS/2, POSIX Threads known as pthreads and Java threads. There is no in built support for POSIX threads or pthreads on Windows but there are Open Source libraries that give you pthreads like interface on Windows.
Threading Basics
· A thread is an independent path of execution through a program.
· It has two components: a kernel object that the OS uses to manage the thread and its stack which it uses to maintain the method parameters and the local variables as it executes the code.
· This independent flow of control is accomplished because a thread maintains its own stack pointer, registers, scheduling properties (such as policy or thread priority), set of pending and blocked signals (A thread is said to be signaled when it is terminated, when active its non signaled) and other thread specific data.
· Any thread can be in one of the following states during its lifetime: 1) Active(Running) 2) Ready(Schedulable) 3) Waiting(Blocked) 4) Terminated
· There are various APIs to manage threads varying according to standards, just to give an example to create a thread using Win32 threading model we need to call Win32 API CreateThread or CRT API _beginthreadex. The same can be accomplished using pthread API pthread_create. Java thread can be created instantiating class object which either extends Thread class or implements Runnable interface (We need to call its start or run method in respective case to start the thread execution).
Threading Issues
All’s well if our threads didn’t have to communicate with each other, but this an ideal assumption which rarely happens practically. Our threads might need to communicate in certain scenarios like
a) When we have multiple threads accessing a shared resource in such a way that the resource does not become corrupt avoiding any race condition. (This requires atomic access to the resource)
b) They the threads are not in a cyclic deadlock condition accessing the resource already acquired by the other thread.
c) When one thread needs to notify one or more other threads that a specific task has been completed.
Thread Synchronization
Thread synchronization is the means to organize the processes’ threads so that multiple threads do no leave resources in an inconsistent state, thread dependency order is respected and thread communication is systematic. All thread synchronization does is to provide atomic access to a piece of code. There are various means to achieve the same depending upon our requirements and the threading model being used.
1. Need an atomic access for a single shared global.
Win32 provides us with InterLocked family of functions to achieve the same:Interlocked function Description InterlockedIncrement Increments variable by 1 atomically InterlockedDecrement Decrements variable by 1 atomically InterlockedExchangeAdd Increments the variable by specified amount InterlockedCompareExchange Compares and exchanges variables atomically InterlockedDecrement64 Decrements 64 bit variable by 1 atomically InterlockedExchangePointer Atomically exchanges a pair of pointer values
They are real fast as they do not put the thread to the waiting state, but are only good enough for elementary value variables. We need an entirely different solution for protecting a data structure.
2. Waiting on a thread to finish its execution.
Win32 has Wait functions for the sameWait function Description WaitForSingleObject Waits for a single object to become signaled (terminate/relinquish control) WaitForMultipleObjects Waits simultaneously on 64 objects, and can track each one independently
The wait functions have a simple interface. A single wait function can be used to wait on objects of varied types viz. a thread, mutex, semaphore, event etc. Using these APIs, it may not be readily apparent if the code is expecting a thread termination, an event to be signaled, or a mutex to be released. PThreads on the other hand have different functions to manage each kind of object
pthread_mutex_lock, pthread_mutex_unlock, pthread_cond_signal, pthread_cond_wait etc.
3. Need to guard atomic update to more sophisticated data structures
We have multiple solutions to this problem. On Win32 we have a choice of usingUse Spin locks, Critical Sections, Mutex and Events, Semaphores, Wait functions. We’ll discuss Critical Section as a solution here
Spin Locks
Spin locks can be implemented using Interlocked family function InterlockedExchange. All it does is poll for a particular value unless it is set.
It is expensive as this does not put the thread to wait and loops idly as in poling hence wasting CPU cycles.BOOL gResourceInUse = FALSE;
void SomeFunc(void)
{
// Waiting for the resource.
while (InterlockedExchange(&gResourceInUse, TRUE) == TRUE)
Sleep(0);
// Access the resource
…
// Release the Access to the resource
InterlockedExchange(&gResourceInUse, FALSE);
}
A critical section is a section of code that must be allowed to complete atomically with no interruption that affects its completion. Different from Spin locks, other threads which want to execute same piece of code are put in wait state. But here we can specify how many times we need to loop as in InterlockedExchange before putting the thread to wait state (as putting the thread to wait state involves context switching and might be heavier still), and this can be done by setting the spint count for the Critical Section. Various APIs to manipulate Critical Section are as follows.Critical Section function Description InitializeCriticalSection Initializes the CRITICAL_SECTION object EnterCriticalSection Puts a lock around critical code section LeaveCriticalSection Removes the lock DeleteCriticalSection Deinitializes the CRITICAL_SECTION object TryEnterCriticalSection If not granted access, immediately returns InitializeCriticalSectionAndSpinCount Initializes the critical section and specifies a spin count to be executed before moving to a wait state SetCriticalSectionSpinCount Changes Spin count at run time
A con of Critical Sections is that we may be caught up in deadlocks as it is hard to specify timeout for wait state.
4. We need protection from threads across processes (Kernel Mode Synchronization)
Spin locks, Critical Section are means to achieve User Mode Synchronization (where only user mode threads are involved). When we need to involve creation of kernel object (A kernel object is simply a memory block allocated by the kernel and is accessible only by the kernel. This memory block is a data structure whose members maintain information about the object. The are several types of kernel objects, such as event objects, file objects, file-mapping objects, mutex objects, process objects, semaphore objects, thread objects, waitable timer objects etc) to manage communication across processes the same is said to be Kernel Mode Synchronization.
A kernel object may be in two states a) Signaled b) Non Signaled. A thread and for that matter a process is created in nonsignaled state and it is marked as signaled when it finishes. So all we need is to create the kind of kernel object we want, around the code we want to protect and let the other thread wait on it until the kernel object is turned to signaled state.
4.1. When you want to wait on a thread/process to complete
Use Wait Functions (discussed above). Wait functions cause a thread to voluntarily place itself into a wait state until specific kernel object becomes signaled.
4.2. When you want to ensure that a thread has mutually exclusive excess to a resource.
Use Mutex Kernel Objects. They work pretty much like critical section with the difference that Critical Section are user mode objects while mutex are kernel mode objects. They are slower than their counterparts. Win32 APIs for manipulating mutex are
CreateMutex, OpenMutex, ReleaseMutex while PThreads have pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_trylock, thread_mutex_unlock for the same.
4.3. When you may be interested to form a listener kind of mechanism between two threads
Use Event Kernel Objects on Windows. An event can be in signaled or nonsignaled state. When signaled, threads waiting on event become schedulable, when nonsignaled, threads waiting keep waiting. Further more an event can be a manual reset or auto reset event. When a manual reset event kernel object becomes signaled, all the threads waiting on the event become schedulable. When an auto reset event becomes signaled, only one of the threads becomes schedulable. The Win32 APIs for the same are CreateEvent, OpenEvent, ResetEvent,
SetEvent, SetEventData. There is no direct equivalent to the Win32 event in pthreads. Rather, there are condition variables (data type pthread_cond_t), and there is no distinction between auto and manual reset. Condition variables most closely resemble auto-reset events, but there are some differences. The APIs are pthread_cond_signal, pthread_cond_wait, pthread_cond_timedwait.
4.4. When you want to synchronize the access in a way where you can provide simultaneous access certain number of times.
Use Semaphore Kernel Objects. For windows a semaphore consists of a maximum resource count (The maximum number allowed to access the resource) and current resource count (The available resources that can be allocated). If the current resource count is greater than 0, the semaphore is signaled, else it’s nonsignaled. The Win32 APIs for the same are CreateSemaphore,
OpenSemaphore, ReleaseSemaphore. Posix semaphore APIs are sem_init, sem_wait, sem_post, sem_getvalue, sem_trywait, destroy.
There are still other synchronization mechanisms like Critical Regions, Monitors, Waitable Timers, Named Semaphores which I haven’t taken up here. If need be they can be discussed. Hope this is useful to get you started on multithreading.
What people said... (0)
Post a Comment