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.
Real-life example of starvation is in the staircase, when two people meet at the opposing side. The staircase can 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 Deadlock:
The 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 succeedsbreak; // leave the loopelse {s.release(0,1); // release what is heldsleep( 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 secondB s.tryAcquire(1,0) => falseB 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: Memory Management in Linux
To highlight the concets presented in this chapter, we end with a more specific example of how memory managed in the Linux operating system. Although Linux memory management has many features in common with UNIX, it has some unique characteristics, and it is quite complex.
Virtual Memory in Linux managed using a three-level table hierarchy, which acoomodates both 64- and 32-bit architectures. For the example show in Figure 3.18, each virtual address is made up of four filds, which are used by the Memory Manager to locate the instruction or data requested:
Main Directory Middle Directory Page Table Directory Actual Page Offset
Figure 3.18 refers to the following virtual address:
Job: 1 Page Table: 3 Page: 2 Line:214
Each job has its own entry in the main directory, which has pointers to each job's middle director. A job's middle directory contains pointers to its corresponding page table directories. In turn, each page table directory has pointers to the actual pages, as shown in Figure 3.18. Finally, the page offset field is used to locate the instruction or data within the requested page (Line 214).
Consider the case where main memory consists of 64 page frames and Job 1 resists 15 page frames. The buddy algorithm first rounds up the request to a power of 2 ( in this case 2 to the 4, which is 16). The group of 64 page frames is divided into two page frames that can satisfy the request, so the job's pages are copied into the page frames as shown in Figure 3.19(a). When job 2 requests 8 page frames, the second page up to 16 page frames is divided in two and the lower half is given to Job 2, as show in Figure 3.19 (b).
When Job 2 releases its page frames they are combined with the upper 8 page frames form a group of 16 page frames, as shown in Figure 3.19(c).
The Page replacement algorithm used by the Linux is an expanded version of the clock algorithm presented in the page replacement policies section of this chapter. Instead of using a single reference bit, Linux uses an 8-bit byte to keep track of a page's activity, which is referred to as its age. Each time a page is referenced, this age variable is incremented. Behind the scenes, at specific intervals, the Memory Manager checks each of use age variables and decreases their value by one. The result of this interaction is it, if a page is not referenced frequently, then its age variable will drop to zero and will be a good candidate for replacement if a page swap is necessary. On the other hand, a page that is frequently used will have a large age value and will not be a good choice for replacement. Therefore, we can say that Linux uses a form of least frequently used (LRU) replacement policy.
Wednesday, November 21, 2007
Two reasons why a regional bank might decide to buy six server computers instead of one supercomputer:
- they have at least backups for their important files whenever the other computers commits error or acquires damages.
- they have at least 3 or 4 computers running whenever 2 or 3 computers have their maintenance.
Microsoft confirms that XP contains random number generator bug
A fix is coming next year in SP3; Vista, Server 2003 and Server 2008 immune
November 21, 2007 (Computerworld) -- Windows XP, Microsoft Corp.'s most popular operating system, sports the same encryption flaws that Israeli researchers recently disclosed in Windows 2000, Microsoft officials confirmed late Tuesday.
The researchers, Benny Pinkas from the University of Haifa and two Hebrew University graduate students, Zvi Gutterman and Leo Dorrendorf, reverse-engineered the algorithm used by Windows 2000's pseudo-random number generator (PRNG), then used that knowledge to pick apart the operating system's encryption. Attackers could exploit a weakness in the PRNG, said Pinkas and his colleagues, to predict encryption keys that would be created in the future as well as reveal the keys that had been generated in the past.
As recently as last Friday, Microsoft hedged in answering questions about whether XP and Vista could be attacked in the same way, saying only that later versions of Windows "contain various changes and enhancements to the random number generator." Yesterday, however, Microsoft responded to further questions and acknowledged that Windows XP is vulnerable to the complex attack that Pinkas, Gutterman and Dorrendorf laid out in their paper, which was published earlier this month.
Windows Vista, Windows Server 2003 and the not-yet-released Windows Server 2008, however, apparently use a modified or different random number generator; Microsoft said they were immune to the attack strategy.
In addition, Microsoft said Windows XP Service Pack 3 (SP3), a major update expected sometime in the first half of 2008, includes fixes that address the random number generator problem.
Microsoft and Pinkas have argued over whether the flaw was a security vulnerability, with the former denying the bug met the definition and the latter claiming it is a serious problem that -- while it needs to piggyback on another, more common kind of exploit -- is far from just a theoretical threat.
Tuesday, even as it conceded that XP also had a weak PRNG, Microsoft continued to downplay the possibility of an attack. "If an attacker has already compromised a victim machine, a theoretical attack could occur on Windows XP," a company spokeswoman said in an e-mail. To exploit the PRNG's flaws, an attacker must have administrative rights to the PC, something that's easily obtained by most run-of-the-mill attacks, Pinkas noted.
Previously, Microsoft had used that prerequisite to reject any claim that Windows 2000 contained the security vulnerability, since Pinkas' proposed attack could not accomplish anything on its own. Microsoft stuck to that position with XP. "Because administrator rights are required for the attack to be successful, and by design, administrators can access all files and resources on a system, this is not inappropriate disclosure of information," the company spokeswoman added.
Newer operating systems, however, are completely in the clear. "Windows Vista, Windows Server 2008 and Windows Server 2003 SP2 are not affected by the type of attack Pinkas describes," said the spokeswoman.
Pinkas applauded Microsoft's decision to patch Windows XP. "We're happy to learn that Microsoft is acknowledging that our attack is indeed an issue, and will fix it in XP SP3."
While Microsoft said it will fix the PRNG in Windows XP, it remained mute about patching the flaw in Windows 2000. The aging operating system, which, according to a recent survey by Forrester Research Inc., still powers approximately 9% of all American and European business computers, is in the last stages of support. In that phase, dubbed "extended support," Microsoft is committed to providing only security updates free of charge.
Because the company has determined that the PRNG problem is not a security vulnerability, it is unlikely to provide a patch.
Source: http://www.computerworld.com/
November 21, 2007 (Computerworld) -- Windows XP, Microsoft Corp.'s most popular operating system, sports the same encryption flaws that Israeli researchers recently disclosed in Windows 2000, Microsoft officials confirmed late Tuesday.
The researchers, Benny Pinkas from the University of Haifa and two Hebrew University graduate students, Zvi Gutterman and Leo Dorrendorf, reverse-engineered the algorithm used by Windows 2000's pseudo-random number generator (PRNG), then used that knowledge to pick apart the operating system's encryption. Attackers could exploit a weakness in the PRNG, said Pinkas and his colleagues, to predict encryption keys that would be created in the future as well as reveal the keys that had been generated in the past.
As recently as last Friday, Microsoft hedged in answering questions about whether XP and Vista could be attacked in the same way, saying only that later versions of Windows "contain various changes and enhancements to the random number generator." Yesterday, however, Microsoft responded to further questions and acknowledged that Windows XP is vulnerable to the complex attack that Pinkas, Gutterman and Dorrendorf laid out in their paper, which was published earlier this month.
Windows Vista, Windows Server 2003 and the not-yet-released Windows Server 2008, however, apparently use a modified or different random number generator; Microsoft said they were immune to the attack strategy.
In addition, Microsoft said Windows XP Service Pack 3 (SP3), a major update expected sometime in the first half of 2008, includes fixes that address the random number generator problem.
Microsoft and Pinkas have argued over whether the flaw was a security vulnerability, with the former denying the bug met the definition and the latter claiming it is a serious problem that -- while it needs to piggyback on another, more common kind of exploit -- is far from just a theoretical threat.
Tuesday, even as it conceded that XP also had a weak PRNG, Microsoft continued to downplay the possibility of an attack. "If an attacker has already compromised a victim machine, a theoretical attack could occur on Windows XP," a company spokeswoman said in an e-mail. To exploit the PRNG's flaws, an attacker must have administrative rights to the PC, something that's easily obtained by most run-of-the-mill attacks, Pinkas noted.
Previously, Microsoft had used that prerequisite to reject any claim that Windows 2000 contained the security vulnerability, since Pinkas' proposed attack could not accomplish anything on its own. Microsoft stuck to that position with XP. "Because administrator rights are required for the attack to be successful, and by design, administrators can access all files and resources on a system, this is not inappropriate disclosure of information," the company spokeswoman added.
Newer operating systems, however, are completely in the clear. "Windows Vista, Windows Server 2008 and Windows Server 2003 SP2 are not affected by the type of attack Pinkas describes," said the spokeswoman.
Pinkas applauded Microsoft's decision to patch Windows XP. "We're happy to learn that Microsoft is acknowledging that our attack is indeed an issue, and will fix it in XP SP3."
While Microsoft said it will fix the PRNG in Windows XP, it remained mute about patching the flaw in Windows 2000. The aging operating system, which, according to a recent survey by Forrester Research Inc., still powers approximately 9% of all American and European business computers, is in the last stages of support. In that phase, dubbed "extended support," Microsoft is committed to providing only security updates free of charge.
Because the company has determined that the PRNG problem is not a security vulnerability, it is unlikely to provide a patch.
Source: http://www.computerworld.com/
Subscribe to:
Posts (Atom)
