1
$\begingroup$

I am doing research on paging algorithms. While learning about the working set algorithm from several scientific sources I was not really able to figure out where exactly the working set is defined or realized.

I can only imagine two ways of realising this. The first is to put it into the page table file with indication bits; the second is to have another page table for the working set.

To be more specific: is the Working Set a completely different, separate list derived from the page table entries, or is it defined in the page table entries?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are you asking about the definition of a working set itself? Can you provide a quote or two from these scientific sources to clarify the question? $\endgroup$
    – Hadi Brais
    May 14 '18 at 1:19
  • $\begingroup$ The sources are: [Peter J. Denning - The Working Set Model for Program Behavior (1968)] (denninginstitute.com/pjd/PUBS/WSModel_1968.pdf) and Andrew S. Tanenbaum - Modern Operating Systems (any edition is fine to use) $\endgroup$
    – Thomas Christopher Davies
    May 14 '18 at 9:08
1
$\begingroup$

Denning provides a rough definition for a working set in Section 2:

Roughly speaking, a working set of pages is the minimum collection of pages that must be loaded in main memory for a process to operate efficiently, without "unnecessary" page faults.

And provides the precise definition in Section 3:

We define the working set of information W(t, r) of a process at time t to be the collection of information referenced by the process during the process time interval (t - r, t).

Thus, the information a process has referenced during the last r seconds of its execution constitutes its working set (Figure 2).

The term "page" in these definitions refers to physical pages, not virtual pages. That's because only those physical pages that have resided in main memory at least once during that period of time are part of the working set of a process.

is the Working Set a completely different, separate list derived from the page table entries, or is it defined in the page table entries?

The working set is not defined by the page table entries. These entries define the whole virtual address space of the process. Also, by only looking at the page table entires, it's not possible to determine or derive the working set. The pages that are resident in main memory in a particular period of time and that have been accessed by the process in that period constitute the working set for that period.

Even if a page table entry includes an accessed bit (like the x86 page table entries) and even if the OS supports the accessed bits, it's still not possible to determine the working set just by looking at the page table entries. That's because the same page table entry may point to multiple physical pages during a period of time. At the end of that period, there is no way to determine all of the physical pages that any page table entry has defined during that period. So some additional data structures need to be used.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hey, thanks for the effort for an answer. What you provided in your information was kind of clear to me already, nevertheless thank you for your information. There is actually another Bit used for the Virtual/CPU Time, giving the OS an idea if a page belongs to the recent working set. I am just not sure if this analysis of the virtual time is enough for the OS to know if such pages belong to the working set, or if it keeps track of all the working sets in a seperate list? $\endgroup$
    – Thomas Christopher Davies
    May 14 '18 at 17:52
  • $\begingroup$ @ThomasChristopherDavies What other bit? What do you mean by the virtual time? $\endgroup$
    – Hadi Brais
    May 14 '18 at 17:56
  • $\begingroup$ According to Carr and Hennesy[81] WSClock ´The virtual time VT of a task is the number of references that have been completed for that task´ And ´Typically, we require (1) a task's virtual time VT, (2) the last reference time LR(p) for each page, and (3) a procedure to detect pages for which VT-LR(p) >= 0´. $\endgroup$
    – Thomas Christopher Davies
    May 15 '18 at 9:51
1
$\begingroup$

I spoke to my professor in operating systems about this matter. He told me, that it is up to the designer of the operating system how he realises the concept of the working set.

The working set is defined by the page table entries. The page table consists of the part for adressing the virtual and the possibly according physical adress and some extra bits, which could differ on different operating systems. Those bits like the "dirty"-bit, the valid-bit or the read-bit help to implement the paging algorithm.

If the working set is used in an operating system, there is an actual need of the virtual time in the page table entry. How this entry in the page table is used is up to the designer of the operating system. The working set could be realised by scanning the page table and finding the entries which by comparing the virtual time of use of the page to the virtual time of the process. Another approach can be to create lists for the complete working set or for different parts of the working set (like read-entries, modified-entries).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.