Sunday, September 12, 2010

CRT Concurrency Runtime: Task Scheduler

The Task Scheduler schedules and coordinates tasks at run time. A task is a unit of work that performs a specific job. The Task Scheduler manages the details that are related to efficiently scheduling tasks on computers that have multiple computing resources.

Windows OS provides a preemptive kernel-mode scheduler,it's a round-robin, priority-based mechanism that gives every task exclusive access to a computing resource for a given time period, and then switches to another task.Although this mechanism provides fairness (every thread makes forward progress), it comes at some cost of efficiency.For example, many computation-intensive algorithms do not require fairness. Instead, it is important that related tasks finish in the least overall time. Cooperative scheduling enables an application to more efficiently schedule work.

Cooperative scheduling is a mechanism that gives every task exclusive access to a computing resource until the task finishes or until the task yields its access to the resource.

The user-mode cooperative scheduler enables application code to make its own scheduling decisions. Because cooperative scheduling enables many scheduling decisions to be made by the application, it reduces much of the overhead that is associated with kernel-mode synchronization.

The Concurrency Runtime uses cooperative scheduling together with the preemptive scheduler of the operating system to achieve maximum usage of processing resources.

Scheduler Design

The concurrency runtime provides the interface Scheduler to implement a specific scheduler adapted to application needs.

Let's discover classes implementing this inerface, for that we can execute the following CQL request:




The concurrency runtime provides two implementations of scheduler, ThreadScheduler and UMSThreadScheduler, and as shown in the dependency graph the SchedulerBase contains all common behavior of these two classes.

Is the Scheduler flexible? a good indicator of flexiblity is to search for all abstract classes used by the scheduler.




As shown in the dependency graph the Scheduler use many abstract classes,it enforces the low coupling, and make the scheduler more flexible, so adapting it to other needs will be easy.


Let's discover the role of each absract class used by the scheduler, for that we will discuss its responsabilities .There are three major responsabilities assigned to the Task Scheduler:

1) Getting Resources(Processors,Cores,Memory):

When the scheduler is created it ask for resources from runtime resource manager as explained in this article.

The scheduler communicate with resource manager using IResourceManager, ISchedulerProxy and IScheduler interfaces.

Resources given by resource manager use scheduler policy to allocate resources to the scheduler.
The policy as shown in this dependency graph is assigned when the scheduler is created.



The concurrency runtime create a default scheduler if no scheduler exists by invocking GetDefaultScheduler method, and a default policy is used.
The Task Scheduler enables applications to use one or more scheduler instances to schedule work, and an application can invoke Scheduler::Create to add another scheduler that uses a specific policy.

The Concurrency::PolicyElementKey enumeration defines the policy keys that are associated with the Task Scheduler.



Here's an article explaining the utility of each policy key, and the default value of each key.

The following collaborations between the scheduler and resource manager shows the role of each interface concerned by the allocation.

- Ask for resource allocation:




- Getting resources from resource manager:



2)Manage Task Queues:

When Schedeluer is created, tasks could be assigned to it to be executed, the Scheduler store tasks into queues.to enforce the cohesion of classes, the queues are not managed directly by the ThreadScheduler class but by ScheduleGroupBase class.

A schedule group affinitizes, or groups, related tasks together. Every scheduler has one or more schedule groups. Use schedule groups when you require a high degree of locality among tasks, for example, when a group of related tasks benefit from executing on the same processor node.

As shown in the following graph, the runtime provides two kind of ScheduleGroup: FairScheduleGroup and CacheLocalScheduleGroup, choosing between thoses two groups as it will be explained later impact the algorithm of choosing the next task to execute by the scheduler.



Every Scheduler has a default schedule group for every scheduling node.The runtime creates one scheduling node for every processor package or Non-Uniform Memory Architecture (NUMA) node. If you do not explicitly associate a task with a schedule group, the scheduler chooses which group to add the task to.

As shown in the following dependency graph ,The schedulingRing is responsable of managing Scheduler Groups, it contains a list of groups and create them.




The Schedule group contains three kind of queues:

1) FIFO Queue

This queue contains lightweight tasks,a lightweight task resembles the function that you provide to the Windows API CreateThread function. Therefore, lightweight tasks are useful when you adapt existing code to use the scheduling functionality of the Concurrency Runtime.

A lighweight task is represented by RealizedChore class, and the FIFO queue of the schedule group is represented by the field m_realizedChores.

Let's search for methods using directly this queue:





So we can add a lightweight task to the group by invoking ScheduleGroupBase::ScheduleTask or Scheduler::ScheduleTask.




Here's an interesting article talking about lighweight tasks.

2)Work Stealing queue:

There's only one FIFO queue associated to the schedule group, but the schedule group reference a list of work sealing queues, for each worker thread there's a local queue associated to it.

A thread that is attached to a scheduler is known as an execution context, or just context, so actually this local queue is associated to Context class.

The Context class provides a programming abstraction for an execution context and offer the ability to cooperatively block, unblock, and yield the current context.

And to be sure that only Context create this kind of queue, let's search of method accessing directly to m_workQueues field.



So the context is responsable of creating this queue, and for each context there's a local work stealing queue associated to it.

To illustrate the behavior of the work-stealing algorithm ,let's imagine that we have two worker thread allocated to the scheduler.

As explained before for each worker thread there's a local queue associated with it.



Three tasks in the queue Worker Thread 1, tasks 3 and 4 are waiting to be executed while the 5 is running.


The Dispatch method finds that there is nothing in the queue, so the task 3 is moved, or "stolen" from its original queue, to be distributed the worker thread available.



How we can create a task managed by work stealing queue? for that let's search for methods indirectly invocking the CreateWorkQueue method.

As shown in this dependency graph, this kind of task could be created by using task_group class.



Using task_group to add new task is more better than using Sheduler::ScheduleTask to create lighweight task, indeed the work stealing algorithm optimize better the using of virtual processors allocated to the scheduler.

However ScheduleTask could be better to migrate easilly from the existing code using CreateThread API.


3)Unblocqued Context queue:

The Context class lets you block or yield the current execution context. Blocking or yielding is useful when the current context cannot continue because a resource is not available.
The Context::Block method blocks the current context. A context that is blocked yields its processing resources so that the runtime can perform other tasks. The Context::Unblock method unblocks a blocked context.

When a context is unblocked and it's available to be executed , it's add to runnable context queue, this queue is represented by the field m_runnableContexts.

Here's a dependency graph showing some cases where the context is added to runnable queue:


So the context is added to the queue when it's unblocked or a virtual processor is retired from the scheduler.


3)Dispatching Tasks:

The scheduler try to search for work to execute, a work could be:

- Unblocked context.
- Lightweight task.
- Task in work stealing queues.


And as explained before all these works are stored in queues managed by Schedule groups, and each group is managed by a scheduling ring.

When a virtual processor is allocated to the scheduler a ThreadProxy class is created and associated to this processor. and after the creation the Dispatch method of the ThreadProxy is invoked.
As shown in the following dependency graph and as explained before the concurrency runtime use abstract classes to enforces low coupling, and the real dispatch invoked depends of the implementation choosed by the runtime, this choice is given by the scheduler policy.



The concrete implementation of Dispatch invoke Dispatch Method of the execution context.


Here's a dependec graph showing methods invocked by concrete implementation of Context::Dispatch method:
So the algorithm of searching the next work to execute is implemented by WorkSearchContext class.

Let's discover all classes used directly by WorkSearchContext to acheive its responsability:




The responsability of WorkSearchContext is to give us a WorkItem to execute, it could be InternalContextBase, RealizedChore or _UnrealizedChore.

To understand better the collaboration between these classes , let's search for methods used directly by WorkSearchContext:



So the WorkSearchContext iterate on SchedulingRing and SheduleGroup classes by using SchedulerBase methods.

And for each ScheduleBase we search for RunnableContext, realizedChore or UnrealizedChore.

The WorkSearchContext class is creaed by the VirtualProcessor class, and as shown in the following dependency graph, the algorithm used is specified when the VirtualProcessor is initialized, and for that it ask the Scheduler for the SchedulingProtocol which describe the scheduling algorithm that will be utilized for the scheduler.



The WorkSearchContext will be notified by the algorithm to use by passing it a value from Algorithm enum.



So two algorithmes are implemented by this class to find a work:

- Cache Local algorithm:

This algorithm will look for runnables context within the current schedule group,then realized chores then unrealized chores, if there's no more work in the curent schedule group it look for the next group in the same shedule ring, and when it finish all works in the current schedule ring it look in the next schedule ring.

So the scheduler prefers to continue to work on tasks within the current schedule group before moving to another schedule group.

This algorithm is implemented by WorkSearchContext::SearchCacheLocal method, and as show by this dependency graph, this method search invoke other methods to search for runnable contexts, RealizedChore or _UnrealizedChore.




Another specificity of this algorithm is that the unblocked contexts are cached per virtual-processor and are typically scheduled in a last-in first-out (LIFO) fashion by the virtual processor which unblocked them.

And to verify this behavior, here's a dependency graph of methods invocked when searching for runnable context:




This algorithm is the default algorithm choosen by the scheduler if no one is specified.

- Fair algorithm:

In this case the scheduler prefers to round-robin through schedule groups after executing each task. Unblocked contexts are typically scheduled in a first-in-first-out (FIFO) fashion. Virtual processors do not cache unblocked contexts.

This algorithm is implemented by WorkSearchContext::SearchFair method, and as show by this dependency graph, this method search invoke other methods to search for runnable contexts, RealizedChore or _UnrealizedChore.

Saturday, August 28, 2010

Visual C++ 2010: What’s new for MFC library?

Some years ago i thought that MFC will be obsolete, and no new features will be added, but i was wrong, VS2008 added many features and functionalities, and with VS 2010 i discovered new improvements.

So what's new in MFC 10? to answer to this question i tried to compare the two versions MFC 9 and MFC 10 using CppDepend.

Removed classes:

Let's begin with breaking changes and search for removed classes:

SELECT TYPES WHERE WasRemoved




It was very strange that this class is removed , and to be sure i searched in the code source and i found it inside #ifdef ENABLE_RIBBON_LAUNCH_BUTTON statement.

The only resource i found in the web talking about this change is here , and i dont know if
adding #define ENABLE_RIBBON_LAUNCH_BUTTON is suficient to compile without problem.


Added Classes:

SELECT TYPES WHERE WasAdded AND isClass





What's the new features added by these classes?

CMFCRibbonCollector,CMFCRibbonConstructor,CMFCRibbonInfo:
When i searched in MSDN the utility of these classes , i didnt found any useful informations, so i searched for methods using CMFCRibbonInfo.

SELECT METHODS WHERE IsDirectlyUsing "CMFCRibbonInfo"




The RibbonBar class use CMFCRibbonInfo to save it to xml or load it.


CJumpList,CAppDestinations:
Jump list is a new useful Window7 feature, it adds a new way of interaction beteween user and application.
here's a good article to add JumpList feature with MFC.


CMFCControlContainer:

This class provides a CWnd support for MFC Control containment of Feature Pack controls.

And to know which controls can be contained inside this container, let's search for classes used by CMFCControlContainer::CreateDlgControl.

Here's the result:



So only these MFC feature pack controls are concerned by this container.


CDocument::CDocumentAdapter:

This class implements ATL::IDocument interface required for "Search and Organize" feature.
My first impression when i discovered that implemention was " WOW, MFC use now interfaces to enforce low coupling".

Let's see the impact of using this interface, for that let's search for classes using CDocumentAdapter :

SELECT TYPES WHERE IsDirectlyUsing "CDocument+CDocumentAdapter"



only CDocument use directly this class.

However IDocument is used by other classes like the new class CMFCPreviewCtrlImpl, so this class can work with CDocumentAdapter and also others classes implementing this interface.

And as explained in the comment of CDocumentAdapter code source:

"Search and Organize handlers are implemented in ATL DLLs, which can be MFC or not-MFC based.Internally handlers refer to IDocument interface, whose implementation in the common case should be supplied by a developer. CDocumentAdapter provides this implementation for MFC and basically calls the appropriate methods of the parent CDocument."


CDataRecoveryHandler:
This class autosaves documents and restores them if an application unexpectedly exits, it's used by Restart Manager feature, here's an interesting article talking about it.

Let's search for classes used by CDataRecoveryHandler:

SELECT TYPES WHERE IsDirectlyUsedBy "CDataRecoveryHandler"



CDataRecoveryHandler is highly coupled with other MFC classes like CDocument, CWinApp, CWnd.



Which MFC classes use the recovery feature?

SELECT TYPES WHERE IsDirectlyUsing "CDataRecoveryHandler"



So all these classes benefit of this new feature especially CDocument.

CTaskDialog:
A pop-up dialog box that functions like a message box but can display additional information to the user.
here's an interesting article talking about this feature.

CMFCVisualManagerVS2008,CMFCVisualManagerWindows7:
Gives an application the apparence of a VS2008 or Windows 7 application.


CGestureConfig:
Used for touch feature.

CFolderPickerDialog:
CFolderPickerDialog class implements CFileDialog in the folder picker mode.

CXMLParser,CXMLParserCollection,CXMLParserRoot:
when i dsicovered these classes, i thouth that is concerning xml parsing but when i searched for methods using them i discovered that only CMFCRibbonInfo use them to save or load its description to xml files.

SELECT METHODS WHERE IsDirectlyUsing "CXMLParserRoot"



CMFCZoomKernel,CMFCScanliner, CMFCScanlinerBitmap :
Not yet documented in MSDN, let's discover which classes use them.

SELECT TYPES WHERE IsDirectlyUsing "CMFCZoomKernel"



And we have the same result for the two other classes.


SafeInt classes:

Extends the integer primitives to help prevent integer overflow and lets you compare different types of integers.

here's a video about using SafeInt.

Methods Removed:

SELECT METHODS WHERE WasRemoved




Almost all theses methodes are not removed but only the signature is changed , and some optional parameters are added, however some methods are removed like CCommandManager::ResetAllImages or CPanelDialog::ClipPaint, and one method was renamed from CMFCRibbonBar::GetTabTrancateRatio to CMFCRibbonBar::GetTabTruncateRatio.



Methods Added:

Let's search for all methods added to MFC10

SELECT METHODS WHERE WasAdded




Which features are added by these new methods?

For that we will focus only in the most used classes.

CWnd:

Here's the methods added for CWnd, and almost all methods added concern touch feature and touch gestures.



CFile,CStdioFile,CFileFind:
Many methods of these classes add CAtlTransactionmanager as optional parameter.

Transactional File System is a new technology first introduced in Windows Vista. It enables you to roll back operations made on the file system and registry.

here's a good article about this feature.

CRecentFileList:



New possibilities to add item to recent file list are now available.

CDocument:
Here's the methods added by CDocument:



Two new features concern methods added :

-Supporting Windows Search with MFC
-Rich Preview

Let's discover the changes concerning dependency of CDocument to other MFC classes,and which additional dependencies are added in MFC10, for that Dependency Matrix can be useful, and the sign "+" in the cell representing the dependency indicate that this dependency is new.



So many dependencies are added, especially with new classes added to MFC10 like CDataRecoveryHandler,and also some other inner classes added to CDocument.


CFileDialog:
Here's the methods added by CFileDialog:




A good news is we can now customize CFileDialog by adding what we want in the dialog.


CMDIChildWndEx:
Here's the methods added by CMDIChildWndEx:



Windows7 add a new interesting features like:taskbar Tabs,Taskbar thumbnails and thumbnail previews, and almost all methods added to CMDIChildWndEx concern theses features.


CFrameWnd:

Windows 7 add also some useful features like OverlayIcon and progressbar in the taskbar, and the methods added to CFrameWnd concern these features.





CWinApp:

Almost all methods added to CWinApp concern the ApplicationRecovery support.





Other useful methods are added like CMFCControlRenderer::SmoothResize and CDrawingmanager::DrawRotated.


Methods where visibility was changed:

SELECT METHODS WHERE VisibilityWasChanged



Almost the visibility of all CMFCRibbonTab methods is changed from private to public.

But when i checked the code source the only modification in the class declaration is the adding of DECLARE_DYNAMIC(CMFCRibbonTab) , this macro include "public:" , so i wonder if this visibility changes is only a side effect of adding this macro.

Methods Not Used Anymore:

Some methods become obsolete when upgrading framework version, did MFC10 not use anymore some methods?

To answer to this question let's execute the query :

SELECT METHODS WHERE IsNotUsedAnymore

here's the result:




Theses methods was declared before in multimon.h , the origin of this file goes back to Windows 98 to let compatibility with Windows 95 in the case of multi monitor, here's an interesting article talking about it.
In MFC10 this file is no longer included in mfc files. and MFC10 use directly GetSystemMetrics instead of xGetSystemmetrics.

Wednesday, August 18, 2010

Where's the model for MFC Doc/View Design?

MFC is a good library that wraps Windows API, and it’s also a framework so it provides a structure for your application and influent the design.

We have to be careful when using frameworks, because it impact also the design, and accepting the structure imposed by a specific framework without understanding its impact could be dangerous.

Let’s take a look into Doc/View architecture proposed by MFC and discuss how MVC pattern could be implemented.


Did CDocument/CView implements MVC pattern?

Doc/View architecture as described by many articles is implementing MVC pattern, but where’s the Model, the controller and the view?

Here’s a description from this msdn article:

“The Document-View variant recognizes all three roles of Model-View-Controller but merges the controller into the view. The document corresponds to the model role in MVC. This variant is present in many existing GUI platforms. An excellent example of Document-View is the Microsoft Foundation Class Library (MFC) in the Microsoft Visual C++ environment. The tradeoff of using this variant is that the view and the controller are more tightly coupled.”

So the CDocument is the model and CView merge the view and controller.



But actually the CDocument is not representing only the model , and to proof it let’s discover some CDocument design and methods:

CDocument derives from CCmdTarget to receive events and commands and contains the following methods : AddView, GetFirstViewPosition,GetNextView,UpdateAllViews.

So this class treats events,refresh and manage views, so it have some controller responsability.


Why CDocument is not the good candidate to be the model?


As described below the CDocument contains controller logic, and considering it also as model impact a lot the cohesion of classes, each classe must have a specific responsibility; it makes the design more flexible.

The model must be independent of any framework used, if it can be a POCO classes it will be wonderful, the question is why coupling the model with a specific framework?
high coupling makes the design more rigid, and any evolution or changes will be very difficult, for example if some client ask to provides also webservices, and if our model is highly coupled with CDocument , this evolution will cost a lot, on the other side if it’s independent to CDocument it can be developed more easily.


What’s the conclusion of this story?

  • High cohesion and low coupling are two powerful concepts that assist your design, but their benefits are more visible only if evolutions or changes are needed.
  • Be careful when using external frameworks, and not understanding the design provided by the framework could impact a lot the design quality of your application.

Friday, February 19, 2010

Could we reuse Garbage collector of V8 javascript engine?

V8 javascript engine is well optimized, and use an efficient way to manage memory.
And I wonder if I can use the garbage collector easily in other projects? and to answer to this question we have to talk about coupling metrics.

There is a whole range of interesting code metrics relative to coupling. The simplest ones are named Afferent Coupling (Ca) and Efferent Coupling (Ce). Basically, the Ca for a code element is the number of code elements that use it and the Ce is the number of code elements that it uses.



You can define Ca and Ce for the graph of projects dependencies, the graph of namespaces dependencies, the graph of types dependencies and the graph of methods dependencies of a code base. You can also define the Ca metric on the fields of a program as the number of methods that access the field. This leads to 9 metrics all supported by the tool CppDepend We precise that when computing Ce.

With CppDepend, if you wish to know which methods of your program are massively used you can write the following CQL Query :

SELECT TOP 10 METHODS ORDER BY MethodCa DESC

Being used a lot is not necessarily a problem. However it is still interesting to know which part of your code base is used a lot.

High Efferent Coupling and design flaws

If you wish to know which types of your program are heavy users of other types you just have to write:

SELECT TOP 10 TYPES ORDER BY TypeCe DESC

High Ce might reveal a design problem. Types with high Ce are entangled with many other implementations. The higher the Ce, the higher the number of responsibilities the type has.


What about reusing garbage collector?


The class representing the garbage collector is MarkCompactCollector, this class has a TypeCe equal to 34, but how many types this class use indirectly.

SELECT TYPES WHERE IsUsedBy "v8.internal.MarkCompactCollector"

And there’s the result



And the metric view shows better relation between MarkCompactCollector class and other V8 types:




So it’s very difficult to isolate only the garbage collector mechanism from V8 source code, Maybe in the future the V8 team will isolate this garbage collector, and it will be used in other projects.