From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.236.111.4 with SMTP id v4mr13180025yhg.55.1425038344101; Fri, 27 Feb 2015 03:59:04 -0800 (PST) X-Received: by 10.140.101.148 with SMTP id u20mr190148qge.5.1425038344063; Fri, 27 Feb 2015 03:59:04 -0800 (PST) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!i13no9097590qae.0!news-out.google.com!n6ni190qar.0!nntp.google.com!j7no8418712qaq.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Fri, 27 Feb 2015 03:59:02 -0800 (PST) Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=193.17.19.232; posting-account=ku4DIwoAAACRt0A2H-srh5aOk_YodLAH NNTP-Posting-Host: 193.17.19.232 User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <0925a2da-6cd2-4c06-bd20-1ffb3d14156b@googlegroups.com> Subject: Uneasy thoughts about priorities, priority inversion and protected objects From: =?ISO-8859-1?Q?Jean_Fran=E7ois_Martinez?= Injection-Date: Fri, 27 Feb 2015 11:59:04 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 4283 X-Received-Body-CRC: 983982464 Xref: news.eternal-september.org comp.lang.ada:25055 Date: 2015-02-27T03:59:02-08:00 List-Id: Both Burns in his "Concurrent and Real Time Programming in Ada" and JP Rose= n in his wikibook (in French) about software engineering "implement" (note = the scare quotes) protected objects by giving a priority to the protected o= bject that is inherited by a task when it runs in it. This prioriry must b= e at least equal to the maximum priority of the tasks that might access the= protected object (a task with a higher priority gets an exception). =A8Pur= pose is to avoid priority inversion when a task with high priority cannot e= nter a protected object because a task with low priority is in it and this = cannot get the processor (and out of the protected object) because a task w= ith medium priority is running. The merit of this model is that it makes p= rotected objects very easy to implement (on monoprocessors): no need of sem= aphores: once a task is in a protected object no other task can enter it be= cause it cannot get the processor. Burns tells this model is recommended/mandated (don't remember) by the ARM. Problem is: there are still priority inversions. Let's consider the follow= ing scenario. Task High is sleeping, Task Medium is waiting for I/O, Task = Low is in protected Object. Now I/O completes so Task Medium should get th= e processor but it doesn't because Low is in protected object with High's p= riority or more. But nobody is waiting for the protected object so there i= s no hurry in getting Low out of it and no reason to delay Medium jsut beca= use Low is in Protected Object. Agreed you are not supposed to spend much = time in Protected Objects so you can consider it is no big deal but it is n= ot satisfactory. It also raises the question of if such a model really all= ows concurrent readers in practice when in monoprocessors. It seems to me a task on a protected object should have its priority raised= only when a task with a higher priority queues behind it. In that case it= s priority should become=20 Max(Own_Priority, Max(Priority_of_Processes_in_the_Queue)). With this mode= l: Low is in Protected_Object running at Low priority, Medium's I/O ends so Me= dium gets the processor, High awakes, grabs the processor from Medium and q= ueues on the protected object, Low gets its priority raised to High, resume= s running, leaves the protected object and returns to its normal priority = (Low), High gets the processor, enters the protected object and keeps runni= ng until it decides to release it. Medium gets the processor. =20 Zero priority inversions. Also we can have multiple readers, even in mono= processors. At least when second reader has ahigher priority than first on= e. =20 Since I don't think for a second none of the smart people who designed Ada = and none of the smart people who have read either the ARM, Burns'book or Ro= sen's wikibook haven't ever had a so obvious idea why is that we still are = in the model I described on the first paragraph? Because it is simpler to = implement? Because it is no big deal? (You are supposed to leave the prot= ected object _fast_). Or is it because I missed someting?=20 --- Jean-Fran=E7ois Martinez