diff --git a/src/com/android/documentsui/services/FileOperationService.java b/src/com/android/documentsui/services/FileOperationService.java
index 40f18d3..fa97ebf 100644
--- a/src/com/android/documentsui/services/FileOperationService.java
+++ b/src/com/android/documentsui/services/FileOperationService.java
@@ -37,13 +37,12 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.util.ArrayList;
-import java.util.HashMap;
+import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
-import java.util.concurrent.atomic.AtomicReference;
 
 import javax.annotation.concurrent.GuardedBy;
 
@@ -99,9 +98,9 @@
 
     private static final int POOL_SIZE = 2;  // "pool size", not *max* "pool size".
 
-    private static final int NOTIFICATION_ID_PROGRESS = 0;
-    private static final int NOTIFICATION_ID_FAILURE = 1;
-    private static final int NOTIFICATION_ID_WARNING = 2;
+    @VisibleForTesting static final int NOTIFICATION_ID_PROGRESS = 1;
+    private static final int NOTIFICATION_ID_FAILURE = 2;
+    private static final int NOTIFICATION_ID_WARNING = 3;
 
     // The executor and job factory are visible for testing and non-final
     // so we'll have a way to inject test doubles from the test. It's
@@ -124,10 +123,11 @@
     @VisibleForTesting Features features;
 
     @GuardedBy("mJobs")
-    private final Map<String, JobRecord> mJobs = new HashMap<>();
+    private final Map<String, JobRecord> mJobs = new LinkedHashMap<>();
 
     // The job whose notification is used to keep the service in foreground mode.
-    private final AtomicReference<Job> mForegroundJob = new AtomicReference<>();
+    @GuardedBy("mJobs")
+    private Job mForegroundJob;
 
     private PowerManager mPowerManager;
     private PowerManager.WakeLock mWakeLock;  // the wake lock, if held.
@@ -270,6 +270,7 @@
             JobRecord record = mJobs.get(jobId);
             if (record != null) {
                 record.job.cancel();
+                updateForegroundState(record.job);
             }
         }
 
@@ -343,18 +344,23 @@
 
         Notification notification = job.getSetupNotification();
         // If there is no foreground job yet, set this job to foreground job.
-        if (mForegroundJob.compareAndSet(null, job)) {
-            if (DEBUG) Log.d(TAG, "Set foreground job to " + job.id);
-            foregroundManager.startForeground(NOTIFICATION_ID_PROGRESS, notification);
+        synchronized (mJobs) {
+            if (mForegroundJob == null) {
+                if (DEBUG) Log.d(TAG, "Set foreground job to " + job.id);
+                mForegroundJob = job;
+                foregroundManager.startForeground(NOTIFICATION_ID_PROGRESS, notification);
+            } else {
+                // Show start up notification
+                if (DEBUG) Log.d(TAG, "Posting notification for " + job.id);
+                notificationManager.notify(
+                        mForegroundJob == job ? null : job.id,
+                        NOTIFICATION_ID_PROGRESS,
+                        notification);
+            }
         }
 
-        // Show start up notification
-        if (DEBUG) Log.d(TAG, "Posting notification for " + job.id);
-        notificationManager.notify(
-                job.id, NOTIFICATION_ID_PROGRESS, notification);
-
         // Set up related monitor
-        JobMonitor monitor = new JobMonitor(job, notificationManager, handler, mJobs);
+        JobMonitor monitor = new JobMonitor(job);
         monitor.start();
     }
 
@@ -388,11 +394,12 @@
 
     @GuardedBy("mJobs")
     private void updateForegroundState(Job job) {
-        Job candidate = mJobs.isEmpty() ? null : mJobs.values().iterator().next().job;
+        Job candidate = getCandidateForegroundJob();
 
         // If foreground job is retiring and there is still work to do, we need to set it to a new
         // job.
-        if (mForegroundJob.compareAndSet(job, candidate)) {
+        if (mForegroundJob == job) {
+            mForegroundJob = candidate;
             if (candidate == null) {
                 if (DEBUG) Log.d(TAG, "Stop foreground");
                 // Remove the notification here just in case we're torn down before we have the
@@ -401,12 +408,11 @@
             } else {
                 if (DEBUG) Log.d(TAG, "Switch foreground job to " + candidate.id);
 
+                notificationManager.cancel(candidate.id, NOTIFICATION_ID_PROGRESS);
                 Notification notification = (candidate.getState() == Job.STATE_STARTED)
                         ? candidate.getSetupNotification()
                         : candidate.getProgressNotification();
-                foregroundManager.startForeground(NOTIFICATION_ID_PROGRESS, notification);
-                notificationManager.notify(candidate.id, NOTIFICATION_ID_PROGRESS,
-                        notification);
+                notificationManager.notify(NOTIFICATION_ID_PROGRESS, notification);
             }
         }
     }
@@ -435,6 +441,19 @@
         }
     }
 
+    @GuardedBy("mJobs")
+    private Job getCandidateForegroundJob() {
+        if (mJobs.isEmpty()) {
+            return null;
+        }
+        for (JobRecord rec : mJobs.values()) {
+            if (!rec.job.isFinished()) {
+                return rec.job;
+            }
+        }
+        return null;
+    }
+
     private static final class JobRecord {
         private final Job job;
         private final Future<?> future;
@@ -452,29 +471,22 @@
      * still need to update notifications if jobs hang, so instead of jobs pushing their states,
      * we poll states of jobs.
      */
-    private static final class JobMonitor implements Runnable {
+    private final class JobMonitor implements Runnable {
         private static final long PROGRESS_INTERVAL_MILLIS = 500L;
 
         private final Job mJob;
-        private final NotificationManager mNotificationManager;
-        private final Handler mHandler;
-        private final Object mJobsLock;
 
-        private JobMonitor(Job job, NotificationManager notificationManager, Handler handler,
-                Object jobsLock) {
+        private JobMonitor(Job job) {
             mJob = job;
-            mNotificationManager = notificationManager;
-            mHandler = handler;
-            mJobsLock = jobsLock;
         }
 
         private void start() {
-            mHandler.post(this);
+            handler.post(this);
         }
 
         @Override
         public void run() {
-            synchronized (mJobsLock) {
+            synchronized (mJobs) {
                 if (mJob.isFinished()) {
                     // Finish notification is already shown. Progress notification is removed.
                     // Just finish itself.
@@ -483,11 +495,13 @@
 
                 // Only job in set up state has progress bar
                 if (mJob.getState() == Job.STATE_SET_UP) {
-                    mNotificationManager.notify(
-                            mJob.id, NOTIFICATION_ID_PROGRESS, mJob.getProgressNotification());
+                    notificationManager.notify(
+                            mForegroundJob == mJob ? null : mJob.id,
+                            NOTIFICATION_ID_PROGRESS,
+                            mJob.getProgressNotification());
                 }
 
-                mHandler.postDelayed(this, PROGRESS_INTERVAL_MILLIS);
+                handler.postDelayed(this, PROGRESS_INTERVAL_MILLIS);
             }
         }
     }
diff --git a/tests/common/com/android/documentsui/services/TestForegroundManager.java b/tests/common/com/android/documentsui/services/TestForegroundManager.java
index f4ba1c1..8b226a0 100644
--- a/tests/common/com/android/documentsui/services/TestForegroundManager.java
+++ b/tests/common/com/android/documentsui/services/TestForegroundManager.java
@@ -23,17 +23,25 @@
 
 class TestForegroundManager implements FileOperationService.ForegroundManager {
 
+    private final TestNotificationManager mNotificationManager;
     private int mForegroundId = -1;
     private Notification mForegroundNotification;
 
+    TestForegroundManager(TestNotificationManager notificationManager) {
+        assert(notificationManager != null);
+        mNotificationManager = notificationManager;
+    }
+
     @Override
     public void startForeground(int id, Notification notification) {
         mForegroundId = id;
         mForegroundNotification = notification;
+        mNotificationManager.notify(null, mForegroundId, mForegroundNotification);
     }
 
     @Override
     public void stopForeground(boolean cancelNotification) {
+        mNotificationManager.cancel(null, mForegroundId);
         mForegroundId = -1;
         mForegroundNotification = null;
     }
@@ -45,12 +53,4 @@
     void assertInBackground() {
         assertNull(mForegroundNotification);
     }
-
-    int getForegroundId() {
-        return mForegroundId;
-    }
-
-    Notification getForegroundNotification() {
-        return mForegroundNotification;
-    }
 }
diff --git a/tests/common/com/android/documentsui/services/TestNotificationManager.java b/tests/common/com/android/documentsui/services/TestNotificationManager.java
index 463f2d4..5adde65 100644
--- a/tests/common/com/android/documentsui/services/TestNotificationManager.java
+++ b/tests/common/com/android/documentsui/services/TestNotificationManager.java
@@ -17,6 +17,7 @@
 package com.android.documentsui.services;
 
 import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertFalse;
 import static junit.framework.Assert.assertNotNull;
 import static junit.framework.Assert.assertTrue;
 
@@ -32,21 +33,10 @@
 
 class TestNotificationManager {
 
-    private final TestForegroundManager mForegroundManager;
     private final SparseArray<HashMap<String, Notification>> mNotifications = new SparseArray<>();
     private final Answer<Void> mAnswer = this::invoke;
 
-    TestNotificationManager(TestForegroundManager foregroundManager) {
-        assert(foregroundManager != null);
-        mForegroundManager = foregroundManager;
-    }
-
-    private void notify(String tag, int id, Notification notification) {
-        if (notification == mForegroundManager.getForegroundNotification()
-                && id != mForegroundManager.getForegroundId()) {
-            throw new IllegalStateException("Mismatching ID and notification.");
-        }
-
+    void notify(String tag, int id, Notification notification) {
         if (mNotifications.get(id) == null) {
             mNotifications.put(id, new HashMap<>());
         }
@@ -54,14 +44,10 @@
         mNotifications.get(id).put(tag, notification);
     }
 
-    private void cancel(String tag, int id) {
+    void cancel(String tag, int id) {
         final HashMap<String, Notification> idMap = mNotifications.get(id);
         if (idMap != null && idMap.containsKey(tag)) {
-            final Notification notification = idMap.get(tag);
-            // Only cancel non-foreground notification
-            if (mForegroundManager.getForegroundNotification() != notification) {
-                idMap.remove(tag);
-            }
+            idMap.remove(tag);
         }
     }
 
@@ -88,6 +74,14 @@
         return null;
     }
 
+    private boolean hasNotification(int id, String jobId) {
+        if (mNotifications.get(id) == null) {
+            return false;
+        }
+        Notification notification = mNotifications.get(id).get(jobId);
+        return notification != null;
+    }
+
     NotificationManager createNotificationManager() {
         return Mockito.mock(NotificationManager.class, mAnswer);
     }
@@ -100,4 +94,12 @@
 
         assertEquals(expect, count);
     }
+
+    void assertHasNotification(int id, String jobid) {
+        assertTrue(hasNotification(id, jobid));
+    }
+
+    void assertNoNotification(int id, String jobid) {
+        assertFalse(hasNotification(id, jobid));
+    }
 }
diff --git a/tests/unit/com/android/documentsui/services/FileOperationServiceTest.java b/tests/unit/com/android/documentsui/services/FileOperationServiceTest.java
index a210c0e..fbaafe8 100644
--- a/tests/unit/com/android/documentsui/services/FileOperationServiceTest.java
+++ b/tests/unit/com/android/documentsui/services/FileOperationServiceTest.java
@@ -78,8 +78,8 @@
         mExecutor = new TestScheduledExecutorService();
         mDeletionExecutor = new TestScheduledExecutorService();
         mHandler = new TestHandler();
-        mForegroundManager = new TestForegroundManager();
-        mTestNotificationManager = new TestNotificationManager(mForegroundManager);
+        mTestNotificationManager = new TestNotificationManager();
+        mForegroundManager = new TestForegroundManager(mTestNotificationManager);
         TestFeatures features = new TestFeatures();
         features.notificationChannel = InstrumentationRegistry.getTargetContext()
                 .getResources().getBoolean(R.bool.feature_notification_channel);
@@ -294,6 +294,32 @@
         mTestNotificationManager.assertNumberOfNotifications(0);
     }
 
+    public void testNotificationUpdateAfterForegroundJobSwitch() throws Exception {
+        startService(createCopyIntent(newArrayList(ALPHA_DOC), BETA_DOC));
+        startService(createCopyIntent(newArrayList(GAMMA_DOC), DELTA_DOC));
+        Job job1 = mCopyJobs.get(0);
+        Job job2 = mCopyJobs.get(1);
+
+        mService.onStart(job1);
+        mTestNotificationManager.assertHasNotification(
+                FileOperationService.NOTIFICATION_ID_PROGRESS, null);
+
+        mService.onStart(job2);
+        mTestNotificationManager.assertHasNotification(
+                FileOperationService.NOTIFICATION_ID_PROGRESS, job2.id);
+
+        job1.cancel();
+        mService.onFinished(job1);
+        mTestNotificationManager.assertHasNotification(
+                FileOperationService.NOTIFICATION_ID_PROGRESS, null);
+        mTestNotificationManager.assertNoNotification(
+                FileOperationService.NOTIFICATION_ID_PROGRESS, job2.id);
+
+        job2.cancel();
+        mService.onFinished(job2);
+        mTestNotificationManager.assertNumberOfNotifications(0);
+    }
+
     private Intent createCopyIntent(ArrayList<DocumentInfo> files, DocumentInfo dest)
             throws Exception {
         DocumentStack stack = new DocumentStack();