Question

Optimal and near-optimal process scheduling and page replacement algorithms.

a) What is the theoretically best process scheduling algorithm?

b) Do shortest job first and shortest remaining time first amount to the same thing or not?

c) Can they be directly implemented?

d) What do you consider the next best scheduling option, and how does it use the recent past to approximate the ideal case?

e) Consider the analogous case in page replacement. What is the best possible choice of page to replace?

f) Can this be known? If not, what is the best approximation of the ideal case, and how does it use knowledge of the recent past to implement it?

g) What is the overhead involved in keeping track of the recent past in the case of page replacement?

Answer 1

near-optimal process scheduling and page replacement algorithm is the theoretically best process scheduling page replacement algorithm

SJF and STRF are same onlt the diffrence is the terms used in non preemtive (SJF) kernel & preemtive (SRTF) kernel

Optimal process scheduling page replacement algorithm is difficult / cannot be implemented as it is very difficult to find out the time when the page is used next time. Also this is possible only when run time analysis of applications is known OR the software running on the system is priory known.

But near-optimal process scheduling page replacement algorithm can be used which can provide nearly optimal performance. In this algorithm OS keeps record of all page references. & OS uses this data to decide which pages to be replaced subsequently.

Ideal example for page replacement in optimal page replacement:

1. If required page is already present, then increment count.
2. If not present, find a page that is never referenced will be referred later in future. If such a page exists, replace this page with new page. If no such page exists, find a page that is referenced farthest in future. Replace this page with new page.