OS Miscs

OS Miscs

Critical section
A critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to enter it (aka bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
How critical sections are implemented varies among operating systems.
The simplest method is to prevent any change of processor control inside the critical section. On uni-processor systems, this can be done by disabling interrupts on entry into the critical section, avoiding system calls that can cause a context switch while inside the section and restoring interrupts to their previous state on exit. Any thread of execution entering any critical section anywhere in the system will, with this implementation, prevent any other thread, including an interrupt, from getting the CPU and therefore from entering any other critical section or, indeed, any code whatsoever, until the original thread leaves its critical section.
This brute-force approach can be improved upon by using semaphores. To enter a critical section, a thread must obtain a semaphore, which it releases on leaving the section. Other threads are prevented from entering the critical section at the same time as the original thread, but are free to gain control of the CPU and execute other code, including other critical sections that are protected by different semaphores.
Semaphore
A semaphore is a protected variable or abstract data type which constitutes the classic method for restricting access to shared resources such as shared memory in a parallel programming environment. A counting semaphore is a counter for a set of available resources, rather than a locked/unlocked flag of a single resource.
Semaphores can be either binary or counting, depending on the number of shared resources. If a single shared resource is used, then we would require just one semaphore for synchronization purposes. In that case, the semaphore is referred as a binary semaphore. In all other cases, where the number of resources shared across users are greater than one, you would use multiple semaphores, in which case they are referred as counting semaphores.
Semaphores basically implement two kinds of operations. One to wait on the semaphore variable and another that signals the semaphore variable. Since semaphores are nothing but a counter, the following algorithm depicts these two semaphore operations:
Assume :
s is the semaphore variable
W(s) denotes waiting on the semaphore
P(s) means signaling the availability of semaphore
The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (uses its turn to do nothing) or maybe sleeps (tells the system not to give it a turn) until a resource is available, whereupon it immediately claims one. The V operation is the inverse; it simply makes a resource available again after the process has finished using it. The P and V operations must be atomic.
In software engineering practice, they are often called wait and signal, or acquire and release.
Binary semaphore vs. Mutex
A mutex is a binary semaphore (a semaphore with capacity of 1), usually including extra features like ownership, priority inversion protection or recursivity. The differences between mutexes and semaphores are operating system dependent, though mutexes are implemented by specialized and faster routines. Mutexes are meant to be used for mutual exclusion (post/release operation is restricted to thread which called pend/acquire) only and binary semaphores are meant to be used for event notification (post-ability from any thread) and mutual exclusion.
Monitor (synchronization)
Monitor is an object intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods.
Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task. Monitors also have a mechanism for signaling other threads that such conditions have been met.
Inter-process communication
Inter-process communication (IPC) is a set of techniques for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC techniques are divided into methods for message passing, synchronization, shared memory, and remote procedure calls (RPC).
Main IPC Methods
File, Signal, Socket, Message queue, Pipe, Named pipe, Semaphore, Shared memory, Message passing, memory-mapped file.
Anonymous pipe
An anonymous pipe is a simplex FIFO communication channel that may be used for one-way interprocess communication.
Typically a parent program opens anonymous pipes, and creates a new process that inherits the other ends of the pipes, or creates several new processes and arranges them in a pipeline.
Two anonymous pipes are required for full-duplex (two-way) communication.
In a Unix shell a pipeline is created using the "|" character and many Unix programs are designed as filters to work with pipes.
Named pipe
A traditional pipe is "unnamed" because it exists anonymously and persists only for as long as the process is running. A named pipe is system-persistent and exists beyond the life of the process and must be deleted once it is no longer being used. Processes generally attach to the named pipe (usually appearing as a file) to perform inter-process communication (IPC).
Instead of a conventional, unnamed, shell pipeline, a named pipeline is explicitly created using mkfifo() or mknod(), and two separate processes can access the pipe by name.
mkfifo my_pipe
gzip -9 -c < my_pipe > out.gz
cat file > my_pipe
rm my_pipe
Pipeline (Unix)
In Unix-like computer operating systems, a pipeline is the original software pipeline: a set of processes chained by their standard streams, so that the output of each process (stdout) feeds directly as input (stdin) to the next one. Each connection is implemented by an anonymous pipe. Filter programs are often used in this configuration.
Shared memory
Shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors.
Since both processes can access the shared memory area like regular working memory, this is a very fast way of communication (as opposed to other mechanisms of IPC such as named pipes, Unix domain sockets or CORBA). On the other hand, it is less powerful, as for example the communicating processes must be running on the same machine (whereas other IPC methods can use a computer network), and care must be taken to avoid issues if processes sharing memory are running on separate CPUs and the underlying architecture is not cache coherent.
Message queue
Message queues and mailboxes are software-engineering components used for interprocess communication, or for inter-thread communication within the same process. They use a queue for messaging – the passing of control or of content.
Message queues provide an asynchronous communications protocol, meaning that the sender and receiver of the message do not need to interact with the message queue at the same time. Messages placed onto the queue are stored until the recipient retrieves them.
Most message queues have set limits on the size of data that can be transmitted in a single message. Those that do not have such limits are known as mailboxes.
There are a number of open source choices of messaging middleware systems, including Apache ActiveMQ, JBoss Messaging.
Paging
In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. The main advantage of paging is that it allows the physical address space of a process to be noncontiguous. Prior to paging, systems had to fit whole programs into storage contiguously which caused various storage and fragmentation problems.
Paging allowes to use disk storage for data that does not fit into physical Random-access memory (RAM)
The main functions of paging are performed when a program tries to access pages that are not currently mapped to physical memory (RAM). This situation is known as a page fault. The operating system must then take control and handle the page fault, in a manner invisible to the program. Therefore, the operating system must:
1. Determine the location of the data in auxiliary storage.
2. Obtain an empty page frame in RAM to use as a container for the data.
3. Load the requested data into the available page frame.
4. Update the page table to show the new data.
5. Return control to the program, transparently retrying the instruction that caused the page fault.
In reaction to a page fault, there are several strategies for guessing what pages might be needed, and speculatively pre-loading them: Demand paging, Anticipatory paging, Swap prefetch, Pre-cleaning.
Memory Segmentation
In a computer system using segmentation, an instruction operand that refers to a memory location includes a value that identifies a segment and an offset within that segment. A segment has a set of permissions, and a length, associated with it.
Segmentation with Paging
In this scheme, segmentations are broken into page, in this way, the user view is segmentation, but OS can implement with demand paging.
Virtual memory
Virtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory (an address space), while in fact it may be physically fragmented and may even overflow on to disk storage.
Virtual memory separates user logical memory from physical memory, it allows an extremely large virtual memory to be provided when only a small physical memory is available.
Page replacement algorithm
In a computer operating system that uses paging for virtual memory memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.
Page replacement algorithms includes: Not recently used(NRU), First-in, first-out(FIFO), Least recently used(LRU),Not frequently used(NFU), Aging
Not recently used
The not recently used (NRU) page replacement algorithm is an algorithm that favours keeping pages in memory that have been recently used.
Least recently used
LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory, it is rather expensive to implement in practice.
Not frequently used
The not frequently used (NFU) page replacement algorithm requires a counter, and every page has one counter of its own which is initially set to 0.
Aging
The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use.


Resources:
http://en.wikipedia.org/wiki/
Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (12) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts