TweetFollow Us on Twitter

May 92 - KON & BAL'S PUZZLE PAGE

KON & BAL'S PUZZLE PAGE

SLEEPING BEAUTY

KONSTANTIN OTHMER AND BRUCE LEAK

See if you can solve this programming puzzle, presented in the form of a dialog between Konstantin Othmer (KON) and Bruce Leak (BAL). The dialog gives clues to help you. Keep guessing until you're done; your score is the number to the left of the clue that gave you the correct answer. These problems are supposed to be tough. If you don't get a high score, at least you'll learn interesting Macintosh trivia.


During the development of QuickTime, a number of interesting bugs reared their ugly heads. Try to figure out this one before KON does.

120 BAL Here's the problem: When you play a movie on a Macintosh IIfx the machine hangs after about six hours. If you turn off the sound, or try it on any Macintosh other than an fx, it doesn't hang.

KON How does it hang? Is the Macintosh locked up?

115 BAL Well, the movies aren't playing. They just all freeze about halfway through. Menus still work, though. You can even switch to the Finder and click between windows and move icons around, but when you launch an application or open a folder, the Finder draws one of the zoom rectangles and then hangs.

KON Like a time bomb. Can you get into MacsBug?

110 BAL Yeah.

KON Whew. For a second I thought this was going to be really tough. You've got MacsBug, so what's the problem?

BAL I don't know, you tell me.

KON How do movies get time? SystemTask or something?

105 BAL No, you have to call MoviesTask.

KON Figures. So I set a break on MoviesTask; is it getting called?

100 BAL Nope.

KON The application is supposed to call it?

95 BAL Yep.

KON So is WaitNextEvent getting called?

90 BAL Nope.

KON But menus work???

85 BAL Yep.

KON WaitNextEvent is being called with a bogus sleep time. I set a breakpoint on it, pull down a menu, and see what the sleep time parameter is.

80 BAL Now you're thinking, Kon! But no. The sleep time is 1, just as it's supposed to be.

KON Hmmm. So I trace 50 times and see where I'm spinning.

75 BAL There's a bunch of stuff going on; it's not just some simple loop.

KON So I record A-traps.

70 BAL There are three traps getting called: ABF7 from inside MF, A0DD (PPCToolbox) from a big block in the system heap that's not QuickTime, and A030 (EventAvail) from a 'scod' resource that's different from the block calling ABF7.

KON There are no null events coming through to the application, so MoviesTask never gets called. The sleep time must never be expiring. Are ticks running?

BAL How do you figure that out?

KON I DM ticks, continue executing, and then DM ticks again.

65 BAL Ticks doesn't change.

KON It's updated by some hardware mechanism at interrupt time, right?

BAL Sure, a hardware mechanism . Is that what they teach you at Caltech?

KON OK, OK. There's a heartbeat task that generates a level-1 interrupt that updates ticks, right?

60 BAL Yeah.

KON So is the level-1 interrupt happening?

BAL How do you check that?

KON I know from reading this cool develop  column that the level-1 interrupt vector is at location $64, so I set a break there and see if it's firing.

55 BAL Wait a second. That's the way ticks are updated on every Macintosh except the fx. This problem happens only on an fx.

KON Why is the fx different?

50 BAL The guy that designed the hardware assumed that the heartbeat task--and thus ticks-- was supposed to happen every 60th of a second. Unfortunately it's supposed to be every 60.14th of a second or something, so Gary Davidian fixed it by installing a Time Manager task that updates ticks. The extended Time Manager, found in System 6.0.4 and later, adds a drift-free mode for Time Manager callbacks. This allows for accurate scheduling of periodic events without long-term drift. With the extended Time Manager, the next callback is scheduled with respect to when the current callback should have fired, rather than the current time. So as of System 6.0.4 there are two types of Time Manager tasks: the regular ones and the drift-free ones. Ticks are updated via a drift-free task, so they advance accurately over time.

KON Hmmm. So is the Time Manager task that updates ticks getting called?

45 BAL Obviously not; ticks aren't changing.

KON How are the tasks in the queue organized?

40 BAL They're kept in the order that they fire in.

KON So where is the ticks task in the queue?

35 BAL Well, it's not the first one, and the first one is scheduled for sometime tomorrow.

KON Fine. I leave and come back tomorrow. Does my movie start playing?

30 BAL It could be. But we're shipping before then.

KON So the first element is getting messed up and never completes. Then none of the other items in the queue get executed because they're all deltas off the first element and the movies hang.

25 BAL Now we're getting somewhere.

KON So how is that first element getting confused?

BAL Whose problem is this?

KON OK. Who owns the first item?

BAL How do you figure that out?

KON I do an IL to see what traps it's calling. I see where it is in the heap. I set a breakpoint on it, force it to fire, and see what it does.

20 BAL You're knee deep in spaghetti. You could probably figure it out this way but it's pretty nasty.

KON OK. I break on InsTime to see who installs it. I break on PrimeTime to see who starts it up. I figure out whether it's using InsTime or InsXTime.

15 BAL The PrimeTime comes from an 'snth' resource. It was installed with InsXTime.

KON Aha! The Sound Manager. That's why it works when the sound is turned off.

BAL They don't pay you enough, Kon.

KON So how does this element get updated in the queue? Don't Time Manager tasks call PrimeTime to reschedule themselves?

10 BAL Yeah.

KON So is someone calling PrimeTime on the Sound Manager task with a bogus value?

5 BAL Not really. It always calls PrimeTime with a value of 0, indicating that it wants to be called right away. The Sound Manager does this since it's not reentrant. By scheduling a task, it knows it won't be called until it's finished servicing the current interrupt, avoiding reentrancy problems.

KON I'm sure everyone that's reading this has figured it out by now. I know I have.

BAL You're bluffing again, Kon.

KON It's easy. Since the drift-free Time Manager schedules tasks based on when they should occur, and since this sound task is using a count of 0 when calling PrimeTime, its backlog gets bigger and bigger. So each PrimeTime call schedules an event that should have occurred further and further in the past. The task is executed immediately, of course, but the backlog builds. It always puts this element at the head of the queue, but eventually it overflows the long that contains the backlog, and the scheduling time becomes incredibly large. There are about 4 billion microseconds in a long, which is about an hour. The Time Manager counts in units that are about 20 microseconds, so it would take about 20 hours to overflow. Take away a bit for signed math and another because it's calculating scheduling times, and I would guess it should hang about once every 5 hours. It must have taken forever to find that one.

BAL Yeah, it was a drag. We fixed it before we shipped QuickTime, of course. But it's just the kind of thing that makes scheduling software projects so hard.

KON Nasty.

BAL Yeah.

KONSTANTIN OTHMER AND BRUCE LEAK have been puzzling about reality, life, the universe, and even computers for a long time. Since the great success of their Graphics '90 World Tour, which included peace-keeping, hostage-freeing, and wall-smashing, they settled down, shipped a few QuickDraw packages, and cleaned out their closets. Then came the coup: da division of da Union. Konstantin got QuickDraw, 200 rubles, and a guaranteed spot at the front of the bread line. Official party line on Bruce: "vacationing in the Crimea." Bruce was actually working on the first QuickDraw spinoff. To provide a seamless upgrade path, and to leverage off of brand awareness, he decided to call this project QuickTime. *

SCORING

  • 100-120 Members of the QuickTime team and their immediate family aren't eligible.
  • 75-95 Scores count only on the first reading!
  • 50-70 Not bad--buy yourself an ice cream.
  • 25-45 The next one will be easier.
  • 5-20 Stick to word searches.*

Thanks to Gary Davidian and Jean-Charles Mourey for reviewing this column.*

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Monolingual 1.6.4 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. If you use your computer in only one (human) language, you... Read more
CleanApp 5.0 - Application deinstaller a...
CleanApp is an application deinstaller and archiver.... Your hard drive gets fuller day by day, but do you know why? CleanApp 5 provides you with insights how to reclaim disk space. There are... Read more
Fantastical 2.0 - Create calendar events...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event details... Read more
Cocktail 8.2 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Direct Mail 4.0.4 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
jAlbum Pro 12.6 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.6 - Create custom photo galler...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
Lyn 1.5.9 - Lightweight image browser an...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
Sublime Text 3080 - Sophisticated text e...
Sublime Text is a sophisticated text editor for code, markup, and prose. You'll love the slick user interface, extraordinary features, and amazing performance. Goto Anything. Use Goto Anything to... Read more
WALTR 1.0.11 - Drag-and-drop any media f...
WALTR is designed to make it easy to upload and convert any music or video file to an iPad or iPhone format for native playback. It supports a huge variety of media file types, including MP3, MP4,... Read more

Bio Inc's New Expansion is Infectin...
Bio Inc., by DryGin Studios, is the real time strategy game where you infect a human body with the worst virus your evil brain can design. Recently, the game was updated to add a whole lot of new features. Now you can play the new “Lethal”... | Read more »
The Monocular Minion is Here! Despicable...
Despicable Me: Minion Rush, by Gameloft, is introducing a new runner to the mix in their latest update. Now you can play as Carl, the prankster minion. Carl has a few new abilities to play with, including running at a higher speed from the start.... | Read more »
Dungeon of Madness (Games)
Dungeon of Madness 1.0.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.0 (iTunes) Description: Dungeon of Madness is an action game where you rotate tiles to create our own route. Help the hero by connecting the... | Read more »
Filters for iPhone (Photography)
Filters for iPhone 1.0 Device: iOS iPhone Category: Photography Price: $.99, Version: 1.0 (iTunes) Description: | Read more »
Jump'N'Shoot Attack (Games)
Jump'N'Shoot Attack 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: A mobile game for gamers! Join Louise Lightfoot, the legendary "Master of Jumping and Shooting", on her mission to save... | Read more »
Space Bounties Inc. (Games)
Space Bounties Inc. 1.4 Device: iOS Universal Category: Games Price: $1.99, Version: 1.4 (iTunes) Description: SuperGameDroid: 4/5 "Satisfying futuristic RPG combat, high replay value, and a heavy dose of nostalgia make Space... | Read more »
Gamebook: Pocket RPG (Games)
Gamebook: Pocket RPG 1.0.11 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.11 (iTunes) Description: Walk into the Land of Lanthir Lamath ruled by wicked skeletons and fight for your life in a thrilling adventure.... | Read more »
Kids Can Mix, Match, and Catch with Tata...
Tatadada MixMatch, by Tatadada Ltd, is a mobile version of the classic game of mix & match. The game uses brightly colored creatures to train your children's pattern matching skills and hand-eye coordination. It's aimed at children around age 5... | Read more »
The Trace: Murder Mystery Game (Games)
The Trace: Murder Mystery Game 1.2.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.2.0 (iTunes) Description: | Read more »
This Week at 148Apps: March 16-20, 2015
Spring Roars In At 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above... | Read more »

Price Scanner via MacPrices.net

Logitech Says MX Master Is Its Most Advanced...
Logitech’s new MX Master Wireless Mouse incorporates the best of Logitech’s many computer mouse innovations into a striking hand-sculpted design. The company claims that the MX Master creates a new... Read more
Save up to $300 on a new Mac, $30 on an iPad,...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store lowered prices on Apple Certified Refurbished 2014 MacBook Airs recently, with models now available starting at $679. An Apple one-year warranty is included with each MacBook, and... Read more
Mac Notebook Evolution; A Desktop Replacement...
More often than not right from the beginning, Apple’s Macs have tended to skew toward small. The original Macs were called “compacts,”, and notwithstanding a few exceptions like the honking Big Mac... Read more
13-inch 1.4GHz/128GB MacBook Air (Apple refur...
The Apple Store has Apple Certified Refurbished 2014 13″ 1.4GHz/128GB MacBook Airs available for $759 including free shipping plus Apple’s standard one-year warranty. Their price is $240 off original... Read more
YEP! Alternative Browser for iOS Now Supports...
Pfaeffikon, Switzerland based Power App AG has announced the release of an update to their Yep! Web Browser (v1.3.0) for iOS8 iPhone and iPad. Yep! hit the App Store shortly after the release of iOS... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $250 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
Clearance 13-inch Retina MacBook Pros availab...
B&H Photo has leftover 2014 13″ Retina MacBook Pros on sale for up to $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1098... Read more
Clearance 2014 MacBook Airs on sale for up to...
B&H Photo has MacBook Airs on sale for up to $180 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $789.99 110 off original MSRP - 11″ 256GB... Read more
Apple refurbished Time Capsules available for...
The Apple Store has certified refurbished Time Capsules available for $100 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $199, $100... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - D...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Systems Engineer - Pre Sales, Educat...
…is responsible for proactively providing technical expertise to drive sales of Apple solutions into assigned accounts. The SE architects, validates, and assists in Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.