CODEWITHSUNDEEP
c#c++.netio
bring
bring

Reputation: 93

Can a write scheduler be optimized using pending writes, total writes, and total bytes written?

I'd like to confirm that this interview question is essentially impossible:

The goal of this project is to create an implementation of a device that can write files to a directory and then to design a write scheduling system for a set of devices. The write scheduler system should consist of an interface named WriteScheduler and at least two concrete implementations of it. The first should be a fair round robin scheduler and the second should be a write scheduler that uses some combination of pending writes, total writes, and total bytes written to optimize the writes in some way. All code for this project should be thread-safe.

Given an unspecified interface, how could a scheduler be optimized with just that data?

Upvotes: 1

Views: 109

Answers (2)

ipavlu
ipavlu

Reputation: 1659

I presume, that the tag c++ was a mistake?

Ok, to the subject:

I can imagine an interface from what you provide us as this...

IDevice: this interface can be even empty interface

Device:

  • must implement IDevice interface,
  • constructor consumes IWriteScheduler instannce,
  • must be thread safe for next ops,
  • method open(string path),
  • method create(string path),
  • method read(out byte[] buffer, int attempt_read_n),
  • method write(in byte[] buffer),
  • method close(),
  • device will place lock around all public methods,
  • all methods will be potentially blocking,

Now IWriteScheduler:

  • Task WriteAsync(IDevice device, int size, Action writing_task)

Device behaviour:

  • Device in write operation is going to create an action with operation to write data into a file,
  • calling an instance of IWriteScheduler: IWriteScheduler.WriteAsync(this, 41561, action) and then waiting on it,
  • OR the Device can return the Task back to caller of Write operation, to let it decide if waiting is appropriate,
  • that is all,

WriteScheduler:

  • will implement IWriteScheduler,
  • has to have a lock on WriteAsync operation,
  • private class DevicesData {IDevice, total_bytes, pending_writes, total_writes, Task last_task } initial last_task has to be task_completed, could be created under older .net versions,
  • has to implement dictionary,
  • virtual WriteAsync method, the default implementation would be round robin, what means that in BlockingWrite method, the scheduler would update the correct DeviceData based on dictionary key IDevice and used last_task of the DeviceData to start next one by chaining based on ContinueWith,
  • simple chaining of tasks is going to ensure round robin scheduling,

Other scheduling methods simply by inheriting from WriteScheduler, overriding the:

virtual Task WriteAsync(IDevice device, int size, Action writing_task);

Task chaining allows to put even delays on write operations and many more tricks.

For scheduiling based on on the pending_writes, total_writes and total_bytes, well there is many ways to schedule and build specific rules that such data structure could handle:

  • there could be writes per second,
  • there could be bytes per second,
  • these could help to keep hard drives from burning out :),
  • both could be handled with data structure by inserting tasks with thread.sleep what would work, but would be awful :),
  • a better solution for delays would be Thread.Timer inside DeviceData and an queue of writing tasks.

I hope it was helpful, I provided analysis on implementation of the interface and some ideas for scheduling scenarios...

/IP/

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490408

It says "...to optimize the writes in some way".

So exactly what you attempt to optimize for is apparently pretty much up to you. For that matter, it may not even be particularly important that your attempted optimization be highly (or at all) successful.

If I had to guess, I'd say they're probably mostly interesting in the basic idea that you can define an abstract interface, then write a couple of implementations of that interface that differ in at least some semi-meaningful way (but still meet the interface's specification).

Upvotes: 1

Related Questions