3. (8 marks) A computer\'s memory holds programs 1 through n, where each program

Question

3. (8 marks) A computer's memory holds programs 1 through n, where each program occupies consecutive memory locations and no two programs overlap. Program i begins at address ai for each 1?i ? n, and a ? ??? ?an. After a certain amount to time, some of the programs change their memory requirements, with the new length of the ith program being li. It might be necessary to shift some of the programs to satisfy the new memory requirements with no programs overlapping. Suppose that the programs must remain in the same order. Further, suppose that the starting addresses of programs 1 and n cannot be changed, and that programs 1 through n - 1 with their new memory requirements can fit into the space between al and an, that is, 11 +12+ . . . + In-l-an-aj Let R be a relation on {1,2,...,n} where: That is, (i,j) E R means that if programs i and j remain at their original starting addresses it is possible to shift programs i + 1 through j - 1 to satisfy the new memory requirements of programs i through j- 1. (a) Prove that R is a partial order relation. (b) Explain why the following statement is true by giving a few sentences of explanation. Do not give a formal proof. If C' is a chain of the partially ordered set {1,2,... ,n) with respect to R such that 1, n E C, then the new memory requirements can be satisfied with no programs overlapping by shifting n - [C| programs

Explanation / Answer

Solution:

(a) R is considered to be in anti-symmetric relationship if in all conditions i,j belongs to A, if iRj and jRi, then i=j. R is considered to be in partial order relationship if R lies in the between the reflexive, anti-symmetric and transitive relationship. Let R={(i,j)|j=2li},R={(i,j)|j=2ki}, referring to some non-negative integer l and is considered to be in binary relationship within the group of natural numbers n(sequence of consequitive memory allocation units). Thus it justified R is in partial order relationship.

(b) "C" is considered to be the part of partially order set "a" which contains consequitive memory allocation from {1,2...n} that is in relationship R such that the sets of new consequitive memory allocation from C can be allocated within set "a", if and only if the number of consequitive memory allocation within "a" becomes available by shifiting n-mod c number of programs towards right without overlapping the memory locations of other programs in "a'. "C" is a subset of the partially order set "a" if the number elements in "C" is part of set "a" and both are considered to be in partial relationship with the relation R. Thus, this statement is considered to be true.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.