diff --git a/media/libmediatranscoding/TranscodingJobScheduler.cpp b/media/libmediatranscoding/TranscodingJobScheduler.cpp
index 1b36d4c..ea07c5f 100644
--- a/media/libmediatranscoding/TranscodingJobScheduler.cpp
+++ b/media/libmediatranscoding/TranscodingJobScheduler.cpp
@@ -76,7 +76,7 @@
         // the topJob now.
         if (!mResourceLost) {
             if (topJob->state == Job::NOT_STARTED) {
-                mTranscoder->start(topJob->key.first, topJob->key.second);
+                mTranscoder->start(topJob->key.first, topJob->key.second, curJob->request);
             } else if (topJob->state == Job::PAUSED) {
                 mTranscoder->resume(topJob->key.first, topJob->key.second);
             }
@@ -257,9 +257,12 @@
     }
 
     for (auto it = jobsToRemove.begin(); it != jobsToRemove.end(); ++it) {
-        // If the job is running, pause it first.
-        if (mJobMap[*it].state == Job::RUNNING) {
-            mTranscoder->pause(clientId, jobId);
+        // If the job has ever been started, stop it now.
+        // Note that stop() is needed even if the job is currently paused. This instructs
+        // the transcoder to discard any states for the job, otherwise the states may
+        // never be discarded.
+        if (mJobMap[*it].state != Job::NOT_STARTED) {
+            mTranscoder->stop(it->first, it->second);
         }
 
         // Remove the job.
diff --git a/media/libmediatranscoding/include/media/TranscoderInterface.h b/media/libmediatranscoding/include/media/TranscoderInterface.h
index 52b357d..ef51f65 100644
--- a/media/libmediatranscoding/include/media/TranscoderInterface.h
+++ b/media/libmediatranscoding/include/media/TranscoderInterface.h
@@ -18,11 +18,13 @@
 #define ANDROID_MEDIA_TRANSCODER_INTERFACE_H
 
 #include <aidl/android/media/TranscodingErrorCode.h>
+#include <aidl/android/media/TranscodingRequestParcel.h>
 #include <media/TranscodingDefs.h>
 
 namespace android {
 
 using ::aidl::android::media::TranscodingErrorCode;
+using ::aidl::android::media::TranscodingRequestParcel;
 class TranscoderCallbackInterface;
 
 // Interface for the scheduler to call the transcoder to take actions.
@@ -31,9 +33,11 @@
     // TODO(chz): determine what parameters are needed here.
     // For now, always pass in clientId&jobId.
     virtual void setCallback(const std::shared_ptr<TranscoderCallbackInterface>& cb) = 0;
-    virtual void start(ClientIdType clientId, JobIdType jobId) = 0;
+    virtual void start(ClientIdType clientId, JobIdType jobId,
+                       const TranscodingRequestParcel& request) = 0;
     virtual void pause(ClientIdType clientId, JobIdType jobId) = 0;
     virtual void resume(ClientIdType clientId, JobIdType jobId) = 0;
+    virtual void stop(ClientIdType clientId, JobIdType jobId) = 0;
 
 protected:
     virtual ~TranscoderInterface() = default;
diff --git a/media/libmediatranscoding/tests/TranscodingJobScheduler_tests.cpp b/media/libmediatranscoding/tests/TranscodingJobScheduler_tests.cpp
index 6931490..25321e3 100644
--- a/media/libmediatranscoding/tests/TranscodingJobScheduler_tests.cpp
+++ b/media/libmediatranscoding/tests/TranscodingJobScheduler_tests.cpp
@@ -39,6 +39,7 @@
 using aidl::android::media::BnTranscodingClientCallback;
 using aidl::android::media::IMediaTranscodingService;
 using aidl::android::media::ITranscodingClient;
+using aidl::android::media::TranscodingRequestParcel;
 
 constexpr ClientIdType kClientId = 1000;
 constexpr JobIdType kClientJobId = 0;
@@ -86,7 +87,8 @@
     // TranscoderInterface
     void setCallback(const std::shared_ptr<TranscoderCallbackInterface>& /*cb*/) override {}
 
-    void start(ClientIdType clientId, JobIdType jobId) override {
+    void start(ClientIdType clientId, JobIdType jobId,
+               const TranscodingRequestParcel& /*request*/) override {
         mEventQueue.push_back(Start(clientId, jobId));
     }
     void pause(ClientIdType clientId, JobIdType jobId) override {
@@ -95,6 +97,9 @@
     void resume(ClientIdType clientId, JobIdType jobId) override {
         mEventQueue.push_back(Resume(clientId, jobId));
     }
+    void stop(ClientIdType clientId, JobIdType jobId) override {
+        mEventQueue.push_back(Stop(clientId, jobId));
+    }
 
     void onFinished(ClientIdType clientId, JobIdType jobId) {
         mEventQueue.push_back(Finished(clientId, jobId));
@@ -112,7 +117,7 @@
     }
 
     struct Event {
-        enum { NoEvent, Start, Pause, Resume, Finished, Failed } type;
+        enum { NoEvent, Start, Pause, Resume, Stop, Finished, Failed } type;
         ClientIdType clientId;
         JobIdType jobId;
     };
@@ -127,6 +132,7 @@
     DECLARE_EVENT(Start);
     DECLARE_EVENT(Pause);
     DECLARE_EVENT(Resume);
+    DECLARE_EVENT(Stop);
     DECLARE_EVENT(Finished);
     DECLARE_EVENT(Failed);
 
@@ -296,11 +302,20 @@
     EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::NoEvent);
 
     // Cancel running real-time job JOB(0).
-    // - Should be paused first then cancelled.
+    // - Should be stopped first then cancelled.
     // - Should also start offline job JOB(2) because real-time queue is empty.
     EXPECT_TRUE(mScheduler->cancel(CLIENT(0), JOB(0)));
-    EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Pause(CLIENT(0), JOB(0)));
+    EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Stop(CLIENT(0), JOB(0)));
     EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Start(CLIENT(0), JOB(3)));
+
+    // Submit real-time job JOB(4), offline JOB(3) should pause and JOB(4) should start.
+    mScheduler->submit(CLIENT(0), JOB(4), UID(0), mRealtimeRequest, mClientCallback0);
+    EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Pause(CLIENT(0), JOB(3)));
+    EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Start(CLIENT(0), JOB(4)));
+
+    // Cancel paused JOB(3). JOB(3) should be stopped.
+    EXPECT_TRUE(mScheduler->cancel(CLIENT(0), JOB(3)));
+    EXPECT_EQ(mTranscoder->popEvent(), TestTranscoder::Stop(CLIENT(0), JOB(3)));
 }
 
 TEST_F(TranscodingJobSchedulerTest, TestFinishJob) {
diff --git a/services/mediatranscoding/SimulatedTranscoder.cpp b/services/mediatranscoding/SimulatedTranscoder.cpp
index aa397d8..1b68d5c 100644
--- a/services/mediatranscoding/SimulatedTranscoder.cpp
+++ b/services/mediatranscoding/SimulatedTranscoder.cpp
@@ -47,7 +47,8 @@
     mCallback = cb;
 }
 
-void SimulatedTranscoder::start(ClientIdType clientId, JobIdType jobId) {
+void SimulatedTranscoder::start(ClientIdType clientId, JobIdType jobId,
+                                const TranscodingRequestParcel& /*request*/) {
     queueEvent(Event::Start, clientId, jobId);
 }
 
@@ -59,6 +60,10 @@
     queueEvent(Event::Resume, clientId, jobId);
 }
 
+void SimulatedTranscoder::stop(ClientIdType clientId, JobIdType jobId) {
+    queueEvent(Event::Stop, clientId, jobId);
+}
+
 void SimulatedTranscoder::queueEvent(Event::Type type, ClientIdType clientId, JobIdType jobId) {
     ALOGV("%s: job {%lld, %d}: %s", __FUNCTION__, (long long)clientId, jobId, toString(type));
 
@@ -120,12 +125,12 @@
                 if (event.type == Event::Start) {
                     remainingUs = std::chrono::microseconds(kJobDurationUs);
                 }
-            } else if (running && event.type == Event::Pause) {
+            } else if (running && (event.type == Event::Pause || event.type == Event::Stop)) {
                 running = false;
                 remainingUs -= (std::chrono::system_clock::now() - lastRunningTime);
             } else {
                 ALOGW("%s: discarding bad event: job {%lld, %d}: %s", __FUNCTION__,
-                        (long long)event.clientId, event.jobId, toString(event.type));
+                      (long long)event.clientId, event.jobId, toString(event.type));
                 continue;
             }
 
diff --git a/services/mediatranscoding/SimulatedTranscoder.h b/services/mediatranscoding/SimulatedTranscoder.h
index 6e6da64..646ba4e 100644
--- a/services/mediatranscoding/SimulatedTranscoder.h
+++ b/services/mediatranscoding/SimulatedTranscoder.h
@@ -37,7 +37,7 @@
 class SimulatedTranscoder : public TranscoderInterface {
 public:
     struct Event {
-        enum Type { NoEvent, Start, Pause, Resume, Finished, Failed } type;
+        enum Type { NoEvent, Start, Pause, Resume, Stop, Finished, Failed } type;
         ClientIdType clientId;
         JobIdType jobId;
     };
@@ -48,9 +48,11 @@
 
     // TranscoderInterface
     void setCallback(const std::shared_ptr<TranscoderCallbackInterface>& cb) override;
-    void start(ClientIdType clientId, JobIdType jobId) override;
+    void start(ClientIdType clientId, JobIdType jobId,
+               const TranscodingRequestParcel& request) override;
     void pause(ClientIdType clientId, JobIdType jobId) override;
     void resume(ClientIdType clientId, JobIdType jobId) override;
+    void stop(ClientIdType clientId, JobIdType jobId) override;
     // ~TranscoderInterface
 
 private: