Computer Science Questions: Process Synchronization-Scheduling/Threads

Threads 1. You get an awesome job writing software at Pixel Entertainment, a leading producer of

computer animated movies and games. You are tasked with writing a rendering algorithm, and quickly realize that by dividing the processing across multiple threads, you can take advantage of parallelism to reduce rendering times. Refer to this scenario, when answering the following questions:

a. Is this scenario an example of using threads to implement task parallelism?

b. At a meeting with the Product Owner, you learned your program will be bundled

with a tablet that is powered by a single processor (1 core). Will using multiple threads achieve parallelism on this device? Briefly explain.

c. Later, you receive an email about a change in plan. Your program will now be

shipped on another vendor’s tablet that is powered by a processor with 4 cores. When you read the tablet’s developer’s guide, you learn it runs an Unix like operating system that includes the vendor’s own version of the pthreads library that implements the many-to-one model. Can threads be used to achieve parallelism on this platform? Briefly explain.

d. Assume you chose not to use the 4 core tablet’s pthreads library, could parallelism

be achieved by dividing the work across multiple cooperating processes? Briefly explain.

2. Explain the difference between concurrency and parallelism?

3. Can parallelism be achieved on a single processor system? Explain.

4. Can concurrency be achieved on a single processor system? Explain.

5. How are data parallelism and task parallelism different?

6. Within a multithreaded process, some of the process’ resources are shared by all of the

threads. Circle the resources that are exclusive to each thread. o Register values o Heap Memory o Code o Stack memory

7. Refer to this diagram when answering the following questions:

ser thread

a. This is a diagram of the threading model.

b. In this model, if a user thread makes a blocking system call, are the other user threads able to do work while the system call is in progress? Briefly explain.

8. Refer to this diagram when answering the following questions:

user thread

k k k kernel thread

a. This is a diagram of the threading model. In this model, user threads are attached to kernel threads using intermediate data structures called .

b. In this model, if a user thread makes a blocking system call, are the other

user threads able to do work while the system call is in progress? Briefly explain.

9. Refer to this diagram when answering the following questions:

user thread

kernel thread

a. This is a diagram of the threading model.

b. In this model, if a user thread makes a blocking system call, are the other user threads able to do work while the system call is in progress? Briefly explain.

c. Thread pools are often used with this model. What is a thread pool? Describe

one benefit they provide.

d. A limitation of this model is that it places an upper threshold on the number of threads an operating system can support. Can a thread pool help address this issue? Briefly explain.

10. When threads are applied correctly, your application can benefit in a number of ways. In the list below, cross out the two items that are not true benefits.

• Responsiveness – may allow continued execution if part of process is blocked,

especially important for user interfaces • Resource Sharing – threads share resources of process, easier than shared memory

or message passing

• Synchronization – unlike shared memory between processes, synchronization is not required when threads share memory

• Economy – cheaper than process creation, thread switching lower overhead than context switching

• Isolation – the execution of one thread cannot interfere with the execution of another thread

• Scalability – process can take advantage of multiprocessor architectures

Process Scheduling 1. What is the main goal of a process scheduling algorithm?

2. What is the purpose of a ready queue?

3. What are device queues?

4. How do preemptive schedulers differ from non-preemptive schedulers?

5. Which scheduling scenarios do not impact non-preemptive schedulers:

• A process switches from the running to the waiting state • A process switches from the running to the ready state • A process switches from the waiting state to the ready state • A process terminates

6. What role does the dispatcher play in process scheduling?

7. Which of the following statements about schedulers are true?

• Round-robin degrades to first-come first-served when the time quantum is too small

• The preemptive version of shortest-job-first scheduling is called shortest- remaining-time-first

• Exponential averaging is used to estimate the optimum time quantum for round- robin schedulers

• Priority-scheduling may result in low priority processes having to wait indefinitely for processor time

8. What does it mean for a process to cycle between CPU bursts and I/O bursts?

9. The processes listed below are in the ready queue of a first-come first-serve (FCFS) scheduler. Use this information to answer the following questions.

Process Queue Order Burst Time (ms) P1 1 8 P2 2 12 P3 3 4 P4 4 2

a. Draw a Gantt chart to show the times and durations each process is active. (2 pts)

b. Calculate the average wait time for this scenario

c. What is situation called where short processes wait behind long processes and how does it impact the system?

d. The FCFS was replaced with a round robin (RR) scheduler. It is implemented with a

quantum of 4. Draw a Gantt chart to show when each process is active for this scheduler.

e. Calculate the average wait time for the RR scenario.

f. The scheduler is now replaced by a shortest-job-first (SJF) scheduler. Draw a Gantt chart to show when each process is active for this scheduler.

g. Calculate the average wait time for the SJF scheduler.

h. What makes SJF difficult to implement in practice?

Process Priority (1 is highest priority) P1 4 P2 2 P3 1 P4 3

a. The scheduler is now replaced by a priority scheduler. Using the given process priorities, draw a Gantt chart to show when each process is active for this scheduler.

b. Calculate the average wait time for the priority scheduler.

10. What does it mean for a process to be starved by a priority scheduler and what can be

done to prevent this from occurring?

11. What effect does the time quantum of a round robin scheduler have on process scheduling? What happens if the time quantum is too big or too small?

12. What is processor affinity?

Process Synchronization

13. What is a critical section and why is it important for programmers to be aware of them in them in their code?

14. List and describe the three requirements for a complete solution to the critical section

problem.

15. What does it mean for a processor instruction to be atomic and why is this property important? Give an example of an atomic instruction a processor might provide.