How Anomalous Is Belady's Anomaly?
Saved in:
| Title: | How Anomalous Is Belady's Anomaly? |
|---|---|
| Authors: | McMaster, Kirby1 kmcmaster@weber.edu, Sambasivam, Samuel2 ssambasivam@apu.edu, Anderson, Nicole3 nanderson@winona.edu |
| Source: | Issues in Informing Science & Information Technology. 2009, Vol. 6, p825-836. 12p. 7 Charts, 3 Graphs. |
| Subjects: | Virtual storage (Computer science), Paging (Computer science), Computer storage devices, Computer simulation, Computer science |
| Abstract: | In a virtual memory system using demand paging, the page fault rate of a process varies with the number of memory frames allocated to the process. When an increase in the number of frames allocated leads to an increase in the number of page faults, Belady's anomaly is said to occur. In this study we used computer simulation to examine four conditions that affect the incidence of Belady's anomaly: (1) page replacement algorithm (FIFO vs. Random Page), (2) process size, (3) reference string length, and (4) memory frames allocated to the process. We found that over a wide range of process sizes and reference string lengths, Belady's anomaly occurred for up to 58.6% of the (random) reference strings under FIFO, and up to 100% of the reference strings for Random Page. Under conditions where anomalies occur most often, the average frame allocation level was around 75% of the process size for FIFO, but just over 50% of the process size for Random Page. Throughout the study, Belady's anomaly occurred so frequently that it no longer seems anomalous. This is especially true for the Random Page algorithm. [ABSTRACT FROM AUTHOR] |
| Copyright of Issues in Informing Science & Information Technology is the property of Informing Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 44457589 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: How Anomalous Is Belady's Anomaly? – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22McMaster%2C+Kirby%22">McMaster, Kirby</searchLink><relatesTo>1</relatesTo><i> kmcmaster@weber.edu</i><br /><searchLink fieldCode="AR" term="%22Sambasivam%2C+Samuel%22">Sambasivam, Samuel</searchLink><relatesTo>2</relatesTo><i> ssambasivam@apu.edu</i><br /><searchLink fieldCode="AR" term="%22Anderson%2C+Nicole%22">Anderson, Nicole</searchLink><relatesTo>3</relatesTo><i> nanderson@winona.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Issues+in+Informing+Science+%26+Information+Technology%22">Issues in Informing Science & Information Technology</searchLink>. 2009, Vol. 6, p825-836. 12p. 7 Charts, 3 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Virtual+storage+%28Computer+science%29%22">Virtual storage (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Paging+%28Computer+science%29%22">Paging (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+devices%22">Computer storage devices</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+simulation%22">Computer simulation</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+science%22">Computer science</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: In a virtual memory system using demand paging, the page fault rate of a process varies with the number of memory frames allocated to the process. When an increase in the number of frames allocated leads to an increase in the number of page faults, Belady's anomaly is said to occur. In this study we used computer simulation to examine four conditions that affect the incidence of Belady's anomaly: (1) page replacement algorithm (FIFO vs. Random Page), (2) process size, (3) reference string length, and (4) memory frames allocated to the process. We found that over a wide range of process sizes and reference string lengths, Belady's anomaly occurred for up to 58.6% of the (random) reference strings under FIFO, and up to 100% of the reference strings for Random Page. Under conditions where anomalies occur most often, the average frame allocation level was around 75% of the process size for FIFO, but just over 50% of the process size for Random Page. Throughout the study, Belady's anomaly occurred so frequently that it no longer seems anomalous. This is especially true for the Random Page algorithm. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Issues in Informing Science & Information Technology is the property of Informing Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=44457589 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.28945/1101 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 12 StartPage: 825 Subjects: – SubjectFull: Virtual storage (Computer science) Type: general – SubjectFull: Paging (Computer science) Type: general – SubjectFull: Computer storage devices Type: general – SubjectFull: Computer simulation Type: general – SubjectFull: Computer science Type: general Titles: – TitleFull: How Anomalous Is Belady's Anomaly? Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: McMaster, Kirby – PersonEntity: Name: NameFull: Sambasivam, Samuel – PersonEntity: Name: NameFull: Anderson, Nicole IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: 2009 Type: published Y: 2009 Identifiers: – Type: issn-print Value: 15475840 Numbering: – Type: volume Value: 6 Titles: – TitleFull: Issues in Informing Science & Information Technology Type: main |
| ResultId | 1 |
