diff --git a/compos/service/Android.bp b/compos/service/Android.bp
index 142460e..6270c9a 100644
--- a/compos/service/Android.bp
+++ b/compos/service/Android.bp
@@ -29,7 +29,9 @@
     apex_available: [
         "com.android.compos",
     ],
-    // Access to SystemService etc
-    sdk_version: "system_server_current",
+    // Access to SystemService, ServiceManager#waitForService etc
+    libs: ["services"],
+    sdk_version: "",
+    platform_apis: true,
     installable: true,
 }
diff --git a/compos/service/java/com/android/server/compos/IsolatedCompilationJobService.java b/compos/service/java/com/android/server/compos/IsolatedCompilationJobService.java
index 7bea1ab..2aacc2d 100644
--- a/compos/service/java/com/android/server/compos/IsolatedCompilationJobService.java
+++ b/compos/service/java/com/android/server/compos/IsolatedCompilationJobService.java
@@ -16,10 +16,20 @@
 
 package com.android.server.compos;
 
+import static java.util.Objects.requireNonNull;
+
 import android.app.job.JobParameters;
 import android.app.job.JobService;
+import android.os.IBinder;
+import android.os.RemoteException;
+import android.os.ServiceManager;
+import android.system.composd.ICompilationTask;
+import android.system.composd.ICompilationTaskCallback;
+import android.system.composd.IIsolatedCompilationService;
 import android.util.Log;
 
+import java.util.concurrent.atomic.AtomicReference;
+
 /**
  * A job scheduler service responsible for performing Isolated Compilation when scheduled.
  *
@@ -28,17 +38,158 @@
 public class IsolatedCompilationJobService extends JobService {
     private static final String TAG = IsolatedCompilationJobService.class.getName();
 
+    private final AtomicReference<CompilationJob> mCurrentJob = new AtomicReference<>();
+
     @Override
     public boolean onStartJob(JobParameters params) {
         Log.i(TAG, "starting job");
 
-        // TODO(b/199147668): Implement
+        CompilationJob oldJob = mCurrentJob.getAndSet(null);
+        if (oldJob != null) {
+            // This should probably never happen, but just in case
+            oldJob.stop();
+        }
 
-        return false; // Finished
+        // This function (and onStopJob) are only ever called on the main thread, so we don't have
+        // to worry about two starts at once, or start and stop happening at once. But onCompletion
+        // can be called on any thread, so we need to be careful with that.
+
+        CompilationCallback callback = new CompilationCallback() {
+            @Override
+            public void onSuccess() {
+                onCompletion(params, true);
+            }
+
+            @Override
+            public void onFailure() {
+                onCompletion(params, false);
+            }
+        };
+        CompilationJob newJob = new CompilationJob(callback);
+        mCurrentJob.set(newJob);
+
+        try {
+            // This can take some time - we need to start up a VM - so we do it on a separate
+            // thread. This thread exits as soon as the compilation Ttsk has been started (or
+            // there's a failure), and then compilation continues in composd and the VM.
+            new Thread("IsolatedCompilationJob_starter") {
+                @Override
+                public void run() {
+                    newJob.start();
+                }
+            }.start();
+        } catch (RuntimeException e) {
+            Log.e(TAG, "Starting CompilationJob failed", e);
+            return false; // We're finished
+        }
+        return true; // Job is running in the background
     }
 
     @Override
     public boolean onStopJob(JobParameters params) {
-        return false; // Don't reschedule
+        CompilationJob job = mCurrentJob.getAndSet(null);
+        if (job == null) {
+            return false; // No need to reschedule, we'd finished
+        } else {
+            job.stop();
+            return true; // We didn't get to finish, please re-schedule
+        }
+    }
+
+    void onCompletion(JobParameters params, boolean succeeded) {
+        Log.i(TAG, "onCompletion, succeeded=" + succeeded);
+
+        CompilationJob job = mCurrentJob.getAndSet(null);
+        if (job == null) {
+            // No need to call jobFinished if we've been told to stop.
+            return;
+        }
+        // On success we don't need to reschedule.
+        // On failure we could reschedule, but that could just use a lot of resources and still
+        // fail; instead we just let odsign do compilation on reboot if necessary.
+        jobFinished(params, /*wantReschedule=*/ false);
+    }
+
+    interface CompilationCallback {
+        void onSuccess();
+
+        void onFailure();
+    }
+
+    static class CompilationJob extends ICompilationTaskCallback.Stub
+            implements IBinder.DeathRecipient {
+        private final AtomicReference<ICompilationTask> mTask = new AtomicReference<>();
+        private final CompilationCallback mCallback;
+        private volatile boolean mStopRequested = false;
+        private volatile boolean mCanceled = false;
+
+        CompilationJob(CompilationCallback callback) {
+            mCallback = requireNonNull(callback);
+        }
+
+        void start() {
+            IBinder binder = ServiceManager.waitForService("android.system.composd");
+            IIsolatedCompilationService composd =
+                    IIsolatedCompilationService.Stub.asInterface(binder);
+
+            if (composd == null) {
+                throw new IllegalStateException("Unable to find composd service");
+            }
+
+            try {
+                ICompilationTask composTask = composd.startTestCompile(this);
+                mTask.set(composTask);
+                composTask.asBinder().linkToDeath(this, 0);
+            } catch (RemoteException e) {
+                throw e.rethrowAsRuntimeException();
+            }
+
+            if (mStopRequested) {
+                // We were asked to stop while we were starting the task. We need to
+                // cancel it now, since we couldn't before.
+                cancelTask();
+            }
+        }
+
+        void stop() {
+            mStopRequested = true;
+            cancelTask();
+        }
+
+        private void cancelTask() {
+            ICompilationTask task = mTask.getAndSet(null);
+            if (task != null) {
+                mCanceled = true;
+                Log.i(TAG, "Cancelling task");
+                try {
+                    task.cancel();
+                } catch (RuntimeException | RemoteException e) {
+                    // If canceling failed we'll assume it means that the task has already failed;
+                    // there's nothing else we can do anyway.
+                    Log.w(TAG, "Failed to cancel CompilationTask", e);
+                }
+            }
+        }
+
+        @Override
+        public void binderDied() {
+            onFailure();
+        }
+
+        @Override
+        public void onSuccess() {
+            mTask.set(null);
+            if (!mCanceled) {
+                mCallback.onSuccess();
+            }
+        }
+
+        @Override
+        public void onFailure() {
+            mTask.set(null);
+            if (!mCanceled) {
+                mCallback.onFailure();
+            }
+        }
     }
 }
diff --git a/compos/service/java/com/android/server/compos/IsolatedCompilationService.java b/compos/service/java/com/android/server/compos/IsolatedCompilationService.java
index d2e1f2a..cbc3371 100644
--- a/compos/service/java/com/android/server/compos/IsolatedCompilationService.java
+++ b/compos/service/java/com/android/server/compos/IsolatedCompilationService.java
@@ -17,11 +17,18 @@
 package com.android.server.compos;
 
 import android.annotation.NonNull;
+import android.app.job.JobInfo;
+import android.app.job.JobScheduler;
+import android.content.ComponentName;
 import android.content.Context;
+import android.provider.DeviceConfig;
 import android.util.Log;
 
 import com.android.server.SystemService;
 
+import java.io.File;
+import java.util.concurrent.TimeUnit;
+
 /**
  * A system service responsible for performing Isolated Compilation (compiling boot & system server
  * classpath JARs in a protected VM) when appropriate.
@@ -30,6 +37,8 @@
  */
 public class IsolatedCompilationService extends SystemService {
     private static final String TAG = IsolatedCompilationService.class.getName();
+    private static final int JOB_ID = 5132250;
+    private static final long JOB_PERIOD_MILLIS = TimeUnit.DAYS.toMillis(1);
 
     public IsolatedCompilationService(@NonNull Context context) {
         super(context);
@@ -37,8 +46,52 @@
 
     @Override
     public void onStart() {
-        Log.i(TAG, "Started");
+        // Note that our binder service is exposed directly from native code in composd, so
+        // we don't need to do anything here.
+    }
 
-        // TODO(b/199147668): Implement
+    @Override
+    public void onBootPhase(/* @BootPhase */ int phase) {
+        if (phase != PHASE_BOOT_COMPLETED) return;
+
+        if (!isIsolatedCompilationSupported()) {
+            Log.i(TAG, "Isolated compilation not supported, not scheduling job");
+            return;
+        }
+
+        ComponentName serviceName =
+                new ComponentName("android", IsolatedCompilationJobService.class.getName());
+
+        JobScheduler scheduler = getContext().getSystemService(JobScheduler.class);
+        if (scheduler == null) {
+            Log.e(TAG, "No scheduler");
+            return;
+        }
+        int result =
+                scheduler.schedule(
+                        new JobInfo.Builder(JOB_ID, serviceName)
+                                .setRequiresDeviceIdle(true)
+                                .setRequiresCharging(true)
+                                .setPeriodic(JOB_PERIOD_MILLIS)
+                                .build());
+        if (result != JobScheduler.RESULT_SUCCESS) {
+            Log.e(TAG, "Failed to schedule job");
+        }
+    }
+
+    private static boolean isIsolatedCompilationSupported() {
+        // Check that the relevant experiment is enabled on this device
+        // TODO - Remove this once we are ready for wider use.
+        if (!DeviceConfig.getBoolean(
+                "virtualization_framework_native", "isolated_compilation_enabled", false)) {
+            return false;
+        }
+
+        // Check that KVM is enabled on the device
+        if (!new File("/dev/kvm").exists()) {
+            return false;
+        }
+
+        return true;
     }
 }