Please follow the assignment instructions attached.
Arizona State University SER334: Operating Systems Lecturer Acuña Revised 11/26/2019 ADJ - Problem Set II 1 Problems (40 points; 13 points problem 1,2 ; 14 points problem 3) Complete the following four problems. Both the syllabus rules and ADJ Ruleset 1v2 are in e�ect. M7: Process Synchronization I 1. [Silberschatz, Acuña] Assume that a context switch takes time T . Propose an algoithm to determine how long a process to hold a spinlock, based on the process load of a system and T. If the spinlock is held for long, switching to a mutex lock (where waiting threads are put to sleep) would give the system better CPU utilization by decreasing wasted cycles (i.e, the busy waiting in a spinlock). Analyze the problem, design an algorithm for computing the bound, and justify the algorithm's optimality. [5A+3D+5J points] M9: CPU Scheduling 2. [Acuña] Design an e�cient (i.e., Big-Oh of a polynomial) algorithm for determining the time quantum t for a round robin scheduler. The algorithm must consider the current process load and compute t, where system throughput is maximized for some interval. Analyze the problem, design an algorithm for computing the bound, and justify the algorithm's optimality. [5A+3D+5J points] M11: Virtual Memory 3. [Acuña] Consider the following fragment of code: #de f i n e OFFSET(x , y , columns ) = (y ∗ columns + x) // check i f two matr i ce s are the same . i n t equa l s ( IntMatr ix ∗ th i s , IntMatr ix ∗ other ) { i f ( other == NULL) return 0 ; i f ( other−>co l s != th i s−>co l s | | other−>rows l s != th i s−>rows ) re turn 0 ; f o r ( i n t y = 0 ; y < th="" i="" s−="">rows ; y++) f o r ( i n t x = 0 ; x < th="" i="" s−="">co l s ; x++) //no i n t e n t a t i o n a l magic ; po in t e r a r i thmet i c s i n c e C won ' t a l low [ ] [ ] i f (∗ ( th i s−>data + OFFSET(x , y , th i s−>co l s ) ) != ∗( other−>data + OFFSET(x , y , th i s−>co l s ) ) re turn 0 ; re turn 1 ; } What page replacement scheme (of FIFO, OPR, LRU, MFU) should be used for this code? Analyze the problem, design a choice, and justify the choice. [5A+4D+5J points] 1 2 Submission The submission for this assignment has one part: a write up. The �le should be attached to the homework submission link on Canvas. Writeup: Submit the ADJ answers in PDF format. Please name your �le as "LastName1and2ADJ2.pdf" where the last names are given in alphabetic order (e.g. "EdgarLisonbeeADJ2.pdf"). 2 Notes on Solving ADJ Problems Ruben Acuña April 15, 2019 Abstract This document contains some miscellaneous notes on solving problems in the context of the ADJ ruleset that you may �nd useful. Notes come mainly from discussion with students. Author's Note: the following should be not new ideas. They should been mentioned (at least in passing) in your other courses (e.g., ENG102, MAT243, SER216, SER222, SER315...) 1 Analysis Ideas Although there are many approaches to doing the analysis of a problem, for the sake of having a starting place, I suggested the following parts of an analysis (with a minor example of design a sorting algorithm): 1. Construct de�nitions to represent domain knowledge and assumptions. Prob- lems do not exist in a vacuum, especially not the engineering problems we expect to see. Every problem exists in some problem domain, which is typically rich in existing knowledge, problems, and solutions. Unfortunately, problem domains can also include con�icting information, and so even if someone is familiar with the domain, they may read the material you have written, with your internal de�nitions/understandings, and come to a di�erent conclusion. We wish to prevent this. Our solution to this is to be speci�c in expressing the concepts and knowledge that our ideas are founded upon. Rather than only saying �Design an algorithm to sort an input array�, we might want to add the following: An input array is a sequence of elements, where each element is ordered (via the comparison operators) with the other elements in the array. Given an input array A, design an algorithm which converts A = a0a1a2...an to some A′ with ∀0≤k≤n, ak < an+1. notice that in making this statement, we have clari�ed our problem: we now know that we are sorting in an ascending order (the original only made the claim �sorted� which might have included the reverse as well). this clari�cation came from our explicit de�nition of what is an input array and what it means for an input array to be sorted. as a thought exercise, consider the di�erence between domain knowledge and assump- tions. 1 2. quantify the problem in terms of the de�nitions. design problems are typi- cally under-speci�ed. this means that the problem as initially stated does not have a solution, or does not have a best solution. there simply isn't enough information to construct and validate such things. under-speci�ed problems are extremely common in practice - the complexity of real world problems in engineering almost mandates it. it's only in realms of mathematics or logic that problems are well-de�ned. here, problems are, in a sense, qualitative. we are expressing with descriptive words what something should look like or act like. if we say something like: �the algorithm should run fast on reasonably sized datasets�, what do we mean? what is fast? what is a reasonably sized dataset? these questions require more speci�city. we should say something more like: �the algorithm should always complete in less than 2ns on an in- put dataset that has at most 2048 elements.� making this more quantitative statement - i.e., saying �2ns� instead of �fast� - requires us to make reasonable assumptions about the problem, from which we can make statements about the problem with respect to the de�nitions which we to represent the foundations of the problem domain. 3. determine a metric for a solution optimal to the quanti�ed problem. it is a bold statement to claim that a particular design is the best design. and a related question: is the best design unique? ideally, we what some mechanism by which we can judge a particular design as being a solution as well as its relative �e�ectiveness� to other designs. if this mechanism is particularly generic, we may even be able to make the boldest of claims: this is the best design. in the previous section, we made our problem more quantitative by de�ning it as �the algorithm should always complete in less than 2ns on an input dataset that has at most 2048 elements.� we might consider the following metric: can the algorithm sort an input array of size 2048 in less than 2ns? this gives us the simplest possible metric: it has a yes or no answer, and requires no optimization (i.e., we do not have to ask if there is a better solution; anything that satis�es it is equally optimal, and we are done with the problem.) note that using this metric technically requires that any algorithm does increasing amounts of work as the size of the input array increases. generally speaking, this is a reasonable assumption. although our metric is �ne, some additional work is required to apply it when we do the justi�cation for a design: we should use algorithm analysis techniques on a design to estimate how long an algorithm will take to run, then the yes/no metric can be applied to it (i.e., check if the time it takes is less than our requirement). as a �nal important note: an analysis is not a design. it does not argue or support a particular solution, instead it should capture what it means for something to be a solution to the problem, and what it means for something to be the best solution. 2 arizona state university lecturer acuña adj - ruleset 1v2 summary: in this handout, we review the basic ideas and ruleset involved in solving adj problems. 1 introduction the goal of adj assignments is simple: they are a way to practice strengthening and defending your ideas through engineering design. our ideas are precious, and we should keep them safe. we should endeavor to make them strong so that they can survive away from us, among other competing ideas. consider: in a typical essay answer homework question, the student is asked to provide a solution to a short problem statement. the student provides an idea that answers the question, and if it looks good, the grader will give marks. but: was it a good answer? how can someone (student or grader) even evaluate the correctness of answer? if it's not a numerical answer, is it at all obvious? it's not uncommon to look at a question, and think: �why didn't they like that??!?� here, our question was been left alone and needed to be able to justify itself to an evaluator. you aren't there in the room to point out stu� to the grader, your idea must be able to stand alone. a typical issue is that a problem is either misunderstood, or not approached in a sound way. in that case, it's di�cult to specify a solution, as well as to check if a solution is correct, or be able to compare it to other answers. a second issue is not producing the support for answer to show that it is better than alternatives. for some examples of answers which could be strengthened, consider the following legacy exam question: consider the algorithmic task of changing a photograph into the art style known as cubism. in such a �lter, regions of pixels are transformed into rectangular regions with a single color. for example, the following image: would be �ltered to say we want to design a image �lter algorithm to apply a cubism �lter. of the �ve issues in multi-core programming, which is the most problematic for multi-threading this problem? justify. 1. �data splitting� concerns: is this right? this answer doesn't include justi�cation. what if it's a guess? the reader will have questions, �why not pick something else?� 2. �communication between threads as some of the image depends on the area outside of the assigned portion in a single thread. the �nal result may be di�erent depending on how the combination of the threads into the 2d array representing the image is processed.� concerns: communication isn't one of the �ve issues, so even if the idea is good, it doesn't answer the speci�c question being an+1.="" notice="" that="" in="" making="" this="" statement,="" we="" have="" clari�ed="" our="" problem:="" we="" now="" know="" that="" we="" are="" sorting="" in="" an="" ascending="" order="" (the="" original="" only="" made="" the="" claim="" �sorted�="" which="" might="" have="" included="" the="" reverse="" as="" well).="" this="" clari�cation="" came="" from="" our="" explicit="" de�nition="" of="" what="" is="" an="" input="" array="" and="" what="" it="" means="" for="" an="" input="" array="" to="" be="" sorted.="" as="" a="" thought="" exercise,="" consider="" the="" di�erence="" between="" domain="" knowledge="" and="" assump-="" tions.="" 1="" 2.="" quantify="" the="" problem="" in="" terms="" of="" the="" de�nitions.="" design="" problems="" are="" typi-="" cally="" under-speci�ed.="" this="" means="" that="" the="" problem="" as="" initially="" stated="" does="" not="" have="" a="" solution,="" or="" does="" not="" have="" a="" best="" solution.="" there="" simply="" isn't="" enough="" information="" to="" construct="" and="" validate="" such="" things.="" under-speci�ed="" problems="" are="" extremely="" common="" in="" practice="" -="" the="" complexity="" of="" real="" world="" problems="" in="" engineering="" almost="" mandates="" it.="" it's="" only="" in="" realms="" of="" mathematics="" or="" logic="" that="" problems="" are="" well-de�ned.="" here,="" problems="" are,="" in="" a="" sense,="" qualitative.="" we="" are="" expressing="" with="" descriptive="" words="" what="" something="" should="" look="" like="" or="" act="" like.="" if="" we="" say="" something="" like:="" �the="" algorithm="" should="" run="" fast="" on="" reasonably="" sized="" datasets�,="" what="" do="" we="" mean?="" what="" is="" fast?="" what="" is="" a="" reasonably="" sized="" dataset?="" these="" questions="" require="" more="" speci�city.="" we="" should="" say="" something="" more="" like:="" �the="" algorithm="" should="" always="" complete="" in="" less="" than="" 2ns="" on="" an="" in-="" put="" dataset="" that="" has="" at="" most="" 2048="" elements.�="" making="" this="" more="" quantitative="" statement="" -="" i.e.,="" saying="" �2ns�="" instead="" of="" �fast�="" -="" requires="" us="" to="" make="" reasonable="" assumptions="" about="" the="" problem,="" from="" which="" we="" can="" make="" statements="" about="" the="" problem="" with="" respect="" to="" the="" de�nitions="" which="" we="" to="" represent="" the="" foundations="" of="" the="" problem="" domain.="" 3.="" determine="" a="" metric="" for="" a="" solution="" optimal="" to="" the="" quanti�ed="" problem.="" it="" is="" a="" bold="" statement="" to="" claim="" that="" a="" particular="" design="" is="" the="" best="" design.="" and="" a="" related="" question:="" is="" the="" best="" design="" unique?="" ideally,="" we="" what="" some="" mechanism="" by="" which="" we="" can="" judge="" a="" particular="" design="" as="" being="" a="" solution="" as="" well="" as="" its="" relative="" �e�ectiveness�="" to="" other="" designs.="" if="" this="" mechanism="" is="" particularly="" generic,="" we="" may="" even="" be="" able="" to="" make="" the="" boldest="" of="" claims:="" this="" is="" the="" best="" design.="" in="" the="" previous="" section,="" we="" made="" our="" problem="" more="" quantitative="" by="" de�ning="" it="" as="" �the="" algorithm="" should="" always="" complete="" in="" less="" than="" 2ns="" on="" an="" input="" dataset="" that="" has="" at="" most="" 2048="" elements.�="" we="" might="" consider="" the="" following="" metric:="" can="" the="" algorithm="" sort="" an="" input="" array="" of="" size="" 2048="" in="" less="" than="" 2ns?="" this="" gives="" us="" the="" simplest="" possible="" metric:="" it="" has="" a="" yes="" or="" no="" answer,="" and="" requires="" no="" optimization="" (i.e.,="" we="" do="" not="" have="" to="" ask="" if="" there="" is="" a="" better="" solution;="" anything="" that="" satis�es="" it="" is="" equally="" optimal,="" and="" we="" are="" done="" with="" the="" problem.)="" note="" that="" using="" this="" metric="" technically="" requires="" that="" any="" algorithm="" does="" increasing="" amounts="" of="" work="" as="" the="" size="" of="" the="" input="" array="" increases.="" generally="" speaking,="" this="" is="" a="" reasonable="" assumption.="" although="" our="" metric="" is="" �ne,="" some="" additional="" work="" is="" required="" to="" apply="" it="" when="" we="" do="" the="" justi�cation="" for="" a="" design:="" we="" should="" use="" algorithm="" analysis="" techniques="" on="" a="" design="" to="" estimate="" how="" long="" an="" algorithm="" will="" take="" to="" run,="" then="" the="" yes/no="" metric="" can="" be="" applied="" to="" it="" (i.e.,="" check="" if="" the="" time="" it="" takes="" is="" less="" than="" our="" requirement).="" as="" a="" �nal="" important="" note:="" an="" analysis="" is="" not="" a="" design.="" it="" does="" not="" argue="" or="" support="" a="" particular="" solution,="" instead="" it="" should="" capture="" what="" it="" means="" for="" something="" to="" be="" a="" solution="" to="" the="" problem,="" and="" what="" it="" means="" for="" something="" to="" be="" the="" best="" solution.="" 2="" arizona="" state="" university="" lecturer="" acuña="" adj="" -="" ruleset="" 1v2="" summary:="" in="" this="" handout,="" we="" review="" the="" basic="" ideas="" and="" ruleset="" involved="" in="" solving="" adj="" problems.="" 1="" introduction="" the="" goal="" of="" adj="" assignments="" is="" simple:="" they="" are="" a="" way="" to="" practice="" strengthening="" and="" defending="" your="" ideas="" through="" engineering="" design.="" our="" ideas="" are="" precious,="" and="" we="" should="" keep="" them="" safe.="" we="" should="" endeavor="" to="" make="" them="" strong="" so="" that="" they="" can="" survive="" away="" from="" us,="" among="" other="" competing="" ideas.="" consider:="" in="" a="" typical="" essay="" answer="" homework="" question,="" the="" student="" is="" asked="" to="" provide="" a="" solution="" to="" a="" short="" problem="" statement.="" the="" student="" provides="" an="" idea="" that="" answers="" the="" question,="" and="" if="" it="" looks="" good,="" the="" grader="" will="" give="" marks.="" but:="" was="" it="" a="" good="" answer?="" how="" can="" someone="" (student="" or="" grader)="" even="" evaluate="" the="" correctness="" of="" answer?="" if="" it's="" not="" a="" numerical="" answer,="" is="" it="" at="" all="" obvious?="" it's="" not="" uncommon="" to="" look="" at="" a="" question,="" and="" think:="" �why="" didn't="" they="" like="" that??!?�="" here,="" our="" question="" was="" been="" left="" alone="" and="" needed="" to="" be="" able="" to="" justify="" itself="" to="" an="" evaluator.="" you="" aren't="" there="" in="" the="" room="" to="" point="" out="" stu�="" to="" the="" grader,="" your="" idea="" must="" be="" able="" to="" stand="" alone.="" a="" typical="" issue="" is="" that="" a="" problem="" is="" either="" misunderstood,="" or="" not="" approached="" in="" a="" sound="" way.="" in="" that="" case,="" it's="" di�cult="" to="" specify="" a="" solution,="" as="" well="" as="" to="" check="" if="" a="" solution="" is="" correct,="" or="" be="" able="" to="" compare="" it="" to="" other="" answers.="" a="" second="" issue="" is="" not="" producing="" the="" support="" for="" answer="" to="" show="" that="" it="" is="" better="" than="" alternatives.="" for="" some="" examples="" of="" answers="" which="" could="" be="" strengthened,="" consider="" the="" following="" legacy="" exam="" question:="" consider="" the="" algorithmic="" task="" of="" changing="" a="" photograph="" into="" the="" art="" style="" known="" as="" cubism.="" in="" such="" a="" �lter,="" regions="" of="" pixels="" are="" transformed="" into="" rectangular="" regions="" with="" a="" single="" color.="" for="" example,="" the="" following="" image:="" would="" be="" �ltered="" to="" say="" we="" want="" to="" design="" a="" image="" �lter="" algorithm="" to="" apply="" a="" cubism="" �lter.="" of="" the="" �ve="" issues="" in="" multi-core="" programming,="" which="" is="" the="" most="" problematic="" for="" multi-threading="" this="" problem?="" justify.="" 1.="" �data="" splitting�="" concerns:="" is="" this="" right?="" this="" answer="" doesn't="" include="" justi�cation.="" what="" if="" it's="" a="" guess?="" the="" reader="" will="" have="" questions,="" �why="" not="" pick="" something="" else?�="" 2.="" �communication="" between="" threads="" as="" some="" of="" the="" image="" depends="" on="" the="" area="" outside="" of="" the="" assigned="" portion="" in="" a="" single="" thread.="" the="" �nal="" result="" may="" be="" di�erent="" depending="" on="" how="" the="" combination="" of="" the="" threads="" into="" the="" 2d="" array="" representing="" the="" image="" is="" processed.�="" concerns:="" communication="" isn't="" one="" of="" the="" �ve="" issues,="" so="" even="" if="" the="" idea="" is="" good,="" it="" doesn't="" answer="" the="" speci�c="" question="">