Operating System Misc

http://www.zrzahid.com/process-threads-and-synchronization/
Given n, print numbers from zero to n sequentially using two threads such that one thread prints only odds and other prints only evens.

Process
Process is an execution stream in the context of a particular process state. By Execution Stream we mean a sequence of instructions executed sequentially i.e. only one thing happens at a time. By Process State we mean everything that can affect, or be affected by, the process: code, data, call stack, open files, network connections, etc.

A process has a self-contained execution environment. A process generally has a complete, private set of basic run-time resources e.g. process has its own memory space. Process memory is divided into four sections as shown in Figure below:

• Text Section : contains compiled program code loaded when program is launched.
• Data Section : contains global and static variables, allocated and initialized prior to executing main
• Stack : contains local variables, function call frames. It starts from higher memory address and shrink down as elements are added.
• Heap : used for dynamic memory allocation using for example, new, delete, malloc, free, etc.

Note that the stack and the heap start at opposite ends of the process’s free space and grow towards each other. If they should ever meet, then either a stack overflow error will occur, or else a call to new or malloc will fail due to insufficient memory available.

Thread
Thread is unit of sequential execution. In other words, Threads are multiple execution streams within a single process. Threads share process state such as memory, open files, etc. Each thread has a separate stack for procedure calls (in shared memory).

Threads are sometimes called lightweight processes. Both processes and threads provide an execution environment, but creating a new thread requires fewer resources than creating a new process.

Threads exist within a process — every process has at least one. Threads share the process’s resources, including memory and open files. This makes for efficient, but potentially problematic, communication.

Process vs Threads
A process is an execution environment provided by the operating system that has its own set of private resources such as memory, open files, etc. On the other hand, Threads live within a process and share its resources : memory, open files, etc.

A process runs independently and isolated of other processes. It cannot directly access shared data in other processes. The resources of the process, e.g. memory and CPU time, are allocated to it via the operating system.

A thread is a so called lightweight process. It has its own call stack, but can access shared data of other threads in the same process. Every thread has its own memory cache. If a thread reads shared data it stores this data in its own memory cache. A thread can re-read the shared data.

For example, a Java application runs by default in one process. Within a Java application you work with several threads to achieve parallel processing or asynchronous behavior.

Process vs Program
A program by itself is not a process. It is a static entity made up of program statement while process is a dynamic entity. Program contains the instructions to be executed by processor.

A program takes a space at single place in main memory and continues to stay there. A program does not perform any action by itself.

How Process Works?
A process lifecycle goes through some states as described in the following figure –

When processes are swapped out of memory and later restored, additional information must also be stored and restored. Key among them are the program counter and the value of all program registers. kernel uses a Process Control Block (PCB) to keep track of processes as showed in following figure –

• Process State : Running, waiting, etc.
• PIDs : Process ID, and parent process ID.
• CPU registers and Program Counter : Information to restore swapped process out of memory.
• Memory-Management information : page tables or segment tables.
• I/O Status information : Devices allocated, open file tables, etc.
• Accounting information : user and kernel CPU time consumed, account numbers, limits, etc.

The dispatcher/scheduler is the one of the most important component (a kernel process itself) in OS that runs processes/threads. it does time slicing of the processor and assign one single thread to be in running state. Then it swaps this process by saving its state and load states of another process/thread from the scheduling queue based on a scheduling criteria or algorithm such as FIFO, Round Robin, or Priority based scheduling etc and run it. This incident is known as Context Switch i.e. changing the thread currently running on a CPU by first saving the state of the old process, then loading the state of the new process.

Note that, only one process can be running on a cpu at a particular time slice of the processor. So, if a thread is executing, scheduler isn’t running. So, question is how scheduler will run again to take control and schedule next process? Answer is Traps and Interrupts.

Traps are events occurring in current thread that cause a change of control into the operating system. There are 3 ways to trap OS –

• System call.
• Error (illegal instruction, addressing violation, etc.).
• Page fault.

Interrupts are events occurring outside the current thread that cause a state switch into the operating system, for example completion of am I/O, expiration of a timer, keyboard events etc. The context switch process can be described pictorially as follows –

Process Creation

• Load code and data into memory.
• Create and initialize process control block.
• Create first thread with call stack.
• Provide initial values for “saved state” for the thread
• Make process known to dispatcher; dispatcher “resumes” to beginning of process.

IPC : Inter Process Communication
Processes are often seen as synonymous with programs or applications. However, what the user sees as a single application may in fact be a set of cooperating processes. To facilitate communication between processes, most operating systems support Inter Process Communication (IPC) resources, such as message queues, pipes and sockets. IPC is used not just for communication between processes on the same system, but processes on different systems.

Read more in here.

Concurrency and Synchronization
When multiple threads access shared resources such that some of them modify a resource and others are reading that resource then we will face all sorts of data consistency problem due to synchronization issues among threads. For example, if thread A reads shared data which is later changed by thread B and thread A is unaware of this change. Let’s first define some terms before jumping into details –

• Synchronization : using atomic operations to ensure correct operation of cooperating threads.
• Critical section : a section of code, or collection of operations, in which only one thread may be executing at a given time. E.g. shopping.
• Mutual exclusion : mechanisms used to create critical sections (ensure that only one thread is doing certain things at a given time).

However, synchronization can introduce thread contention, which occurs when two or more threads try to access the same resource simultaneously and cause the Java runtime to execute one or more threads more slowly, or even suspend their execution. Starvation and livelock are forms of thread contention.

• Starvation : Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by “greedy” threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
• Livelock : A thread often acts in response to the action of another thread. If the other thread’s action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They’re still blocking each other.

Typically, mutual exclusion achieved with a locking mechanism: prevent others from doing something. For example, before shopping, leave a note on the refrigerator: don’t shop if there is a note. We can lock an object that can only be owned by a single thread at any given time. Basic operations on a lock:

• Acquire: mark the lock as owned by the current thread; if some other thread already owns the lock then first wait until the lock is free. Lock typically includes a queue to keep track of multiple waiting threads.
• Release: mark the lock as free (it must currently be owned by the calling thread).

Synchronization mechanisms need more than just mutual exclusion; also need a way to wait for another thread to do something (e.g., wait for a character to be added to the buffer). We can achieve this by using Condition variables.

Condition variables are used to wait for a particular condition to become true (e.g. characters in buffer).

• _wait(condition, lock): release lock, put thread to sleep until condition is signaled; when thread wakes up again, re-acquire lock before returning.
• signal(condition, lock): if any threads are waiting on condition, wake up one of them. Caller must hold lock, which must be the same as the lock used in the wait call.
• broadcast(condition, lock): same as signal, except wake up all waiting threads.

Note: after signal, signaling thread keeps lock, waking thread goes on the queue waiting for the lock.
Warning: when a thread wakes up after condition_wait there is no guarantee that the desired condition still exists: another thread might have snuck in.

When locks and condition variables are used together like this, the result is called aMonitor. Monitor is a collection of procedures manipulating a shared data structure.

• One lock that must be held whenever accessing the shared data (typically each procedure acquires the lock at the very beginning and releases the lock before returning).
• One or more condition variables used for waiting.

Semaphore vs Mutex

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.

Formally, 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.

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.

Formally, 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).

Implement Locks
Uniprocessor solution –

• Acquire Lock : disable interrupts.
• put thread to sleep if lock not available:
• Hardware provides some sort of atomic read-modify-write instruction, which can be used to build higher-level synchronization operations such as locks. For example, aswap: atomically read memory value and replace it with a given value: returns old value.

struct lock {
    int locked;
    struct queue q;
    int sync;         /* Normally 0. */
};

void lock_acquire(struct lock *l) {
    Disable interrupts;
    while (aswap(&l->sync, 1) {
        /* Do nothing */
    }
    if (!l->locked) {
        l->locked = 1;
        l->sync = 0;
    } else {
        queue_add(&l->q, thread_current());
        l->sync = 0;
        thread_block();
    }
    Enable interrupts;
}

void lock_release(struct lock *l) {
    Disable interrupts;
    while (aswap(&l->sync, 1) {
        /* Do nothing */
    }
    if (queue_empty(&l->q) {
        l->locked = 0;
    } else {
        thread_unblock(queue_remove(&l->q));
    }
    l->sync = 0;
    Enable interrupts;
}

Threads and Concurrency in Java
In the Java virtual machine, every object and class is logically associated with a monitor. To implement the mutual exclusion capability of monitors, a lock (sometimes called a mutex) is associated with each object and class. This is called a semaphore.

If one thread owns a lock on some data, then no others can obtain that lock until the thread that owns the lock releases it. It would be not convenient if we need to write a semaphore all the time when we do multi-threading programming. Luckily, we don’t need to since JVM does that for us automatically.

To claim a monitor region which means data not accessible by more than one thread, Java provide synchronized statements and synchronized methods. Once the code is embedded with synchronized keyword, it is a monitor region. The locks are implemented in the background automatically by JVM.

Each object/class is associated with a Monitor. To enable collaboration of different threads, Java provide wait() and notify() to suspend a thread and to wake up another thread that are waiting on the object respectively. These methods can only be invoked within a synchronized statement or synchronized method. The reason is that if a method does not require mutual exclusion, there is no need to monitor or collaborate between threads, every thread can access that method freely.

The synchronized keyword in Java ensures:

• that only a single thread can execute a block of code at the same time
• that each thread entering a synchronized block of code sees the effects of all previous modifications that were guarded by the same lock

Synchronization is necessary for mutually exclusive access to blocks of and for reliable communication between threads.

We can use the synchronized keyword for the definition of a method. This would ensure that only one thread can enter this method at the same time. Another threads which is calling this method would wait until the first threads leaves this method.

public synchronized void method() {
  //critical codes
} 

We can also use the synchronized keyword to protect blocks of code within a method. This block is guarded by a key, which can be either a string or an object. This key is called the lock. All code which is protected by the same lock can only be executed by one thread at the same time

public void method() {
  //un-critical codes

   synchronized (this) {
     //wait for resource
     //critical codes
   }
   //notify all

   //un-critical codes
} 

notify() vs notifyAll()

• wait() tells the calling thread to give up the monitor and go to sleep until some other thread enters the same monitor and calls notify( ).
• notify() wakes up the first thread that called wait() on the same object.

In some cases, all waiting threads can take useful action once the wait finishes. An example would be a set of threads waiting for a certain task to finish; once the task has finished, all waiting threads can continue with their business. In such a case you would use notifyAll() to wake up all waiting threads at the same time.

Another case, for example mutually exclusive locking, only one of the waiting threads can do something useful after being notified (in this case acquire the lock). In such a case, you would rather use notify(). Properly implemented, you could use notifyAll() in this situation as well, but you would unnecessarily wake threads that can’t do anything anyway.

Thread vs Runnable
There are two way to create threads in Java – implementing a Runnable interface or by extending Thread class.

1. Provide a Runnable object. The Runnable interface defines a single method, run, meant to contain the code executed in the thread. The Runnable object is passed to the Thread constructor, as in the HelloRunnable example:

public class HelloRunnable implements Runnable {

    public void run() {
        System.out.println("Hello from a thread!");
    }

    public static void main(String args[]) {
        (new Thread(new HelloRunnable())).start();
    }

}

2. Subclass Thread. The Thread class itself implements Runnable, though its run method does nothing. An application can subclass Thread, providing its own implementation of run, as in the HelloThread example:

public class HelloThread extends Thread {

    public void run() {
        System.out.println("Hello from a thread!");
    }

    public static void main(String args[]) {
        (new HelloThread()).start();
    }

}

Which one to use when?

• Java doesn’t support multiple inheritance, which means we can only extend one class in Java. So if we extended Thread class then we can’t extend or inherit another class. So in situations where a child class in a hierarchy needs to be run as thread then we need to implement Runnable interface.
• If we are not making any modification on Thread than use Runnable interface instead.
• Runnable interface represent a Task which can be executed by either plain Thread or Executors or any other means. so logical separation of Task as Runnable than Thread is good design decision.
• Separating task as Runnable means we can reuse the task and also has liberty to execute it from different means. since you can not restart a Thread once it completes. again Runnable vs Thread for task, Runnable is winner.
• Java designer recognizes this and that’s why Executors accept Runnable as Task and they have worker thread which executes those task.
• Inheriting all Thread methods are additional overhead just for representing a Task which can can be done easily with Runnable.

Interrupts and Join

An interrupt is an indication to a thread that it should stop what it is doing and do something else. It’s up to the programmer to decide exactly how a thread responds to an interrupt, but it is very common for the thread to terminate. This is the usage emphasized in this lesson.

A thread sends an interrupt by invoking interrupt on the Thread object for the thread to be interrupted. For the interrupt mechanism to work correctly, the interrupted thread must support its own interruption. In java we can catch InterruptedException to catch the interrupt –

for (int i = 0; i < importantInfo.length; i++) {
    // Pause for 4 seconds
    try {
        Thread.sleep(4000);
    } catch (InterruptedException e) {
        // We've been interrupted: no more messages.
        return;
    }
    // Print a message
    System.out.println(importantInfo[i]);
}

Many methods that throw InterruptedException, such as sleep, are designed to cancel their current operation and return immediately when an interrupt is received.

What if a thread goes a long time without invoking a method that throws InterruptedException? Then it must periodically invoke Thread.interrupted, which returns true if an interrupt has been received.

for (int i = 0; i < inputs.length; i++) {
    heavyCrunch(inputs[i]);
    if (Thread.interrupted()) {
        // We've been interrupted: no more crunching.
        throw new InterruptedException();
    }
}

The interrupt mechanism is implemented using an internal flag known as the interrupt status. Invoking Thread.interrupt sets this flag. When a thread checks for an interrupt by invoking the static method Thread.interrupted, interrupt status is cleared. The non-static isInterrupted method, which is used by one thread to query the interrupt status of another, does not change the interrupt status flag.

By convention, any method that exits by throwing an InterruptedException clears interrupt status when it does so. However, it's always possible that interrupt status will immediately be set again, by another thread invoking interrupt.

The join method allows one thread to wait for the completion of another. If t is a Thread object whose thread is currently executing,

t.join();

causes the current thread to pause execution until t's thread terminates. Overloads of join allow the programmer to specify a waiting period. However, as with sleep, join is dependent on the OS for timing, so you should not assume that join will wait exactly as long as you specify.

Like sleep, join responds to an interrupt by exiting with an InterruptedException.

Volatile and Immutable

If a variable is declared with the volatile keyword then it is guaranteed that any thread that reads the field will see the most recently written value. The volatile keyword will not perform any mutual exclusive lock on the variable.

Another simplest way to avoid problems with concurrency is to share only immutabledata between threads. Immutable data is data which cannot changed. In order to make a class immutable we need to design the class such that -

• all its fields are final
• the class is declared as final
• this reference is not allowed to be used during construction
• any fields which refer to mutable data objects are private
• it doesn't have no setter method
• they are never directly returned of otherwise exposed to a caller
• if they are changed internally in the class this change is not visible and has no effect outside of the class

An immutable class may have some mutable data which is uses to manages its state but from the outside this class nor any attribute of this class can get changed.

For all mutable fields, e.g. Arrays, that are passed from the outside to the class during the construction phase, the class needs to make a defensive-copy of the elements to make sure that no other object from the outside still can change the data.

https://dzone.com/articles/performance-impact-io
影响IO密集型应用性能的因素

In a typical scenario, when data is written to a file, it is first written to a memory area reserved as the page cache. The page holding the newly written data is considered dirty. After a period of time per the kernel IO policy, the kernel flushes the dirty data to the device queue to persist to hard disk. Once the data gets to the queue, the rest is mechanical: The device driver reads the IO requests, then spins, seeks and writes to the physical disk block where the file is. The journal file is written first if enabled, then the actual file.

In a recent discussion with a few other engineers, an idea of disabling file system journaling came up to improve disk write latency. While this is certainly true because it is one less disk operation per write, the actual time gained is negligible because the journal file is in the same block as the file to be written. The benefits of having the journal file to restore the disk from a crash far outweighs the little latency saved.

The scenario gets more complicated when the JVM’s garbage collector is in the middle of cleaning the heap and is caught in the kernel-busily-flushing moment. Some GC events are stop-the-world (STW) event that require all the application threads to pause in order to reach a safe state such that the objects can be moved around in the heap. If one of application threads is trying to write while the kernel is busy flushing, this thread will get stuck behind the flushing job and won’t be able to respond to the summon to pause. This would cause a ripple effect: The busy disk blocks the write thread, the thread prolonged the GC pause, and the pause makes the application appear non-responsive. This problem can be identified in the GC log when there is long STW pause with little CPU time spent in “usr” and “sys”, correlated with disk activity.

At the device configuration level, storing the frequently accessed files on different devices could also help to avoid the problem of a single congested device queue. Alternatively, if applicable, having multiple sets of RAID1 would yield more device queues, which is better than having a single volume with all the disks which only has one device queue.

If cost is not prohibitive, consider upgrading to SSD which has 6 to 7 times the bandwidth of the spinning disk. The caveats for SSD, however, is its occasional needs to do data compaction. The performance impact of data compaction could be bad.

always avoid unnecessary disk access.

http://www.geeksforgeeks.org/what-exactly-spooling-is-all-about/

SPOOL is an acronym for simultaneous peripheral operations on-line.  It is a kind of buffering mechanism or a process in which data is temporarily held to be used and executed by a device, program or the system. Data is sent to and stored in memory or other volatile storage until the program or computer requests it for execution.

Spooling works like a typical request queue where data, instructions and processes from multiple sources are accumulated for execution later on. Generally, it is maintained on computer’s physical memory, buffers or the I/O device-specific interrupts. The spool is processed in FIFO manner i.e. whatever first instruction is there in the queue will be popped and executed.

1) The most common can be found in I/O devices like keyboard printers and mouse. For example, In printer, the documents/files that are sent to the printer are first stored in the memory or the printer spooler. Once the printer is ready, it fetches the data from the spool and prints it.

Even experienced a situation when suddenly for some seconds your mouse or keyboard stops working? Meanwhile, we usually click again and again here and there on the screen to check if its working or not. When it actually starts working, what and wherever we pressed during its hang state gets executed very fast because all the instructions got stored in the respective device’s spool.

2) A batch processing system uses spooling to maintain a queue of ready-to-run jobs which can be started as soon as the system has the resources to process them.

3) Spooling is capable of overlapping I/O operation for one job with processor operations for another job. i.e. multiple processes can write documents to a print queue without waiting and resume with their work.

4) E-mail: an email is delivered by a MTA (Mail Transfer Agent) to a temporary storage area where it waits to be picked up by the MA (Mail User Agent)

http://www.geeksforgeeks.org/sleep-mode-vs-hibernate-mode-computer/

Sleep

• RAM status: When the computer is turned into sleep mode, it saves the current context in the RAM and it makes sure that the RAM is on. So it consumes less power to keep the RAM powered on. It takes less time (two seconds) to on the system by simply pressing power button and we return to the unsaved work.
• Time Duration: Sleep mode is useful if you want to stop working for a short period of time.

Hibernate

• RAM status: Hibernate is similar to shutting down the computer. It saves the context in the hard drive and as soon as the computer is on, it loads the data from hard drive to the RAM and so it takes more time than sleep but less than the time taken to on the computer when it was shutdown. It do not consume any power because there is no need to power on the RAM.
• Time duration: Prefer using this mode if you won’t be using your system for an extended period of time. The settings can be changed in the system, such that the system turns into Hibernate mode or sleep mode when the power button is pressed.