The Fibonacci sequence is the series of numbers 0, 1, 1, 2, 3, 5, 8, ....Formally, it

Provide two programming examples in which multithreading provides better performance than a single-threaded solution.

What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

Describe the actions taken by a kernel to context-switch between kernellevel threads.

What resources are used when a thread is created? How do they differ from those used when a process is created?

Assume that an operating system maps user-level threads to the kernel using the many-to-many model and that the mapping is done through LWPs. Furthermore, the system allows developers to create real-time threads for use in real-time systems. Is it necessary to bind a real-time thread to an LWP? Explain.

Provide two programming examples in which multithreading does not provide better performance than a single-threaded solution.

Under what circumstances does a multithreaded solution using multiple kernel threads provide better performance than a single-threaded solution on a single-processor system?

Which of the following components of program state are shared across threads in a multithreaded process? a. Register values b. Heap memory c. Global variables d. Stack memory

Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a singleprocessor system? Explain.

In Chapter 3, we discussed Googles Chrome browser and its practice of opening each new website in a separate process. Would the same benefits have been achieved if instead Chrome had been designed to open each new website in a separate thread? Explain.

Is it possible to have concurrency but not parallelism? Explain.

Using Amdahls Law, calculate the speedup gain of an application that has a 60 percent parallel component for (a) two processing cores and (b) four processing cores.

Determine if the following problems exhibit task or data parallelism: The multithreaded statistical program described in Exercise 4.21 The multithreaded Sudoku validator described in Project 1 in this chapter The multithreaded sorting program described in Project 2 in this chapter The multithreaded web server described in Section 4.1

A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the program terminates, when the program results must be written to a single file. Between startup and termination, the program is entirely CPUbound. Your task is to improve the performance of this application by multithreading it. The application runs on a system that uses the one-to-one threading model (each user thread maps to a kernel thread). How many threads will you create to perform the input and output? Explain. How many threads will you create for the CPU-intensive portion of the application? Explain.

Consider the following code segment: pid t pid; pid = fork(); if (pid == 0) { /* child process */ fork(); thread create( . . .); } fork(); a. How many unique processes are created? b. How many unique threads are created?

As described in Section 4.7.2, Linux does not distinguish between processes and threads. Instead, Linux treats both in the same way, allowing a task to be more akin to a process or a thread depending on the set of flags passed to the clone() system call. However, other operating systems, such as Windows, treat processes and threads differently. Typically, such systems use a notation in which the data structure for a process contains pointers to the separate threads belonging to the process. Contrast these two approaches for modeling processes and threads within the kernel.

The program shown in Figure 4.16 uses the Pthreads API. What would be the output from the program at LINE C and LINE P?

Consider a multicore system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be greater than the number of processing cores in the system. Discuss the performance implications of the following scenarios. a. The number of kernel threads allocated to the program is less than the number of processing cores. b. The number of kernel threads allocated to the program is equal to the number of processing cores. c. The number of kernel threads allocated to the program is greater than the number of processing cores but less than the number of user-level threads. #include <pthread.h> #include <stdio.h> #include <types.h> int value = 0; void *runner(void *param); /* the thread */ int main(int argc, char *argv[]) { pid t pid; pthread t tid; pthread attr t attr; pid = fork(); if (pid == 0) { /* child process */ pthread attr init(&attr); pthread create(&tid,&attr,runner,NULL); pthread join(tid,NULL); printf("CHILD: value = %d",value); /* LINE C */ } else if (pid > 0) { /* parent process */ wait(NULL); printf("PARENT: value = %d",value); /* LINE P */ } } void *runner(void *param) { value = 5; pthread exit(0); } F

Pthreads provides an API for managing thread cancellation. The pthread setcancelstate() function is used to set the cancellation state. Its prototype appears as follows: pthread setcancelstate(int state, int *oldstate) The two possible values for the state are PTHREAD CANCEL ENABLE and PTHREAD CANCEL DISABLE. Using the code segment shown in Figure 4.17, provide examples of two operations that would be suitable to perform between the calls to disable and enable thread cancellation. int oldstate; pthread setcancelstate(PTHREAD CANCEL DISABLE, &oldstate); /* What operations would be performed here? */ pthread setcancelstate(PTHREAD CANCEL ENABLE, &oldstate); Figure 4.17 C program for Exercise 4.19.

Modify programming problem Exercise 3.20 from Chapter 3, which asks you to design a pid manager. This modification will consist of writing a multithreaded program that tests your solution to Exercise 3.20. You will create a number of threadsfor example, 100and each thread will request a pid, sleep for a random period of time, and then release the pid. (Sleeping for a random period of time approximates the typical pid usage in which a pid is assigned to a new process, the process executes and then terminates, and the pid is released on the processs termination.) On UNIX and Linux systems, sleeping is accomplished through the sleep() function, which is passed an integer value representing the number of seconds to sleep. This problem will be modified in Chapter 5.

Write a multithreaded program that calculates various statistical values for a list of numbers. This program will be passed a series of numbers on the command line and will then create three separate worker threads. One thread will determine the average of the numbers, the second will determine the maximum value, and the third will determine the minimum value. For example, suppose your program is passed the integers 90 81 78 95 79 72 85 The program will report The average value is 82 The minimum value is 72 The maximum value is 95 The variables representing the average, minimum, and maximum values will be stored globally. The worker threads will set these values, and the parent thread will output the values once the workers have exited. (We could obviously expand this program by creating additional threads that determine other statistical values, such as median and standard deviation.)

Write a multithreaded program that calculates various statistical values for a list of numbers. This program will be passed a series of numbers on the command line and will then create three separate worker threads. One thread will determine the average of the numbers, the second will determine the maximum value, and the third will determine the minimum value. For example, suppose your program is passed the integers 90 81 78 95 79 72 85 The program will report The average value is 82 The minimum value is 72 The maximum value is 95 The variables representing the average, minimum, and maximum values will be stored globally. The worker threads will set these values, and the parent thread will output the values once the workers have exited. (We could obviously expand this program by creating additional threads that determine other statistical values, such as median and standard deviation.)4.18. (Assume that the radius of this circle is 1.) First, generate a series of random points as simple (x, y) coordinates. These points must fall within the Cartesian coordinates that bound the square. Of the total number of random points that are generated, some will occur within the circle. Next, estimate by performing the following calculation: = 4 (number of points in circle) / (total number of points) Write a multithreaded version of this algorithm that creates a separate thread to generate a number of random points. The thread will count the number of points that occur within the circle and store that result in a global variable. When this thread has exited, the parent thread will calculate and output the estimated value of . It is worth experimenting with the number of random points generated. As a general rule, the greater the number of points, the closer the approximation to . In the source-code download for this text, we provide a sample program that provides a technique for generating random numbers, as well as determining if the random (x, y) point occurs within the circle. Readers interested in the details of the Monte Carlo method for estimating should consult the bibliography at the end of this chapter. In Chapter 5, we modify this exercise using relevant material from that chapter. 4.2

Repeat Exercise 4.22, but instead of using a separate thread to generate random points, use OpenMP to parallelize the generation of points. Be careful not to place the calculcation of in the parallel region, since you want to calculcate only once. 4

Write a multithreaded program that outputs prime numbers. This program should work as follows: The user will run the program and will enter a number on the command line. The program will then create a separate thread that outputs all the prime numbers less than or equal to the number entered by the user.

Modify the socket-based date server (Figure3.21) in Chapter 3 so that the server services each client request in a separate thread.

The Fibonacci sequence is the series of numbers 0, 1, 1, 2, 3, 5, 8, .... Formally, it can be expressed as: fib0 = 0 fib1 = 1 fibn = fibn1 + fibn2 Write a multithreaded program that generates the Fibonacci sequence. This program should work as follows: On the command line, the user will enter the number of Fibonacci numbers that the program is to generate. The program will then create a separate thread that will generate the Fibonacci numbers, placing the sequence in data that can be shared by the threads (an array is probably the most convenient data structure). When the thread finishes execution, the parent thread will output the sequence generated by the child thread. Because the parent thread cannot begin outputting the Fibonacci sequence until the child thread finishes, the parent thread will have to wait for the child thread to finish. Use the techniques described in Section 4.4 to meet this requirement.

Exercise 3.25 in Chapter 3 involves designing an echo server using the Java threading API. This server is single-threaded, meaning that the server cannot respond to concurrent echo clients until the current client exits. Modify the solution to Exercise 3.25 so that the echo server services each client in a separate request.