Santa Claus task and practical logistics

It is known that only 5% of programmers are able to solve problems of multi-threaded programming. And in place with that, with an increase in the number of cores, even for mobile devices, the need to use several threads increases many times. Every day there are new programming languages ​​specifically designed for solving specific problems of parallel programming, and in already well-known and widely used solutions methods appear that not only facilitate understanding, but also reduce the solution of the problem to a kind of program code poetry.

While reading the book “The Perfect Code” edited by Andy Oram and Greg Wilson, I happened to encounter an interesting task in the chapter on parallel processing (ch. 24. p. 444). In it, the author, Simon Peyton Jones, gives a solution in Haskell. There he also states that there are solutions to the Sat Klaus problem for the Ada95 and Polyphonic C # languages. Due to my professional interests, I had to discuss with my colleagues a few earlier possibilities of multi-stream Apple implementation for the Objective-C language.

It is considered that it is necessary to program at the level of abstractions, not “in language”, but with the same success one can look for the beauty of poetry in emotions, and not in the elegance of a syllable expressed through language. Under the cut, I propose to sing with me a song for those for whom linguistic expressiveness is not an empty sound, but a melody that stirs imagination.

')

Formulation of the problem:

“Santa periodically sleeps until she is awakened either by all of her nine reindeer who have returned from free grazing, or by a group of three elves, of which he has only nine. If deer wake him up, he harnesses each of them into a sleigh, delivers toys with them, and in the end unharns them (releasing them for free release). If the elves wake him up, he leads each group to his office, confers with them on the development of new toys, and in conclusion, each of them leaves the office (giving the opportunity to return to work). If Santa Claus is waited at the same time by a group of elves and a group of deer, he will give priority to deer. ” (WITH)

Introduction:

It seemed to me that this is an ideal task to demonstrate the capabilities of the language. At one time, I had a lot of programming in C # multi-threaded applications, and then I thought that there was no perfect language for this purpose. With # bribed its simplicity and efficiency. But Apple has turned this process into a song. And as in every song you need to feel that rhythm, that meter, which will give pleasure from the heard music. At first, dealing with the clutter of a brace notation is not a trivial task, designed for people with developed perseverance and attentiveness.

Arguing about the task it is easy to come to the conclusion that there is not much difference between the Elves and the Reindeer. In our formulation, both of these biological forms can be equated to an abstract person who can perform some little understood action. By and large, it does not even matter what kind of action it is, but, based on the initial conditions, the Deer graze, and the Elves work. And so and so on the implementation of their personal actions need some time. Moreover, each individual spends on the action of an individual amount of this precious resource.

All code is written using ARC, in XCode 4.3. This clarification is necessary because, first, XCode 4.3. learned to see the methods, even if they are described after their use, and secondly, the ARC does not care about the destruction of objects and special dispatching of memory. Those. objects not only do not need to be freed, it is simply forbidden by the compiler. The gain is significant - in the transparency of the code, and in the speed of execution, and, of course, in time spent on debugging.

We first describe the corresponding interfaces:

@interface Persone : NSObject { NSInteger number; } @property (nonatomic, copy) NSString *name; //   . - (Persone *)execution; @end #import "Common.h" @interface Elf : Persone @end #import "Common.h" @interface Deer : Persone @end 

As we see. everything is very simple and does not cause any additional questions.

With Santa's interface all the more interesting.

 #import "Common.h" @interface Santa : Persone @property (nonatomic) BOOL isBusy; //  ?  \ . - (Persone *)wakeUp:(NSArray *)group; //. , .    . . ! @end 

According to the condition of the problem, one of the two types of groups can wake up Santa. But, there may be surprises. For example, Santa can not sleep, at the moment when the group will be assembled, and accordingly, an understanding of whether the boss can be disturbed is required.

In each of the interfaces there is a mysterious file that may cause confusion:

#import "Common.h" But with it everything is simple - it describes the value of the constants used in the program, as well as some other header files:

 #import "Persone.h" #import "Deer.h" #import "Elf.h" #import "Santa.h" #import "Groups.h" #define kAllMessages 1 //    ,      . #define kGroupDeers @"Deer" //    . #define kGroupElfs @"Elf" //    . #define kMontsDeer 12 //      1-12. #define kMontsElf 18 //     . 1-18. #define kMontsSanta 4 //    . #define countElfInGroup 3 //     ,    . #define countDeerInGroup 9 //     ,    . 

There remains the last significant interface, which is intended for the information of persons of the same type in groups:

 #import "Common.h" @interface Groups : NSObject { NSMutableDictionary *groups; //  . } - (Groups *)add:(Persone *)persone; //     . - (NSArray *)ready; //   . @end 

Implementation:

It is quite obvious that to solve our problem we need one and only one Santa, one and only one mechanism of forming groups and an arbitrary number of instances of Deer and Elves.

Let's start with a simple ... First, create the Deer.

 #import "Common.h" @implementation Deer static int count; @synthesize name; - (id)init { if(count >=9) return nil; //      9. self = [super init]; if (self) { count++; number = count; self.name = kGroupDeers; } return self; } 

The initializer is quite stereotypical and does not need any explanation. The superclass has a name property, which we will use later in the form of a variable containing the key values ​​for the dictionary.

 - (void)eat { dispatch_async(dispatch_get_global_queue(0, 0), ^{ NSInteger month = (arc4random() % kMontsDeer) + 1; #if kAllMessages NSLog(@"%d-      %d ", number, month); #endif [NSThread sleepForTimeInterval:month]; #if kAllMessages NSLog(@"%d-    ", number); #endif dispatch_async(dispatch_get_main_queue(), ^{ [[[Groups alloc] init] add:self]; }); }); } 

And here it is more interesting. The eat method starts a separate thread of execution for the current instance of the Deer. That is, each Deer, and in the future and the Elves, we will live and prosper in separate streams. Despite the complex bracket construction, in reality, everything is extremely simple here: dispatch_async (dispatch_get_global_queue (0, 0), ^ {}); - puts what is described in brackets into the execution queue. The argument dispatch_get_global_queue means a global queue. (0, 0) - the first 0 indicates the priority, by default, Normal, the second 0 does not mean anything at all in the iOS SDK, and is reserved for further development of the technology.

Inside the described block we find: NSInteger month = (arc4random ()% kMontsDeer) + 1; - getting a random number of months of grazing by the Deer. The range of integers obtained in this formula is from 1 to kMontsDeer. The following is a delay in the execution of the process - a kind of pasture emulation - [NSThread sleepForTimeInterval: month]; And completing this method is adding to a similar queue but already for the main thread of some code. This some code is another queue, but already created at the level of the current program. As we remember, the group dispatcher should have one and only one for the entire application. In other words - he is singleton. Therefore, the creation of its instance through the initializer, in fact, will return to us an already existing instance, if it was created by someone earlier. The add method will simply add the current Stag to the receive queue.

 - (Persone *)execution { [self eat]; return self; } @end 

The latter method only provides the coordination of basic interfaces. Those. creates a template execute method.

In the same way we create a class for elves.

 #import "Common.h" @implementation Elf static int count; @synthesize name; - (id)init { if(count >=10) return nil; //      10. self = [super init]; if (self) { count++; number = count; self.name = kGroupElfs; } return self; } - (void)work { dispatch_async(dispatch_get_global_queue(0, 0), ^{ NSInteger month = (arc4random() % kMontsElf) + 1; #if kAllMessages NSLog(@"   %d .   %d ", number, month); #endif [NSThread sleepForTimeInterval:month]; #if kAllMessages NSLog(@"  %d ", number); #endif dispatch_async(dispatch_get_main_queue(), ^{ [[[Groups alloc] init] add:self]; }); }); } - (Persone *)execution { [self work]; return self; } @end 

Divide and win

The task of the Group class is to dispatch and form groups. The mechanism is quite simple. Each person is queued for his type, (i.e. Elves to elves, Deer to deers), and then, if the required number of copies is collected in a queue, is removed from there and placed in a buffer specially designed for them - Santa -Claus.

 #import "Common.h" @implementation Groups static Groups *instance; - (id)init { if(instance!=nil) return instance; self = [super init]; if (self) { groups = [NSMutableDictionary dictionary]; instance = self; } return self; } - (Groups *)add:(Persone *)persone { NSMutableArray *queue = [groups objectForKey:persone.name]; //     . if(queue == nil) queue = [NSMutableArray array]; [queue addObject:persone]; //    . [groups setValue:queue forKey:persone.name]; #if kAllMessages NSLog(@"  \"%@\"  %d", persone.name, queue.count); #endif Santa *santa = [[Santa alloc] init]; if(santa.isBusy == NO) [santa wakeUp:[self ready]]; return self; } - (NSArray *)queueElf { NSMutableArray *queue = [groups objectForKey:kGroupElfs]; if(queue.count < countElfInGroup) return nil; //     . NSMutableArray *group = [NSMutableArray array]; for (int i=0; i<countElfInGroup; i++) // 3    ... [group addObject:[queue objectAtIndex:i]]; for (id item in group) // ...    . [queue removeObject:item]; [groups setValue:queue forKey:kGroupElfs]; return [group copy]; } - (NSArray *)queueDeer { NSMutableArray *queue = [groups objectForKey:kGroupDeers]; if(queue.count < countDeerInGroup) return nil; //     . NSArray *group = [queue copy]; for (id item in group) //   . [queue removeObject:item]; [groups setValue:queue forKey:kGroupDeers]; return group; } - (NSArray *)ready { NSArray *group = [self queueElf]; if(group!=nil) return group; return [self queueDeer]; } 

As mentioned earlier, this class is a singleton. Being written using ARC, its creation seems to be extremely simple. It is assumed that an instance of this class will be used only within the main thread. This will prevent the problem when the same instance of the dictionary implementing the queues is accessed from different threads. Of course, this creates some overhead in terms of execution time, but, they are so insignificant that they can be neglected.

The most interesting place of this code is the following section:

 Santa *santa = [[Santa alloc] init]; if(santa.isBusy == NO) [santa wakeUp:[self ready]]; 

We, like with the group dispatcher, receive a copy of our Santa, and then we will be him, stuffing the resulting group into his chambers. No matter what. For this, it will be Deers or Elves - (NSArray *) ready method answers

To my horror, I noticed that in preparing the article I confused the conditions of the problem. Those. in my case, all other things being equal, Santa serves elves, not deer. In addition, I have a maximum number of elves equal to 10, not 9. Both of these faults are easily fixable. For example, the method changes to the following:

 - (NSArray *)ready { NSArray *group = [self queueDeer]; if(group!=nil) return group; return [self queueElf]; } 

However, in the future, when it comes to the protocols of work, such an amended condition is assumed.

Madrigal

And so we got to the final character of our song - Santa:

 #import "Common.h" @implementation Santa static Santa *santa; static int count; BOOL doWork; @synthesize isBusy; static int groupNumber; - (id)init { if(santa!=nil) return santa; self = [super init]; if (self) { santa = self; count++; number = count; NSLog(@">>  %d- ", number); } return self; } - (void)sleep { NSLog(@">>  %d ....", number); } - (Santa *)wakeUp:(NSArray *)group { if(group == nil) return self; NSLog(@">>  %d .... ", number); [self work:group]; //    . return self; } - (BOOL)isBusy { return doWork; } - (void)work:(NSArray *)group { if(doWork == YES) return; doWork = YES; __block Santa *santa = self; __block NSArray *currentGroup = group; __block NSInteger IDGroup = ++groupNumber; dispatch_async(dispatch_get_global_queue(0, 0), ^{ NSInteger month = (arc4random() % kMontsSanta) + 1; NSLog(@">>    %d- .   %d  c  ID %d", number, month, IDGroup); [santa portalIn:currentGroup]; [NSThread sleepForTimeInterval:month]; NSLog(@">>  %d   c  ID %d", number, IDGroup); dispatch_async(dispatch_get_main_queue(), ^{ doWork = NO; [[santa portalOut:currentGroup] sleep]; //     . }); }); } - (Persone *)execution { NSLog(@"Yahoo!!!"); return self; } - (Santa *)portalIn:(NSArray *)group { if([[group objectAtIndex:0] isKindOfClass:[Elf class]]) NSLog(@">>  %d    ", number); if([[group objectAtIndex:0] isKindOfClass:[Deer class]]) NSLog(@"\n\t\t      yp p\n\t\t  p p  y p.\n\t\t y,  p  p p,\n\t\t y  p,    p"); return self; } - (Santa *)portalOut:(NSArray *)group { for (Persone *persone in group) [persone execution]; return self; } 

Before moving on to the most difficult part of the code, you need to briefly stop at two methods:

entrance door method:

 portalIn:(NSArray *)group 

and exit door method:

 portalOut:(NSArray *)group. 

It would have been possible to do without them, but this was the initial condition of the task - to focus attention on the entrance and exit doors.

The execution method only signals that a call has been made to this instance of Santa. Every time we manipulate Santa, we show his number. We do this for reasons that the reader is convinced that all actions occur with a single Santa throughout the duration of the action.

Method

  wakeUp:(NSArray *)group 

admits the group to the emergency rooms and wakes up Santa. All the main things happen in the work method.

First, we check if Santa is busy.

 if(doWork == YES) return; 

This is a redundant check and can be removed. But, better we will miss one wake-up call than something goes according to plan. Then we post the sign “busy” and lock the entrance doors:

 doWork = YES; 

Next, we need to prepare some variables for use within the threads, background and main:

 __block Santa *santa = self; __block NSArray *currentGroup = group; __block NSInteger IDGroup = ++groupNumber; 

If this is not done, an exception may be raised to accessing unshared resources. The above simple manipulation ensures that this does not happen. It should be noted here that the double underscore is used in the __block keyword. those. the _ character is used twice! Then we create a separate stream for Santa, as we did with Deer and Elves, and release the incoming group to Santa's chambers using the entrance door method: [santa portalIn: currentGroup];

Depending on who came to Santa, he does one of two things - either holding a planning meeting or delivering presents. When the work is completed, Santa unlocks the door and sends the guests to their former place of work. All the magic of the task lies in the exit door method. As is known, “Iteration is peculiar to man, recursion is divine.” - L. Peter Deutsch. Since this method is called within the main thread, it can safely recursively call the execution of a new task by person. An elf or a deer, once born, will perform its duties indefinitely until it is stopped by a direct shot to the head from the SIGABRT .

And now it's time for the song.

In a convenient place you need to place the creation code of our people. I have it located in - (void) viewDidLoad

Verse 1.

  for (int i = 0; i<9; i++) [[[Deer alloc] init] execution]; for (int i = 0; i<10; i++) [[[Elf alloc] init] execution]; for (int i = 0; i<4; i++) [[[Santa alloc] init] execution]; 

But since we have already eaten the dog to create threads, why not wrap it all in a separate thread?

Verse 2.

  dispatch_async(dispatch_get_global_queue(0, 0), ^{ for (int i = 0; i<9; i++) [[[Deer alloc] init] execution]; for (int i = 0; i<10; i++) [[[Elf alloc] init] execution]; for (int i = 0; i<4; i++) [[[Santa alloc] init] execution]; }); 

It is quite obvious that since each person lives in a separate stream, then the sequence of creating each person will be determined only by chance. What to do? Especially for this, there is a very elegant way to indicate the flow creation sequence:

Verse 3.

 dispatch_async(dispatch_get_global_queue(0, 0), ^{ dispatch_group_t group = dispatch_group_create(); dispatch_group_async(group, dispatch_get_global_queue(0, 0), ^{for (int i = 0; i<30; i++) [[[Deer alloc] init] execution];}); dispatch_group_async(group, dispatch_get_global_queue(0, 0), ^{for (int i = 0; i<30; i++) [[[Elf alloc] init] execution];}); dispatch_group_notify(group, dispatch_get_global_queue(0, 0), ^{for (int i = 0; i<10; i++) [[[Santa alloc] init] execution];}); }); 

In the first background thread, a group is created within which the creation of the Reindeer and the Elves begins. And when they are completed, the thread starts to create Santa.

If in the first cases the protocol is approximately like this:
>> 1-
1- 6
2- 7
3- 9
4- 4
5- 3
Yahoo!!!
7- 5
9- 2
Yahoo!!!
Yahoo!!!
Yahoo!!!
6- 8
3 . 15
5 . 17
4 . 10
2 . 16
8- 3


In the latter case, it will be something like this:

1- 7
4- 5
3- 12
2- 7
5- 3
6- 4
7- 7
8- 11
9- 6
1 . 11
2 . 2
3 . 16
4 . 4
5 . 16
6 . 1
7 . 2
8 . 14
9 . 15
10 . 3
>> 1-
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
Yahoo!!!
6
"Elf" 1
2
"Elf" 2



The study of the logs of this application is a very interesting task. But since they are infinitely long, I will give only references, for those who want to delve into the sequence of actions, or to offer my own more optimal way to solve the problem. Below I also provide a link to the source code of the application.

What could be interesting in the logs? The fact is that the different values ​​of the initial constants provide for completely different behavior of the characters. For example, during the initial debugging, I found that Santa could never start delivering presents, as he would be constantly busy with the routine of meetings. After a long and unsuccessful search for errors in the code, it was found that everything fits within the standard statistical model: if the duration of the task at the Elf is too short (3-4) months, then groups will be formed so often that the Reindeer will wait indefinitely in queues (recall that the problem was solved with the inversion of the condition).

What is the practical value of this exercise in terms of logistics? Suppose you are a project manager for Scrum . Since you have to hold daily meetings, sometimes turning into plenary sessions of the USSR Supreme Soviet, it may be that the Elf will not have time to develop, and the project will go on to the stage of constant time pressure . A similar situation can occur in the team leader lead server-side developer developer client clients, with the only difference that the team lead, as a rule, ceases to perform its immediate duties (sleep (sleep);), and is forced to endlessly rake the code of Reindeer or malicious Elves And if you break away from the sphere of IT, then the coefficients of the task of Santa, are fundamental in the process of loading / unloading / storing goods. In general, it is easy enough to find analogues in real life.

Conclusion:

In the above code, there are some not quite obvious techniques that need to be said separately.

one)

 NSMutableArray *group = [NSMutableArray array]; [skip] return [group copy]; 

Programmers who still work without ARC will be horrified by such code. And, most likely, they will use something like [[NSArray arrayWithArray: group] autorelise]; for the object to collapse to the minimum functionality. However, in ARC, this need is eliminated, and the code becomes more transparent.

2)

 - (Santa *)portalOut:(NSArray *)group { [skip] return self; } 

The method returning the current object allows reducing the listing due to the use of the objective-c prisobochnoy record: [self portalOut: currentGroup] sleep]; For fans of functional languages ​​and those who like extensible C # methods (which are actively used in LINQ), this is like a balm for the soul ... Of course, for debugging purposes, it makes sense to split the method call into two lines.

3)

 #if kAllMessages NSLog(@"   %d .   %d ", number, month); #endif 

The kAllMessages precompilation directive is contained in the Common.h file. If you uncomment it, you will see all the actions performed by the characters, as in the above logs. By default, only Santa's actions are displayed in the console. I did not dwell on the console output in the article, since, as a rule, this is the first thing with which an acquaintance begins when studying objective-c.

Categorical imperative:

It took several times more time to write an article than to write an application and debug it. If you are not yet using an asynchronous manager, it's time to test it and evaluate the ease of implementation. And let him throw a stone at me who thinks that Apple was able to solve this problem without reaching the pinnacle of grace for multi-threaded applications.

References:

Application source code (iOS SDK 5, XCode 4.3).
Application log without thread execution groups.
Application log with a thread execution group.
An abbreviated log of Santa's work in a thread group.

Summary:

The article describes the mechanism for creating a multi-threaded application in the language of objective-C in relation to iOS SDK 3+. As an example, the task of Santa from the field of logistics was given. Source code demonstrates the use of asynchronous dispatcher.

 dispatch_async, 

queues of the main application thread

 dispatch_get_main_queue() 

the background flow of the application

  dispatch_get_global_queue 

and delay interval

  [NSThread sleepForTimeInterval:month]; 

. To create additional queues, linear arrays and a dynamic dictionary provided by Objective-C were used.

UPD: Updated the link to the source code.