1.A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
A Starvation is similar in effect to deadlock. Two or more programs become deadlocked together, when each of them wait for a resource occupied by another program in the same set. On the other hand, one or more programs are in starvation, when each of them is waiting for resources that are occupied by programs, that may or may not be in the same set that are starving. Moreover, in a deadlock, no program in the set changes its state.
A race is a synchronozation problem between two processes vying for the same resources.
2. Real-life example of deadlock is the traffic jam.
Real-life example of starvation is when two people meet at one-way. The one-way can only be accomodated by one person.
Real-life example of Race is when two people arrived at the same time on the same door.
3. Four Necessary Conditions for DeadlockThe presence of deadlock in a systems is characterized by these four necessary conditions. The term necessary means that if there is deadlock then all four must be present.
a. Mutual exclusive resource access - A resource acquired is held exclusively, i.e., it is not shared by other processes.
b. No preemption - A process' resources cannot be taken away from it. Only the process can give up its resources.
c. Hold and Wait - A process has some resources and is blocked requesting more.
d. Circularity - This means that there is a circular chain of two or more processes in which the resources needed by one process are held by the next process.
4. Algorithm for prevention of deadlock and starvation:
public boolean tryAcquire( int n0, int n1, ... ) { if ( for all i: ni ≤ availi ) { // successful acquisition availi -= ni for all i; return true; // indicate success } else return false; // indicate failure}
init) Semaphore s = new Semaphore(1,1);
Thread A Thread B
-------- --------
s.acquire(1,0); s.acquire(0,1);
s.acquire(0,1); s.acquire(1,0);
Thread B
--------
while(true) {
s.acquire(0,1);
if ( s.tryAcquire(1,0) ) // if second acquisition succeeds
break; // leave the loop
else {
s.release(0,1); // release what is held
sleep( SOME_AMOUNT); // pause a bit before trying again
}
}
run action s.value
--- ------ -------
(1,1)
A s.acquire(1,0) (0,1)
B s.acquire(0,1) (0,0)
A s.acquire(0,1) A blocks on second
B s.tryAcquire(1,0) => false
B s.release(0,1) (0,1)
A s.acquire(0,1) (0,0) A succeeds on second
5.
a. Deadlock can be occurred. When the bridge is destroyed.
b. When there are no traffic lights.
c. To prevent deadlock make all the road to be one-way.
6.
a. This is not a deadlocked.
b. There is no blocked processes.
c. P2 can freely request on R1 and R2.
d. P1 can freely request on R1 and R2.
e. Both P1 and P2 have requested R2.
1. P1 will wait after the request of P2.
2. P2 will wait after the request of P1.
Tuesday, January 15, 2008
Thursday, December 13, 2007
Case Study: Linux Memory Management
Linux Memory Management Overview
[Note: This overview of Linux's Memory Management is several years old. Linux's MM has gone through a nearly complete rewrite since this was written. However, if you can't understand the Linux MM code, reading this and understanding that this documents the predecessor to the current MM code may help you out.]
The Linux memory manager implements demand paging with a copy-on-write strategy relying on the 386's paging support. A process acquires its page tables from its parent (during a fork()) with the entries marked as read-only or swapped. Then, if the process tries to write to that memory space, and the page is a copy-on-write page, it is copied, and the page is marked read-write. An exec() results in the reading in of a page or so from the executable. The process then faults in any other pages it needs.
Each process has a page directory which means it can access 1 KB of page tables pointing to 1 MB of 4 KB pages which is 4 GB of memory. A process' page directory is initialized during a fork by copy_page_tables(). The idle process has its page directory initialized during the initialization sequence.
Each user process has a local descriptor table that contains a code segment and data-stack segment. These user segments extend from 0 to 3 GB (0xc0000000). In user space, linear addresses and logical addresses are identical.
On the 80386, linear address run from 0GB to 4GB. A linear address points to a particular memory location within this space. A linear address is not a physical address--it is a virtual address. A logical address consists of a selector and an offset. The selector points to a segment and the offset tells how far into that segment the address is located)
The kernel code and data segments are priveleged segments defined in the global descriptor table and extend from 3 GB to 4 GB. The swapper page directory (swapper_page_dir is set up so that logical addresses and physical addresses are identical in kernel space.
The space above 3 GB appears in a process' page directory as pointers to kernel page tables. This space is invisible to the process in user mode but the mapping becomes relevant when privileged mode is entered, for example, to handle a system call. Supervisor mode is entered within the context of the current process so address translation occurs with respect to the process' page directory but using kernel segments. This is identically the mapping produced by using the swapper_pg_dir and kernel segments as both page directories use the same page tables in this space. Only task[0] (the idle task, sometimes called the swapper task for historical reasons, even though it has nothing to do with swapping in the Linux implementation) uses the swapper_pg_dir directly.
The user process' segment_base = 0x00, page_dir private to the process.
user process makes a system call: segment_base=0xc0000000 page_dir = same user page_dir.
swapper_pg_dir contains a mapping for all physical pages from 0xc0000000 to 0xc0000000 + end_mem, so the first 768 entries in swapper_pg_dir are 0's, and then there are 4 or more that point to kernel page tables.
The user page directories have the same entries as swapper_pg_dir above 768. The first 768 entries map the user space.
The upshot is that whenever the linear address is above 0xc0000000 everything uses the same kernel page tables.
The user stack sits at the top of the user data segment and grows down. The kernel stack is not a pretty data structure or segment that I can point to with a ``yon lies the kernel stack.'' A kernel_stack_frame (a page) is associated with each newly created process and is used whenever the kernel operates within the context of that process. Bad things would happen if the kernel stack were to grow below its current stack frame. [Where is the kernel stack put? I know that there is one for every process, but where is it stored when it's not being used?]
User pages can be stolen or swapped. A user page is one that is mapped below 3 GB in a user page table. This region does not contain page directories or page tables. Only dirty pages are swapped.
Minor alterations are needed in some places (tests for process memory limits comes to mind) to provide support for programmer defined segments.
[Note: This overview of Linux's Memory Management is several years old. Linux's MM has gone through a nearly complete rewrite since this was written. However, if you can't understand the Linux MM code, reading this and understanding that this documents the predecessor to the current MM code may help you out.]
The Linux memory manager implements demand paging with a copy-on-write strategy relying on the 386's paging support. A process acquires its page tables from its parent (during a fork()) with the entries marked as read-only or swapped. Then, if the process tries to write to that memory space, and the page is a copy-on-write page, it is copied, and the page is marked read-write. An exec() results in the reading in of a page or so from the executable. The process then faults in any other pages it needs.
Each process has a page directory which means it can access 1 KB of page tables pointing to 1 MB of 4 KB pages which is 4 GB of memory. A process' page directory is initialized during a fork by copy_page_tables(). The idle process has its page directory initialized during the initialization sequence.
Each user process has a local descriptor table that contains a code segment and data-stack segment. These user segments extend from 0 to 3 GB (0xc0000000). In user space, linear addresses and logical addresses are identical.
On the 80386, linear address run from 0GB to 4GB. A linear address points to a particular memory location within this space. A linear address is not a physical address--it is a virtual address. A logical address consists of a selector and an offset. The selector points to a segment and the offset tells how far into that segment the address is located)
The kernel code and data segments are priveleged segments defined in the global descriptor table and extend from 3 GB to 4 GB. The swapper page directory (swapper_page_dir is set up so that logical addresses and physical addresses are identical in kernel space.
The space above 3 GB appears in a process' page directory as pointers to kernel page tables. This space is invisible to the process in user mode but the mapping becomes relevant when privileged mode is entered, for example, to handle a system call. Supervisor mode is entered within the context of the current process so address translation occurs with respect to the process' page directory but using kernel segments. This is identically the mapping produced by using the swapper_pg_dir and kernel segments as both page directories use the same page tables in this space. Only task[0] (the idle task, sometimes called the swapper task for historical reasons, even though it has nothing to do with swapping in the Linux implementation) uses the swapper_pg_dir directly.
The user process' segment_base = 0x00, page_dir private to the process.
user process makes a system call: segment_base=0xc0000000 page_dir = same user page_dir.
swapper_pg_dir contains a mapping for all physical pages from 0xc0000000 to 0xc0000000 + end_mem, so the first 768 entries in swapper_pg_dir are 0's, and then there are 4 or more that point to kernel page tables.
The user page directories have the same entries as swapper_pg_dir above 768. The first 768 entries map the user space.
The upshot is that whenever the linear address is above 0xc0000000 everything uses the same kernel page tables.
The user stack sits at the top of the user data segment and grows down. The kernel stack is not a pretty data structure or segment that I can point to with a ``yon lies the kernel stack.'' A kernel_stack_frame (a page) is associated with each newly created process and is used whenever the kernel operates within the context of that process. Bad things would happen if the kernel stack were to grow below its current stack frame. [Where is the kernel stack put? I know that there is one for every process, but where is it stored when it's not being used?]
User pages can be stolen or swapped. A user page is one that is mapped below 3 GB in a user page table. This region does not contain page directories or page tables. Only dirty pages are swapped.
Minor alterations are needed in some places (tests for process memory limits comes to mind) to provide support for programmer defined segments.
Thursday, November 22, 2007
Two Reasons Why Regional Bank decided to buy six server computers instead of one supercomputer:
- it can save investments with the six server computers.
- it can backup for their important files from the other computers while other computers needs maintenance.
Operating System News
The Most Popular Operating System in the World
What is the world's most widely used operating system? It's not Windows, Unix or Linux, but ITRON, a Japanese real-time kernel for small-scale embedded systems. ITRON runs on mobile phones, digital cameras, CD players and countless other electronic devices.
ITRON emerged as an ambitious Japanese initiative known as The Real-time Operating system Nucleus (TRON). Launched in 1984, TRON was designed to replace disparate computer systems with a unified, open architecture for a "total computer environment."
Its ultimate goal was to create "highly functionally distributed systems" in which all system components are connected to a real-time network . Professor Ken Sakamura, spiritual father of TRON, conceived the project as a social infrastructure akin to the electrical power grid or water supply system.
Now, the T-Engine Forum, an offshoot of the TRON project with more than 250 member companies, has been working to create a standardized development environment for embedded applications based on ITRON. Vendors of proprietary solutions are worried -- or at least should be.
//-->
//-->
ITRON Is First
ITRON, the first in a series of open-source specifications for the TRON architecture, answered a pressing need for Japan's electronics firms, which traditionally have written their own software for embedded systems, a time-consuming and cumbersome process that often results in a plethora of different and incompatible systems.
The ITRON specification is a standard real-time OS kernel that can be tailored to any embedded system. ITRON already has been ported to a wide range of microprocessor architectures and has quickly become Japan's de facto standard for embedded systems. Today, the specification is used in an estimated 3 billion microprocessors.
ITRON has been followed by several other specifications -- among them Business TRON (BTRON), a multilingual, ubiquitous computing environment with a programmable GUI, and Communications and Central TRON (CTRON), a real-time, multitasking operating system akin to Unix.
Japanese telecom giant NTT has embraced CTRON and made it the de facto standard in Japan's telecom industry.
Source: http://www.linuxinsider.com/
What is the world's most widely used operating system? It's not Windows, Unix or Linux, but ITRON, a Japanese real-time kernel for small-scale embedded systems. ITRON runs on mobile phones, digital cameras, CD players and countless other electronic devices.
ITRON emerged as an ambitious Japanese initiative known as The Real-time Operating system Nucleus (TRON). Launched in 1984, TRON was designed to replace disparate computer systems with a unified, open architecture for a "total computer environment."
Its ultimate goal was to create "highly functionally distributed systems" in which all system components are connected to a real-time network . Professor Ken Sakamura, spiritual father of TRON, conceived the project as a social infrastructure akin to the electrical power grid or water supply system.
Now, the T-Engine Forum, an offshoot of the TRON project with more than 250 member companies, has been working to create a standardized development environment for embedded applications based on ITRON. Vendors of proprietary solutions are worried -- or at least should be.
//-->
//-->
ITRON Is First
ITRON, the first in a series of open-source specifications for the TRON architecture, answered a pressing need for Japan's electronics firms, which traditionally have written their own software for embedded systems, a time-consuming and cumbersome process that often results in a plethora of different and incompatible systems.
The ITRON specification is a standard real-time OS kernel that can be tailored to any embedded system. ITRON already has been ported to a wide range of microprocessor architectures and has quickly become Japan's de facto standard for embedded systems. Today, the specification is used in an estimated 3 billion microprocessors.
ITRON has been followed by several other specifications -- among them Business TRON (BTRON), a multilingual, ubiquitous computing environment with a programmable GUI, and Communications and Central TRON (CTRON), a real-time, multitasking operating system akin to Unix.
Japanese telecom giant NTT has embraced CTRON and made it the de facto standard in Japan's telecom industry.
Source: http://www.linuxinsider.com/
Subscribe to:
Posts (Atom)
