diff --git a/init/reboot.cpp b/init/reboot.cpp
index 17e3576..ce81483 100644
--- a/init/reboot.cpp
+++ b/init/reboot.cpp
@@ -398,7 +398,7 @@
         LOG(INFO) << "terminating init services";
 
         // Ask all services to terminate except shutdown critical ones.
-        ServiceManager::GetInstance().ForEachService([](Service* s) {
+        ServiceManager::GetInstance().ForEachServiceShutdownOrder([](Service* s) {
             if (!s->IsShutdownCritical()) s->Terminate();
         });
 
@@ -434,7 +434,7 @@
 
     // minimum safety steps before restarting
     // 2. kill all services except ones that are necessary for the shutdown sequence.
-    ServiceManager::GetInstance().ForEachService([](Service* s) {
+    ServiceManager::GetInstance().ForEachServiceShutdownOrder([](Service* s) {
         if (!s->IsShutdownCritical()) s->Stop();
     });
     ServiceManager::GetInstance().ReapAnyOutstandingChildren();
@@ -448,7 +448,7 @@
         LOG(INFO) << "vold not running, skipping vold shutdown";
     }
     // logcat stopped here
-    ServiceManager::GetInstance().ForEachService([&kill_after_apps](Service* s) {
+    ServiceManager::GetInstance().ForEachServiceShutdownOrder([&kill_after_apps](Service* s) {
         if (kill_after_apps.count(s->name())) s->Stop();
     });
     // 4. sync, try umount, and optionally run fsck for user shutdown
diff --git a/init/service.cpp b/init/service.cpp
index e800d32..d0a0751 100644
--- a/init/service.cpp
+++ b/init/service.cpp
@@ -155,6 +155,8 @@
     : name(name), value(value) {
 }
 
+unsigned long Service::next_start_order_ = 1;
+
 Service::Service(const std::string& name, const std::vector<std::string>& args)
     : Service(name, 0, 0, 0, {}, 0, 0, "", args) {}
 
@@ -182,6 +184,7 @@
       swappiness_(-1),
       soft_limit_in_bytes_(-1),
       limit_in_bytes_(-1),
+      start_order_(0),
       args_(args) {
     onrestart_.InitSingleTrigger("onrestart");
 }
@@ -283,6 +286,7 @@
 
     pid_ = 0;
     flags_ &= (~SVC_RUNNING);
+    start_order_ = 0;
 
     // Oneshot processes go into the disabled state on exit,
     // except when manually restarted.
@@ -805,6 +809,7 @@
     time_started_ = boot_clock::now();
     pid_ = pid;
     flags_ |= SVC_RUNNING;
+    start_order_ = next_start_order_++;
     process_cgroup_empty_ = false;
 
     errno = -createProcessGroup(uid_, pid_);
@@ -1096,6 +1101,19 @@
     }
 }
 
+// Shutdown services in the opposite order that they were started.
+void ServiceManager::ForEachServiceShutdownOrder(const std::function<void(Service*)>& callback) const {
+    std::vector<Service*> shutdown_services;
+    for (const auto& service : services_) {
+        if (service->start_order() > 0) shutdown_services.emplace_back(service.get());
+    }
+    std::sort(shutdown_services.begin(), shutdown_services.end(),
+              [](const auto& a, const auto& b) { return a->start_order() > b->start_order(); });
+    for (const auto& service : shutdown_services) {
+        callback(service);
+    }
+}
+
 void ServiceManager::ForEachServiceInClass(const std::string& classname,
                                            void (*func)(Service* svc)) const {
     for (const auto& s : services_) {
diff --git a/init/service.h b/init/service.h
index 62a3299..a0dc1b4 100644
--- a/init/service.h
+++ b/init/service.h
@@ -108,6 +108,7 @@
     int priority() const { return priority_; }
     int oom_score_adjust() const { return oom_score_adjust_; }
     bool process_cgroup_empty() const { return process_cgroup_empty_; }
+    unsigned long start_order() const { return start_order_; }
     const std::vector<std::string>& args() const { return args_; }
 
   private:
@@ -149,6 +150,8 @@
     template <typename T>
     bool AddDescriptor(const std::vector<std::string>& args, std::string* err);
 
+    static unsigned long next_start_order_;
+
     std::string name_;
     std::set<std::string> classnames_;
     std::string console_;
@@ -190,6 +193,8 @@
 
     bool process_cgroup_empty_ = false;
 
+    unsigned long start_order_;
+
     std::vector<std::string> args_;
 };
 
@@ -209,6 +214,7 @@
     Service* FindServiceByPid(pid_t pid) const;
     Service* FindServiceByKeychord(int keychord_id) const;
     void ForEachService(const std::function<void(Service*)>& callback) const;
+    void ForEachServiceShutdownOrder(const std::function<void(Service*)>& callback) const;
     void ForEachServiceInClass(const std::string& classname,
                                void (*func)(Service* svc)) const;
     void ForEachServiceWithFlags(unsigned matchflags,