Stanford CS Education Library Link

I cam across this link of Stanford CS Education Library which provides some very great online material for C  and Data Structures. There is online material available for Perl and Unix also , but as for now I have been exploring tutorials on C and Linked Lists.They are easy to understand and very engaging.Whenever I think of studying about data structures,I would first start with Schaum’s and then venture to writing programs on my own.The “LinkedList basics” pdf fills the void in between.It assumes you are equipped with basic theory and takes you forward in programming for linked lists.It starts with the very basics and explains all the concepts involved.A very good starting point for beginners .Great concepts for intermediates also.The best part is that it explains everything  from a programmer point of view and does not miss upon the basics.

Here are direct links to course material for LinkedList Basics, Essential C and Pointers and Memory

Mutex and Semaphores

I found this article on mutexes and semaphores really an interesting read.

The author has tried to explain the difference between mutex and semaphores elaborating and explaining the famous Bathroom example  quoted here :

Mutex vs. Semaphore, what is the difference?

The Toilet Example  (c) Copyright 2005, Niclas Winquist

Mutex:

Is a key to a toilet. One person can have the key – occupy the toilet – at the time. When finished, the person gives (frees) the key to the next person in the queue.

Officially: “Mutexes are typically used to serialise access to a section of  re-entrant code that cannot be executed concurrently by more than one thread. 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.”
Ref: Symbian Developer Library

(A mutex is really a semaphore with value 1.)

Semaphore:

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count – the count of keys – is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Officially: “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).”
Ref: Symbian Developer Library

The author thus concludes that the correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects.

A mutex is owned by a process. Whereas, semaphore allows one or more processes to share the resource.

mutex_lock(&mutex_obj)
// access global_data
mutex_unlock(&mutex_obj)H

Here, you are locking global data so that only one process can access it. Others will wait in a queue to access this global data.While in semaphore you can define how many concurrent processes can access that resource at a time.

sem(10) // ten process have the concurrent access

sem_lock(&sem_obj)
//access global_data
sem_unlock(&sem_obj)

When one process locks the semaphore the count decrements by 1. So when the count=0, all the processes are using the data.

Difference between binary semaphore and mutex :

A binary semaphore is like a mutex but there is a fundamental difference between a binary semaphore and a mutex in that if  mutex is acquired by some process, only that process can unlock it, where as a binary semaphore can be unlocked by any other process.

Properties of mutex and sempahore :

1. As pointed out by Michael barr, semaphores can also be used to signal from an interrupt service routine (ISR) to a task. Signaling a semaphore is a non-blocking RTOS behavior and thus ISR safe. Because this technique eliminates the error-prone need to disable interrupts at the task level, signaling from within an ISR is an excellent way to make embedded software more reliable by design.

2. In mutex, recursive calling is possible, where as this feature is not available in binary semaphore.Mutex can be recursively locked by same thread so though it has to be released by thread same number of times. In case of binary semaphore it is not possbile.

3. Priority inversion  is possible with a mutex. The same is not applicable in case of binary semaphore.With three threads A,B and C, with high , medium and low priority – if A and B are blocked on some event , C gets a chance to run. C while running can enter a critical section and lock a mutex.Meanwhile A and B become ready to run , and if A has to claim the mutex, it has to wait for C to release the mutex.However, if B does not have dependency on the mutex, it can run , as C has lower priority than B, thus C cannot proceed until B is running and A is blocked by a lower priority process running -B.

The risk of priority inversion can be eliminated by changing the operating system internal implementation of mutexes. Of course, this adds to the overhead cost of acquiring and releasing mutexes. However, it is not necessary to change the implementation of semaphores, which do not cause priority inversion when used for signaling. This is a second important reason for having distinct APIs for these two very different RTOS primitives.

And as I dug  Operating Systems by William Stallings, I took the following para from Stallings as conclusive:

To begin, the semaphore has a zero or positive value.If the value is positive,that value equals the number of processes that can issue a wait and immediately continue to execute.If the  value is zero, either by initialization or because a number of processes equal to the initial semaphore value have issued a wait.the next process to issue a wait is blocked,and the semaphore value goes negative.Each subsequent wait drives the semaphore value further into minus territory.The negative value equals the number of processes waiting to be unblocked.Each signal unblocks one of the waiting processes when the semaphore value is negative.

For both counting semaphores and binary semaphores, a queue is used to hold processes waiting on the semaphore.The question arises of the order in which processes are removed form such a queue.The fairest removal policy is  first-in-first-out (FIFO).The process that has been blocked the longest is released from the queue first;a semaphore whose definition includes this policy is called a “Strong Semaphore”.A semaphore that does not specify the order in which procceses are removed from the queue is a “weak semaphore”.

“A concept related to binary semaphore is the mutex.A key difference between the two is that the process that locks the mutex (Sets the value to zero) must be the one to unlock it.In contrast, it is possible for one process to lock a binary semaphore and for another to unlock it”

In some of the literature and in some textbooks, no distinction is made between a mutex and a binary semaphore.However, in practice, a number of operating systems such as Linux , Windows and Solaris offer a mutex facility that conforms to the definition in this book”

Links for references :

http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore

http://vodoom.wordpress.com/2008/09/24/difference-between-binary-semaphore-and-mutex/

http://geekswithblogs.net/shahed/archive/2006/06/09/81268.aspx

Adding adsense on WordPress blog

I was exploring the monetizing option  for another wordpress blog  of mine.And the first option I could think of was Adsense hoping that I would find lot of online support for the same. But when I tried to add adsense code to my blog,I realized it wasn’t that straightforward.This post is the info I collected from googling on the same.

To  be able to monetize through a wordpress blog, you need to first buy the domain from wordpress,but even if you buy a domain name, you can’t use the advertising on wordpress.com.Second requirement is that  you are the host of the domain and not wordpress.com as these types of blogs (like mine : embbytes.wordpress.com ) are not allowed to use javascript. Allowing javascript on a hosted platform is a security risk.So, you can’t use adsense on wordpress.com blogs. Read the wordpress terms of service  on advertising here - they don’t allow users to place advertisements on their free blogs.

So,what you would need to do is either get a VIP wordpress or get your own webhosting and domain name and go wordpress.org.  Then you can use adsense. As long as wordpress.com is hosting your blog, even getting a domain name doesn’t work. Other hosting options can be found here

After you have gone through these steps and are ready to insert the adsense code in your blog- don’t even think about editing the WordPress code unless you have some development experience.  Even if you are a developer editing the WP code is unnecessary and a maintenance issue.

The simplest way to add and place adsense code on your wordpress blog is adding a text widget.You can choose to use a plugin from the number of plugins available on wordpress.org for adding adsense code .This  link will help you through the steps.Another easier way is to place the code directly in the text widget without using a plugin as explained here in Add Google Adsense to Wordprss without plugins

I kept trying to add the code without a plugin using the latter method , but the widget won’t show anything on my blog’s sidebar except the title of the widget.And whenever, I would re-open the widget for editing, the code would disappear, just the titlebar text remained.This was because I realized later – I hadn’t shelled out the money to buy the domain and web hosting.

For the whole process from setting up your adsense a/c , to getting adsense code and placing it in your blog with visual illustrations, I found this link very helpful.

P.S. Nothing comes for free!

 

Why initializing global variables to zero is a bad idea

I got this book issued from my office library :”Embedded Real Time Systems Programming” by Sriram V Iyer and Pankaj Gupta.Though it looked like a book for beginners, I got it issued anyways,because that is exactly what you need sometimes!

The book is written in a very simple language and touches all the topics and spheres an embedded engineer would be confronted with, each with an equal space.The book is peppered with the authors’ own experiences during their programming career and how the concept was applied there.I haven’t finished the book yet, but I’d like to share this one excerpt from the book which looks like a misleadingly simple concept but corrected one very basic mistake I’d commit .I’d always initialize global variables to zero for the sake of readability.The following section helped clear a myth.

An excerpt on segments from ”Embedded Real Time Systems Programming” by Sriram V Iyer and Pankaj Gupta

In compiling parlance,a segment is usually a collection of related/similar data.

A program is a collection of code and data.Every program has the following segments :

1)data

2)bss/zeroinit

3)stack

4)text/code

The above four are common segments found in most of the programs.

Text/Code Segment : The program exists in the text segment.

The data can be classified as :

1)Global variables

• Initialized
• Uninitialized

2)Local variables

Data Segment :

This consists of global(global and static) variables that have been initialized to some value.The space for these initialized variables is assigned at compile time.So,having more initialized global variables leads to an increase in size of the final executable.This is not usually desirable.

We all know that if have an array (global or local) with initialisers less than that of the size of the array,the rest of the elements are initialized to zero.For eg, consider

int a[100] = {0,1,2};

This means that a[0] = 0, a[1] = 1, a[2] =2 and the rest a[3] to a[99] are initialized to 0.

But the danger of  above initialization is that ,for the sake of initializing 3 members of the array,we have added the space needed for 100 integers to the size of the final executable.If the integer size in your machine is 4 bytes,then the code size increases by 400 bytes.That is quite a lot of memory in the embedded systems.

Sometimes, global variables are initialized to 0 for the sake of clarity :

int i= 0;

init j = 0;

int main(void)

{

//….

}

But, this initialization to 0 is superfluous and is not required.But as a result of initialization,the final code size will increase by a few bytes.Uninitialized global variables are automatically initialized to zero.But, the main objective of this section is to bring home the point that initialized global variables are part of the data segment(that take space in the final executable).

BSS segment

This is the place for uninitialized global variables.Adding uninitialized global variables does not increase the code size. A note of the size of the bss segment is kept in the executable.During the loading of the executable,the size for the bss segment is allocated at run time.Then the memory allocated for the BSS segment is zeroed.(Now,we know how global variables are initialized to zero)

Tips :

If you have global integer/array variables initialized to zero,then you may very well remove the initializers to save object code size.

Interrupts Detection

I was asked an interesting question by a fellow team member – ” how the processor comes to know that interrupt has been raised”- the answer to which was – Processor samples the IRQ (in ARM) / interrupt line at a fixed interval of time  which may be equal to a few bus cycles , or for eg after every instruction execution.If there is a change on the line in accordance with the interrupt configuration (Edge triggered or level triggered), the processor comes to know that interrupt has been raised.

The next question was “Isn’t it also a kind of  polling then?”.Yes.Its polling but better than polling each device in turn for interrupt request.We “sample” just one line at a particular time interval.

This Q-A session motivated me to return to my favorite online resource on interrupt handling in ARM  by Andrew N. Sloss.This one is to be kept handy when you are implementing interrupts or handling interrupts in ARM.

How to delete Large folders from your Windows PC fastly

I have a large amount of  source code in my PC which eats up my hard disk very fast.So, I have to clean up my hard disk periodically.However,permanent delete with Shift+delete is too annoying.First, it calculates the time required to delete the contents and then gives a pop up asking for confirmation.At time this pop-up appears after 15-20 mins which means you have to be around your PC to attend to the pop-up.This process is sure to take a lot of time and CPU since its known that commands through GUI will be costlier than DOS commands which are more closer to the OS core,than their GUI counterparts.

After googling and reading various discussions on forums, I concluded and found the following set of DOS commands to be most useful of the lot.

del /f/s/q  folder_name > nul
rmdir /s/q  folder_name

del command is command to delete one or more files in the specified folder name

• /f – force , it ignores the read only settings of files and deletes them anyway
• /s – recursively delete subdirectories
• /q – quiet mode, does not prompt for yes/no before deleting
• nul   to avoid the overhead of writing to screen for every singe file

rmdir :  delete directory as specified by the folder_name

• /s   – removes all directories and files in the specified directory in addition to the directory itself. Used to remove a directory tree.
• /q – quiet mode, does not prompt for yes/no before deleting

del command does not delete the directory structure.To overcome this drawback,rmdir is used as next command to delete the empty directory structure as well.

You can copy these commands in the same order to a bat file and change the folder_name to the name of required folder to be deleted.And run the bat file.The bat file invokes a command window and the commands go to their job quietly and very fastly and you find your available hard disk amount going up.

I took these 2 links here and here as references.

Bootloader flow for an ARM based embedded system-2 (Important operations during the start up)

This post has been moved to my blog on embeddedrelated.com alongwith the first part on bootrom and s/w bootloader

Memories in Embedded System

Dynamic random access memory(DRAM)

It is the most commonly used RAM for devices.It has the lowest cost per megabyte compared with other types of RAM.DRAM is dynamic—it needs to have its storage cells refreshed and given a new electronic charge every few
milliseconds, so you need to set up a DRAM controller before using the memory.
Static random access memory (SRAM)

It is faster than the more traditional DRAM, but requires more silicon area. SRAM is static—the RAM does not require refreshing. The access time for SRAM is considerably shorter than the equivalent DRAM because SRAM does not require a pause between data accesses. Because of its higher cost, it is used mostly for smaller high-speed tasks, such as fast memory and caches.
Synchronous dynamic random access memory (SDRAM)

is one of many subcategories of DRAM. It can run at much higher clock speeds than conventional memory. SDRAM
synchronizes itself with the processor bus because it is clocked. Internally the data is fetched from memory cells, pipelined, and finally brought out on the bus in a burst. The old-style DRAM is asynchronous, so does not burst as efficiently as SDRAM.

DDRAM (DDR RAM)

This is double density RAM and is a variant of SDRAM.It is a new technology and is a clock-doubled version of SDRAM,which is replacing SDRAM nowadays.

Cache

A cache is a small, fast array of memory placed between the processor core and main memory that stores portions of recently referenced main memory. The processor uses cache memory instead of main memory whenever possible to increase system performance. The goal of a cache is to reduce the memory access bottleneck imposed on the processor core by slow memory.

Tightly coupled memory 

Tightly coupled memory is RAM which is placed very close to processor and hence is fast.TCM is more reliable than cache in the sense that data once placed in TCM is never cached out , ie it stays where it is placed and hence it is guaranteed to be present there and getting access fastly.

Difference between Kernel and OS

So, how many of you like me were always confused between kernel and OS and used to use the two terms interchangably.I don’t know..may be I am the only one.But anyways , here is a link that satisfied my curiosity and gave me a convincing answer.Quoting from :

http://www.differencebetween.net/technology/difference-between-operating-system-and-kernel/

Operating System vs Kernel

For most people, using a computer is second nature. This is made possible by the operating system that is running on top of the computer and hardware and makes it possible to communicate with it without having to use machine language or binary. The operating system provides us with an interface, whether graphic or text, where we can view the result of the commands we enter. It also provides us with an array of tools to configure the computer to our liking, at the very barest. But all this would not be possible without the kernel. The kernel is the core of the operating system and it is responsible for translating the commands into something that can be understood by the computer.

The aspect that a lot of programmers like about the kernel is in the abstraction. Hardware abstraction allows programmers to write code that can work on a wide array of hardware. Without hardware abstraction, each program needs to be written specifically for a given hardware configuration and would probably not work in another. This is the case with device drivers. These are specific pieces of code that identifies the hardware and gives the operating system a means to communicate with the device.

Although the kernel is the core of the operating system, most people are not even aware of it existence because it is buried behind a lot of other software. To provide a whole package that lets people use their computers, an operating system includes software that covers a lot of the common uses of computers. This includes a simple word processing application and a media player among other things.

Applications are created for specific applications as it needs to interact with its kernel in order to communicate with the hardware beneath it. Since each kernel is different, applications for one operating system are not able to execute on others. Some applications are also not capable of executing in older or newer versions of the same operating system due to the changes that are implemented.

Summary:
1. An operating system is a software package that communicates directly to the computer hardware and all your applications run on top of it while the kernel is the part of the operating system that communicates directly to the hardware
2. Though each operating system has a kernel, this is buried behind a lot of other software and most users don’t even know it exists

Microkernel

As a part of ongoing OS studies, I am trying to understand the concept of  microkernels practically and for this I came across the following useful piece of information to aid my understanding:

What are kernels and microkernels?

A core feature of any operating system, the kernel manages communication between hardware and software. The kernel is responsible for managing memory, and I/O to memory, cache, the hard drive, and other devices. It also handles device signals, task scheduling, and other essential duties. The kernel is one of the first components loaded into memory during the boot process, and remains active as long as the computer is operational. Kernels vary widely in function and scope, but always greatly affect their operating system’s capabilities. For this reason, particularly in Unix, administrators tweak the kernels to best suit their requirements.

Compared to a typical kernel, a microkernel is compact, performing only the basic functions universal to all computers. Designed to be integrated into different operating systems, a microkernel works with OS-specific servers that provide higher level functions. This component-based structure improves a system’s portability, but potentially at the expense of performance. Mach and its derivatives, the most prominent examples of the microkernel architecture, are the foundations of systems such as Tru64 Unix, the GNU Hurd, and Mac OS X.

<Courtesy : http://kb.iu.edu/data/agsv.html>

In microkernels,we neednot compile the whole kernel when we add drivers unlike monolithic kernels.(Normally ,for eg, in linux, you ‘ll recompile the whole kernel for changes in a particular driver)

Also task switching takes more time in a kernel,because it requires switching between user mode and kernel mode ,switching address spaces etc.In microkernels, task switching is less costly.

A very interesting read is  a mail chain between Linus and Tanenbaum where they argue about monolithic vs micro kernels.

Here is the link :

http://www.dina.dk/~abraham/Linus_vs_Tanenbaum.html