Wednesday, January 13, 2016

Salomon Singer - Mutexes & Semaphores Demystified @ Barr Group, 13 May 2015

Summary @ 46:48


Summary @ 47:16

For the 54 minutes video: https://vimeo.com/128176447

Salomon Singer, mailto:ssinger@barrgroup.com, is the principal engineer at the Barr Group having 30+ years experience in embedded systems. In this excellent talk, he explains the mutexes and semaphores and emphasizes the differences between them. Please note that in the Internet there are a lot of wrong information on how mutexes and semaphores differ!

 I took the following notes while watching the excellent talk:

11:25  Salomon Singer starts his talk after Michael Barr's introduction on

       the Barr Group etc.

12:45  Code at risk due to shared resources is called critical section. Left

       unprotected we might have race condition.

15:00  Tasks are like cars approaching an intersection. Need a protocol to

       prevent mishaps.

16:00  Mutual Exclusion: the programmer should be involved for protecting

       the critical sections.

17:00  Mutex is an operating system data structure to ensure that tasks have

       exclusive access to shared variables or hardware resources. It is 
       short for "mutual exclusion". It is used to prevent race conditions.

17:30  Pseudocode:

           Acquire mutex
           // Critical section code
           Release mutex

17:55  Each mutex protects one shared resource.


18:30  Bathroom key analogy: only one person may use the bathroom at a time.

           Mutex: bathroom key
           Tasks: customers
           Shared resource: bathroom

19:00  One conceptual implementation:

           typedef struct {
               TCB *p_block_q; // queue of blocked tasks: a linked list
                               // of waiting tasks
                               // NULL if there is no waiting task
               int value;      // current mutex state: 1 -> available
           } mutex_t;          //                      0 -> not available

20:00  Each mutex is created at the request of a task. Pseudocode:

          // allocate space for a mutex
          m. p_block_q = (TCB *)NULL; // no tasks waiting
          m.value = 1;                // initially available
          return &m;                  // return a handle

20:42  Mutexes are totally scalable solution: if N tasks try to acquire the

       mutex, only the first one will succeed and N - 1 tasks will wait in 
       the queue. When a tasks releases the mutex, one task in the wait queue 
       will be ready.

21:26  Summary: a mutex is created in the available state. Always use a mutex

       by protocol. Never release a mutex previously not acquired.

22:32  What if two tasks call the same function at about the same time?

       Each such function must be reentrant! Non-reentrant functions are
       the source of many problems that are extremely difficult if not 
       impossible to reproduce.

24:30  Requirements for reentrancy:

          - Safe to use automatic variables: each task has its own stack.
          - Unsafe to use static or dynamic variables: unless protected 
            with mutexes. 
          - Peripheral registers: access must always be protected!

25:30  Example: TCP/IP networking. The network driver controls just one 

       chip just like a global variable.

26:50  Reentrant functions are the best places to use mutexes.


27:27  Where and when to use mutexes:

           Rule 1: Use mutexes in "leaf node" source files, i.e. in source
                   files that don't make calls to any other source files.
           Rule 2: Avoid mutexes in "task level" source files. Prefer 
                   directional intertask communication like semaphores, 
                   mailboxes or message queues.

28:40  What is semaphore? It is an RTOS-provided data structure, at core 

       an integer counter. Safe for parallel-running tasks. All the data
       structure updates inside the RTOS are atomic.

29:15  Types of Semaphores:

           - Counting Semaphore: a multitasking safe counter. Can be 
             incremented/decremented automatically via API calls.
           - Binary Semaphore: Can be set to 1 or 0 automatically via API
             calls.
           - Mutual Exclusion Semaphore (Mutex): A special binary semaphore
             with additional capabilities.

30:10  One conceptual implementation:

           typedef struct {
               TCB *p_block_q; // queue of blocked tasks: a linked list
                               // of waiting tasks
                               // NULL if there is no waiting task
               int value;      // current state: 0..N
           } sem_t;

30:45  OS Implementer: similarities keep coming!

       OS user: try to forget you ever saw this!

30:55  Because semaphores and mutexes have completely different uses!


31:20  ISR's can only make non-blocking calls:

           - It is never safe to wait for a semaphore.
           - However, it is safe to signal a semaphore: that will never block!

31:55  Tasks can safely wait and signal a semaphore.

32:00  Mutexes vs Semaphores:

           - Mutexes are to be used only for mutual exclusion. Always
             init 1, wait() first and then leave().

32:30      - Semaphores are for one-to-one signalling. Can be init to any

             value. Typically init to 0. There is no prescribed order to
             use the API.

34:10  Problem: multiple identical resources. Analogy: 2+ bathrooms.


34:35  If you Google this problem, many sources say a counting semaphore will

       work! They are all wrong. A counting semaphore can't protect 2+ 
       resources! Need to know which one is available.
  
34:55  The right solution will be using distinct mutexes for each bathroom. One
       key for women and another key for men.

35:28  Priority inversion problem.

       A high priority task needs a resource being used by a low-priority task.
       So, it is waiting for the low-priority task. However, a medium-priority
       task preempts the low-priority task having higher priority!  
       Consequently, the high-priority tasks wait for the low-priority task
       longer than necessary! It may cause the high-priority task to miss a
       deadline.

37:48  What is the implications of priority inversion? It is impossible to

       be certain that all deadlines will be met! Thus, we need a way to 
       prevent priority inversions.

38:35  Priority inversion workarounds for mutexes:

           - Highest locker or priority ceiling protocol. Can be implemented 
             above the RTOS. Each shared resource is assigned a priority just 
             above its users' priorities. Calls to raise and lower task 
             priorities are used instead of mutex calls.

39:28      - Priority inheritance protocol. Can be implemented only in the

             RTOS. The priority of a task that holds a resource is increased 
             automatically but only when a high-priority task wants the resource
             and only until the low-priority task releases it. Upon completion, 
             the priority of the task will be demoted. It scales nicely.

40:00  Priority ceiling example.


41:18  Priority inheritance example.


42:43  Priority inheritance scales nicely example.


44:34  Mars Pathfinder story: priority inversion example. WxWorks has a mutex 

       priority inheritance option, but it wasn't turned on!

47:50  Starts to answer the questions.









  

Friday, January 8, 2016

Prof. Allen B. Downey - Introduction to Semaphores @ 2010

Making a demo with Sync @ 17:05

For the 60 minutes video: https://www.youtube.com/watch?v=RaEUw107dpg

In this video Prof. Allen B. Downey talks about concurrency basics and semaphores. He makes nice demos with his Python Sync app. This is a nice video for introduction to concurrency.

36:50  Starts to talks about free books.

44:25  Starts to answer the questions.

Thursday, January 7, 2016

Scott Meyers – The Most Important Design Guideline @ ConFu, Latvia, 13 Nov 2014

Summary @ 57:18

For the 
59 minutes video: https://www.youtube.com/watch?v=5tg1ONG18H8

The Most Important Design Guideline? article by Scott Meyers is about the similar topic.

Scott Meyers talks basically on the interface design. I took the following notes while watching the excellent talk:

00:24  I want to talk about single most important guideline I know 
       of writing software independent of the its language, its tasks, its 
       users, etc.
       
00:50  #1 Make interfaces easy to use correctly and hard to use incorrectly.

00:55  We spend a gigantic amount of time on interfaces!

01:40  There are two types of interfaces.

01:45  #1 Encountered by everybody:
          GUI/Software interfaces
          Command line interfaces
          Speech interfaces
          
01:50  #2 Encountered by software developers:
          Library interfaces
          Module interfaces
          Class interfaces
          Method and function interfaces
          Generics and template interfaces
          
04:00  Interface users are typically smart and motivated.

05:00  If they use your software improperly, it is your fault!

05:27  What this means is that software should be designed and implemented 
       to be easy to correctly and hard to use incorrectly.

06:05  The software development industry should shoot for Rico Mariani's 
       "pit of success".
       
06:20  It means by default all forces should push you in the right direction.

06:46  Principle of least astonishment: strive to maximize the likelihood 
       that user expectations about an interface are correct.
       
07:30  Your job is to maximize the odds that the guesses are correct.

07:42  If users can do something, it should do what they expect.

07:55  If users know what they want to do, they should be able to guess how 
       to do it.

08:20  UI counterexamples:
       Starting from Win 95, press the Start button to shutdown the computer.
       
08:45  The rationale was "everything else we tried was worse".

09:12  What is biggest complain about Win 8? It doesn't have a "Start" button!

09:40  If your interface is so liked & so long-lived, be proud of it!

10:45  [In an old Mac OS] in order to eject the removable media, drag its icon
       to the trash can!

12:25  In Win XP, choosing the large font size instead of the normal one was very 
       problematic!
       
13:10  While installing Qt 4.8 on a Win computer, "The install path must not 
       contain any spaces..." Pointing to poor porting from Unix!
       
15:45  Expedia and Kayak's calendar selection UI's in 2010, i.e. after iPhone: 
       Kayak allowed swipe, but Expedia didn't!
       
16:20  Some interfaces are so bad, it is really difficult describe exactly what 
       is wrong with them! A very poor UI example from a calendar app.
      
18:15  Slate mobile app for reading articles: the "Top Comment" inserted into 
       the middle of article!

19:40  General techniques:
           - Avoid gratuitous incompatibilities with the surrounding environment: 
             take advantage of what people already know
           - Offer natural syntax
           - Offer intuitive semantics:
               In API's, when in doubt, do as built-in or standard library types 
               do. In GUI's, try to have mouse clicks, keyboard shortcuts and 
               gestures mean the "usual things".
               
22:25  More specific techniques:
           - Choose good names: the very first impression that people get is based
             on names!
             
24:50  UI counter example: Adobe Acrobat 9 after modifying a PDF displaying a
       dlgbox with three buttons: "Do you want to save changes to your file? 
       Yes, No, Cancel." What does "Cancel" mean is confusing!
       
25:45  OpenOffice has a similar "Save, Discard, Cancel" dlgbox!

26:30  Being desktop apps, i.e. space isn't so restricted, you can put more 
       text on the "Cancel" buttons.

26:45  Another solution, without asking silently saving the file which brings 
       other UI challenges.

27:05  One of things I find is that if you have UI challenge that is making 
       difficult for people to do the right thing try to come up with an 
       alternative design that makes the problem completely go away!

27:25  "Gulf of execution": distance between what you want to do and the action
       you must take to get it done. Larger the gulf of execution, the more 
       difficult to use the software.

28:00  As interface designers, our goal is to minimize the "gulf of execution" 
       and turn it into "pit of success"!

28:45  "Choose good names" API counterexample: In C++ equal_range is based on 
       equivalence, not equality! 
       
29:05  Be consistent in all kind of things: in naming, in error reporting etc.

30:15  "Be consistent" GUI counterexamples:

31:20      - "Mail Compose button" on different locations on iPhone, iPad and MAC
             OS X! Works against muscle memory...

32:28  "Be consistent" cross-device counterexamples:
           - Marriott Rewards Card. It carries numbers grouped by blanks. The web 
             UI accepts the spaces, but the server rejects the number submitted! 
             Stupid UI designers...
             
           - An ATM UI asks for cash or check deposit, but the hardware buttons 
             are placed below the wrong UI buttons! Misleading...
             
34:10      - Java container size? both "length" and "size" used!

34:40      - .NET 1.0 container size? both "Length" and "Count" used! People
             claims thanks to the IDE, no problem. But they are wrong on two 
             counts:
             1 - "L" and "C" are different letters!
             2 - Not always an IDE is used!
             Plus, as .NET supports reflection, you have to query the objects for
             more than necessary!

36:40      - C Standard Library file functions: fscanf(), fgetpos() and fseek() 
             gets the FILE pointer as the first argument. However, fgets(), 
             fputc() and freopen() gets the FILE pointer as the last argument!
             Even very very experienced C developers are confused: 
             "This inconsistency has frustrated millions of developers for more 
             than 30 years" - Ferenc Mihaly
             
37:59      - C++ Standard Library function to eliminate all container elements 
             with a given value: for 8 containers erase() and for 2 containers 
             remove() are used! I am intimately familiar with the developments in
             C++ there are reasons for it and the reasons are not good! The smart 
             people never looked at the problem at this level, but the programmers
             look at this level!
             
39:20      - C++ Standard Library: if the sort() function doesn't run in N * logN 
             time which can be detected during compilation, the code it 
             rejected! However, binary_search() either runs in logN or N. 
             Conceptual inconsistency...
             
41:20      - C++ Standard Library: have sort() and stable_sort(), however 
             list::sort() specialization is guaranteed to be stable! Inconsistent
             naming...             
             
42:30  Progressive Disclosure: discriminate between "expert" and "normal" not to 
       overwhelm the users. Not uncommon in GUI's.
       
43:45      - GUI from an app called SUPER: categorized the options. Categorization
             alone may be fine, but it is just not progressive disclosure!

44:20      - Applicable to API design, too: bundle advanced functionality into 
             separate objects. Functionality is hidden, unless such objects are 
             requested. Ken Arnold's "Programmers are People, too" article cites
             Java JButton class offering >100 methods. However, typical use only 
             a small minority! His suggestion: retain only commonly-used methods
             in JButton, bundle rarely-used method into an object accessible via
             JButton's getExpertKnobs method. Plus, bundle integration 
             functionality into an object accessible via getIntegrationHooks 
             method.

46:20  Document Before Implementing: proven way to discover interface problems.
       Unpleasant to explain -> unpleasant to use. Plus:
           - Surprising or underspecified behaviors
           - Bad names
           - Inconsistencies

47:20  If you are using a strongly typed programming language, i.e. statically 
       typed, the type system is your friend. Many errors can be prevented through
       stronger typing.
       
47:40  C++ Date class:
           Date(int month, int day, int year);
           
48:20  If in an API, any time adjacent parameters are of the same type, callers
       can pass them in wrong order! It should be avoided as much as possible. 
       Easy to use incorrectly!
       
48:45  Fix it by introducing Month, Day and Year types.
       Date d(4, 8, 2005); -> Date d(Month(4), Day(8), Year(2005)); 
       Besides preventing the user errors, the code is now easier to read.
       
49:49  Typedef's are synonyms and using them for int's make the code easier to
       read, but compiler doesn't detect errors! Programming to make you feel 
       better about yourself! You haven't improved the type safety in any way...
       
50:30  Why I fixated on 4/8/2015? The day we got "Darla". My wife and I have no 
       kids, having a dog is good!
       
51:30  Constrain values: Month(-4) is still possible! Let the Month class has
       public static 12 const Month objects per actual month and disable new 
       Month object creation, i.e. let the Month ctor be private and explicit. 
       So, Month(-4) won't even compile!
       
52:40  Addressing the day and year is harder, but it is possible.

52:52  When you design an interface, you should always ask yourself what kinds of 
       errors might people make in this interface.

53:00  Given the errors they could make, what actions can we take to prevent them?

53:15  Given the errors, the cost associated with the errors, the prevention and 
       the cost associated with the preventing them, you can make an engineering
       or business decision.
       
53:50  Even constraining values may lead to a false sense of of security. For 
       example, on the Lonely Planet web site June 31 was possible!
       
54:05  Consistency: two different methods for date specification on the Lonely 
       Planet. Bad for muscle memory!
              
54:53  Avoid over reliance on string. String is known as a type sink!

56:07  Different types facilitate type-specific type formatting and validation
       code!

56:19  Rather than using strings in your API's, you should be using something
       just descriptive about what they stand for.

57:28  Starts to answer the questions.






           


   

           



















     









   

     
















Tuesday, January 5, 2016

Bjarne Stroustrup - Writing Good C++14 @ CppCon 2015, 21 September 2015

For the 101 minutes video: https://www.youtube.com/watch?v=1OEu9C51K2A

For the C++ Core Gudilelines: https://github.com/isocpp/CppCoreGuidelines

For the Microsoft GSLhttps://github.com/isocpp/CppCoreGuidelines




Bjarne Stroustrup talks basically on the Guidelines Support Library (GSL). I took the following notes while watching the excellent talk:


02:55  Very few people write modern C++ code.

03:36

04:40  Inventing a new language in order get a better and simpler
       one is a bad idea!

08:50  We don't like coding rules. They are aimed to prevent 
       accidents: basically "don't do" lists. Not aimed for quality 
       code.

09:50  Coding rules recommends restrictions on C++ features.

10:00  There are a lot of bad advice!

11:58

12:07  I don't understand the MISRA C++ pointer rules: they are 
       miserable!

17:56  Language subsetting doesn't work.

18:15  Write high-level code via libraries using all the language 
       features.

19:10  After you build the superset, i.e. language + libraries, you 
       subset.

19:30  What we want is "C++ on steroids".  

23:40  Tool support, i.e. static analysis, is essential.

25:10  No resource leaks: RAII, i.e. no naked new and delete!

32:50  GSL: owner is for fixing the dangling pointer nightmare.

33:15  Owner is intended to simplify static analysis.

37:00  Besides dangling pointers, there are other pointer misuses:
       range errors: fix it with array_view.
       nullptr dereferencing: fix it with non_null.

37:18  We want to minimize run-time checks, because we want to run
       fast!

37:50  My least favorite interface:
       void f(int *p, int n);
       why?
       So common!
       So error-prone!
       Fix it with array_view.

40:15  nullptr problems: fix it with not_null.

41:30  not_null is for minimising run-time checking!

42:20  "Smart pointers" are overused to overcome ownership and 
       dangling pointer problems.

43:12  As the dangling pointers are eliminated by tools, you don't
       need to use them! 

47:30  Too many rules: the tools should know the rules and will 
       point you the relevant ones.

49:15  There are too many rules and it doesn't work me! I want lots 
       of rules.

50:00  I hate camel case.

51:20  We aren't unambitious: 
       Aim type and resource safety.
       Consider all 4+ millions C++ programmers.
       Zero-overhead principle.

51:50  We aim to change the way we write code.

53:52  Help wanted! There are currently only two editors: me and 
       Herb Sutter.

55:02  The basic C++ model is now complete.

57:20  Starts to answer the questions.