diff --git a/AndroidManifest.xml b/AndroidManifest.xml
index 9778d2c..39c5385 100644
--- a/AndroidManifest.xml
+++ b/AndroidManifest.xml
@@ -716,14 +716,15 @@
                     android:mimeType="vnd.android.cursor.dir/voicemails"/>
             </intent-filter>
         </receiver>
-        <service
-            android:name="com.android.phone.vvm.omtp.sync.OmtpVvmSyncService"
-            android:exported="false" />
 
         <service
             android:name="com.android.phone.vvm.omtp.sms.OmtpProvisioningService"
             android:exported="false" />
 
+        <service
+          android:name="com.android.phone.vvm.omtp.scheduling.TaskSchedulerService"
+          android:exported="false" />
+
         <receiver android:name="com.android.phone.vvm.omtp.VvmPackageInstallReceiver"
             androidprv:systemUserOnly="true">
             <intent-filter>
diff --git a/src/com/android/phone/Assert.java b/src/com/android/phone/Assert.java
index d4233b2..143e66f 100644
--- a/src/com/android/phone/Assert.java
+++ b/src/com/android/phone/Assert.java
@@ -24,17 +24,39 @@
  */
 public class Assert {
 
+    private static Boolean sIsMainThreadForTest;
+
     public static void isTrue(boolean condition) {
         if (!condition) {
             throw new AssertionError("Expected condition to be true");
         }
     }
 
+    public static void isMainThread() {
+        if (sIsMainThreadForTest != null) {
+            isTrue(sIsMainThreadForTest);
+            return;
+        }
+        isTrue(Looper.getMainLooper().equals(Looper.myLooper()));
+    }
+
     public static void isNotMainThread() {
+        if (sIsMainThreadForTest != null) {
+            isTrue(!sIsMainThreadForTest);
+            return;
+        }
         isTrue(!Looper.getMainLooper().equals(Looper.myLooper()));
     }
 
     public static void fail() {
         throw new AssertionError("Fail");
     }
+
+    /**
+     * Override the main thread status for tests. Set to null to revert to normal behavior
+     */
+    @NeededForTesting
+    public static void setIsMainThreadForTesting(Boolean isMainThread) {
+        sIsMainThreadForTest = isMainThread;
+    }
 }
diff --git a/src/com/android/phone/vvm/omtp/VvmPhoneStateListener.java b/src/com/android/phone/vvm/omtp/VvmPhoneStateListener.java
index 64b37c6..1cb23d4 100644
--- a/src/com/android/phone/vvm/omtp/VvmPhoneStateListener.java
+++ b/src/com/android/phone/vvm/omtp/VvmPhoneStateListener.java
@@ -16,7 +16,6 @@
 package com.android.phone.vvm.omtp;
 
 import android.content.Context;
-import android.content.Intent;
 import android.telecom.PhoneAccountHandle;
 import android.telephony.PhoneStateListener;
 import android.telephony.ServiceState;
@@ -25,6 +24,7 @@
 import com.android.phone.PhoneUtils;
 import com.android.phone.vvm.omtp.sync.OmtpVvmSourceManager;
 import com.android.phone.vvm.omtp.sync.OmtpVvmSyncService;
+import com.android.phone.vvm.omtp.sync.SyncTask;
 import com.android.phone.vvm.omtp.sync.VoicemailStatusQueryHelper;
 import com.android.phone.vvm.omtp.utils.PhoneAccountHandleConverter;
 
@@ -76,10 +76,7 @@
                         .v(TAG, "Signal returned: requesting resync for " + subId);
                 // If the source is already registered, run a full sync in case something was missed
                 // while signal was down.
-                Intent serviceIntent = OmtpVvmSyncService.getSyncIntent(
-                        mContext, OmtpVvmSyncService.SYNC_FULL_SYNC, mPhoneAccount,
-                        true /* firstAttempt */);
-                mContext.startService(serviceIntent);
+                SyncTask.start(mContext, mPhoneAccount, OmtpVvmSyncService.SYNC_FULL_SYNC);
             } else {
                 VvmLog.v(TAG,
                         "Signal returned: reattempting activation for " + subId);
@@ -90,9 +87,6 @@
             }
         } else {
             VvmLog.v(TAG, "Notifications channel is inactive for " + subId);
-            mContext.stopService(OmtpVvmSyncService.getSyncIntent(
-                    mContext, OmtpVvmSyncService.SYNC_FULL_SYNC, mPhoneAccount,
-                    true /* firstAttempt */));
 
             if (!OmtpVvmSourceManager.getInstance(mContext).isVvmSourceRegistered(mPhoneAccount)) {
                 return;
diff --git a/src/com/android/phone/vvm/omtp/imap/ImapHelper.java b/src/com/android/phone/vvm/omtp/imap/ImapHelper.java
index 4db02d0..f700dda 100644
--- a/src/com/android/phone/vvm/omtp/imap/ImapHelper.java
+++ b/src/com/android/phone/vvm/omtp/imap/ImapHelper.java
@@ -86,13 +86,19 @@
     private final OmtpVvmCarrierConfigHelper mConfig;
 
     public ImapHelper(Context context, PhoneAccountHandle phoneAccount, Network network) {
+        this(context, new OmtpVvmCarrierConfigHelper(context,
+                PhoneUtils.getSubIdForPhoneAccountHandle(phoneAccount)), phoneAccount, network);
+    }
+
+    public ImapHelper(Context context, OmtpVvmCarrierConfigHelper config,
+            PhoneAccountHandle phoneAccount, Network network) {
         mContext = context;
         mPhoneAccount = phoneAccount;
         mNetwork = network;
-        mConfig = new OmtpVvmCarrierConfigHelper(context,
-                PhoneUtils.getSubIdForPhoneAccountHandle(phoneAccount));
+        mConfig = config;
         mPrefs = new VisualVoicemailPreferences(context,
                 phoneAccount);
+
         try {
             TempDirectory.setTempDirectory(context);
 
diff --git a/src/com/android/phone/vvm/omtp/protocol/Vvm3EventHandler.java b/src/com/android/phone/vvm/omtp/protocol/Vvm3EventHandler.java
index 3645407..3b62424 100644
--- a/src/com/android/phone/vvm/omtp/protocol/Vvm3EventHandler.java
+++ b/src/com/android/phone/vvm/omtp/protocol/Vvm3EventHandler.java
@@ -116,7 +116,7 @@
             case CONFIG_REQUEST_STATUS_SUCCESS:
                 PhoneAccountHandle handle = PhoneAccountHandleConverter
                         .fromSubId(config.getSubId());
-                if (VoicemailChangePinActivity.isDefaultOldPinSet(context, handle)) {
+                if (!VoicemailChangePinActivity.isDefaultOldPinSet(context, handle)) {
                     return false;
                 } else {
                     postError(context, config, PIN_NOT_SET);
diff --git a/src/com/android/phone/vvm/omtp/scheduling/BaseTask.java b/src/com/android/phone/vvm/omtp/scheduling/BaseTask.java
new file mode 100644
index 0000000..92327b5
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/BaseTask.java
@@ -0,0 +1,201 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.annotation.CallSuper;
+import android.annotation.MainThread;
+import android.annotation.WorkerThread;
+import android.content.Context;
+import android.content.Intent;
+import android.os.SystemClock;
+import android.support.annotation.NonNull;
+
+import com.android.phone.Assert;
+import com.android.phone.NeededForTesting;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Provides common utilities for task implementations, such as execution time and managing {@link
+ * Policy}
+ */
+public abstract class BaseTask implements Task {
+
+    private static final String EXTRA_SUB_ID = "extra_sub_id";
+
+    private Context mContext;
+
+    private int mId;
+    private int mSubId = TaskId.SUB_ID_ANY;
+
+    private boolean mHasStarted;
+    private volatile boolean mHasFailed;
+
+    @NonNull
+    private final List<Policy> mPolicies = new ArrayList<>();
+
+    private long mExecutionTime;
+
+    private static Clock sClock = new Clock();
+
+    protected BaseTask(int id) {
+        mId = id;
+        mExecutionTime = getTimeMillis();
+    }
+
+    /**
+     * Modify the task ID to prevent arbitrary task from executing. Can only be called before {@link
+     * #onCreate(Context, Intent, int, int)} returns.
+     */
+    @MainThread
+    public void setId(int id) {
+        Assert.isMainThread();
+        mId = id;
+    }
+
+    @MainThread
+    public boolean hasStarted() {
+        Assert.isMainThread();
+        return mHasStarted;
+    }
+
+    @MainThread
+    public boolean hasFailed() {
+        Assert.isMainThread();
+        return mHasFailed;
+    }
+
+    public Context getContext() {
+        return mContext;
+    }
+
+    /**
+     * Should be call in the constructor or {@link Policy#onCreate(BaseTask, Intent, int, int)} will
+     * be missed.
+     */
+    @MainThread
+    public BaseTask addPolicy(Policy policy) {
+        Assert.isMainThread();
+        mPolicies.add(policy);
+        return this;
+    }
+
+    /**
+     * Indicate the task has failed. {@link Policy#onFail()} will be triggered once the execution
+     * ends. This mechanism is used by policies for actions such as determining whether to schedule
+     * a retry. Must be call inside {@link #onExecuteInBackgroundThread()}
+     */
+    @WorkerThread
+    public void fail() {
+        Assert.isNotMainThread();
+        mHasFailed = true;
+    }
+
+    @MainThread
+    public void setExecutionTime(long timeMillis) {
+        Assert.isMainThread();
+        mExecutionTime = timeMillis;
+    }
+
+    public long getTimeMillis() {
+        return sClock.getTimeMillis();
+    }
+
+    /**
+     * Creates an intent that can be used to restart the current task. Derived class should build
+     * their intent upon this.
+     */
+    public Intent createRestartIntent() {
+        return createIntent(getContext(), this.getClass(), mSubId);
+    }
+
+    /**
+     * Creates an intent that can be used to start the {@link TaskSchedulerService}. Derived class
+     * should build their intent upon this.
+     */
+    public static Intent createIntent(Context context, Class<? extends BaseTask> task, int subId) {
+        Intent intent = TaskSchedulerService.createIntent(context, task);
+        intent.putExtra(EXTRA_SUB_ID, subId);
+        return intent;
+    }
+
+    @Override
+    public TaskId getId() {
+        return new TaskId(mId, mSubId);
+    }
+
+    @Override
+    @CallSuper
+    public void onCreate(Context context, Intent intent, int flags, int startId) {
+        mContext = context;
+        mSubId = intent.getIntExtra(EXTRA_SUB_ID, TaskId.SUB_ID_ANY);
+        for (Policy policy : mPolicies) {
+            policy.onCreate(this, intent, flags, startId);
+        }
+    }
+
+    @Override
+    public long getReadyInMilliSeconds() {
+        return mExecutionTime - getTimeMillis();
+    }
+
+    @Override
+    @CallSuper
+    public void onBeforeExecute() {
+        for (Policy policy : mPolicies) {
+            policy.onBeforeExecute();
+        }
+        mHasStarted = true;
+    }
+
+    @Override
+    public void onCompleted() {
+        if (mHasFailed) {
+            for (Policy policy : mPolicies) {
+                policy.onFail();
+            }
+        }
+
+        for (Policy policy : mPolicies) {
+            policy.onCompleted();
+        }
+    }
+
+    @Override
+    public void onDuplicatedTaskAdded(Task task) {
+        for (Policy policy : mPolicies) {
+            policy.onDuplicatedTaskAdded();
+        }
+    }
+
+    @NeededForTesting
+    static class Clock {
+
+        public long getTimeMillis() {
+            return SystemClock.elapsedRealtime();
+        }
+    }
+
+    /**
+     * Used to replace the clock with an deterministic clock
+     */
+    @NeededForTesting
+    static void setClockForTesting(Clock clock) {
+        sClock = clock;
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/BlockerTask.java b/src/com/android/phone/vvm/omtp/scheduling/BlockerTask.java
new file mode 100644
index 0000000..9d91828
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/BlockerTask.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.content.Context;
+import android.content.Intent;
+
+import com.android.phone.vvm.omtp.VvmLog;
+
+/**
+ * Task to block another task of the same ID from being queued for a certain amount of time.
+ */
+public class BlockerTask extends BaseTask {
+
+    private static final String TAG = "BlockerTask";
+
+    public static final String EXTRA_TASK_ID = "extra_task_id";
+    public static final String EXTRA_BLOCK_FOR_MILLIS = "extra_block_for_millis";
+
+    public BlockerTask() {
+        super(TASK_INVALID);
+    }
+
+    @Override
+    public void onCreate(Context context, Intent intent, int flags, int startId) {
+        super.onCreate(context, intent, flags, startId);
+        setId(intent.getIntExtra(EXTRA_TASK_ID, TASK_INVALID));
+        setExecutionTime(getTimeMillis() + intent.getIntExtra(EXTRA_BLOCK_FOR_MILLIS, 0));
+    }
+
+    @Override
+    public void onExecuteInBackgroundThread() {
+        // Do nothing.
+    }
+
+    @Override
+    public void onDuplicatedTaskAdded(Task task) {
+        VvmLog
+            .v(TAG, task.toString() + "blocked, " + getReadyInMilliSeconds() + "millis remaining");
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/MinimalIntervalPolicy.java b/src/com/android/phone/vvm/omtp/scheduling/MinimalIntervalPolicy.java
new file mode 100644
index 0000000..8bb22ca
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/MinimalIntervalPolicy.java
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.content.Intent;
+
+import com.android.phone.vvm.omtp.scheduling.Task.TaskId;
+
+/**
+ * If a task with this policy succeeds, a {@link BlockerTask} with the same {@link TaskId} of the
+ * task will be queued immediately, preventing the same task from running for a certain amount of
+ * time.
+ */
+public class MinimalIntervalPolicy implements Policy {
+
+    BaseTask mTask;
+    TaskId mId;
+    int mBlockForMillis;
+
+    public MinimalIntervalPolicy(int blockForMillis) {
+        mBlockForMillis = blockForMillis;
+    }
+
+    @Override
+    public void onCreate(BaseTask task, Intent intent, int flags, int startId) {
+        mTask = task;
+        mId = mTask.getId();
+    }
+
+    @Override
+    public void onBeforeExecute() {
+
+    }
+
+    @Override
+    public void onCompleted() {
+        if (!mTask.hasFailed()) {
+            Intent intent = mTask
+                    .createIntent(mTask.getContext(), BlockerTask.class, mId.subId);
+            intent.putExtra(BlockerTask.EXTRA_TASK_ID, mId.id);
+            intent.putExtra(BlockerTask.EXTRA_BLOCK_FOR_MILLIS, mBlockForMillis);
+            mTask.getContext().startService(intent);
+        }
+    }
+
+    @Override
+    public void onFail() {
+
+    }
+
+    @Override
+    public void onDuplicatedTaskAdded() {
+
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/Policy.java b/src/com/android/phone/vvm/omtp/scheduling/Policy.java
new file mode 100644
index 0000000..fcb01b8
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/Policy.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.content.Intent;
+
+/**
+ * A set of listeners managed by {@link BaseTask} for common behaviors such as retrying. Call {@link
+ * BaseTask#addPolicy(Policy)} to add a policy.
+ */
+public interface Policy {
+
+    void onCreate(BaseTask task, Intent intent, int flags, int startId);
+
+    void onBeforeExecute();
+
+    void onCompleted();
+
+    void onFail();
+
+    void onDuplicatedTaskAdded();
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/PostponePolicy.java b/src/com/android/phone/vvm/omtp/scheduling/PostponePolicy.java
new file mode 100644
index 0000000..f23d7f7
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/PostponePolicy.java
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.content.Intent;
+
+import com.android.phone.vvm.omtp.VvmLog;
+
+/**
+ * A task with Postpone policy will not be executed immediately. It will wait for a while and if a
+ * duplicated task is queued during the duration, the task will be postponed further. The task will
+ * only be executed if no new task was added in postponeMillis. Useful to batch small tasks in quick
+ * succession together.
+ */
+public class PostponePolicy implements Policy {
+
+    private static final String TAG = "PostponePolicy";
+
+    private final int mPostponeMillis;
+    private BaseTask mTask;
+
+    public PostponePolicy(int postponeMillis) {
+        mPostponeMillis = postponeMillis;
+    }
+
+    @Override
+    public void onCreate(BaseTask task, Intent intent, int flags, int startId) {
+        mTask = task;
+        mTask.setExecutionTime(mTask.getTimeMillis() + mPostponeMillis);
+    }
+
+    @Override
+    public void onBeforeExecute() {
+        // Do nothing
+    }
+
+    @Override
+    public void onCompleted() {
+        // Do nothing
+    }
+
+    @Override
+    public void onFail() {
+        // Do nothing
+    }
+
+    @Override
+    public void onDuplicatedTaskAdded() {
+        if (mTask.hasStarted()) {
+            return;
+        }
+        VvmLog.d(TAG, "postponing " + mTask);
+        mTask.setExecutionTime(mTask.getTimeMillis() + mPostponeMillis);
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/RetryPolicy.java b/src/com/android/phone/vvm/omtp/scheduling/RetryPolicy.java
new file mode 100644
index 0000000..3c2274f
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/RetryPolicy.java
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.content.Intent;
+
+import com.android.phone.vvm.omtp.VvmLog;
+
+/**
+ * A task with this policy will automatically re-queue itself if {@link BaseTask#fail()} has been
+ * called during {@link BaseTask#onExecuteInBackgroundThread()}. A task will be retried at most
+ * <code>retryLimit</code> times and with a <code>retryDelayMillis</code> interval in between.
+ */
+public class RetryPolicy implements Policy {
+
+    private static final String TAG = "RetryPolicy";
+    private static final String EXTRA_RETRY_COUNT = "extra_retry_count";
+
+    private final int mRetryLimit;
+    private final int mRetryDelayMillis;
+
+    private BaseTask mTask;
+
+    private int mRetryCount;
+    private boolean mFailed;
+
+    public RetryPolicy(int retryLimit, int retryDelayMillis) {
+        mRetryLimit = retryLimit;
+        mRetryDelayMillis = retryDelayMillis;
+    }
+
+    @Override
+    public void onCreate(BaseTask task, Intent intent, int flags, int startId) {
+        mTask = task;
+        mRetryCount = intent.getIntExtra(EXTRA_RETRY_COUNT, 0);
+        if (mRetryCount > 0) {
+            VvmLog.d(TAG, "retry #" + mRetryCount + " for " + mTask + " queued, executing in "
+                    + mRetryDelayMillis);
+            mTask.setExecutionTime(mTask.getTimeMillis() + mRetryDelayMillis);
+        }
+    }
+
+    @Override
+    public void onBeforeExecute() {
+
+    }
+
+    @Override
+    public void onCompleted() {
+        if (!mFailed) {
+            return;
+        }
+        if (mRetryCount >= mRetryLimit) {
+            VvmLog.d(TAG, "Retry limit for " + mTask + " reached");
+            return;
+        }
+
+        Intent intent = mTask.createRestartIntent();
+        intent.putExtra(EXTRA_RETRY_COUNT, mRetryCount + 1);
+
+        mTask.getContext().startService(intent);
+    }
+
+    @Override
+    public void onFail() {
+        mFailed = true;
+    }
+
+    @Override
+    public void onDuplicatedTaskAdded() {
+
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/Task.java b/src/com/android/phone/vvm/omtp/scheduling/Task.java
new file mode 100644
index 0000000..62762e7
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/Task.java
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.annotation.MainThread;
+import android.annotation.WorkerThread;
+import android.content.Context;
+import android.content.Intent;
+
+import java.util.Objects;
+
+/**
+ * A task for {@link TaskSchedulerService} to execute. Since the task is sent through a intent to
+ * the scheduler, The task must be constructable with the intent. Specifically, It must have a
+ * constructor with zero arguments, and have all relevant data packed inside the intent. Use {@link
+ * TaskSchedulerService#createIntent(Context, Class)} to create a intent that will construct the
+ * Task.
+ *
+ * <p>Only {@link #onExecuteInBackgroundThread()} is run on the worker thread.
+ */
+public interface Task {
+
+    /**
+     * TaskId to indicate it has not be set. If a task does not provide a default TaskId it should
+     * be set before {@link Task#onCreate(Context, Intent, int, int) returns}
+     */
+    int TASK_INVALID = -1;
+
+    /**
+     * TaskId to indicate it should always be queued regardless of duplicates. {@link
+     * Task#onDuplicatedTaskAdded(Task)} will never be called on tasks with this TaskId.
+     */
+    int TASK_ALLOW_DUPLICATES = -2;
+
+    int TASK_UPLOAD = 1;
+    int TASK_SYNC = 2;
+
+    /**
+     * Used to differentiate between types of tasks. If a task with the same TaskId is already in
+     * the queue the new task will be rejected.
+     */
+    class TaskId {
+
+        /**
+         * Special subId value to indicate unspecified subId. Having SUB_ID_ANY does NOT prevent
+         * task on other subId from executing.
+         */
+        public static final int SUB_ID_ANY = -1;
+
+        /**
+         * Indicates the operation type of the task.
+         */
+        public final int id;
+        /**
+         * Same operation for a different subId is allowed. subId is used to differentiate phone
+         * accounts in multi-SIM scenario. For example, each SIM can queue a sync task for their
+         * own.
+         */
+        public final int subId;
+
+        public TaskId(int id, int subId) {
+            this.id = id;
+            this.subId = subId;
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            if (!(object instanceof TaskId)) {
+                return false;
+            }
+            TaskId other = (TaskId) object;
+            return id == other.id && subId == other.subId;
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hash(id, subId);
+        }
+    }
+
+    TaskId getId();
+
+    @MainThread
+    void onCreate(Context context, Intent intent, int flags, int startId);
+
+    /**
+     * @return number of milliSeconds the scheduler should wait before running this task. A value
+     * less than {@link TaskSchedulerService#READY_TOLERANCE_MILLISECONDS} will be considered ready.
+     * If no tasks are ready, the scheduler will sleep for this amount of time before doing another
+     * check (it will still wake if a new task is added). The first task in the queue that is ready
+     * will be executed.
+     */
+    @MainThread
+    long getReadyInMilliSeconds();
+
+    /**
+     * Called on the main thread when the scheduler is about to send the task into the worker
+     * thread, calling {@link #onExecuteInBackgroundThread()}
+     */
+    @MainThread
+    void onBeforeExecute();
+
+    /**
+     * The actual payload of the task, executed on the worker thread.
+     */
+    @WorkerThread
+    void onExecuteInBackgroundThread();
+
+    /**
+     * Called on the main thread when {@link #onExecuteInBackgroundThread()} has finished or thrown
+     * an uncaught exception. The task is already removed from the queue at this point, and a same
+     * task can be queued again.
+     */
+    @MainThread
+    void onCompleted();
+
+    /**
+     * Another task with the same TaskId has been added. Necessary data can be retrieved from the
+     * other task, and after this returns the task will be discarded.
+     */
+    @MainThread
+    void onDuplicatedTaskAdded(Task task);
+}
diff --git a/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerService.java b/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerService.java
new file mode 100644
index 0000000..7bc3262
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerService.java
@@ -0,0 +1,345 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.annotation.MainThread;
+import android.annotation.Nullable;
+import android.annotation.WorkerThread;
+import android.app.Service;
+import android.content.Context;
+import android.content.Intent;
+import android.os.Binder;
+import android.os.Handler;
+import android.os.HandlerThread;
+import android.os.IBinder;
+import android.os.Looper;
+import android.os.Message;
+import android.os.PowerManager;
+import android.os.PowerManager.WakeLock;
+
+import com.android.internal.annotations.VisibleForTesting;
+import com.android.phone.Assert;
+import com.android.phone.NeededForTesting;
+import com.android.phone.vvm.omtp.VvmLog;
+import com.android.phone.vvm.omtp.scheduling.Task.TaskId;
+
+import java.util.ArrayDeque;
+import java.util.Queue;
+
+/**
+ * A service to queue and run {@link Task} on a worker thread. Only one task will be ran at a time,
+ * and same task cannot exist in the queue at the same time. The service will be started when a
+ * intent is received, and stopped when there are no more tasks in the queue.
+ */
+public class TaskSchedulerService extends Service {
+
+    private static final String TAG = "TaskSchedulerService";
+
+    private static final int READY_TOLERANCE_MILLISECONDS = 100;
+    /**
+     * When there are no more tasks to be run the service should be stopped. But when all tasks has
+     * finished there might still be more tasks in the message queue waiting to be processed,
+     * especially the ones submitted in {@link Task#onCompleted()}. Wait for a while before stopping
+     * the service to make sure there are no pending messages.
+     */
+    private static final int STOP_DELAY_MILLISECONDS = 5_000;
+    private static final String EXTRA_CLASS_NAME = "extra_class_name";
+
+    private static final String WAKE_LOCK_TAG = "TaskSchedulerService_wakelock";
+
+    // The thread to run tasks on
+    private volatile WorkerThreadHandler mWorkerThreadHandler;
+
+    private Context mContext = this;
+    /**
+     * Used by tests to turn task handling into a single threaded process by calling {@link
+     * Handler#handleMessage(Message)} directly
+     */
+    private MessageSender mMessageSender = new MessageSender();
+
+    private MainThreadHandler mMainThreadHandler;
+
+    private WakeLock mWakeLock;
+
+    /**
+     * Main thread only, access through {@link #getTasks()}
+     */
+    private final Queue<Task> mTasks = new ArrayDeque<>();
+    private boolean mWorkerThreadIsBusy = false;
+
+    private final Runnable mStopServiceWithDelay = new Runnable() {
+        @Override
+        public void run() {
+            VvmLog.d(TAG, "Stopping service");
+            stopSelf();
+
+        }
+    };
+    /**
+     * Should attempt to run the next task when a task has finished or been added.
+     */
+    private boolean mTaskAutoRunDisabledForTesting = false;
+
+    @VisibleForTesting
+    final class WorkerThreadHandler extends Handler {
+
+        public WorkerThreadHandler(Looper looper) {
+            super(looper);
+        }
+
+        @Override
+        @WorkerThread
+        public void handleMessage(Message msg) {
+            Assert.isNotMainThread();
+            Task task = (Task) msg.obj;
+            try {
+                VvmLog.v(TAG, "executing task " + task);
+                task.onExecuteInBackgroundThread();
+            } catch (Throwable throwable) {
+                VvmLog.e(TAG, "Exception while executing task " + task + ":" + throwable);
+            }
+
+            Message schedulerMessage = mMainThreadHandler.obtainMessage();
+            schedulerMessage.obj = task;
+            mMessageSender.send(schedulerMessage);
+        }
+    }
+
+    @VisibleForTesting
+    final class MainThreadHandler extends Handler {
+
+        public MainThreadHandler(Looper looper) {
+            super(looper);
+        }
+
+        @Override
+        @MainThread
+        public void handleMessage(Message msg) {
+            Assert.isMainThread();
+            Task task = (Task) msg.obj;
+            getTasks().remove(task);
+            task.onCompleted();
+            mWorkerThreadIsBusy = false;
+            maybeRunNextTask();
+        }
+    }
+
+    @Override
+    @MainThread
+    public void onCreate() {
+        super.onCreate();
+        mWakeLock = getSystemService(PowerManager.class)
+                .newWakeLock(PowerManager.PARTIAL_WAKE_LOCK, WAKE_LOCK_TAG);
+        mWakeLock.acquire();
+        HandlerThread thread = new HandlerThread("VvmTaskSchedulerService");
+        thread.start();
+
+        mWorkerThreadHandler = new WorkerThreadHandler(thread.getLooper());
+        mMainThreadHandler = new MainThreadHandler(Looper.getMainLooper());
+    }
+
+    @Override
+    public void onDestroy() {
+        mWorkerThreadHandler.getLooper().quit();
+        mWakeLock.release();
+    }
+
+    @Override
+    @MainThread
+    public int onStartCommand(@Nullable Intent intent, int flags, int startId) {
+        Assert.isMainThread();
+        Task task = createTask(intent, flags, startId);
+        if (task == null) {
+            VvmLog.e(TAG, "cannot create task form intent");
+        } else {
+            addTask(task);
+        }
+        // STICKY means the service will be automatically restarted will the last intent if it is
+        // killed.
+        return START_NOT_STICKY;
+    }
+
+    @MainThread
+    @VisibleForTesting
+    void addTask(Task task) {
+        Assert.isMainThread();
+        if (task.getId().id == Task.TASK_INVALID) {
+            throw new AssertionError("Task id was not set to a valid value before adding.");
+        }
+        if (task.getId().id != Task.TASK_ALLOW_DUPLICATES) {
+            Task oldTask = getTask(task.getId());
+            if (oldTask != null) {
+                oldTask.onDuplicatedTaskAdded(task);
+                return;
+            }
+        }
+        mMainThreadHandler.removeCallbacks(mStopServiceWithDelay);
+        getTasks().add(task);
+        maybeRunNextTask();
+
+    }
+
+    @MainThread
+    @Nullable
+    private Task getTask(TaskId taskId) {
+        Assert.isMainThread();
+        for (Task task : getTasks()) {
+            if (task.getId().equals(taskId)) {
+                return task;
+            }
+        }
+        return null;
+    }
+
+    @MainThread
+    private Queue<Task> getTasks() {
+        Assert.isMainThread();
+        return mTasks;
+    }
+
+    /**
+     * Create an intent that will queue the <code>task</code>
+     */
+    public static Intent createIntent(Context context, Class<? extends Task> task) {
+        Intent intent = new Intent(context, TaskSchedulerService.class);
+        intent.putExtra(EXTRA_CLASS_NAME, task.getName());
+        return intent;
+    }
+
+    @VisibleForTesting
+    @MainThread
+    @Nullable
+    Task createTask(@Nullable Intent intent, int flags, int startId) {
+        Assert.isMainThread();
+        if (intent == null) {
+            return null;
+        }
+        String className = intent.getStringExtra(EXTRA_CLASS_NAME);
+        VvmLog.d(TAG, "create task:" + className);
+        if (className == null) {
+            throw new IllegalArgumentException("EXTRA_CLASS_NAME expected");
+        }
+        try {
+            Task task = (Task) Class.forName(className).newInstance();
+            task.onCreate(mContext, intent, flags, startId);
+            return task;
+        } catch (ClassNotFoundException | IllegalAccessException | InstantiationException e) {
+            throw new IllegalArgumentException(e);
+        }
+    }
+
+    @MainThread
+    private void maybeRunNextTask() {
+        Assert.isMainThread();
+        if (mWorkerThreadIsBusy) {
+            return;
+        }
+        if (mTaskAutoRunDisabledForTesting) {
+            // If mTaskAutoRunDisabledForTesting is true, runNextTask() must be explicitly called
+            // to run the next task.
+            return;
+        }
+
+        runNextTask();
+    }
+
+    @VisibleForTesting
+    @MainThread
+    void runNextTask() {
+        Assert.isMainThread();
+        if (getTasks().isEmpty()) {
+            prepareStop();
+            return;
+        }
+        Long minimalWaitTime = null;
+        for (Task task : getTasks()) {
+            long waitTime = task.getReadyInMilliSeconds();
+            if (waitTime < READY_TOLERANCE_MILLISECONDS) {
+                task.onBeforeExecute();
+                Message message = mWorkerThreadHandler.obtainMessage();
+                message.obj = task;
+                mWorkerThreadIsBusy = true;
+                mMessageSender.send(message);
+                return;
+            } else {
+                if (minimalWaitTime == null || waitTime < minimalWaitTime) {
+                    minimalWaitTime = waitTime;
+                }
+            }
+        }
+        VvmLog.d(TAG, "minimal wait time:" + minimalWaitTime);
+        if (!mTaskAutoRunDisabledForTesting && minimalWaitTime != null) {
+            // No tests are currently ready. Sleep until the next one should be.
+            // If a new task is added during the sleep the service will wake immediately.
+            mMainThreadHandler.postDelayed(new Runnable() {
+                @Override
+                public void run() {
+                    maybeRunNextTask();
+                }
+            }, minimalWaitTime);
+        }
+    }
+
+    private void prepareStop() {
+        VvmLog.d(TAG,
+                "No more tasks, stopping service if no task are added in "
+                        + STOP_DELAY_MILLISECONDS + " millis");
+        mMainThreadHandler.postDelayed(mStopServiceWithDelay, STOP_DELAY_MILLISECONDS);
+    }
+
+    static class MessageSender {
+
+        public void send(Message message) {
+            message.sendToTarget();
+        }
+    }
+
+    @NeededForTesting
+    void setContextForTest(Context context) {
+        mContext = context;
+    }
+
+    @NeededForTesting
+    void setTaskAutoRunDisabledForTest(boolean value) {
+        mTaskAutoRunDisabledForTesting = value;
+    }
+
+    @NeededForTesting
+    void setMessageSenderForTest(MessageSender sender) {
+        mMessageSender = sender;
+    }
+
+    @NeededForTesting
+    void clearTasksForTest() {
+        mTasks.clear();
+    }
+
+    @Override
+    @Nullable
+    public IBinder onBind(Intent intent) {
+        return new LocalBinder();
+    }
+
+    @NeededForTesting
+    class LocalBinder extends Binder {
+
+        @NeededForTesting
+        public TaskSchedulerService getService() {
+            return TaskSchedulerService.this;
+        }
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/sms/OmtpMessageReceiver.java b/src/com/android/phone/vvm/omtp/sms/OmtpMessageReceiver.java
index 6eda4af..277e882 100644
--- a/src/com/android/phone/vvm/omtp/sms/OmtpMessageReceiver.java
+++ b/src/com/android/phone/vvm/omtp/sms/OmtpMessageReceiver.java
@@ -35,6 +35,8 @@
 import com.android.phone.vvm.omtp.VvmLog;
 import com.android.phone.vvm.omtp.sync.OmtpVvmSourceManager;
 import com.android.phone.vvm.omtp.sync.OmtpVvmSyncService;
+import com.android.phone.vvm.omtp.sync.SyncOneTask;
+import com.android.phone.vvm.omtp.sync.SyncTask;
 import com.android.phone.vvm.omtp.sync.VoicemailsQueryHelper;
 import com.android.phone.vvm.omtp.utils.PhoneAccountHandleConverter;
 
@@ -122,15 +124,11 @@
                 if (queryHelper.isVoicemailUnique(voicemail)) {
                     Uri uri = VoicemailContract.Voicemails.insert(mContext, voicemail);
                     voicemail = builder.setId(ContentUris.parseId(uri)).setUri(uri).build();
-                    serviceIntent = OmtpVvmSyncService.getSyncIntent(mContext,
-                            OmtpVvmSyncService.SYNC_DOWNLOAD_ONE_TRANSCRIPTION, phone,
-                            voicemail, true /* firstAttempt */);
+                    SyncOneTask.start(mContext, phone, voicemail);
                 }
                 break;
             case OmtpConstants.MAILBOX_UPDATE:
-                serviceIntent = OmtpVvmSyncService.getSyncIntent(
-                        mContext, OmtpVvmSyncService.SYNC_DOWNLOAD_ONLY, phone,
-                        true /* firstAttempt */);
+                SyncTask.start(mContext, phone, OmtpVvmSyncService.SYNC_DOWNLOAD_ONLY);
                 break;
             case OmtpConstants.GREETINGS_UPDATE:
                 // Not implemented in V1
@@ -140,10 +138,6 @@
                         "Unrecognized sync trigger event: " + message.getSyncTriggerEvent());
                 break;
         }
-
-        if (serviceIntent != null) {
-            mContext.startService(serviceIntent);
-        }
     }
 
     private void updateSource(PhoneAccountHandle phone, int subId, StatusMessage message) {
@@ -161,10 +155,7 @@
             // Add the source to indicate that it is active.
             vvmSourceManager.addSource(phone);
 
-            Intent serviceIntent = OmtpVvmSyncService.getSyncIntent(
-                    mContext, OmtpVvmSyncService.SYNC_FULL_SYNC, phone,
-                    true /* firstAttempt */);
-            mContext.startService(serviceIntent);
+            SyncTask.start(mContext, phone, OmtpVvmSyncService.SYNC_FULL_SYNC);
 
             PhoneGlobals.getInstance().clearMwiIndicator(subId);
         } else {
diff --git a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSourceManager.java b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSourceManager.java
index 1b9e53f..1972ca6 100644
--- a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSourceManager.java
+++ b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSourceManager.java
@@ -111,7 +111,6 @@
                 .handleEvent(OmtpEvents.OTHER_SOURCE_REMOVED);
         removePhoneStateListener(phoneAccount);
         mActiveVvmSources.remove(phoneAccount);
-        OmtpVvmSyncService.cancelAllRetries(mContext, phoneAccount);
     }
 
     public void addPhoneStateListener(Phone phone) {
diff --git a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncReceiver.java b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncReceiver.java
index 415fc91..b424281 100644
--- a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncReceiver.java
+++ b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncReceiver.java
@@ -31,10 +31,7 @@
     public void onReceive(final Context context, Intent intent) {
         if (VoicemailContract.ACTION_SYNC_VOICEMAIL.equals(intent.getAction())) {
             VvmLog.v(TAG, "Sync intent received");
-            Intent syncIntent = OmtpVvmSyncService
-                    .getSyncIntent(context, OmtpVvmSyncService.SYNC_FULL_SYNC, null, true);
-            intent.putExtra(OmtpVvmSyncService.EXTRA_IS_MANUAL_SYNC, true);
-            context.startService(syncIntent);
+            SyncTask.start(context, null, OmtpVvmSyncService.SYNC_FULL_SYNC);
         }
     }
 }
diff --git a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncService.java b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncService.java
index 7e62829..163b204 100644
--- a/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncService.java
+++ b/src/com/android/phone/vvm/omtp/sync/OmtpVvmSyncService.java
@@ -15,13 +15,8 @@
  */
 package com.android.phone.vvm.omtp.sync;
 
-import android.app.AlarmManager;
-import android.app.IntentService;
-import android.app.PendingIntent;
 import android.content.Context;
-import android.content.Intent;
 import android.net.Network;
-import android.net.NetworkInfo;
 import android.net.Uri;
 import android.provider.VoicemailContract;
 import android.telecom.PhoneAccountHandle;
@@ -29,7 +24,6 @@
 import android.text.TextUtils;
 
 import com.android.phone.PhoneUtils;
-import com.android.phone.VoicemailStatus;
 import com.android.phone.settings.VisualVoicemailSettingsUtil;
 import com.android.phone.vvm.omtp.OmtpEvents;
 import com.android.phone.vvm.omtp.OmtpVvmCarrierConfigHelper;
@@ -37,6 +31,9 @@
 import com.android.phone.vvm.omtp.VvmLog;
 import com.android.phone.vvm.omtp.fetch.VoicemailFetchedCallback;
 import com.android.phone.vvm.omtp.imap.ImapHelper;
+import com.android.phone.vvm.omtp.scheduling.BaseTask;
+import com.android.phone.vvm.omtp.sync.VvmNetworkRequest.NetworkWrapper;
+import com.android.phone.vvm.omtp.utils.PhoneAccountHandleConverter;
 
 import java.util.HashMap;
 import java.util.List;
@@ -46,13 +43,10 @@
 /**
  * Sync OMTP visual voicemail.
  */
-public class OmtpVvmSyncService extends IntentService {
+public class OmtpVvmSyncService {
 
     private static final String TAG = OmtpVvmSyncService.class.getSimpleName();
 
-    // Number of retries
-    private static final int NETWORK_RETRY_COUNT = 3;
-
     /**
      * Signifies a sync with both uploading to the server and downloading from the server.
      */
@@ -70,23 +64,8 @@
      */
     public static final String SYNC_DOWNLOAD_ONE_TRANSCRIPTION =
             "download_one_transcription";
-    /**
-     * The account to sync.
-     */
-    public static final String EXTRA_PHONE_ACCOUNT = "phone_account";
-    /**
-     * The voicemail to fetch.
-     */
-    public static final String EXTRA_VOICEMAIL = "voicemail";
-    /**
-     * The sync request is initiated by the user, should allow shorter sync interval.
-     */
-    public static final String EXTRA_IS_MANUAL_SYNC = "is_manual_sync";
-    // Minimum time allowed between full syncs
-    private static final int MINIMUM_FULL_SYNC_INTERVAL_MILLIS = 60 * 1000;
 
-    // Minimum time allowed between manual syncs
-    private static final int MINIMUM_MANUAL_SYNC_INTERVAL_MILLIS = 3 * 1000;
+    private final Context mContext;
 
     // Record the timestamp of the last full sync so that duplicate syncs can be reduced.
     private static final String LAST_FULL_SYNC_TIMESTAMP = "last_full_sync_timestamp";
@@ -95,170 +74,68 @@
 
     private VoicemailsQueryHelper mQueryHelper;
 
-    public OmtpVvmSyncService() {
-        super("OmtpVvmSyncService");
+    public OmtpVvmSyncService(Context context) {
+        mContext = context;
+        mQueryHelper = new VoicemailsQueryHelper(mContext);
     }
 
-    public static Intent getSyncIntent(Context context, String action,
-            PhoneAccountHandle phoneAccount, boolean firstAttempt) {
-        return getSyncIntent(context, action, phoneAccount, null, firstAttempt);
-    }
-
-    public static Intent getSyncIntent(Context context, String action,
-            PhoneAccountHandle phoneAccount, Voicemail voicemail, boolean firstAttempt) {
-
-        Intent serviceIntent = new Intent(context, OmtpVvmSyncService.class);
-        serviceIntent.setAction(action);
-        if (phoneAccount != null) {
-            serviceIntent.putExtra(EXTRA_PHONE_ACCOUNT, phoneAccount);
-        }
-        if (voicemail != null) {
-            serviceIntent.putExtra(EXTRA_VOICEMAIL, voicemail);
-        }
-
-        cancelRetriesForIntent(context, serviceIntent);
-        return serviceIntent;
-    }
-
-    /**
-     * Cancel all retry syncs for an account.
-     *
-     * @param context The context the service runs in.
-     * @param phoneAccount The phone account for which to cancel syncs.
-     */
-    public static void cancelAllRetries(Context context, PhoneAccountHandle phoneAccount) {
-        cancelRetriesForIntent(context, getSyncIntent(context, SYNC_FULL_SYNC, phoneAccount,
-                false));
-    }
-
-    /**
-     * A helper method to cancel all pending alarms for intents that would be identical to the given
-     * intent.
-     *
-     * @param context The context the service runs in.
-     * @param intent The intent to search and cancel.
-     */
-    private static void cancelRetriesForIntent(Context context, Intent intent) {
-        AlarmManager alarmManager = (AlarmManager) context.getSystemService(Context.ALARM_SERVICE);
-        alarmManager.cancel(PendingIntent.getService(context, 0, intent, 0));
-
-        Intent copyIntent = new Intent(intent);
-        if (SYNC_FULL_SYNC.equals(copyIntent.getAction())) {
-            // A full sync action should also cancel both of the other types of syncs
-            copyIntent.setAction(SYNC_DOWNLOAD_ONLY);
-            alarmManager.cancel(PendingIntent.getService(context, 0, copyIntent, 0));
-            copyIntent.setAction(SYNC_UPLOAD_ONLY);
-            alarmManager.cancel(PendingIntent.getService(context, 0, copyIntent, 0));
-        }
-    }
-
-    @Override
-    public void onCreate() {
-        super.onCreate();
-        mQueryHelper = new VoicemailsQueryHelper(this);
-    }
-
-    @Override
-    protected void onHandleIntent(Intent intent) {
-        if (intent == null) {
-            VvmLog.d(TAG, "onHandleIntent: could not handle null intent");
-            return;
-        }
-        String action = intent.getAction();
-        PhoneAccountHandle phoneAccount = intent.getParcelableExtra(EXTRA_PHONE_ACCOUNT);
+    public void sync(BaseTask task, String action, PhoneAccountHandle phoneAccount,
+            Voicemail voicemail) {
         VvmLog.log(TAG, "Sync requested: " + action +
                 " for all accounts: " + String.valueOf(phoneAccount == null));
-
-        boolean isManualSync = intent.getBooleanExtra(EXTRA_IS_MANUAL_SYNC, false);
-        Voicemail voicemail = intent.getParcelableExtra(EXTRA_VOICEMAIL);
         if (phoneAccount != null) {
             VvmLog.v(TAG, "Sync requested: " + action + " - for account: " + phoneAccount);
-            setupAndSendRequest(phoneAccount, voicemail, action, isManualSync);
+            setupAndSendRequest(task, phoneAccount, voicemail, action);
         } else {
             VvmLog.v(TAG, "Sync requested: " + action + " - for all accounts");
             OmtpVvmSourceManager vvmSourceManager =
-                    OmtpVvmSourceManager.getInstance(this);
+                    OmtpVvmSourceManager.getInstance(mContext);
             Set<PhoneAccountHandle> sources = vvmSourceManager.getOmtpVvmSources();
             for (PhoneAccountHandle source : sources) {
-                setupAndSendRequest(source, null, action, isManualSync);
+                setupAndSendRequest(task, source, null, action);
             }
         }
     }
 
-    private void setupAndSendRequest(PhoneAccountHandle phoneAccount, Voicemail voicemail,
-            String action, boolean isManualSync) {
-        if (!VisualVoicemailSettingsUtil.isEnabled(this, phoneAccount)) {
+    private void setupAndSendRequest(BaseTask task, PhoneAccountHandle phoneAccount,
+            Voicemail voicemail, String action) {
+        if (!VisualVoicemailSettingsUtil.isEnabled(mContext, phoneAccount)) {
             VvmLog.v(TAG, "Sync requested for disabled account");
             return;
         }
 
-        if (SYNC_FULL_SYNC.equals(action)) {
-            long lastSyncTime = new VisualVoicemailPreferences(this, phoneAccount)
-                    .getLong(LAST_FULL_SYNC_TIMESTAMP, NO_PRIOR_FULL_SYNC);
-            long currentTime = System.currentTimeMillis();
-            int minimumInterval = isManualSync ? MINIMUM_MANUAL_SYNC_INTERVAL_MILLIS
-                    : MINIMUM_MANUAL_SYNC_INTERVAL_MILLIS;
-            if (currentTime - lastSyncTime < minimumInterval) {
-                // If it's been less than a minute since the last sync, bail.
-                VvmLog.v(TAG, "Avoiding duplicate full sync: synced recently for "
-                        + phoneAccount.getId());
-
-                /**
-                 *  Perform a NOOP change to the database so the sender can observe the sync is
-                 *  completed.
-                 *  TODO: Instead of this hack, refactor the sync to be synchronous so the sender
-                 *  can use sendOrderedBroadcast() to register a callback once all syncs are
-                 *  finished
-                 *  b/26937720
-                 */
-                VoicemailStatus.edit(this, phoneAccount).apply();
+        OmtpVvmCarrierConfigHelper config = new OmtpVvmCarrierConfigHelper(mContext,
+                PhoneAccountHandleConverter.toSubId(phoneAccount));
+        try (NetworkWrapper network = VvmNetworkRequest.getNetwork(config, phoneAccount)) {
+            if (network == null) {
+                VvmLog.e(TAG, "unable to acquire network");
+                task.fail();
                 return;
             }
-            new VisualVoicemailPreferences(this, phoneAccount).edit()
-                    .putLong(LAST_FULL_SYNC_TIMESTAMP, currentTime)
-                    .apply();
+            doSync(task, network.get(), phoneAccount, voicemail, action);
         }
-
-        VvmNetworkRequestCallback networkCallback = new SyncNetworkRequestCallback(this,
-                phoneAccount, voicemail, action);
-        networkCallback.requestNetwork();
     }
 
-    private void doSync(Network network, VvmNetworkRequestCallback callback,
-            PhoneAccountHandle phoneAccount, Voicemail voicemail, String action) {
-        int retryCount = NETWORK_RETRY_COUNT;
-        try {
-            while (retryCount > 0) {
-                try (ImapHelper imapHelper = new ImapHelper(this, phoneAccount, network)) {
-                    if (!imapHelper.isSuccessfullyInitialized()) {
-                        VvmLog.w(TAG, "Can't retrieve Imap credentials.");
-                        return;
-                    }
-
-                    boolean success = true;
-                    if (voicemail == null) {
-                        success = syncAll(action, imapHelper, phoneAccount);
-                    } else {
-                        success = syncOne(imapHelper, voicemail, phoneAccount);
-                    }
-                    imapHelper.updateQuota();
-
-                    // Need to check again for whether visual voicemail is enabled because it could have
-                    // been disabled while waiting for the response from the network.
-                    if (VisualVoicemailSettingsUtil.isEnabled(this, phoneAccount) &&
-                        !success) {
-                        retryCount--;
-                        VvmLog.v(TAG, "Retrying " + action);
-                    } else {
-                        // Nothing more to do here, just exit.
-                        imapHelper.handleEvent(OmtpEvents.DATA_IMAP_OPERATION_COMPLETED);
-                        return;
-                    }
-                }
+    private void doSync(BaseTask task, Network network, PhoneAccountHandle phoneAccount,
+            Voicemail voicemail, String action) {
+        try(ImapHelper imapHelper = new ImapHelper(mContext, phoneAccount, network)) {
+            if (!imapHelper.isSuccessfullyInitialized()) {
+                VvmLog.w(TAG, "Can't retrieve Imap credentials.");
+                return;
             }
-        } finally {
-            if (callback != null) {
-                callback.releaseNetwork();
+
+            boolean success;
+            if (voicemail == null) {
+                success = syncAll(action, imapHelper, phoneAccount);
+            } else {
+                success = syncOne(imapHelper, voicemail, phoneAccount);
+            }
+            imapHelper.updateQuota();
+
+            if (success) {
+                imapHelper.handleEvent(OmtpEvents.DATA_IMAP_OPERATION_COMPLETED);
+            } else {
+                task.fail();
             }
         }
     }
@@ -277,58 +154,22 @@
         VvmLog.v(TAG, "upload succeeded: [" + String.valueOf(uploadSuccess)
                 + "] download succeeded: [" + String.valueOf(downloadSuccess) + "]");
 
-        boolean success = uploadSuccess && downloadSuccess;
-        if (!uploadSuccess || !downloadSuccess) {
-            if (uploadSuccess) {
-                action = SYNC_DOWNLOAD_ONLY;
-            } else if (downloadSuccess) {
-                action = SYNC_UPLOAD_ONLY;
-            }
-        }
-
-        return success;
+        return uploadSuccess && downloadSuccess;
     }
 
     private boolean syncOne(ImapHelper imapHelper, Voicemail voicemail,
             PhoneAccountHandle account) {
         if (shouldPerformPrefetch(account, imapHelper)) {
-            VoicemailFetchedCallback callback = new VoicemailFetchedCallback(this,
+            VoicemailFetchedCallback callback = new VoicemailFetchedCallback(mContext,
                     voicemail.getUri());
             imapHelper.fetchVoicemailPayload(callback, voicemail.getSourceData());
         }
 
         return imapHelper.fetchTranscription(
-                new TranscriptionFetchedCallback(this, voicemail),
+                new TranscriptionFetchedCallback(mContext, voicemail),
                 voicemail.getSourceData());
     }
 
-    private class SyncNetworkRequestCallback extends VvmNetworkRequestCallback {
-
-        Voicemail mVoicemail;
-        private String mAction;
-
-        public SyncNetworkRequestCallback(Context context, PhoneAccountHandle phoneAccount,
-                Voicemail voicemail, String action) {
-            super(context, phoneAccount);
-            mAction = action;
-            mVoicemail = voicemail;
-        }
-
-        @Override
-        public void onAvailable(Network network) {
-            super.onAvailable(network);
-            NetworkInfo info = getConnectivityManager().getNetworkInfo(network);
-            if (info == null) {
-                VvmLog.d(TAG, "Network Type: Unknown");
-            } else {
-                VvmLog.d(TAG, "Network Type: " + info.getTypeName());
-            }
-
-            doSync(network, this, mPhoneAccount, mVoicemail, mAction);
-        }
-
-    }
-
     private boolean upload(ImapHelper imapHelper) {
         List<Voicemail> readVoicemails = mQueryHelper.getReadVoicemails();
         List<Voicemail> deletedVoicemails = mQueryHelper.getDeletedVoicemails();
@@ -393,9 +234,10 @@
         // The leftover messages are messages that exist on the server but not locally.
         boolean prefetchEnabled = shouldPerformPrefetch(account, imapHelper);
         for (Voicemail remoteVoicemail : remoteMap.values()) {
-            Uri uri = VoicemailContract.Voicemails.insert(this, remoteVoicemail);
+            Uri uri = VoicemailContract.Voicemails.insert(mContext, remoteVoicemail);
             if (prefetchEnabled) {
-                VoicemailFetchedCallback fetchedCallback = new VoicemailFetchedCallback(this, uri);
+                VoicemailFetchedCallback fetchedCallback =
+                        new VoicemailFetchedCallback(mContext, uri);
                 imapHelper.fetchVoicemailPayload(fetchedCallback, remoteVoicemail.getSourceData());
             }
         }
@@ -405,7 +247,7 @@
 
     private boolean shouldPerformPrefetch(PhoneAccountHandle account, ImapHelper imapHelper) {
         OmtpVvmCarrierConfigHelper carrierConfigHelper = new OmtpVvmCarrierConfigHelper(
-                this, PhoneUtils.getSubIdForPhoneAccountHandle(account));
+                mContext, PhoneUtils.getSubIdForPhoneAccountHandle(account));
         return carrierConfigHelper.isPrefetchEnabled() && !imapHelper.isRoaming();
     }
 
diff --git a/src/com/android/phone/vvm/omtp/sync/SyncOneTask.java b/src/com/android/phone/vvm/omtp/sync/SyncOneTask.java
new file mode 100644
index 0000000..17dfaed
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/sync/SyncOneTask.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.phone.vvm.omtp.sync;
+
+import android.content.Context;
+import android.content.Intent;
+import android.telecom.PhoneAccountHandle;
+import android.telecom.Voicemail;
+
+import com.android.phone.vvm.omtp.scheduling.BaseTask;
+import com.android.phone.vvm.omtp.scheduling.RetryPolicy;
+import com.android.phone.vvm.omtp.utils.PhoneAccountHandleConverter;
+
+/**
+ * Task to download a single voicemail from the server. This task is initiated by a SMS notifying
+ * the new voicemail arrival, and ignores the duplicated tasks constraint.
+ */
+public class SyncOneTask extends BaseTask {
+
+    private static final int RETRY_TIMES = 2;
+    private static final int RETRY_INTERVAL_MILLIS = 5_000;
+
+    private static final String EXTRA_PHONE_ACCOUNT_HANDLE = "extra_phone_account_handle";
+    private static final String EXTRA_SYNC_TYPE = "extra_sync_type";
+    private static final String EXTRA_VOICEMAIL = "extra_voicemail";
+
+    private PhoneAccountHandle mPhone;
+    private String mSyncType;
+    private Voicemail mVoicemail;
+
+    public static void start(Context context, PhoneAccountHandle phone, Voicemail voicemail) {
+        Intent intent = BaseTask
+                .createIntent(context, SyncTask.class, PhoneAccountHandleConverter.toSubId(phone));
+        intent.putExtra(EXTRA_PHONE_ACCOUNT_HANDLE, phone);
+        intent.putExtra(EXTRA_SYNC_TYPE, OmtpVvmSyncService.SYNC_DOWNLOAD_ONE_TRANSCRIPTION);
+        intent.putExtra(EXTRA_VOICEMAIL, voicemail);
+        context.startService(intent);
+    }
+
+    public SyncOneTask() {
+        super(TASK_ALLOW_DUPLICATES);
+        addPolicy(new RetryPolicy(RETRY_TIMES, RETRY_INTERVAL_MILLIS));
+    }
+
+    public void onCreate(Context context, Intent intent, int flags, int startId) {
+        super.onCreate(context, intent, flags, startId);
+        mPhone = intent.getParcelableExtra(EXTRA_PHONE_ACCOUNT_HANDLE);
+        mSyncType = intent.getStringExtra(EXTRA_SYNC_TYPE);
+        mVoicemail = intent.getParcelableExtra(EXTRA_VOICEMAIL);
+    }
+
+    @Override
+    public void onExecuteInBackgroundThread() {
+        OmtpVvmSyncService service = new OmtpVvmSyncService(getContext());
+        service.sync(this, mSyncType, mPhone, mVoicemail);
+    }
+
+    @Override
+    public Intent createRestartIntent() {
+        Intent intent = super.createRestartIntent();
+        intent.putExtra(EXTRA_PHONE_ACCOUNT_HANDLE, mPhone);
+        intent.putExtra(EXTRA_SYNC_TYPE, mSyncType);
+        intent.putExtra(EXTRA_VOICEMAIL, mVoicemail);
+        return intent;
+    }
+
+}
diff --git a/src/com/android/phone/vvm/omtp/sync/SyncTask.java b/src/com/android/phone/vvm/omtp/sync/SyncTask.java
new file mode 100644
index 0000000..d4efc6e
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/sync/SyncTask.java
@@ -0,0 +1,76 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.sync;
+
+import android.content.Context;
+import android.content.Intent;
+import android.telecom.PhoneAccountHandle;
+
+import com.android.phone.vvm.omtp.scheduling.BaseTask;
+import com.android.phone.vvm.omtp.scheduling.MinimalIntervalPolicy;
+import com.android.phone.vvm.omtp.scheduling.RetryPolicy;
+import com.android.phone.vvm.omtp.utils.PhoneAccountHandleConverter;
+
+/**
+ * System initiated sync request.
+ */
+public class SyncTask extends BaseTask {
+
+    private static final int RETRY_TIMES = 2;
+    private static final int RETRY_INTERVAL_MILLIS = 5_000;
+    private static final int MINIMAL_INTERVAL_MILLIS = 60_000;
+
+    private static final String EXTRA_PHONE_ACCOUNT_HANDLE = "extra_phone_account_handle";
+    private static final String EXTRA_SYNC_TYPE = "extra_sync_type";
+
+    private PhoneAccountHandle mPhone;
+    private String mSyncType;
+
+    public static void start(Context context, PhoneAccountHandle phone, String syncType) {
+        Intent intent = BaseTask
+                .createIntent(context, SyncTask.class, PhoneAccountHandleConverter.toSubId(phone));
+        intent.putExtra(EXTRA_PHONE_ACCOUNT_HANDLE, phone);
+        intent.putExtra(EXTRA_SYNC_TYPE, syncType);
+        context.startService(intent);
+    }
+
+    public SyncTask() {
+        super(TASK_SYNC);
+        addPolicy(new RetryPolicy(RETRY_TIMES, RETRY_INTERVAL_MILLIS));
+        addPolicy(new MinimalIntervalPolicy(MINIMAL_INTERVAL_MILLIS));
+    }
+
+    public void onCreate(Context context, Intent intent, int flags, int startId) {
+        super.onCreate(context, intent, flags, startId);
+        mPhone = intent.getParcelableExtra(EXTRA_PHONE_ACCOUNT_HANDLE);
+        mSyncType = intent.getStringExtra(EXTRA_SYNC_TYPE);
+    }
+
+    @Override
+    public void onExecuteInBackgroundThread() {
+        OmtpVvmSyncService service = new OmtpVvmSyncService(getContext());
+        service.sync(this, mSyncType, mPhone, null);
+    }
+
+    @Override
+    public Intent createRestartIntent() {
+        Intent intent = super.createRestartIntent();
+        intent.putExtra(EXTRA_PHONE_ACCOUNT_HANDLE, mPhone);
+        intent.putExtra(EXTRA_SYNC_TYPE, mSyncType);
+        return intent;
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/sync/UploadTask.java b/src/com/android/phone/vvm/omtp/sync/UploadTask.java
new file mode 100644
index 0000000..afdee58
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/sync/UploadTask.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.sync;
+
+import android.content.Context;
+import android.content.Intent;
+
+import com.android.phone.vvm.omtp.scheduling.BaseTask;
+import com.android.phone.vvm.omtp.scheduling.PostponePolicy;
+
+/**
+ * Upload task triggered by database changes. Will wait until the database has been stable for
+ * {@link #POSTPONE_MILLIS} to execute.
+ */
+public class UploadTask extends BaseTask {
+
+    private static final int POSTPONE_MILLIS = 5_000;
+
+    public UploadTask() {
+        super(TASK_UPLOAD);
+        addPolicy(new PostponePolicy(POSTPONE_MILLIS));
+    }
+
+    public static void start(Context context) {
+        Intent intent = BaseTask
+                .createIntent(context, UploadTask.class, TaskId.SUB_ID_ANY);
+        context.startService(intent);
+    }
+
+    @Override
+    public void onExecuteInBackgroundThread() {
+        OmtpVvmSyncService service = new OmtpVvmSyncService(getContext());
+        service.sync(this, OmtpVvmSyncService.SYNC_UPLOAD_ONLY, null, null);
+    }
+}
diff --git a/src/com/android/phone/vvm/omtp/sync/VoicemailProviderChangeReceiver.java b/src/com/android/phone/vvm/omtp/sync/VoicemailProviderChangeReceiver.java
index c2e6178..bf2e125 100644
--- a/src/com/android/phone/vvm/omtp/sync/VoicemailProviderChangeReceiver.java
+++ b/src/com/android/phone/vvm/omtp/sync/VoicemailProviderChangeReceiver.java
@@ -24,15 +24,14 @@
  * Receives changes to the voicemail provider so they can be sent to the voicemail server.
  */
 public class VoicemailProviderChangeReceiver extends BroadcastReceiver {
+
     @Override
     public void onReceive(Context context, Intent intent) {
         boolean isSelfChanged = intent.getBooleanExtra(VoicemailContract.EXTRA_SELF_CHANGE, false);
         OmtpVvmSourceManager vvmSourceManager =
                 OmtpVvmSourceManager.getInstance(context);
         if (vvmSourceManager.getOmtpVvmSources().size() > 0 && !isSelfChanged) {
-            Intent serviceIntent = OmtpVvmSyncService.getSyncIntent(
-                    context, OmtpVvmSyncService.SYNC_UPLOAD_ONLY, null, true /* firstAttempt */);
-            context.startService(serviceIntent);
+            UploadTask.start(context);
         }
     }
 }
diff --git a/src/com/android/phone/vvm/omtp/sync/VvmNetworkRequest.java b/src/com/android/phone/vvm/omtp/sync/VvmNetworkRequest.java
new file mode 100644
index 0000000..fba6a26
--- /dev/null
+++ b/src/com/android/phone/vvm/omtp/sync/VvmNetworkRequest.java
@@ -0,0 +1,104 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.sync;
+
+import android.net.Network;
+import android.telecom.PhoneAccountHandle;
+
+import com.android.phone.vvm.omtp.OmtpVvmCarrierConfigHelper;
+import com.android.phone.vvm.omtp.VvmLog;
+
+import java.io.Closeable;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.Future;
+
+/**
+ * Class to retrieve a {@link Network} synchronously. {@link #getNetwork(OmtpVvmCarrierConfigHelper,
+ * PhoneAccountHandle)} will block until a suitable network is retrieved or it has failed.
+ */
+public class VvmNetworkRequest {
+
+    private static final String TAG = "VvmNetworkRequest";
+
+    /**
+     * A wrapper around a Network returned by a {@link VvmNetworkRequestCallback}, which should be
+     * closed once not needed anymore.
+     */
+    public static class NetworkWrapper implements Closeable {
+
+        private final Network mNetwork;
+        private final VvmNetworkRequestCallback mCallback;
+
+        private NetworkWrapper(Network network, VvmNetworkRequestCallback callback) {
+            mNetwork = network;
+            mCallback = callback;
+        }
+
+        public Network get() {
+            return mNetwork;
+        }
+
+        @Override
+        public void close() {
+            mCallback.releaseNetwork();
+        }
+    }
+
+    public static NetworkWrapper getNetwork(OmtpVvmCarrierConfigHelper config,
+            PhoneAccountHandle handle) {
+        FutureNetworkRequestCallback callback = new FutureNetworkRequestCallback(config, handle);
+        callback.requestNetwork();
+        try {
+            return callback.getFuture().get();
+        } catch (InterruptedException | ExecutionException e) {
+            VvmLog.e(TAG, "can't get future network", e);
+            return null;
+        }
+    }
+
+    private static class FutureNetworkRequestCallback extends VvmNetworkRequestCallback {
+
+        /**
+         * {@link CompletableFuture#get()} will block until {@link CompletableFuture#
+         * complete(Object) } has been called on the other thread.
+         */
+        private final CompletableFuture<NetworkWrapper> mFuture = new CompletableFuture<>();
+
+        public FutureNetworkRequestCallback(OmtpVvmCarrierConfigHelper config,
+                PhoneAccountHandle phoneAccount) {
+            super(config, phoneAccount);
+        }
+
+        public Future<NetworkWrapper> getFuture() {
+            return mFuture;
+        }
+
+        @Override
+        public void onAvailable(Network network) {
+            super.onAvailable(network);
+            mFuture.complete(new NetworkWrapper(network, this));
+        }
+
+        @Override
+        public void onFailed(String reason) {
+            super.onFailed(reason);
+            mFuture.complete(null);
+        }
+
+    }
+}
diff --git a/tests/Android.mk b/tests/Android.mk
index e1b564f..59cba42 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -25,7 +25,7 @@
 
 LOCAL_MODULE_TAGS := tests
 
-LOCAL_JAVA_LIBRARIES := telephony-common
+LOCAL_JAVA_LIBRARIES := telephony-common android-support-test
 
 LOCAL_INSTRUMENTATION_FOR := TeleService
 
diff --git a/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTest.java b/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTest.java
new file mode 100644
index 0000000..27dd87e
--- /dev/null
+++ b/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTest.java
@@ -0,0 +1,130 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.spy;
+import static org.mockito.Mockito.verify;
+
+import android.support.test.runner.AndroidJUnit4;
+
+import com.android.phone.vvm.omtp.scheduling.Task.TaskId;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+@RunWith(AndroidJUnit4.class)
+public class BaseTaskTest extends BaseTaskTestBase {
+
+
+    @Test
+    public void testBaseTask() {
+        DummyBaseTask task = (DummyBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, DummyBaseTask.class, 123));
+        assertTrue(task.getId().equals(new TaskId(1, 123)));
+        assertTrue(!task.hasStarted());
+        assertTrue(!task.hasRun);
+        mService.runNextTask();
+        assertTrue(task.hasStarted());
+        assertTrue(task.hasRun);
+        verify(task.policy).onBeforeExecute();
+        verify(task.policy).onCompleted();
+    }
+
+    @Test
+    public void testFail() {
+        FailingBaseTask task = (FailingBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, FailingBaseTask.class, 0));
+        mService.runNextTask();
+        verify(task.policy).onFail();
+    }
+
+    @Test
+    public void testDuplicated() {
+        DummyBaseTask task1 = (DummyBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, DummyBaseTask.class, 123));
+        verify(task1.policy, never()).onDuplicatedTaskAdded();
+
+        DummyBaseTask task2 = (DummyBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, DummyBaseTask.class, 123));
+        verify(task1.policy).onDuplicatedTaskAdded();
+
+        mService.runNextTask();
+        assertTrue(task1.hasRun);
+        assertTrue(!task2.hasRun);
+    }
+
+    @Test
+    public void testDuplicated_DifferentSubId() {
+        DummyBaseTask task1 = (DummyBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, DummyBaseTask.class, 123));
+        verify(task1.policy, never()).onDuplicatedTaskAdded();
+
+        DummyBaseTask task2 = (DummyBaseTask) submitTask(
+                BaseTask.createIntent(mTestContext, DummyBaseTask.class, 456));
+        verify(task1.policy, never()).onDuplicatedTaskAdded();
+        mService.runNextTask();
+        assertTrue(task1.hasRun);
+        assertTrue(!task2.hasRun);
+
+        mService.runNextTask();
+        assertTrue(task2.hasRun);
+    }
+
+    @Test
+    public void testReadyTime() {
+        BaseTask task = spy(new DummyBaseTask());
+        assertTrue(task.getReadyInMilliSeconds() == 0);
+        mTime = 500;
+        assertTrue(task.getReadyInMilliSeconds() == -500);
+        task.setExecutionTime(1000);
+        assertTrue(task.getReadyInMilliSeconds() == 500);
+    }
+
+    public static class DummyBaseTask extends BaseTask {
+
+        public Policy policy;
+        public boolean hasRun = false;
+
+        public DummyBaseTask() {
+            super(1);
+            policy = mock(Policy.class);
+            addPolicy(policy);
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            hasRun = true;
+        }
+    }
+
+    public static class FailingBaseTask extends BaseTask {
+
+        public Policy policy;
+        public FailingBaseTask() {
+            super(1);
+            policy = mock(Policy.class);
+            addPolicy(policy);
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            fail();
+        }
+    }
+}
diff --git a/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTestBase.java b/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTestBase.java
new file mode 100644
index 0000000..1ffd3c4
--- /dev/null
+++ b/tests/src/com/android/phone/vvm/omtp/scheduling/BaseTaskTestBase.java
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import com.android.phone.vvm.omtp.scheduling.BaseTask.Clock;
+
+import org.junit.After;
+import org.junit.Before;
+
+public class BaseTaskTestBase extends TaskSchedulerServiceTestBase {
+
+    /**
+     * "current time" of the deterministic clock.
+     */
+    public long mTime;
+
+    @Before
+    public void setUpBaseTaskTest() {
+        mTime = 0;
+        BaseTask.setClockForTesting(new TestClock());
+    }
+
+    @After
+    public void tearDownBaseTaskTest() {
+        BaseTask.setClockForTesting(new Clock());
+    }
+
+
+    private class TestClock extends Clock {
+
+        @Override
+        public long getTimeMillis() {
+            return mTime;
+        }
+    }
+}
diff --git a/tests/src/com/android/phone/vvm/omtp/scheduling/PolicyTest.java b/tests/src/com/android/phone/vvm/omtp/scheduling/PolicyTest.java
new file mode 100644
index 0000000..9761d01
--- /dev/null
+++ b/tests/src/com/android/phone/vvm/omtp/scheduling/PolicyTest.java
@@ -0,0 +1,145 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import android.support.test.runner.AndroidJUnit4;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+@RunWith(AndroidJUnit4.class)
+public class PolicyTest extends BaseTaskTestBase {
+
+    private static int sExecuteCounter;
+
+    @Before
+    public void setUpPolicyTest() {
+        sExecuteCounter = 0;
+    }
+
+    @Test
+    public void testPostponePolicy() {
+        Task task = submitTask(BaseTask.createIntent(mTestContext, PostponeTask.class, 0));
+        mService.runNextTask();
+        assertTrue(task.getReadyInMilliSeconds() == 1000);
+        submitTask(BaseTask.createIntent(mTestContext, PostponeTask.class, 0));
+        assertTrue(task.getReadyInMilliSeconds() == 1000);
+        mTime = 500;
+        submitTask(BaseTask.createIntent(mTestContext, PostponeTask.class, 0));
+        assertTrue(task.getReadyInMilliSeconds() == 1000);
+        mTime = 2500;
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 1);
+    }
+
+    @Test
+    public void testRetryPolicy() {
+        Task task = submitTask(BaseTask.createIntent(mTestContext, FailingRetryTask.class, 0));
+        mService.runNextTask();
+        // Should queue retry at 1000
+        assertTrue(sExecuteCounter == 1);
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 1);
+        mTime = 1500;
+        mService.runNextTask();
+        // Should queue retry at 2500
+        assertTrue(sExecuteCounter == 2);
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 2);
+        mTime = 2000;
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 2);
+        mTime = 3000;
+        mService.runNextTask();
+        // No more retries are queued.
+        assertTrue(sExecuteCounter == 3);
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 3);
+        mTime = 4500;
+        mService.runNextTask();
+        assertTrue(sExecuteCounter == 3);
+    }
+
+    @Test
+    public void testMinimalIntervalPolicy() {
+        MinimalIntervalPolicyTask task1 = (MinimalIntervalPolicyTask) submitTask(
+                BaseTask.createIntent(mTestContext, MinimalIntervalPolicyTask.class, 0));
+        mService.runNextTask();
+        assertTrue(task1.hasRan);
+        MinimalIntervalPolicyTask task2 = (MinimalIntervalPolicyTask) submitTask(
+                BaseTask.createIntent(mTestContext, MinimalIntervalPolicyTask.class, 0));
+        mService.runNextTask();
+        assertTrue(!task2.hasRan);
+
+        mTime = 1500;
+        mService.runNextTask();
+
+        MinimalIntervalPolicyTask task3 = (MinimalIntervalPolicyTask) submitTask(
+                BaseTask.createIntent(mTestContext, MinimalIntervalPolicyTask.class, 0));
+        mService.runNextTask();
+        assertTrue(task3.hasRan);
+    }
+
+    public abstract static class PolicyTestTask extends BaseTask {
+
+        public PolicyTestTask() {
+            super(1);
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            sExecuteCounter++;
+        }
+    }
+
+    public static class PostponeTask extends PolicyTestTask {
+
+        PostponeTask() {
+            addPolicy(new PostponePolicy(1000));
+        }
+    }
+
+    public static class FailingRetryTask extends PolicyTestTask {
+
+        public FailingRetryTask() {
+            addPolicy(new RetryPolicy(2, 1000));
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            super.onExecuteInBackgroundThread();
+            fail();
+        }
+    }
+
+    public static class MinimalIntervalPolicyTask extends PolicyTestTask {
+
+        boolean hasRan;
+
+        MinimalIntervalPolicyTask() {
+            addPolicy(new MinimalIntervalPolicy(1000));
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            super.onExecuteInBackgroundThread();
+            hasRan = true;
+        }
+    }
+
+}
diff --git a/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTest.java b/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTest.java
new file mode 100644
index 0000000..2dd4ecf
--- /dev/null
+++ b/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTest.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import android.support.test.runner.AndroidJUnit4;
+
+import com.android.phone.vvm.omtp.scheduling.Task.TaskId;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.concurrent.TimeoutException;
+
+@RunWith(AndroidJUnit4.class)
+public class TaskSchedulerServiceTest extends TaskSchedulerServiceTestBase {
+
+    @Test
+    public void testTaskIdComparison() {
+        TaskId id1 = new TaskId(1, 1);
+        TaskId id2 = new TaskId(1, 1);
+        TaskId id3 = new TaskId(1, 2);
+        assertTrue(id1.equals(id2));
+        assertTrue(id1.equals(id1));
+        assertTrue(!id1.equals(id3));
+    }
+
+    @Test
+    public void testAddDuplicatedTask() throws TimeoutException {
+        TestTask task1 = (TestTask) submitTask(
+                TaskSchedulerService.createIntent(mTestContext, TestTask.class));
+        TestTask task2 = (TestTask) submitTask(
+                TaskSchedulerService.createIntent(mTestContext, TestTask.class));
+        assertTrue(task1.onDuplicatedTaskAddedCounter.invokedOnce());
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyNotRan(task2);
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyNotRan(task2);
+    }
+
+    @Test
+    public void testAddDuplicatedTaskAfterFirstCompleted() throws TimeoutException {
+        TestTask task1 = (TestTask) submitTask(
+                TaskSchedulerService.createIntent(mTestContext, TestTask.class));
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        TestTask task2 = (TestTask) submitTask(
+                TaskSchedulerService.createIntent(mTestContext, TestTask.class));
+        assertTrue(task1.onDuplicatedTaskAddedCounter.neverInvoked());
+        mService.runNextTask();
+        verifyRanOnce(task2);
+    }
+
+    @Test
+    public void testAddMultipleTask() {
+        TestTask task1 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(1, 0)));
+        TestTask task2 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(2, 0)));
+        TestTask task3 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(1, 1)));
+        assertTrue(task1.onDuplicatedTaskAddedCounter.neverInvoked());
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyNotRan(task2);
+        verifyNotRan(task3);
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyRanOnce(task2);
+        verifyNotRan(task3);
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyRanOnce(task2);
+        verifyRanOnce(task3);
+    }
+
+    @Test
+    public void testNotReady() {
+        TestTask task1 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(1, 0)));
+        task1.readyInMilliseconds = 1000;
+        mService.runNextTask();
+        verifyNotRan(task1);
+        TestTask task2 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(2, 0)));
+        mService.runNextTask();
+        verifyNotRan(task1);
+        verifyRanOnce(task2);
+        task1.readyInMilliseconds = 50;
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyRanOnce(task2);
+    }
+
+    @Test
+    public void testInvalidTaskId() {
+        Task task = mock(Task.class);
+        when(task.getId()).thenReturn(new TaskId(Task.TASK_INVALID, 0));
+        thrown.expect(AssertionError.class);
+        mService.addTask(task);
+    }
+
+    @Test
+    public void testDuplicatesAllowedTaskId() {
+        TestTask task1 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(Task.TASK_ALLOW_DUPLICATES, 0)));
+        TestTask task2 = (TestTask) submitTask(
+                putTaskId(TaskSchedulerService.createIntent(mTestContext, TestTask.class),
+                        new TaskId(Task.TASK_ALLOW_DUPLICATES, 0)));
+        assertTrue(task1.onDuplicatedTaskAddedCounter.neverInvoked());
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyNotRan(task2);
+        mService.runNextTask();
+        verifyRanOnce(task1);
+        verifyRanOnce(task2);
+    }
+}
diff --git a/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTestBase.java b/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTestBase.java
new file mode 100644
index 0000000..63f5c2f
--- /dev/null
+++ b/tests/src/com/android/phone/vvm/omtp/scheduling/TaskSchedulerServiceTestBase.java
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.phone.vvm.omtp.scheduling;
+
+import static org.mockito.Matchers.any;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import android.content.ComponentName;
+import android.content.Context;
+import android.content.Intent;
+import android.os.IBinder;
+import android.os.Message;
+import android.support.test.InstrumentationRegistry;
+import android.support.test.rule.ServiceTestRule;
+import android.support.test.runner.AndroidJUnit4;
+
+import com.android.phone.Assert;
+import com.android.phone.vvm.omtp.scheduling.Task.TaskId;
+import com.android.phone.vvm.omtp.scheduling.TaskSchedulerService.MainThreadHandler;
+import com.android.phone.vvm.omtp.scheduling.TaskSchedulerService.WorkerThreadHandler;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.rules.ExpectedException;
+import org.junit.runner.RunWith;
+
+import java.util.concurrent.TimeoutException;
+
+@RunWith(AndroidJUnit4.class)
+public class TaskSchedulerServiceTestBase {
+
+    private static final String EXTRA_ID = "test_extra_id";
+    private static final String EXTRA_SUB_ID = "test_extra_sub_id";
+
+    public TaskSchedulerService mService;
+
+    @Rule
+    public final ExpectedException thrown = ExpectedException.none();
+
+    @Rule
+    public final ServiceTestRule mServiceRule = new ServiceTestRule();
+
+    public Context mTargetContext;
+    public Context mTestContext;
+
+    private static boolean sIsMainThread = true;
+
+    private final TestMessageSender mMessageSender = new TestMessageSender();
+
+    public static Intent putTaskId(Intent intent, TaskId taskId) {
+        intent.putExtra(EXTRA_ID, taskId.id);
+        intent.putExtra(EXTRA_SUB_ID, taskId.subId);
+        return intent;
+    }
+
+    public static TaskId getTaskId(Intent intent) {
+        return new TaskId(intent.getIntExtra(EXTRA_ID, 0), intent.getIntExtra(EXTRA_SUB_ID, 0));
+    }
+
+    @Before
+    public void setUp() throws TimeoutException {
+        Assert.setIsMainThreadForTesting(true);
+        mTargetContext = InstrumentationRegistry.getTargetContext();
+        IBinder binder = null;
+        // bindService() might returns null on 2nd invocation because the service is not unbinded
+        // yet. See https://code.google.com/p/android/issues/detail?id=180396
+        while (binder == null) {
+            binder = mServiceRule
+                    .bindService(new Intent(mTargetContext, TaskSchedulerService.class));
+        }
+        mService = ((TaskSchedulerService.LocalBinder) binder).getService();
+        mTestContext = createTestContext(mTargetContext, mService);
+        mService.setMessageSenderForTest(mMessageSender);
+        mService.setTaskAutoRunDisabledForTest(true);
+        mService.setContextForTest(mTestContext);
+    }
+
+    @After
+    public void tearDown() {
+        Assert.setIsMainThreadForTesting(null);
+        mService.setTaskAutoRunDisabledForTest(false);
+        mService.clearTasksForTest();
+        mService.stopSelf();
+    }
+
+    public Task submitTask(Intent intent) {
+        Task task = mService.createTask(intent, 0, 0);
+        mService.addTask(task);
+        return task;
+    }
+
+    public static void verifyRanOnce(TestTask task) {
+        assertTrue(task.onBeforeExecuteCounter.invokedOnce());
+        assertTrue(task.executeCounter.invokedOnce());
+        assertTrue(task.onCompletedCounter.invokedOnce());
+    }
+
+    public static void verifyNotRan(TestTask task) {
+        assertTrue(task.onBeforeExecuteCounter.neverInvoked());
+        assertTrue(task.executeCounter.neverInvoked());
+        assertTrue(task.onCompletedCounter.neverInvoked());
+    }
+
+    public static class TestTask implements Task {
+
+        public int readyInMilliseconds;
+
+        private TaskId mId;
+
+        public final InvocationCounter onCreateCounter = new InvocationCounter();
+        public final InvocationCounter onBeforeExecuteCounter = new InvocationCounter();
+        public final InvocationCounter executeCounter = new InvocationCounter();
+        public final InvocationCounter onCompletedCounter = new InvocationCounter();
+        public final InvocationCounter onDuplicatedTaskAddedCounter = new InvocationCounter();
+
+        @Override
+        public void onCreate(Context context, Intent intent, int flags, int startId) {
+            onCreateCounter.invoke();
+            mId = getTaskId(intent);
+        }
+
+        @Override
+        public TaskId getId() {
+            return mId;
+        }
+
+        @Override
+        public long getReadyInMilliSeconds() {
+            Assert.isMainThread();
+            return readyInMilliseconds;
+        }
+
+        @Override
+        public void onBeforeExecute() {
+            Assert.isMainThread();
+            onBeforeExecuteCounter.invoke();
+        }
+
+        @Override
+        public void onExecuteInBackgroundThread() {
+            Assert.isNotMainThread();
+            executeCounter.invoke();
+        }
+
+        @Override
+        public void onCompleted() {
+            Assert.isMainThread();
+            onCompletedCounter.invoke();
+        }
+
+        @Override
+        public void onDuplicatedTaskAdded(Task task) {
+            Assert.isMainThread();
+            onDuplicatedTaskAddedCounter.invoke();
+        }
+    }
+
+    public static class InvocationCounter {
+
+        private int mCounter;
+
+        public void invoke() {
+            mCounter++;
+        }
+
+        public boolean invokedOnce() {
+            return mCounter == 1;
+        }
+
+        public boolean neverInvoked() {
+            return mCounter == 0;
+        }
+    }
+
+    private class TestMessageSender extends TaskSchedulerService.MessageSender {
+
+        @Override
+        public void send(Message message) {
+            if (message.getTarget() instanceof MainThreadHandler) {
+                Assert.setIsMainThreadForTesting(true);
+            } else if (message.getTarget() instanceof WorkerThreadHandler) {
+                Assert.setIsMainThreadForTesting(false);
+            } else {
+                throw new AssertionError("unexpected Handler " + message.getTarget());
+            }
+            message.getTarget().handleMessage(message);
+        }
+    }
+
+    public static void assertTrue(boolean condition) {
+        if (!condition) {
+            throw new AssertionError();
+        }
+    }
+
+    private static Context createTestContext(Context targetContext, TaskSchedulerService service) {
+        TestContext context = mock(TestContext.class);
+        when(context.getService()).thenReturn(service);
+        when(context.startService(any())).thenCallRealMethod();
+        when(context.getPackageName()).thenReturn(targetContext.getPackageName());
+        return context;
+    }
+
+    public abstract class TestContext extends Context {
+
+        @Override
+        public ComponentName startService(Intent service) {
+            getService().onStartCommand(service, 0, 0);
+            return null;
+        }
+
+        public abstract TaskSchedulerService getService();
+    }
+}