# Notes See the [notice](/notice) before reading the notes. ## Fall 2022 * [CSCI-GA 3033 Graphics Computing Units](https://notes.dizy.cc/graphics-processing-units/) by Mohamed Zahran ## Spring 2022 * [CSCI-GA 2590 Natural Language Processing](https://notes.dizy.cc/natural-language-processing/) by Adam Meyers * [CSCI-GA 1170 Fundamental Algorithms](https://notes.dizy.cc/fundamental-algorithms/) by Chee Yap ## Fall 2021 * [CSCI-GA 2820 DevOps and Agile Methodologies](https://notes.dizy.cc/devops/) by John Rofrano * [CSCI-GA 2250 Operating Systems](https://notes.dizy.cc/operating-systems/) by Hubertus Franke ## Spring 2021 * [CSCI-GA 2110 Programming Languages](https://notes.dizy.cc/programming-languages/) by Cory Plock # Notice Please note that even though this site is public, it's solely for my final exam preparation or other personal purposes. The correctness of any information posted on this site is not guaranteed. So read it with caution. Some links on this site may not work for you, because they may point to a private or protected page that you are not authorized to access. Don't contact me and ask for them, because as I've said, they are copyrighted. Unless you're convinced that it's a public resource and the link is just broken, you can react me at . This site is **NOT** supposed to help you with your homework. You **MUST NOT** straight copy the answers, solutions or codes and use them as your course hand-ins. Plagiarism is strongly prohibited, and remember, it does no good for you. Also, I thank all professors that put hard work into their teaching. If you think this site is helpful for your final exam preparation, and want to contribute, feel free to submit issues, fork the repo or submit pull requests. But keep in mind that this site's source code and content are all licensed under [GLP-3.0](https://github.com/dizys/notes/blob/main/LICENSE). Make sure that your use of this repo conform to the open-source license. At last, happy hacking! # Overview | Course code | CSCI-GA.2820-003 | | ----------- | -------------------- | | Professor | John Rofrano | | Email | | ## Grading A midterm and a final. | Component | Weight | | ------------------ | ------ | | Project & teamwork | 40% | | Mid-term | 30% | | Final | 30% | # DevOps Culture, Agile Development, & Cloud Native Technologies DevOps is a recognition that Development and Operations needs to stop working alone in their "siloed" towers and start working together. To do this we need: * A **culture** of collaboration valuing openness, trust, and transparency * An **application design** that does not require entire systems to be redeployed just to add a single function * An **application design** that does not require entire systems to be redeployed just to add a single function * A dynamic software-defined, **programmable platform** to continuously deploy onto ## Traditional Waterfall Development Requirements -> Design -> Code -> Integration -> Test -> Deploy In traditional waterfall development: 1. Each step ended when the next begins; 2. Mistakes found in the later stages are more expensive to fix; 3. No provisions for changing requirements **Problem with this approach:** * No provisions for changing requirements * Because all of the teams worked separately, the development team was not always aware of operational roadblocks that might prevent the program from working as anticipated * The people the furthest from the code who knew the least about it were deploying it into production ## Extreme Programming In 1996, Kent Beck introduced Extreme Programming based on an interactive approach to software development. It was intended to improve software quality and responsiveness to changing customer requirements. It was one of the first agile methods. ## Agile Manifesto In 2001, seventeen software developers met at a resort in Snowbird, Utah to discuss these lightweight development methods. Together, they published the Manifesto for Agile Software Development. * **Individuals and interactions** over processes and tools * **Working software** over comprehensive documentation * **Customer collaboration** over contract negotiation * **Responding to change** over following a plan That is, while there is value in the items on the right, we value the items on the left more. ## Agile Development Cycle: ... -> Requirements -> Plan -> Design -> Develop -> Release -> Track & Monitor -> ... * Requirements and solutions evolve through the collaborative effort of **self-organizing** and **cross-functional** teams and their customers * It advocates **adaptive planning**, evolutionary development, early delivery, and **continual improvement** * It encourages rapid and flexible **response to change** ### **Agile Dilemma / Why Agile alone not good enough?** While Agile improved the speed and accuracy of software for developers, it did nothing for operations. Many development team just got frustrated by ops not being able to deliver at the speed of development. ### How Agile are your teams? * [x] Small team: 5 ± 2 * [x] Dedicated * [x] Co-located * [x] Cross-functional * [x] Self managing ### Working as an Agile Team * Iterative Sprints * Groomed Backlogs * Customer Stories * 2 Week Deliverables ### Agile Antipatterns You will fail if you... * Lack of real Product Owner * If your teams are too large * If your teams and not dedicated * If your teams are geographically distributed * If your teams siloed * If your teams are not self managing ## The history reminds us that DevOps is: * From the practitioners, by practitioners * Not a product, specification, job title * An experience-based movement * Decentralized and open to all ## Goal of Microservice is Agility * Smart experimentation * Moving in-market with maximum velocity and minimum risk * Gaining quick valuable insight to continuously change the value proposition and quality ## DevOps Thinking / Tenets * Social Coding * Behavior and Test Driven Development * Working in small batches * Build **Minimum Viable Products** for gaining insights * Failure leads to understanding ### Think Cloud Native * The Twelve-Factor App describes patterns for cloud-native architectures which leverage microservices * Applications are design as a collection of stateless microservices * State is maintained in separate databases and persistent object stores * Resilience and horizontal scaling is achieved through deploying multiple instances * Failing instances are killed and re-spawned, not debugged and patched (cattle not pets) * DevOps pipelines help manage continuous delivery of services ### Think Microservices The microservice architectural style is an approach to developing a single application as a **suite of small services**, each **running in its own process** and communicating with lightweight mechanisms, often an HTTP resource API. These services are **built around business capabilities** and **independently deployable** by fully automated deployment machinery. ### Design for Failure * Embrace failures: they will happen! Move from "How to avoid" —> "How to identify & what to do about it". Move from "Pure operational concern" —> "developer concern". * External calls to other services that you don’t control are especially prone to problems: * Use separate thread pools * Time out quickly * Circuit breaker pattern: identify problem and do something about it to avoid cascading failures * Bulkhead pattern: Isolation from start to limit scope of failure (separate thread pools) * Monkey testing: test by breaking (yes, on purpose! see: Netflix Chaos Monkey and Simian Army) ### Think Continuous Automation Automation is speed + repeatability. * Continuous Integration (CI) * Continuous Delivery (CD) * Build Automation * Canary Rollouts / Blue-Green * Failing Forward * Application Release Automation ## Working DevOps * Facilitate a culture of **teaming and collaboration** * Establish **agile development** as a shared discipline * **Automate relentlessly** to enable rapid DevOps response * Push **smaller releases faster**, measure and remediate impact ## Taylorism Named after the US industrial engineer Frederick Winslow Taylor (1856-1915) who in his 1911 book 'Principles Of Scientific Management' laid down the fundamental principles of large-scale manufacturing through **assembly-line** factories. * Adoption of **Command and Control Management**: the dominant method of management in the Western world * Organizations divided into (ostensibly) independent **functional silos**: organizations divided into (ostensibly) independent functional silos * **Decision-making** is separated from work: managers do the planning and decide what workers should do; workers mindlessly do the tasks they are ask to accomplish #### Taylorism is not appropriate for Craft Work: * Taylorism may have been good during the industrial revolution, but not so much in the technology revolution * Taylorism may have been good during the industrial revolution, but not so much in the technology revolution * The people power requirements have been lowered * Taylorism is not appropriate for "knowledge" work like software development ### Required DevOps behaviors | Traditional IT practices | DevOps | | -------------------------------------- | ---------------------------------------- | | Organizational silos and hand-offs | Shared ownership and high collaboration | | Fear of change | Risk management by embracing change | | Build once, hand crafted "snow flakes" | Ephemeral infrastructure as code | | Manual fulfillment | Automated Self Service | | Alarms, call-backs, and escalations | Feedback loops and data driven responses | ### How DevOps Manages Risk * Deployment is king * Deployment must be painless * You have deployed the same thing several times before it gets to production * Deployment is decoupled from activation * Risk is managed via activation controls (blue-green deploys with canary testing) * 10% of the user base, waves of activation, etc. * Deployment is not “one size fits all” * It is a rail yard of interconnecting steps and microprocesses ### Ephemeral Infrastructure * Cattle, not Pets * Servers are built on demand via automation * Logging into the server is seen as failure * Release through parallel infrastructure * Build the new version on new infrastructure; stage transition between environments (zero downtime) * Transient Infrastructure * Throw away when it is no longer needed * This eliminates entropy - a major source of failure ### Immutable Delivery * Applications are packaged in containers * Same container that developer runs on their laptop runs in production * Rolling updates with immediate roll-back * No variance limits side-effects * Dependencies are contained ### Zero-Downtime Deployments * Blue-green deployment is a zero-downtime deployment technique that consists of two nearly identical production environments, called Blue and Green. * They differ by the artifacts that the developer has intentionally changed, typically by the version of the application. At any given time, at least one of the environments is active. * Using the blue-green deployment technique, you can realize the following benefits: * Take software quickly from the final stage of testing to live production. * Deploy a new version of an application without disrupting traffic to the application. * Rollback rapidly. If there is something wrong with one of your environments, you can quickly switch to the other environment. ### Spotify Case Study #### Organizational Structure * **Squads** are grouped into Tribes (light-weight matrix) * **Chapters** of competency areas are formed across Squads * **Guilds** are informal light-weight community of interests across the company #### Autonomous Squads * Each Squad has its own mission aligned with the business * Feels like a "mini-startup" * Self Organizing / Cross-functional * 5-7 engineers, less than 10 * Squads have end-to-end responsibility for what they build * Build, commit, deploy, maintenance, operations, EVERYTHING! * With a long term mission usually around a single business domain ### DevOps Organizational Objective Shared Consciousness with Distributed (local) Control ### Actions v.s. Consequences: Functional Silos Breed Bad Behavior * Bad behavior arises when you abstract people away from the consequences of their actions. * Functional silos abstract people away from the consequences of their actions. * For example: By adding a QA Team, developers are abstracted away from the consequences of writing buggy code. #### Actions have Consequences * Make people aware of the consequences of their actions * Create cross-functional teams - or - * Have developers rotate through operations teams * Have operations people attend developer standups and showcases * Make people responsible for the consequences of their actions * Having developers on Pager Duty, or own the SLA for the products and services they build ### DevOps Measurement / Metrics DevOps changes the objective of the measurement from Mean Time To Failure (MTTF, make sure you never go down) -> Mean Time To Recovery (MTTR, you will go down, make sure you can recover quickly) Metrics: * A **BASELINE** provides a concrete number for comparison as you implement your DevOps changes: * It currently requires six team members 10 hours to deploy a new release of our product. * This costs us $X for every release * Metric **GOALS** allow you to reason about these numbers and judge the success of your transition process: * Reduce deployment time from 10 hours to 2 hours. * Increase percentage of defects detected in testing from 25% to 50% #### Actionable Metric Examples * Reduce time-to-market for new features. * Increase overall availability of the product. * Reduce the time it takes to deploy a software release. * Increase the percentage of defects detected in testing before production release. * Make more efficient use of hardware infrastructure. * Provide performance and user feedback to the product manager in a more timely manner #### Top 4 Actionable Metric 1. Mean Lead Time: How long does it take from idea to production? 2. Release Frequency: How often can you deliver changes? 3. Change Failure Rate: How often to changes fail? 4. Mean Time to Recovery (MTTR): How quickly can you recover from failure? #### Culture Measurements * On my team information is actively sought * On my team failures are learning opportunities and messengers of them are not punished * On my team responsibilities are shared * On my team cross functional collaboration is encouraged and rewarded * On my team failure causes inquiry * On my team new ideas are welcomed #### Key metric: Cycle Time * Cycle time is a key metric for Agile kanban teams. * Cycle time is the amount of time it takes for a unit of work to travel through the team’s workflow–from the moment work starts to the moment it ships. * By optimizing cycle time, the team can confidently forecast the delivery of future work. #### Keys to High Performance You MUST do all three: 1. Technical Practices 2. Lean Processes (Agile) 3. Culture ### Busted DevOps Myths * You cannot buy DevOps In-A-Box * You cannot order 20 units of DevOps for this quarter * You cannot sprinkle DevOps on something to make it better * You cannot become DevOps without changing your culture * You can’t change your companies culture just by adopting new tools …but they can help reinforce it * Using Containers won't fix your broken culture * You cannot maintain your current organizational structure and become DevOps ### DevOps Summary * A Cultural Movement * Emphasizing Collaboration, Sharing, and Transparency * Promoting Automation and Infrastructure as Code * Achieving Continuous Integration and Delivery of Changes * Immutable Delivery * With One set of Metrics to rule them all #### DevOps Maturity Matrix | Maturity Level | People | Process | Technology | | -------------------------------- | -------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- | |

Level 1:

Ad Hoc

| | | | |

Level 2:

Repeatable

| | | | |

Level 3:

Defined

| | | | |

Level 4:

Measured

| Collaboration based on shared metrics with a focus on removing bottlenecks | | | |

Level 5:

Optimized

| A culture of continuous improvement permeates through the organization | | | #### Key Takeaways * DevOps is about breaking down the silos and working as a Single Agile Team * Culture is the #1 success factor in DevOps. Building a culture of shared responsibility, transparency and faster feedback is the foundation of every high performing DevOps team * DevOps starts with learning how to work differently. It embraces cross-functional teams with openness, transparency, and respect as pillars * Being able to recover quickly from failure is more important than having failures less often * Measurements should encourage innovation and collaboration, and not punish failure (blameless culture) # Social Coding Social Coding with GitHub ## Git Rules 1. Create a Git repository for every new project 2. Create a new branch for every new feature 3. Use Pull Requests to merge code to Master ## Source Code Management * Source Code Management is the practice of tracking versions of source code as it is being developed. * A source code manager (SCM) is a software tool used by teams of programmers to manage source code * These are also referred to as Version Control Systems (VCS) * SCMs can be Centralized or Distribute ### Distributed or Centralized * Distributed revision control (DRCS) takes a peer-to-peer approach, as opposed to the client-server approach of centralized systems * Rather than a single, central repository on which clients synchronize, each peer’s working copy of the codebase is a bona-fide repository * Distributed revision control conducts synchronization by exchanging patches (change-sets) from peer to peer ### Decentralized systems * No canonical, reference copy of the codebase exists by default; only working copies. * Common operations (such as commits, viewing history, and reverting changes) are fast, because there is no need to communicate with a central server. * Communication is only necessary when pushing or pulling changes to or from other peers. * Each working copy effectively functions as a remote backup of the codebase and of its change-history, providing natural protection against data loss. ### Git: Decentralized SCM System * A distributed source code management (SCM) tool invented by Linus Torvalds in 2005 for Linux kernel development * Code is kept in a repository and every developer has a full copy * Works locally without any server * Works remotely with GitHub, GitLab, & BitBucket ### GitHub: A website that hosts git repositories * A web site that hosts git repositories * Founded in 2007, has 40 million registered developers and was acquired by Microsoft for a whopping $7.5 billion in 2018 * Free and Paid accounts * Adds ability to track Issues and Bugs * Provides webhooks to integrate other tools ## Why You Need to Know Git? * The use of Git and software code repositories has fundamentally changed the way enterprises do software development for proprietary code and open source code alike. * In addition, open source software has blossomed because some of the Git repositories host open source code for free. * Most significantly, Git and code repositories have facilitated the DevOps methodology that is so impactful to software development. ![Git Command Workflow](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2F2pOdXSU07zXn6wuypIsh%2Fimage.png?alt=media\&token=40e390da-3211-416c-b531-341db826596d) ## What is Social Coding? * In the past developers worked on **private** repositories and you had to be a member of the team to contribute * With Social Coding, repositories are **public** and everyone is encouraged to Fork the code and contribute * You would think that anarchy would ensue but it actually works quite well because it is controlled by the repository owner ### Code Reuse Dilemma * You see a project that is 80% of what you need but there are some missing features * You feel that if you make a feature request of the project owner, your request will be at the bottom of their priorities (If they get funding cuts, you know that your feature request will be cut) * So you rebuild 100% of what you need so as not to have a dependency on another project ### Social Coding Solution * Discuss the new feature with the repo owner and agree to develop it * Open an **Issue** and assign it to yourself so that everyone knows what you are working on * **Fork** the code, create a **branch**, and make your changes * Issue a **Pull Request** when you are ready to review and merge your work back into the main project ## GitHub Is A DevOps Enabler * [x] Open Culture: Forking and Pull Requests enable openness * [x] Emphasize Collaboration and Sharing (no Silos): Issues and Comments invite Collaboration and Planning * [x] Infrastructure as Code: Git the the perfect place to store all of your infrastructure scripts * [x] Automate Everything: Git works well with Travis CI, Jenkins, and other automation tools ## Git Overview Brief introduction [up here](#git-decentralized-scm-system). * Git works well with Travis CI, Jenkins, and other automation tools * Developers work in their own BRANCHES (even in FORKS) * The MASTER branch should always be ready to deploy * PULL REQUESTS are used to MERGE code BRANCHES into MASTER ### Detailed Feature Branch Workflow * CLONE a Repository (FORK first if not part of Dev Team) * Assign the ISSUE for your work to yourself and place it in working status * Create a BRANCH to work on an ISSUE * Run the Test suite to make sure you can run the code * Make changes to code and test cases and COMMIT to local BRANCH * Run the Test suite early and often to make sure you didn’t break anything * PUSH changes to remote BRANCH * Did we mention testing the code early and often? * Create PULL REQUEST when all tests pass and code is ready for review / MERGE ### Why is Testing So Important? * Automated testing must pass before your Pull Request will be accepted * Automated testing is your guarantee that you didn’t break anything * Without automated testing you cannot fully automate the DevOps pipeline ## Guidelines for Contributing: \`CONTRIBUTION.md\` To help your project contributors do good work, you can add a file with contribution guidelines to the root of your project's repository. Then, whenever someone opens a pull request or creates an issue, they will see a link to that file. Good Social Coding requires that everyone know and follow the guidelines. As you can imagine, with outside contributors there must be coding standards. Use a `CONTRIBUTION.md` file to document how to contribute. It’s a good idea to publish your coding standards on your GitHub Wiki or other public place and point to them in your `CONTRIBUTION.md` file. When a Pull Request is made, you should also check that the standards have been followed. ## Issues: Tacking What You Do * When a Pull Request is made, you should also check that the standards have been followed * ISSUES can be features or defects or pull requests or … * You should not be working on code without an open ISSUE * You should not be working on code without an open ISSUE ## Branches * Branching is a core concept in Git: Branching is a core concept in Git * The only rule: Anything in the **master**/**main** branch must always be deployable * It's extremely important that your new branch is created off of master when working on a feature or a fix ## Pull Request Workflow Use a PULL REQUEST to notify the team that you changes are ready to be reviewed and merged into the MASTER branch. The pull request workflow helps us to share information. Benefits: * A second set of eyes: Sometimes you may have solved a problem, but when someone reviews it they pointed out a subtle flaw, or perhaps a way you could solve it more elegantly. It also helps identify things like security exposures. This results in a much cleaner codebase. * Knowledge sharing: It is dangerous to only have one developer that understands the code. Having another developer review the code allows for shared understanding and protects against one developer leaving the project. * Allows automation of unit testing: You setup your GitHub project to run unit tests on pull requests so that we can verify that everything works before merging. ### Prepare for Pull Request * You want to make sure that you are using the latest code before you make a pull request * The remote master branch has probably moved on since you created your branch * Therefore it is necessary "rebase to" or "merge with" the current master ## Fetch vs Pull * Fetch will bring down all of the changes from the remote repository * Pull will merge the changes from the current branch with your local workspace Note: Pull does a fetch so if you just want to pull there is no need to fetch. ## Merge vs Rebase **Merge** joins two branches together, usually your branch and master but it can be any two branches only changing the checked out branch. If there are no conflicts and the current HEAD is an ancestor of the merge branch, git will fast-forward the merge by moving the pointer forward. Merge retains all the history as it happened chronologically **Rebase** will replay your changes on top of the current version of master. It will look as if your branch was created from the current state of master. It will look as if your branch was created from the current state of master. You can optionally do this before pushing/creating to remote branch otherwise use merge. **Never rebase once you have pushed to a remote**. It will mess everyone else up because it changes history in a way that is incompatible. ## Reset vs Revert ### Reset: Rewind the Mistakes Before Push If you have NOT pushed to a remote branch, you can use `reset` to go back to a previous commit. Reset rewinds the commits as if they never happened. * To get rid of the last two commits ```bash git reset --soft HEAD~2 git reset --hard master@{1} ``` * `--soft` will undo the commit history and leave the files staged * `--mixed` will undo the history and the staging so the files are untracked (default) * `--hard` will undo and **delete** your files! ### Revert: Rewind the Mistakes After Push If you made a commit and pushed it to the remote, how to do undo it because other people may have access to the remote? ```bash git revert ``` Revert is the only **safe** undo for a commit that has a remote push. Note: revert will not remove files that are pushed remotely. ### Comparison **Reset** will alter history as if it never existed. This will confuse remote repos so once you push a commit you should not reset it. **Revert** will undo history by adding a commit that reverses the changes. This is remote repo friendly. ## Merge Conflicts Git cannot merge code that has the **same line** of code changed in two **different branches**. This requires **manual intervention** and probably collaboration with the developer who made the other changes. #### Resolution For pull requests, you should merge from the master branch first. If there were conflicts, they would appear in the current branch. * Edit the file in conflict and commit. (If is during a rebase, you should `git rebase --continue`). ```bash git commit -am "Fix: Resolve conflicts" ``` * Then you can proceed to merge the pull requests into the master branch. ### Abort a Merge or Rebase Never leave a merge or rebase in an unfinished state! * For merge, you can abort it with: `git merge --abort` * For rebase, you can abort it with: `git rebase --abort` # Agile Planning Agile Development and Planning ## Problem with Tradintional Waterfall Development {% hint style="info" %} Requirements -> Design -> Code -> Intergration -> Test -> Deploy * Each step ended when the next begins * Mistakes found in the later stages are more expensive to fix * No provisions for changing requirements * No idea if it works until the end {% endhint %} * There was usually a long time between software releases * Because all of the teams worked separately, the development team was not always aware of operational roadblocks that might prevent the program from working as anticipated * The people the furthest from the code who knew the least about it were deploying it into production ## 12 Principles Behind the Agile Manifesto 1. Our highest priority is to satisfy the customer through early and **continuous delivery** of valuable software. 2. **Welcome changing requirements**, even late in development. Agile processes harness change for the customer's competitive advantage. 3. Deliver working software frequently, from a couple of weeks to a couple of months, with a preference to the **shorter timescale**. 4. Business people and developers must **work together** daily throughout the project. 5. Build projects around **motivated individuals**. Give them the environment and support they need, and **trust** them to get the job done. 6. The most efficient and effective method of conveying information to and within a development team is **face-to-face** conversation. 7. **Working software** is the primary measure of progress. 8. Agile processes promote **sustainable development**. The sponsors, developers, and users should be able to maintain a constant pace indefinitely. 9. Continuous attention to **technical excellence** and good design enhances agility. 10. Simplicity: the art of maximizing the amount of work not done is essential. 11. The best architectures, requirements, and designs emerge from **self-organizing teams**. 12. At regular intervals, the **team reflects** on how to become more effective, then tunes and adjusts its behavior accordingly. ## What Agile is not... * Agile is not a new version of a waterfall SDLC, where you do legacy development in sprints * Agile is not just the development team in each sprint, like you do in waterfall development. * The Agile Manifesto does not include the term “agile project management” (and so there are no "project managers" in Agile) ## Agile Development Cycle: ... -> Requirements -> Plan -> Design -> Develop -> Release -> Track & Monitor -> ... * Requirements and solutions evolve through the collaborative effort of **self-organizing** and **cross-functional** teams and their customers * It advocates **adaptive planning**, evolutionary development, early delivery, and **continual improvement** * It encourages rapid and flexible **response to change** ## Agile and Scrum **Scrum** is the most popular Agile development **framework**. * **Agile** is a PHILOSOPHY for doing work, not prescriptive. * **Scrum** is a METHODOLOGY for doing work that adds PROCESS to Agile thinking ### Scrum * A management **framework** for incremental product development using one or more small cross-functional, self-organizing teams * Provides a **structure** of roles, meetings, rules, and artifacts * Uses fixed-length **iterations**, called Sprints, which are typically two weeks long: Scrum teams attempt to build a potentially shippable (properly tested) product increment every iteration ### Ingredients of Scrum * Roles: Product Owner + Development Team + Scrum Master * Artifacts: Product Backlog + Sprint Backlog + Done Increment * Events: Sprint Planning + Daily Scrum + Sprint Review + Sprint Retrospective + Sprint ### Benefits of Scrum Organizations that have adopted agile Scrum have experienced: * Higher productivity * Better-quality products * Reduced time to market * Improved stakeholder satisfaction * Better team dynamics * Happier employees ### Organization of Scrum Teams * Small team (7 ± 2) * Dedicated * Co-located * Cross-functional * Self managing ### Scrum Roles: Product Owner, Scrum Master... #### Product Owner * Represents the stakeholder interests * Responsible for **product vision** * Final arbiter of requirements questions * Constantly **re-prioritizes** the Product Backlog, adjusting any expectations such as release plans * Accepts or rejects each product increment * Decides whether to ship * Decides whether to continue development * May contribute as a team member #### Scrum Master (Agile Coach) * Facilitates the Scrum process * Creates an environment conducive to team self-organization * **Shields the team** from external interference and distractions to keep it "in the zone" * Helps **resolve impediments** * Enforces Sprint timeboxes * Captures empirical data to adjust forecasts * Has no management authority over the team (anyone with authority over the team is by definition not its ScrumMaster) #### Scrum Team * **Cross-functional** (e.g., includes members with testing skills, and often others not traditionally called developers: business analysts, domain experts, etc.) * Self-organizing / **self-managing**, without externally assigned roles * Consists of 5 ± 2 **dedicated co-located** collaborative members * Most successful when located in one team room, particularly for the first few Sprints * Most successful with long-term, full-time membership. Scrum moves work to a flexible learning team and avoids moving people or splitting them between teams. * **Negotiates commitments** with the Product Owner — **one Sprint at a time** * Has **autonomy** regarding how to reach commitments ### The Agile Dilemma While Agile improved the speed and accuracy of software for developers, it did nothing for operations. Many development teams just got frustrated by ops not being able to deliver at the speed of development. ### Goal of Agile and DevOps are Aligned | The Goal of Agile | The Goals of DevOps | | ----------------------------- | ---------------------------------------------------------------------------------------- | | Develop software faster | Accelerate time to market | | Be responsive to changes | Improve IT’s value by more closely aligning development, IT operations, and the business | | Obtain higher quality results | Increase IT productivity | ### Agile Antipatterns You will fail if you... * Lack of real Product Owner * If your teams are too large * If your teams and not dedicated * If your teams are geographically distributed * If you teams siloed * If your teams are not self managing ## Transform to DevOps/Agile ### Bad Formulas Leading to Failure * Product Manager becomes Product Owner * Project Manager becomes Scrum Master * Developers become Scrum Team ### Comparing Traditional and DevOps/Agile Roles | Role | Traditional IT | Role | Agile IT | | ---------------- | ------------------------------------------------------------------------------------------------ | ------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Product Manager | Business person who manages the budget and doesn't really need to be technical | Product Owner | Visionary that leads the team in a series of experiments design to achieve the goal. Conduit between the stakeholders and the team translating between business and technical goals | | Project Manager | Task Master that keeps everyone marching to a fixed plan. Documents impediments as project risks | Scrum Master | Coach that keeps the team focused on the current sprint and eliminating impediments while buffering team from interruptions | | Development Team | Made up of developers only | Scrum Team | Cross-functional team consisting of developers, testers, security, business analysts, operations, etc. | ## Agile Tenets Agile takes ideas from Lean Manufacturing and Extreme Programming (XP) * Working in Small Batches * Creating Minimum Viable Products (MVP) * Using Behavior Driven Design (BDD) to make sure that you are building the right * Practicing Test Driven Development (TDD) to make sure that you are building the thing right * Pair Programming to improve code quality and knowledge saturation ## Minimum Viable Product * MVP is NOT the result of "Phase 1" of a project * It IS the cheapest/easiest thing you can build to start testing your **value hypothesis** and **learning** * The former focuses on delivery, while the latter focuses on learning * At the end of each MVP you decide whether to pivot or persevere ### What is Agile Development? * Agile is an *iterative* approach to software development consistent with the Agile Manifesto * Emphasizing flexibility, interactivity, and a high level of transparency * Using **small**, **co-located**, **cross-functional**, **self-organizing** teams. ## Spotify: Case Study ### Organizational Structure * **Squads** are grouped into Tribes (light-weight matrix) * **Chapters** of competency areas are formed across Squads * **Guilds** are informal light-weight community of interests across the company ### Autonomous Squads * Each Squad has its own mission aligned with the business * Feels like a ”mini-startup” * Self organizing / Cross-funcitonal * 5-7 engineers, less than 10 * Squads have end-to-end reponsibility for what they build * Build, commit, deploy, maintenance, operations, EVERYTHING! * With a long term mission usually around a single business domain ### Spotify’s Changes to Scrum * Renamed **Scrum Master** to **Agile Coach**: Because they wanted servant leaders vs process masters * Renamed **Scrum Team** to **Squad**: Because their key driving force is Autonomy ## Why is Autonomy Important? * It’s motivating... and motivated people build better stuff * Autonomy is fast — letting decisions happen locally in the squad * It minimizes hand-offs and waiting so you don’t get bogged down ## Why Use ZenHub? * Helps you manage where you are in project based on GitHub Issues * Gives you an easy way to let management know how you are doing * Because it’s integrated with GitHub, it is always up to date * Developers only need to use one tool: GitHub ## What is Kanban? A Japanese manufacturing system in which the supply of components is regulated through the use of an instruction card sent along the production line. It is an instruction card used in a kanban system. ### Core Principles of Kanban * **Visualize the workflow**: You cannot manage what you cannot see. By making all the work visible, including blockers and queues, you can identify issues early on and improve collaboration. * **Limit work in progress (WIP)**: Work in progress limits (WIP limits) determine the minimum and maximum amount of work for each column on the board or for each workflow. * **Manage and enhance the flow**: Ideally, you want a fast, smooth flow, which shows that the team is creating value quickly. The team should analyze problems in the flow then implement changes. * **Make process policies explicit**: Everyone needs to understand how things work or what “done” really means. You can modify the board to make these processes more clear; for example, you could redesign it to specify how the work should flow. * **Continuously improve**: Teams measure their effectiveness by tracking flow, measuring cycle time, and increasing quality of work. ### Scrum vs Kanban | | Scrum | Kanban | | ------------------- | ----------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------- | | Cadence | Regular fixed length sprints (ie, 2 weeks) | Continuous flow | | Release methodology | At the end of each sprint if approved by the product owner | Continuous delivery or at the team's discretion | | Roles | Product owner, scrum master, development team | No existing roles. Some teams enlist the help of an agile coach. | | Key metrics | Velocity | Cycle time | | Change philosophy | Teams should strive to not make changes to the sprint forecast during the sprint. Doing so compromises learnings around estimation. | Change can happen at any time | ## Default ZenHub Pipelines * **New Issues** is the landing point for new Issues. Anyone can create new Issues. They should be triaged weekly. * **Icebox** represents items that are a low priority. This keeps them out of the way of current work while not forgetting about them entirely. * **Product** Backlog represents an ordered list of groomed stories ready too be added to the next sprint. * **Sprint Backlog** is a prioritized backlog of items ready for development. The higher an issue is on this list, the higher the priority. Higher-priority items will typically have more in-depth information. * **In Progress**: This is what is actively being worked on. Each Issue in this pipeline should have an assigned owner who is responsible for its completion. This communicates to the rest of the team that the task is underway. * **Review/QA:** Issues that are open to the team for review and testing. Usually this means the code is deployed and ready for further examination. * **Done**: Issues in this pipeline need no further work and are ready to be closed. Having a good ‘Definition of Done’ agreed upon before work starts on an Issue is very helpful here! ## Sprint A Sprint is one iteration through the design, code, test, deploy cycle. Usually 2 weeks in duration but could be shorter or longer (but not too much longer... remember working in "small batches"). Every Sprint should have a Goal this way everyone knows what goal they are working towards ## Steps in the Scrum Process ![Steps in the Scrum Process](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2F684T4nKOtXS18NW2YbGl%2Fimage.png?alt=media\&token=d3373721-b569-4340-a3a2-0485b9ba9fe6) ## The 5 Scrum Meetings ![The 5 Scum Meetings](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2FJWM0Q5h5zJvUNcCvnxul%2Fimage.png?alt=media\&token=b1afe548-efd1-4aef-9b5d-67b746892d33) ### Backlog Refinement Meeting * Product Owner sorts the Product Backlog in Priority Order to meet business objectives * The team may estimate the amount of effort they would expend to complete items in the Product Backlog and provides other technical information to help the Product Owner prioritize them * Large vague items are split and clarified, considering both business and technical concerns * Sometimes a subset of the team, in conjunction with the Product Owner and other stakeholders, will compose and split Product Backlog Items before involving the entire team in estimation ### Mechanics of Backlog Refinement * Goal: At the end of Backlog Refinement the New Issues column is empty * Take Stories from New Issues and: * Move them into the ranked Backlog if they will be worked on soon * Move them into the Ice Box if they are a good idea but not now * Reject them if they are not where you want to go * Groom the Backlog by ranking the Stories in order of importance and making sure the story contains enough information for a developer to start working on it ### Grooming the Backlog * Make sure that all Issues are groomed and stories are complete * Keep the Backlog ranked by priority so that the important Issues are always on top: The priority is determined by the "**So that**" benefit statement * Size the Issues if possible or leave to Sprint Planning ## Agile Concepts and GitHub * Sprint -> Milestone * Epics -> Epics * User Stories -> GitHub Issues * Tasks -> Markdown Checklist (`- [ ]`) * Product backlog -> Open issues without a Milestone * Sprint backlog --> Issues with a Milestone ## Fixed Releases are deprecated * **Rationale**: risk == number of engineering hours since last deployment. (i.e., less hours == less risk) * **Bottom line**: Feature deployment should be a **non-event** that happens all the time. ## GitHub Issues Issues are the way GitHub tracks things to do. * They could be **Features Requests** * They could be **User Stories** * They could be **Bug Reports** * They could be just about anything you need them to be ## What are User Stories? A user story represents a small piece of business value that a team can deliver in an iteration. While traditional requirements (like use cases) try to be as detailed as possible, a user story is defined incrementally, in three stages: 1. The brief description of the need 2. The conversations that happen during backlog grooming and iteration planning to solidify the details 3. The tests that confirm the story's satisfactory completion ### INVEST acronym criteria | Criterion | Remark | | --------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------- | | **I**ndependent | We want to be able to develop in any sequence | | **N**egotiable | Avoid too much detail; keep them flexible so the team can adjust how much of the story to implement | | **V**aluable | Users or customers get some value from the story | | **E**stimable | The team must be able to use them for planning | | **S**mall | Large stories are harder to estimate and plan. By the time of iteration planning, the story should be able to be designed, coded, and tested within the iteration | | **T**estable | Document acceptance criteria, or the definition of done for the story, which lead to test cases | ### Story Driven Development * User Stories document a persona requesting a function to achieve a goal * The typical form is as follows: ``` As a I need So that ``` * User Stories can be entered into GitHub as **Issues** ### Define Done / Acceptance Criteria I like to include the following in each User Story: * **Assumptions**: List any assumptions about how to implement the Story * **Acceptance Criteria**: Define what it means to be "done" ### Hypothesis Driven Development Hypotheses pair a statement that asserts or predicts value with a testable condition that can be measured. The typical form is as follows: ``` We believe that Will lead to And this will be proven when ``` Where possible, the signal that is being measured should be an actionable metric and not a vanity metric ## Technical Debt Technical debt is anything you need to do that doesn't involve creating a new feature. Technical debt builds up when you take shortcuts. Examples of Technical Debt: Code refactoring, Setup and maintenance of environments, Changing technology like databases. ## Sprint Planning Attendees: Product Owner, Scrum Master, Development Team * The Product Owner is responsible for declaring which Product Backlog Items are the most important to the business during Backlog Refinement. * The Development Team looks at the latest product Increment, projected velocity, and past performance. Based on the data, the Development Team forecast what can be achieved. * The team Assigns work from the Product Backlog to the Sprint Milestone. * Plan to spend 4 hours for a 2 week sprint. ### Steps for creating a Sprint Plan 1. Create a Milestone for the Sprint 2. Assign Issues from the Backlog to the Milestone 3. Filter ZenHub by the Milestone to work the plan ### Sprint Planning Goals * Each Sprint should have a clearly defined Business Goal. * The Product Owner comes with a proposal of the Sprint Goal and Product Backlog Items supporting it. * The whole Scrum Team collaborates on crafting the Sprint Goal, so everybody understands why we are building the Increment. ### Mechanics of Sprint Planning * Take Issues from the top of the ranked Backlog and assign them to the Sprint Milestone * Groom the Story by clarifying and assigning Story Points, Labels, and making sure the story contain enough information for a developer to start working on it * Stop adding Stories when your team’s Velocity is reached ### Team Velocity The number of Story Points a team can complete in a single Sprint. This will change over time as the team gets better at estimating and better at executing. The Velocity is unique to the team because the story point assignment is unique to the team ### Story Points * Story Points acknowledge the fact that sizing using absolute time-to-complete is highly inaccurate so it uses an estimate of complexity * It is measurement of a feature’s size **relative** to other features usually expressed in T-Shirt sized (S, M, L, X) or Fibonacci numbers (1, 2, 3, 5, 8, 13, 21) * The important thing is to agree on "average" and evaluate from that (i.e., is it the same, larger, or smaller than average) ### A Story Point Measures... Effort, Complexity and Uncertainty. ### What Size Should A User Story Be? * A Story should be small enough to be coded and tested within a single Sprint iteration — ideally just a few days * When a Story is too large in scope it is considered to be an **Epic** * Backlog items tend to start as Epics when they are lower priority and less defined * For sprint planning, Epics should be broken down into smaller stories, but not so small that you have moved into detailed design. ### Epics * Epics are Stories that are so big, they need to be broken up into smaller Stories * A single Story should be smaller than a Sprint * Epics are usually larger than a Sprint * Epics are a way of grouping Stories with a common goal together * Epics can be larger than a Milestone ## Daily Standup Attendees: Scrum Master, Development Team, Product Owner (optional) * Occurs every day at the same time and place * Called a "standup" because everyone should remain standing during the meeting to keep it short * Timeboxed to 15 minutes * Not a project status meeting — all status should be tabled for later discussion * Each team member briefly reports on their work ### Daily Standup Questions Each team member answers three questions: 1. What did I accomplish the previous day? 2. What will I work on today? 3. What blockers or impediments are in my way? ## Daily Execution * Take the next highest priority item from the Sprint Backlog * Assign it to yourself * Start working on it * No one should have more than one story assigned to them unless they are blocked and want to start a second story while waiting * When you are finished, move the Story to the Done column ## Milestones and Burn-downs **Milestones** can be created for your project, e.g. Sprint, Beta Drop, Demo, Release 1, etc. **Burn-down charts** can be used to measure your progress against a Milestone. ### Burn-down The measurement of Story Points completed vs Story Points remaining for a given Sprint. Over time the Story Points remaining should go down, hence the name: Burndown. ## Sprint Review / Playback Attendees: Product Owner, Scrum Master, Development Team, (optionally Stakeholders + Customers) * Live Demonstration of implemented Stories * Product Owner determines if done based on acceptance criteria and those stories are Closed * Feedback gets converted into new Product Backlog Stories * This is where iterative development allows the creation of products that couldn’t have been specified up front in a plan-driven approach ## Sprint Retrospective Attendees: Scrum Master, Development Team * Team reflects on their progress for the Sprint * What went well? (keep doing) * When did not go well? (stop doing) * What should we change for the next Sprint? * This is critical for maintaining a healthy team ## Vanity Metrics * Consider the total number of daily “hits” to your website is 10,000 * Now what? (what does a "hit" represent?) * Do you really know what actions you took in the past that drove those visitors to you? * Do you really know which actions to take next? * In most cases, I don’t think it’s very helpful ### Actionable Metric Examples * Reduce time-to-market for new features. * Increase overall availability of the product. * Reduce the time it takes to deploy a software release. * Increase the percentage of defects detected in testing before production release. * Make more efficient use of hardware infrastructure. * Provide performance and user feedback to the product manager in a more timely manner. ### Top 4 Actionable Metric 1. **Mean Lead Time**: How long does it take from idea to production? 2. **Release Frequency**: How often can you deliver changes? 3. **Change Failure Rate**: How often to changes fail? 4. **Mean Time to Recovery (MTTR)**: How quickly can you recover from failure? # RESTful APIs Building RESTful Services with Python and Flask ## HyperText Transfer Protocol (HTTP) The HyperText Transport Protocol (HTTP) is how web browsers talk to servers. An HTTP request consists of: * URL * Header * Body ## What is an API? * **A**pplication **P**rogramming **I**nterface * A documented way to interact with a program or service * Defines the **requests** that you can make of the service * Defines the **data** that you can interchange with the service * Defines the **results** that will be returned by the service ## What is REST? * **RE**presentational **S**tate **T**ransfer * A REST API describes a set of resources * A simple way to transfer and manipulate the state of a resource * A service based on REST is called a RESTful service * A RESTful service is exposed through a Uniform Resource Locator (URL) * A client would issue a Hypertext Transfer Protocol (HTTP) request to manipulate it REST is not a Remote Procedure Call (RPC) or just a bunch of verbs as URI's. ## REST Architecture * REST is a **client-server** architecture: The client and the server provide a separation of concerns which allows both the client and the server to evolve independently as it only requires that the interface stays the same * REST is **stateless**: The communication between the client and the server always contains all the information needed to perform the request. There is no session state in the server. * REST is **cacheable**: The client, the server can cache resources in order to improve performance * REST provides a **uniform interface** between components: All components follow the same rules to speak to one another * REST is a **layered system**: Individual components cannot see beyond the immediate layer with which they are interacting ## What Does It Mean to Be RESTful? * Everything is represented as a Resource * Resource identification through URI (Uniform Resource Identifier), e.g., GET * Uniform interface (I should be able to guess the interface given a resource name) * Self-descriptive messages are used to represent Resources (usually XML or JSON) * Stateful interactions through hyperlinks * A service based on REST is called a RESTful service ## What is a Resource? * The fundamental concept in any RESTful API is the resource * A resource is an object with a type, associated data, relationships to other resources, and a set of methods that operate on it * Only a few standard methods are defined for the resource corresponding to the standard HTTP GET, POST, PUT and DELETE methods ## What Does Resource-Based Mean? * Things vs Actions * Nouns vs Verbs * Not a Remote Procedure Call mechanism * Everything is Identified by URI’s: Multiple URI’s can manipulate the same Resource using different HTTP Verbs ## REST Provides a Uniform Interface * Simplifies and decouples the architecture * Fundamental to RESTful design is an interface that almost be guessed: Perform CRUD on Resources * Uses HTTP verbs (POST, GET, PUT, DELETE) * Uses URL’s to address resources * Uses HTTP Response (status, body) ## Stateless Applications * Server maintains no client state * Each request contains enough context to process the message * Any application state must be held on the client side * Allows easy horizontal scaling of application services ## REST API Conventions * Use REST API conventions to provide a consistent and easy to use interface for * REST API conventions define specific behavior for each type of HTTP method. Use the following guidelines as a starting point for designing your API. * **GET** (read) operations only query data. A GET request should never modify data. * **POST** (create) operations create new resource but do not modify existing resources. * **PUT** and **PATCH** (update) operations modify existing resources. (PUT is more common) * **DELETE** (delete) operations destroy resources **PUT** and **DELETE** operations are idempotent, which means they have no further effect when performed multiple times after the first time. # Cloud Native and Microservices Cloud Native Applications and Microservices Architecture ## Goal of Microservice is Agility * Smart experimentation * Moving in-market with maximum velocity and minimum risk * Gaining quick valuable insight to continuously change the value proposition and quality ## Agility: The Three Pillars DevOps: * Cultural Change * Automated Pipeline * Everything as Code * Immutable Infrastructure Microservices: * Loose Coupling/Binding * RESTful APIs * Designed to resist failures * Test by break / fail fast Containers: * Portability * Developer Centric * Ecosystem enabler * Fast startup ## What is Cloud Native? Cloud-native is an approach to building and running applications that exploits the advantages of the cloud computing delivery model that are built using multiple, independent microservices. DevOps drives the patterns of high performing organizations delivering software faster, consistently and reliably at scale Leveraging automation to improve human performance in a high trust culture, moving faster and safer with confidence and operational excellence ### Cloud Native Applications * **The Twelve-Factor App** describes patterns for cloudnative architectures which leverage microservices. * Applications are designed as a collection of stateless microservices. * State is maintained in separate databases and persistent object stores. * Resilience and horizontal scaling is achieved through deploying multiple instances. * Failing instances are killed and re-spawned, not debugged and patched. * DevOps pipelines help manage continuous delivery of services ## What are Microservices? "…the microservice architectural style is an approach to developing a single application as a **suite of small services**, each **running in its own process** and communicating with lightweight mechanisms, often an HTTP resource API. These services are **built around business capabilities** and **independently deployable** by fully automated deployment machinery." by Martin Fowler and James Lewis ### Microservice Architecture An architecture style aimed to achieve flexibility, resiliency and control, based on the following principles: * Single purpose Loose Coupling bounded context * Independent life cycle: developed, deployed and scaled... and hopefully, fail independently * Design for resiliency and owns it’s own data * Polyglot — independent code base * Built by autonomous teams with end-to-end responsibility, doing Continuous Delivery * Communicates with other services over a well defined API ### Advantages of Microservices * Developed by a single team * Developed independently * Developed on its own timetable * Each can be developed in a different language * Manages its own data * Scales and fails independently ### Microservice Challenges * Developers must have significant operational and development skills (DevOps / Multiple languages) * Service interfaces and versions * Duplication of effort across service implementations * Extra complexity of creating a distributed system with these issues, among others: * Network latency * Fault tolerance * Serialization * Designing decoupled non transactional systems is difficult * Avoiding latency of large numbers of small service invocations * Locating service instances * Maintaining availability and consistency with partitioned data * End-to-end automated testing ## Monolithic vs Microservice ### Monolithic Application Deployment * Loosely coupled * Minimal responsibility per service * Small Deployment units * Easy to Scale * Short release cycles * Fast on-boarding for new developers * Develop quickly with fast feedback ### Microservice Application Deployment * Cloud Native Model * Multiple microservices * Configuration: Automated and consistent * Changes: Performed in DevOps Pipeline * Deployment: Only what changes * Advantages for operations * Resiliency through redundant services * Consistent configuration * Automated massive deployment ### Example Microservice Stereotypes * **Data services**: Responsible solely for the storage and retrieval of data associated with a single microservice * **Orchestration services**: Communicate with multiple data services, either to store data associated with multiple microservice, or to read that data back and compose it into larger data structures * **Backends-for-frontends** (**API Gateway**): Single entry point for all clients. May simply proxy/route to the appropriate service, or fan out to multiple services * **Message bus consumers**: Consume and process messages from message buses such as Kafka ### Microservice Design Enables Horizontal Scaling **Vertical Scaling**: Get bigger servers **Horizontal Scaling**: Get bigger servers ### Monolithic vs Microservices Architectures | Category | Monolithic Architecture | Microservices architecture | | --------------- | -------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------- | | Architecture | Built as a single logical executable | Built as a suite of small services | | Modularity | Based on language features | Based on business capabilities | | Agility | Changes to the system involve building and deploying a new version of the entire application | Changes can be applied to each service independently | | Scaling | Entire application scaled when only one part is the bottleneck | Each service scaled independently when needed | | Implementation | Typically entirely developed in one programming language | Each service can be developed in a different programming language | | Maintainability | Large code base is intimidating to new developers | Smaller code bases easier to manage | | Deployment | Complex deployments with maintenance windows and scheduled downtimes | Simple deployment as each service can be deployed individually, with minimal if not zero downtime | ## What Does A Microservice Should Have? * **High Cohesion** (Bounded Context around a Business Domain): Does stuff that needs to change together occur together? * **Low Coupling** (Shared Nothing with Technology Agnostic API): Do you avoid making otherwise independent concerns dependent? * **Low Time to Comprehension** (Small and Single Responsibility): Small enough for one person to understand quickly ## What Does A GOOD Microservice Should Have? * Microservices should have minimal outside dependancies * Business Domains usually have well established boundaries * Microservices should be broken up by Business Domains * With well defined interface * Limiting dependancies as much as possible ## Domain Driven Design * DDD is about designing software based on models of the underlying domain * **Bounded Context** is a central pattern in Domain-Driven Design * DDD deals with large models by dividing them into different Bounded Contexts and being explicit about their interrelationships. ## Microservice Designs Must: * Design for failure * Move from: * How to avoid —> How to identify & what to do about it * Pure operational concern —> developer concern * Plan to be throttled * Plan to retry (with exponential backoff) * Degrade gracefully * Cache when appropriate ### Retry Pattern * Enable an application to handle transient failures when it tries to connect to a service or network resource, by transparently retrying a failed operation. * **Exponentially back-off** delaying longer with each retry ### Circuit Breaker Pattern * You wrap a protected function call in a circuit breaker object, which monitors for failures. * Once the failures reach a certain threshold, the circuit breaker trips, and all further calls to the circuit breaker return with an error, without the protected call being made at all. * Usually you'll also want some kind of monitor alert if the circuit breaker trips. ### Bulkhead Pattern * Isolates consumers and services from cascading failures: An issue affecting a consumer or service can be isolated within its own bulkhead, preventing the entire solution from failing. * This pattern is named Bulkhead because it resembles the sectioned partitions of a ship’s hull: If the hull of a ship is compromised, only the damaged section fills with water, which prevents the ship from sinking. * Allows you to preserve some functionality in the event of a service failure. Other services and features of the application will continue to work. ## Canary Testing * Mitigates the risks of changes to applications in production * Features are activated only for a small percentage of users, and the application performance and adoption results are measured * If those results indicate that the change is good, then it is ramped up to the rest of the user population * If the change is not good, it is rolled back ## A/B Testing * Some set of users are directed to one implementation of a feature, let’s call it the A version, while a different set of users are directed to a different implementation of the feature, let’s call that the B version * This allows DevOps teams to evaluate different implementation options for a feature, and pick the one that works the best in the field, by measuring actual usage * The data from usage analytics is then used to influence the priorities of the remaining stories in the backlog. ## Feature Flags * With Continuous Delivery, code can be tested and delivered into production with “Feature Flags” around the new code * Using these techniques, those features can be made visible to specific audiences to allow testing of those features in a production environment * The act of going Live can happen via a Release Event on a later date when the Feature Flags are turned on in a coordinated way across multiple components, and the new feature is made publicly visible. ## The Twelve-Factor App The twelve-factor app is a methodology for building software-as-a-service apps that: * Use **declarative** formats for setup automation, to minimize time and cost for new developers joining the project; * Have a **clean contract** with the underlying operating system, offering **maximum portability** between execution environments; * Are suitable for **deployment** on modern **cloud platforms**, obviating the need for servers and systems administration; * **Minimize divergence** between development and production, enabling **continuous** deployment for maximum agility; * And can **scale up** without significant changes to tooling, architecture, or development practices ### I. Codebase One codebase tracked in revision control, many deploys * There is always a one-to-one correlation between the codebase and the app * If there are multiple codebases, it’s not an app – it’s a distributed system: Each component in a distributed system is an app, and each can individually comply with twelvefactor. * Multiple apps sharing the same code is a violation of twelve-factor: The solution here is to factor shared code into libraries which can be included through the dependency manager. ### II. Dependencies Explicitly declare and isolate dependencies * Most programming languages offer a packaging system for distributing support libraries, such as Rubygems for Ruby, or PyPi for Python, or Maven for Java: Libraries installed through a packaging system can be installed system-wide (known as “site packages”) or scoped into the directory containing the app (known as “vendoring” or “bundling”) * **A twelve-factor app never relies on implicit existence of system-wide packages** * It declares all dependencies, completely and exactly, via a dependency declaration manifest * Furthermore, it uses a dependency isolation tool during execution to ensure that no implicit dependencies “leak in” from the surrounding system. The full and explicit dependency specification is applied uniformly to both production and development ### III. Config Store config in the environment * An app’s config is everything that is likely to vary between deploys (staging, production, developer environments, etc). This includes: * Resource handles to the database, Memcached, and other backing services * Credentials to external services such as Amazon S3 or Twitter * Per-deploy values such as the canonical hostname for the deploy * Apps sometimes store config as constants in the code. This is a violation of twelve-factor, which **requires strict separation of config from code**. Config varies substantially across deploys, code does not. ### IV. Backing services Treat backing services as attached resources * A backing service is any service the app consumes over the network as part of its normal operation * **The code for a twelve-factor app makes no distinction between local and third party services** * To the app, both are attached resources, accessed via a URL or other locator/credentials stored in the config * A deploy of the twelve-factor app should be able to swap out a local MySQL database with one managed by a third party (such as Amazon RDS) without any changes to the app’s code ### V. Build, release, run Strictly separate build and run stages A codebase is transformed into a (non-development) deploy through three stages: * The **build** stage is a transform which converts a code repo into an executable bundle known as a build. * The **release** stage takes the build produced by the build stage and combines it with the deploy’s current config. * The **run** stage (also known as “runtime”) runs the app in the execution environment, by launching some set of the app’s processes against a selected release The twelve-factor app uses strict separation between the build, release, and run stages: For example, it is impossible to make changes to the code at runtime, since there is no way to propagate those changes back to the build stage. ### VI. Processes Execute the app as one or more stateless processes * The app is executed in the execution environment as one or more processes * In the simplest case, the code is a stand-alone script, the execution environment is a developer’s local laptop with an installed language runtime, and the process is launched via the command line (for example, python my\_script.py) * On the other end of the spectrum, a production deploy of a sophisticated app may use many process types, instantiated into zero or more running processes * **Twelve-factor processes are stateless and share-nothing**: Any data that needs to persist must be stored in a stateful backing service, typically a database ### VII. Port binding Export services via port binding * **The twelve-factor app is completely self-contained** and does not rely on runtime injection of a webserver into the execution environment to create a web-facing service * The web app **exports HTTP as a service by binding to a port**, and listening to requests coming in on that port. * In a local development environment, the developer visits a service URL like http\:// localhost:5000/ to access the service exported by their app * In deployment, a routing layer handles routing requests from a public-facing hostname to the port-bound web processes. ### VIII. Concurrency Scale out via the process model * **In the twelve-factor app, processes are a first class citizen** * Processes in the twelve-factor app take strong cues from the unix process model for running service daemons * Using this model, the developer can architect their app to handle diverse workloads by assigning each type of work to a process type: For example, HTTP requests may be handled by a web process, and long-running background tasks handled by a worker process ### IX. Disposability Maximize robustness with fast startup and graceful shutdown * **The twelve-factor app’s processes are disposable, meaning they can be started or stopped at a moment’s notice** * This facilitates fast elastic scaling, rapid deployment of code or config changes, and robustness of production deploys * Processes should strive to minimize startup time * Ideally, a process takes a few seconds from the time the launch command is executed until the process is up and ready to receive requests or jobs * Processes shut down gracefully when they receive a SIGTERM signal from the process manager. * For a web process, graceful shutdown is achieved by ceasing to listen on the service port (thereby refusing any new requests), allowing any current requests to finish, and then exiting. ### X. Dev/prod parity Keep development, staging, and production as similar as possible Historically, there have been substantial gaps between development (a developer making live edits to a local deploy of the app) and production (a running deploy of the app accessed by end users). These gaps manifest in three areas: * The **time gap**: A developer may work on code that takes days, weeks, or even months to go into production. * The **personnel gap**: Developers write code, ops engineers deploy it. * The **tools gap**: Developers may be using a stack like Nginx, SQLite, and OS X, while the production deploy uses Apache, MySQL, and Linux. The twelve-factor app is designed for continuous deployment by keeping the gap between development and production small. Looking at the three gaps described on the previous chart: * Make the **time gap** small: a developer may write code and have it deployed hours or even just minutes later. * Make the **personnel gap** small: developers who wrote code are closely involved in deploying it and watching its behavior in production. * Make the **tools gap** small: keep development and production as similar as possible ### XI. Logs Treat logs as event streams Logs provide visibility into the behavior of a running app. In server-based environments they are commonly written to a file on disk (a “logfile”); but this is only an output format. **A twelve-factor app never concerns itself with routing or storage of its output stream** * It should not attempt to write to or manage logfiles * Instead, each running process writes its event stream, unbuffered, to stdout * During local development, the developer will view this stream in the foreground of their terminal to observe the app’s behavior ### XII. Admin processes Run admin/management tasks as one-off processes **One-off admin processes should be run in an identical environment as the regular long-running processes of the app**, such as: * Running database migrations (e.g. manage.py migrate in Django, rake db:migrate in Rails). * Running a console (also known as a REPL shell) to run arbitrary code or inspect the app’s models against the live database. * Running one-time scripts committed into the app’s repo (e.g. php scripts/ fix\_bad\_records.php) They run against a release, using the same codebase and config as any process run against that release. Admin code must ship with application code to avoid synchronization issues # Test Driven Development If it's worth building, it's worth testing ## Why Developers Don't Test * I already know it works! * Others who work on your code in the future won’t know if they broke something * I don’t write broken code! * Sometimes the environment changes and other future libraries read your code * I have no time! * Testing actually saves you time (and stress) in the long run ## Software Testing Levels ### Acceptance Testing A level of the software testing process where a system is tested for acceptability. The purpose of this test is to evaluate the system’s compliance with the business requirements and assess whether it is acceptable for delivery. ### System Testing A level of the software testing process where a complete, integrated system/software is tested. The purpose of this test is to evaluate the system’s compliance with the specified requirements. ### Integration Testing A level of the software testing process where individual units are combined and tested as a group. The purpose of this level of testing is to expose faults in the interaction between integrated units. ### Unit Testing A level of the software testing process where individual units/ components of a software/system are tested. The purpose is to validate that each unit of the software performs as designed. ## DBB & TDD Behavior-Driven Development (BDD) * Describes the behavior of the system from the outside in * Used for Integration / Acceptance Testing Test Driven Development (TDD) * Tests the functions of the system from the inside out * Used for unit testing ### TDD Workflow Cycle: ... -> RED -> GREEN -> REFACTOR -> ... * Write a test case and watch it FAIL * Write the code to make it PASS * REFACTOR the code to make it great knowing that the test case will let you know if you broke anything ### BDD & TDD Cycle ![BDD & TDD](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-537a2b5e71e8ea50a23de4fbdcc997b85a9b3e0c%2Ftdd-bdd.png?alt=media) "BDD is building the right thing, and TDD is building the thing right." ## What is TDD? * Test Driven Development means that your test cases drive the design and development of your code * You write the tests first for the code you wish you had, then you write the code to make the test pass * This keeps you focused on the purpose of the code (i.e., what is it supposed to do) ### Why is automated Testing Important to DevOps? * First and foremost it saves time when developing! * It allows you to run faster because you are more confident * It insures that your code is working as you expected * It insures that future changes don’t break your code * In order to use a DevOps Pipeline, all testing must be automated ### Kent Beck says Good Unit tests... * Run fast (they have short setups, run times, and break downs). * Run in isolation (you should be able to reorder them). * Use data that makes them easy to read and to understand. * Use real data (e.g. copies of production data) when they need to. * Represent one step towards your overall goal. ### The Basic TDD Workflow * Write a failing unit test for the code you wish you had * Write just enough code to make the unit test pass * Refactor the code and repeat ## Test Fixtures A test fixture is a fixed state of a set of objects used as a baseline for running tests. The purpose of a test fixture is to ensure that there is a well known and fixed environment in which tests are run so that results are repeatable. Examples of fixtures: * Preparation of input data and setup/creation of fake or mock objects * Loading a database with a specific, known set of data * Copying a specific known set of files creating a test fixture will create a set of objects initialized to certain states. ### Unittest Fixtures ```py def setUpModule(): # runs once before any tests pass def tearDownModule(): # runs once after all tests pass class MyTestCases(TestCase): @classmethod def setUpClass(cls): # runs once before test class pass @classmethod def tearDownClass(cls): # runs once after test class pass def setUp(self): #runs before each tests pass def tearDown(self): # runs after each tests pass ``` ## Mocking * Mocking creates fake objects that behave like the real thing * Any external service that is not under test should be Mocked * Sometimes you need to change the behavior of a dependent system under test * Maybe you don’t have a remote connection to another component * Or you want to isolate your tests from a remote component ### Methods of Mocking * **Patch**: This patches a function call allowing you to change it’s behavior * **MagicMock**: This mocks an entire object changing it’s behavior. Usually used as a return value ## Factories and Fakes Sometimes you will need fake data to test against, sometimes you will want an entire class to be fake data, Factories and Fakes make this possible. We will use Factory Boy in Python for this. # Continuous Integration Continuous Integration with Travis CI ## Continuous Integration (CI) vs Continuous Delivery (CD) ![CI/CD process](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-a709300e82cb12055bff0121b41d5f67acb62d73%2Fsimple-ci-cd-process.png?alt=media) **Continuous Integration** is the process of continuously integrating every developer's change into the master branch after a set of tests have passed, resulting in potentially deployable code. **Continuous Delivery** is a series of practices designed to ensure that code can be rapidly and safely deployed to production by delivering every change to a production-like environment. ## Traditional Development * Developers work in long lived development branches * Branches are periodically merged into a release (with lots of breakage) * Build are run periodically (e.g., nightly) on release candidate branch * Developers continue to add to the development branch which drifts further and further from the master branch ## Continuous Integration * A development practice that requires developers to integrate code into a shared repository often (e.g., daily) * Developers work in short lived feature branches that are merged into master * Each check-in is then verified by an automated build, allowing teams to detect problems early and often ### Changes are kept small * Committing regularly, every developer can reduce the number of conflicting changes: Checking in a week's worth of work runs the risk of conflicting with other features and can be very difficult to resolve * Using Pull Requests allows team members to communicate about the change they are making * Committing all changes at least once a day (once per feature built) is generally considered part of the definition of Continuous Integration ### Every Pull Request should be built and tested * The system should build commits to the current working version to verify that they integrate correctly * A common practice is to use automated Continuous Integration where a continuous integration server or daemon monitors the revision control system for changes, then automatically runs the build process * Once the code is built, all tests should run to confirm that it behaves as the developers expect it to behave (i.e., make the build self-testing) ## Benefits of CI/CD * Faster reaction times to changes * Reduced code integration risk * Higher code quality * The code in version control works * Less deployment time ## Five Key Principles at the heart of Continuous Delivery * Build quality in * Work in small batches * Computers perform repetitive tasks, people solve problems * Relentlessly pursue continuous improvement * Everyone is responsible ## A CI/CD Pipeline needs... * A code repository to host and manage all your source code * A build server to build the application from source code * An integration server/orchestrator to automate the build and run test code * A repository to store all the binaries and artifacts of the application * Tools for automatic configuration and deployment ## CI/CD + Continuous Deployment ![CI/CD + Continuous Deployment](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-1048c4e6691866a723f88ed95bc5a5c7c98c963a%2Fci-cd-plus-cd-process.png?alt=media) ## Automation is key but insufficient on it's own For business to take advantage of continuous integration and continuous delivery, they must: * Have an **application design** that allows services to be deployed quickly and independently * Have automated all of their **testing** * Have organizational trust that allows **autonomy** and **shared responsibility** * Have **fast feedback loops** with minimal Mean Time to Recovery ## What is Travis CI? * Travis CI is a Continuous Integration tool * It allows you to treat your CI pipeline as code * It can also do deployments for Continuous Delivery ### Continuous Delivery Goals "Continuous Delivery is a software development discipline where you build software in such a way that the software can be released to production at any time" — Martin Fowler. That means: * The Master branch should always be ready to deploy * You need a way to know if something will "break the build" Travis CI gives you a way to achieve this. ### Know if the Build is Broken * Automated Testing is CRITICAL to Continuous Integration * Travis CI can work with any language and any test suite * Lots of languages and test suite support is built-in * Database support is built-in * Webhooks allow Travis-CI to run on every Pull Request * Status is delivered to the Pull Request before a merge # Behavior Driven Development ## What is BDD & TDD Behavior-Driven Development (BDD) * Describes the behavior of the system from the outside in * Used for Integration / Acceptance Testing Test Driven Development (TDD) * Tests the functions of the system from the inside out * Used for unit testing ### BDD * **Given** a set of preconditions: Things that need to happen to put the system into the state needed to perform the tests * **When** an event occurs: Things that the user does to interact with the system under test * **Then** some testable outcome is observed: The expected outcome of the actions performed by the user ### BDD Tactics * Apply the "Five Why's" principle to each proposed User Story, so that its purpose is clearly related to business outcomes * Thinking "from the outside in", in other words implement only those behaviors which contribute most directly to these business outcomes, so as to minimize waste * Describe behaviors in a single notation which is directly accessible to domain experts, testers and developers, so as to improve communication * Apply these techniques all the way down to the lowest levels of abstraction of the software, paying particular attention to the distribution of behavior, so that evolution remains cheap ## The 5 Why's The "5 why's" are a way of continuously asking "why?" over an over until you get to the core of why something happened. ### Examples of 5 Why's Q. "Why did the system fail in production?"\ A. "we found an error condition that wasn't caught" Q. "Why didn't we catch this condition?"\ A. "Because we didn't write a test case for it" Q. "Why didn't we write a test case"\ A. "Because the developer wasn't trained in TDD" Q. "Why wasn't the developer trained in TDD?\ A. "Because we cut the training budget" ### Conclusion of The 5 Why's: Why did the system fail in production? Because we cut the training budget and didn't properly train our new developers. ## Expected Benefits of BDD * BDD offers more precise guidance on organizing the conversation between developers, testers and domain experts * Notations originating in the BDD approach, in particular the given-when-then canvas, are closer to everyday language and have a shallower learning curve compared to TDD tools * Tools targeting a BDD approach generally afford the automatic generation of technical and end user documentation from BDD "specifications" ## BDD Workflow * First, the developers, testers and business folks explore the problem domain, and collaborate to produce concrete examples that describe the behavior they want. * Next, the team use Behave to run those examples as automated acceptance tests. * As the team work on the solution, Behave tells you which examples are implemented and working, and warns you about the ones that aren’t. * Before you know it, you have one document that’s both the specification and the tests for your software. ## BDD Uses Gherkin Syntax * **Given**: the purpose of givens is to put the system in a known state before the user (or external system) starts interacting with the system (in the When steps) * **When**: each of these steps should describe the key action the user (or external system) performs * **Then**: is used to observe outcomes. The observations should be related to the business value/benefit in your feature description * **And**: is used for continuations. Given this And that... Then this And that... etc. ## How behave works * Behave looks for a folder named features with files that have an extension of `.feature` * It then looks for a folder under that called steps that contains the Python code to parse the Gherkin sentences in the feature files. Note: There is no relationship between feature files and step files. Behave loads all of the steps regardless of how many files they are contained in ### Loading Test Data feature file: ``` Background: Given a set of specific users | name | department | | Barry | Shipping | | Pudey | Receiving | | Two-Lumps | Receiving | Scenario: How many people in departments When we count the number of people in each department Then we will find two people in "Receiving" But we will find one person in "Shipping" ``` step file: ```python @given('a set of specific users') def step_impl(context): for row in context.table: users.append({ 'name': row['name'], 'department': row['department'] }) ``` ### Variable Substitution * You can use variable substitution to make the steps more generic * This step can now be used to check for any message in a response * It’s a good idea to make steps as generic as possible for maximum reuse ```python @then('I should see "{message}"') def step_impl(context, message): assert message in str(context.resp.text) ``` ### Feature Definition 08-Behavior-Driven-Development.pdf: P22 ### Environment Setup Behave has a way to setup all of the tests in one place: `environment.py` * `before_step(context, step)`, `after_step(context, step)`: These run before and after every step. The step passed in is an instance of Step. * `before_scenario(context, scenario)`, `after_scenario(context, scenario)`: These run before and after each scenario is run. The scenario passed in is an instance of Scenario. * `before_feature(context, feature)`, `after_feature(context, feature)`: These run before and after each feature file is exercised. The feature passed in is an instance of Feature. * `before_tag(context, tag)`, `after_tag(context, tag)`: These run before and after a section tagged with the given name. They are invoked for each tag encountered in the order they’re found in the feature file. * `before_all(context)`, `after_all(context)`: These run before and after the whole shooting match. ## Selenium * Selenium automates browsers. That's it! * It is a web browser driver to test web sites by interacting with the user interface just like a human would * It supports Firefox, Chrome, Safari, IE, PhantomJS * This makes it perfect for testing the integration of multiple microservices that share a common user interface # Platform as a Service ## What is cloud computing? ### NIST Description The National Institute of Standards and Technology (NIST) loosely describes cloud computing as: "A model for enabling convenient, **on-demand** network access to a **shared pool** of **configurable computing resources**, such as networks, servers, storage, applications, and services, that can be **rapidly provisioned and released** with **minimal management effort** or service provider interaction." ### Characteristics * A fundamental shift from physical infrastructure to virtual infrastructure: Seen as a major paradigm shift * A rapid way of provisioning and later releasing computing services on the network Some important characteristics: * Rapid/automated provisioning and (later) release of services * Can be Pay-as-you-go * Appearance of infinite resources * Could be managed or unmanaged ### Why use cloud services instead of running them yourself? You’ll think, “if I was running my own Kafka cluster instead of using Kinesis, I could find the issue and fix it” That may be true, but you should remember two things: 1. That would be a distraction from creating business value 2. You would almost certainly be worse at running it. You’d have more and worse incidents. It’s a service provider’s purpose in life to be good at it and they have economies of scale you don’t. Moving past the “I could always build it myself” attitude can be hard. ## Types of Clouds Based on service provided * Software as a Service (SaaS) * Platform as a Service (PaaS) * Infrastructure as a Service (IaaS) Based on ownership * Public Clouds * Private Clouds * Hybrid Clouds Based on Location * On Premise * Off Premise ## Computing as a Service ![Computing as a Service](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-91bb995b2ef36c3b5f3fc27a47eee9e7cb04ec2e%2Ftype-of-clouds.png?alt=media) ## Types of Cloud Migration * **Image Migration**: Save an image of the server and restore it to a virtual machine * **Workload Migration**: Build a new server in the cloud and reinstall the application * **Cloud Native**: Rewrite the application to take advantage of cloud architectures ## Cloud Enabled * Image Migration and Workload Migration don’t take full advantage of the Cloud * You have the same number of VM’s as you had Physical Servers * Which means you need to manage the same number of servers in the end ## Cloud Native Applications * The *Twelve-Factor* App describes patterns for cloud-native architectures which leverage microservices * Applications are design as a collection of stateless microservices * State is maintained in separate databases and persistent object stores * Resilience and horizontal scaling is achieved through deploying multiple instances * Failing instances are killed and re-spawned, not debugged and patched (cattle not pets) * DevOps pipelines help manage continuous delivery of services ## Microservices An architecture style aimed to achieve flexibility, resiliency and control, based on the following principles: * Loose Coupling bounded context * Independent life cycle: developed, deployed and scaled... and hopefully, fail independently * Design for resiliency * Polyglot * Built by autonomous teams with end-to-end responsibility, doing Continuous Delivery ### Monolithic vs Microservices | Monolithic | Microservices | | ----------------------------------- | ----------------------------------- | | Tightly coupled | Loosely coupled | | Mixed Concerns | Minimal responsibility per service | | Large Deployment units | Small Deployment units | | Hard to Scale | Easy to Scale | | Long release cycles | Short release cycles | | Slow on-boarding for new developers | Fast on-boarding for new developers | | Slower feedback loop | Develop quickly with fast feedback | ### Where to Deploy Our Microservice? * Deploying to Virtual Machines means that you now have to manage VM’s * Not desirable * Patching, upgrading, health check, etc. * Deploying to a Platform frees you up to only worry about your application * Cloud Native Deployment enables agility ## IaaS vs PaaS ![IaaS vs PaaS](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-c944a00da632f58d707b7016219e1a97d95d2292%2Fiaas-vs-paas.png?alt=media) ## Containers vs Virtual Machines VMs: * Virtual Machines are heavy-weight emulations of real hardware Containers: * Containers are light-weight like a process * The app looks like it’s running on the Host OS ## IBM Cloud Services ### Cloud Foundry * **Platform as a Service** for running applications * Offers a set of run-time environments that you deploy into: Java, Python, NodeJS, Ruby, Go, Mobile, etc. * Uses Heroku Buildpacks to provide environments: You can bring your own or use community buildbacks * Deploying code is as easy as: cf push #### Cloud Foundry Architecture The Cloud Foundry platform is abstracted as a set of large-scale distributed services. * It uses Cloud Foundry Bosh to operate the underlying infrastructure from IaaS providers (e.g., VMware, Amazon AWS, OpenStack), * Components are dynamically discoverable and loosely coupled, exposing health through HTTP endpoints so agents can collect state information (app status & system state) and act on it. ### Kubernetes * An open-source system for automating deployment, scaling, and management of containerized applications. * Groups containers that make up an application into logical units for easy management and discovery. * Based on 15 years of experience of running production workloads at Google, combined with best-of-breed ideas and practices from the community ### Docker Docker is a light-weight container service that runs on Linux * File system overlay * One Process Space * One Network Interface * Shares the Linux kernel Containers encapsulate a run-time environment * Your code, libraries, etc. Almost no overhead * Containers spin up in milliseconds * Native performance because there is no emulation * Package only what you need ### Red Hat® OpenShift Open Source application platform based on Containers and Kubernetes. Makes the Kubernetes experience easier for developers and operations OpenShift Provides: * Web Console for Developers * Source-2-Image (S2I) * Built-in CI/CD Pipeline * Validated integrations (Istio, K-Native, etc.) * Integrated container registry ### Serverless * You don't need to provision a server * No permanent infrastructure * Your software only runs when it is needed * You only pay for actual use * Ideal for event driven environments #### Cloud Functions with Apache OpenWhisk OpenWhisk is a cloud-first distributed event-based programming service * It represents an event-action platform that allows you to execute code in response to an event * Provides a serverless deployment and operations model hiding infrastructural complexity: Simply provide the code you want to execute Supported languages/runtimes: * NodeJS * Java * Swift * Python * Docker Supported Events: * Periodic * IBM Cloudant * Message Hub (Kafka) * Mobile Push * GitHub * IBM API Connect ### Plain Old VM’s Sometimes you need a VM because of some unique requirement Deploying to Virtual Machines means that you now have to manage VM’s * Patching, upgrading, health check, etc. * Not desirable * Use as a last resort! ### DevOps Continuous Deployment In order to facilitate Continuous Deployment, you want to deploy into an environment with the least friction * Setting up IaaS VM’s is a lot of work and leaves a large 'attack surface' for predators * Platform as a Service makes deployment frictionless and more secure ## Advantages of PaaS * **Minimal set-up** time to get coding: Developers can concentrate on the application and not the infrastructure * **Large number of services** to take advantage of (Database, Messaging, Analytics, Mobile, etc…) * Very **easy to scale** with demand * Delete it if it doesn’t work out and pay nothing (or very little) # Docker Introduction to Docker ## Docker Concepts * Docker is a platform for developers and sysadmins to develop, deploy, and run applications with containers * The use of Linux containers to deploy applications is called containerization * Containers are not new, but Docker make their use for easily deploying applications simple ## Benefits of Containers * Great isolation * Great manageability * Container encapsulates implementation technology * Efficient resource utilization * Fast deployment ### Containers Enable Immutable Delivery Build once... run anywhere * The same binary that a developer runs on their laptop, runs in production * All dependencies are package in the container * Facilitates rolling updates with immediate roll-back * Consistency limits side-effects ## Containers are just Linux Capabilities Under the Covers Containers are: Linux® processes with isolation and resource confinement that enable you to run sandboxed applications on a shared host kernel using cgroups, namespaces, and chroot. * **cgroups**: Control Groups allow you to control how much resources are allocated to a process (e.g., memory, cpu. etc.) * **namespaces**: Control access to what you can see (e.g., processes, mounts, networking, etc.). What you can't see, you can't access! * **chroot**: Allows you to change the root filesystem. This allows the apparent root to be any linux filesystem whether it be ubuntu, opensuse, redhat or otherwise (i.e., overlay filesystem) In other words, Docker Containers allow you to control: * What resources a process can see * What resources a process can control * What filesystem a process uses ## Containers and Virtual Machines A container runs natively on Linux and shares the kernel of the host machine with other containers It runs a discrete process, taking no more memory than any other executable, making it lightweight By contrast, a virtual machine (VM) runs a full-blown “guest” operating system with virtual access to host resources through a hypervisor . In general, VMs provide an environment with more resources than most applications need To summarize, Virtual Machines are heavy-weight emulations of real hardware. Containers are light-weight process The app looks like it’s running on the Host OS. ## Containers are: * **Flexible**: Even the most complex applications can be containerized * **Lightweight**: Containers leverage and share the host kernel * **Interchangeable**: You can deploy updates and upgrades on-the-fly * **Portable**: You can build locally, deploy to the cloud, and run anywhere * **Scalable**: You can increase and automatically distribute container replicas ### Containers are Scaled on Demand * Cloud Native Microservices use redundancy for resiliency * Containers are spun up as needed and destroyed when no longer needed * This why containers should be immutable and stateless ### Docker Provides Portable Isolated Environments * Docker gives you portable isolated environments * You could have an application that requires Python 3.6 running in one container * With an application that requires Python 2.7 running in another * Completely isolated from each other will no chance of library collisions ## Images and containers A container is launched by running an image. An image is an executable package that includes everything needed to run an application--the code, a runtime, libraries, environment variables, and configuration files. A container is a runtime instance of an image i.e., what the image becomes in memory when executed (that is, an image with state, or a user process). You can see a list of your running containers with the command, `docker ps`, just as you would in Linux ### Docker Layered Filesystem * Docker uses a Copy-On-Write layered filesystem. You can see the layers when you pull or push an image * Only changes from the read-only layers are copied ### Images and Layers * Each Docker image references a list of read- only layers that represent filesystem differences * Layers are stacked on top of each other to form a base for a container’s root filesystem * When you create a new container, you add a new, thin, writable layer on top of the underlying stack * All changes made to the running container - such as writing new files, modifying existing files, and deleting files - are written to this thin writable container layer ## Docker Volumes * Volumes are easier to back up or migrate than bind mounts. * You can manage volumes using Docker CLI commands or the Docker API. * Volumes work on both Linux and Windows containers. * Volumes can be more safely shared among multiple containers. * Volume drivers let you store volumes on remote hosts or cloud providers, to encrypt the contents of volumes, or to add other functionality. * New volumes can have their content pre-populated by a container ## Containers should be... * **Stateless**: All state should be maintained in a Database, Object Store, or Persistent Volume * **Light Weight**: Only one process per container i.e., Container dies when process dies * **Immutable**: Do not install an ssh daemon or any other means of entering the container! * **Run from Docker Registry Images or Built from Dockerfiles**: Treated like code, versioned, and reconstituted when needed... not built by hand! ### What do we mean by Stateless? When we say STATE what do we mean? * Any pieces of data about the client or transaction * Could be the state of a session with the end-user * These should be persisted somewhere (database, session cache, etc.) but NOT in memory! ## What Docker Is NOT? Docker is NOT a Virtual Machine! * Resist the temptation of putting a monolith in a container * Resist the urge to run more than one process per container * It’s a bad idea to store state in a container (just don’t do it!) ## What Can you Do with Docker? * You can run **Containers** from the **Images** in the Docker Registry (e.g., Docker Hub) * You can build Docker **Images** that hold your applications and their dependancies * You can create Docker **Containers** from those Docker images to run your applications * You can share those Docker images via **Docker Hub** or your own Docker registry * You can pull those images from the Docker registry to **deploy** them as Containers on a server running Docker Engine * You can even deploy those containers in the **Bluemix** Container Cloud! ## Containers should be small * Its a good practice to use a tiny Linux distribution for building containers * Docker images should only contain the app and it’s required libraries (not a whole OS!) * mall distributions have a small attack surface and are more secure * Alpine is perfect for this base OS # Security Security and DevOps ## Security in a DevOps world: Security cannot be an afterthought in DevOps * DevOps teams need to involve Security team early for smooth deployment of new features * Opportunity for greater collaboration between DevOps and Security teams * In fact, DevOps requires this collaboration and empathy amongst teams and enables them by making success a joint stakeholders game ## Pull Requests provides Segregation of Duties “Pull requests are the new segregation of duties” - Ed Bellis, Kenna Security * Pull requests let you tell others about changes you've pushed to a repository on GitHub. * Once a pull request is opened, reviewers can examine the potential changes and add follow- up commits before the changes are merged into the repository * The owner of a Pull Request should never be the person that merges it to maintain clear segregation of duties ## DevOps Advantages for Security * DevOps forces **tighter collaboration** with the security teams, instead of last-minute manual audit and reviews which were the norm befor * Security teams must be **engaged early in the design process** to ensure ability to deploy continuously * DevOps Configuration Management * **Standardized configurations** makes it easier to harden them * Standardized configurations makes it easier to diagnose when a security incident is in progress * Easier to ensure policies around secure configuration * DevOps **Version Control** Tools: Enable easier rollback in case of issues * DevOps as a **Compliance** Enabler: Automation (Cookbooks / Playbooks) as evidence of compliance, as well as documentation of policy ## Types of Security Tests Automatable in a DevOps context * For security to be truly woven into DevOps, security tests (like all other tests) should be automated * Security tests you can automate: * Functional Security Tests * Non-functional Security tests against known weaknesses * Security scanning of apps and infrastructure * Security testing application logic * Security test automation frameworks: BDD-security, Mittn, GauntIt * Open-sourced Cookbooks available for common security tools: Nessus, Nmap, SSH, openVPN, iptables, Duo 2FA ## Tools for Security in DevOps Static Analysis, Dynamic Analysis, Fuzzing Manual Code Review, Vulnerability Testing, Software Component Analysis, Runtime Protection, Continuous Security Testing ### Static Analysis Tools for Security in DevOps * Examines all code or runtime binaries to support a thorough search for common vulnerabilities * Static Application Security Testing (SAST) * highly effective at finding flaws, even in previously (manually) reviewed code * some tools have APIs for integration into the DevOps process, and don’t require “code complete” * may require some time to fully scan code ### Dynamic Application Security Testing (DAST) * Dynamically crawls through an app’s interface * Tests how it reacts to various inputs * Offers insight into how code behaves * Helps flush out errors that other tests may not see in dynamic code paths * Typically run against fully built applications * Can be destructive * May require some time to fully scan code * Inline tests that gate a release are often run against new code only * Full application sweeps are run in parallel to inline tests ### Fuzzing Tools for Security in DevOps * Throw lots of random garbage at applications, and see whether it causes errors * Has become essential to identifying misbehaving code which may be exploitable * Con: running through a large test body of possible malicious inputs takes a lot of time ### Manual Code Review for Security in DevOps * Manual reviews often catch obvious stuff that tests miss, and developers can miss on their only pass * Developers ability to write security unit tests varies * All new code should be reviewed with every Pull Request ### Vulnerability Analysis for Security in DevOps * Vulnerability scans based on platform configuration, patch levels, or application composition * Vulnerability scans may even use credentials to query for detailed application information * Should span application, app stack, and the platforms that support it ### Software Component Analysis (SCA) Tools * Hook these tools into your build or CI/CD pipeline * Automatically inventory open source dependencies * Identify out-of-date libraries * Identify libraries with known security vulnerabilities * OWASP Dependency Check: * Open source scanner that catalogs open source components used in an application * Works for Java, .Net, Ruby (gem spec), PHP (composer), Node.js, and Python * Integrates with common build tools and CI servers like Jenkins * Reports on any components with known vulnerabilities reported in the NIST’s National Vulnerability Database (NVD) * Gets updates from NVD data feeds ### Runtime Protection for Security in DevOps * Runtime Application Self Protection (RASP) * Interactive Application Self-Testing (IAST) * Provide execution path scanning, monitoring, and embedded application white listing * Runtime threat protection: Protect applications by detecting attacks in runtime behavior. e.g., In-memory execution monitoring, Virtualized execution paths, Embedded runtime libraries ### Continuous Security Testing * Paid Penetration Testing Service (pen testing aka ethical hacking) * Open Bug Bounty Program (popularized by Facebook, Yahoo, Google, and Microsoft) * Continuous Infrastructure Scanning ## Security as Code * Building security into DevOps tools, practices, and workflows * Uses Continuous Delivery as the control backbone * Uses automation engine for security and compliance ## Responsibilities of Security Organization in DevOps Security should be woven into the DevOps framework delivering code: Security * Security should become part of the operational process of integrating and * Security needs to fit into DevOps, not the other way around Security needs to be tailored to work within the automation and orchestration model to be successful: Reduce security related bottlenecks without losing effectiveness ### How Security Organization can help DevOps Educate, Grow your own support, Help DevOps team understand threats, Advise on remediation practices, Help evaluate security tools, Help with priorities, Write tests, Advocacy ## Open Web Application Security Project (OWASP) Top 10 List: a list of what OWASP considers the current top 10 web application security risks worldwide. The list describes each vulnerability, provides examples, and offers suggestions on how to avoid it. Based on data from seven application security firms, spanning over 500,000 vulnerabilities across hundreds of organizations. Ordering within the top 10 according to their prevalence and their relative exploitability, detectability, and impact ### OWASP #1: Injection * Untrusted data sent to an interpreter as part of a command/query * SQL injection, OS injection, LDAP injection, HTTP command injection * Works by using hostile data to trick the interpreter into executing unintended commands or accessing data without proper authorization * Prevention: * A safe API which avoids the use of the interpreter entirely or provides a parameterized interface * Escape List or keywords or special characters to be blocked * Keyword list needs to be kept updated #### Types of Injection There are many types of injection vulnerabilities, some of the most common include: * SQL Injection * Code Injection * OS Commanding * LDAP Injection * XML Injection * Path Injection * SSI Injection * IMAPO/SMTP Injection * Buffer Overflow All involve allowing untrusted or manipulated requests, commands, or queries to be executed by a web application #### Preventing the Weakness * Use a vetted Library or framework (e.g., SQLAlchemy for SQL) * Use an API which avoids the use off interpreter (parameterized) * Run the application with minimum privileges * Escape all special characters used by an interpreter * Input Validation/Sanitization, white list on allowed characters ### OWASP #2: Broken Authentication and Session Management * Incorrectly/insufficiently implemented Authentication and Session Management * User authentication credentials aren’t protected when stored using hashing or encryption * Credentials can be guessed or overwritten through weak account management functions (e.g., account creation, change password, recover password, weak session IDs) * Session IDs are exposed in the URL * Session IDs don’t timeout * Passwords, session IDs, and other credentials are sent over unencrypted connections * Allows attackers to user identities by stealing passwords, keys, or session tokens * Can be handled by taking authentication and session management out of the application into specialized technologies specifically meant for those purposes * Avoid XSS flaws which can be used to steal session IDs ### OWASP #3: Sensitive Data Exposure Many apps do not properly protect sensitive data * Credit cards, tax IDs, authentication credentials, passwords, health records, and personal information * Never send or store sensitive data stored in clear text * Use of old / weak cryptographic algorithms * Use of weak crypto keys generated * Key mismanagement (keys not rotated) * Missing browser security directives or headers when sensitive data is handled by browser? All sensitive data must be encrypted at rest and in transit: Use Federal Information Processing Standard (FIPS 140) validated cryptographic modules #### How to Prevent Sensitive Information Exposure? Recommendation: Scrub error messages, API calls * Replace default server error pages with custom error pages * Do not display file paths, IOs, serve names or stack traces in error messages * Do not reveal implementation details or version information in error messages (e.g., SQL, JQuery, Java) * Do not pass email addresses, accounts or other sensitive info in path/query of request (use POST body) * Error details go in the log. Your end user doesn't want to see implementation details anyhow Do not include private information in logs (passwords, etc.) ### OWASP #4: XML External Entities (XXE) * Due to older or poorly configured XML processors * External entity references within XML documents can be used to disclose internal files by using * File URI handler * Remote code execution * Denial of Service attacks * Mitigation * Avoid XML and use less complex data formats like JSON * Patch or upgrade all XML processors and libraries in use by app or OS * Disable XML External Entity processing in all XML parsers in the app ### OWASP #5: Broken Access Control Due to: * Lack of controls on what authenticated users are allowed to do * Poorly implemented controls that can be easily bypassed Attackers can exploit these flaws to access unauthorized functionality and/or data Mitigation to avoid these attacks: * Access control should be enforced on server-side (not client-side) * Deny access to functionality and data, by default * Limit the scope of access, e.g., specific organizations and business units Log access control failures and alert admins upon repeated failures * Include access control as part of unit and integration tests ### OWASP #6: Security Misconfiguration Default server settings are often insecure or can be exploited * Admin console is auto-installed but not removed * Directory listing is not disabled on server * Stack traces are returned to users, exposing underlying flaws. * Useful for debugging, but also a gift for attackers! Sample apps (which may have flaws) not removed from production server Mitigation to avoid these attacks: * Software should be kept up to data with patches, etc. * Security settings should be defined, implemented, and maintained Harden servers prior to service activation * Run scans and do audits periodically to help detect future misconfigurations or missing patches ### OWASP #7: Cross-Site Scripting (XSS) App takes untrusted data and sends it to web browser without proper validation or escaping * XSS allows attackers to execute scripts in the victim’s browser * Hijack user sessions * Deface web sites * Redirect user to malicious sites * Typically prevented by: * Looking for suspicious HTTP requests/keywords that can trigger scripting engine: Banned HTML tags and escape sequences * Escape List or keywords or special characters to be blocked ### OWASP #8: Insecure Deserialization * Serialization / Marshalling: converting a data structure into a format that can be stored or transmitted * Deserialization / Unmarshalling: extracting a data structure from a series of bytes * Databases, middleware, web services, network protocols all use serialization/deserialization * Insecure Deserialization occurs when an app or API processes a request to deserialize tampered objects provided by attacker * Mitigation to avoid these attacks: * Do not accept serialized objects from untrusted sources * Integrity checks such as digital signatures to verify source and prevent tampering * Enforcing strict type constraints on objects prior to deserialization ### OWASP #9: Using Components with Known Vulnerabilities * Components: libraries, IDEs, frameworks, etc. * Vulnerabilities in such components can be exploited for a range of attacks, resulting in data loss or server takeover * Mitigation to avoid these risks: * Identify all components and the versions you are using, including all dependencies * Monitor the security of these components in public databases, project mailing lists, and security mailing lists * Keep them up to date with patches and fixes ### OWASP #10: Insufficient Logging and Monitoring Identifying a breach took an average of 191 days \[OWASP, 2016]: Plenty of time for attacker to use a small exploit and launch a full-fledged attack Due to: * Lack of logging and monitoring: * Logins and login failures are not logged * No intrusion detection capabilities * Poorly implemented logging and monitoring: * Logs are collected but stored locally and never aggregated * Poorly implemented alerting thresholds * Unclear log messages Mitigation to avoid these attacks: * Log all auditable events (logins, login failures, high-value transactions) * Aggregate and analyze log data with Centralized Log Management * Implement Security Incident Event Management solutions # Swagger and OpenAPI Introduction to Swagger & OpenAPI ## Why is Documentation Important? * Without documentation, no one will know how to call your API * If no one calls your API, it has no reason to exist * If your API has no reason to exist, you will be unemployed * When you are unemployed, you will wish you had written documentation for your API ;-) ## What is Swagger? An open-source framework for designing and describing REST APIs. Equally suitable for both designing new APIs and documenting your existing APIs. A Swagger specification describes the API endpoint, available resources and operations that can be called against these resources. ### Why Swagger? * The simple YAML format is human-readable, machine-readable and self- explanatory * There is a variety of tools built around it that facilitate API development * Swagger `Codegen` can generate server code and client SDKs based on a Swagger specification * `Swagger UI` can render Swagger specifications to interactive API documentation, like the one at * These are just a few examples of how Swagger can help API developers ### API First Approach * Design the API First and generate a Mock * Use Python Library like `Connexion` to Implement * `Connexion` allows the code to comply with the API ! ### Problems with using External Documentation * A separate thing for developers to update * Too easy for developers to change the code and forget to change the documentation * Requires developers to look in a separate place for documentation instead of being in-line with the code ## What is SwaggerHub? SwaggerHub is an online platform where you can design your APIs and collaborate on them using Swagger – be it public APIs, internal private APIs or microservices The core principle behind Swagger and SwaggerHub is Design First, Code Later. That is, you start by laying out your API, its resources, operations and data models, and once the design is complete you implement the business logic Your API definitions are saved in the SwaggerHub cloud and can be synchronized with external systems like GitHub or Amazon API Gateway # Kubernetes Introduction to Kubernetes ## Why choose Kubernetes? * An open-source system for automating deployment, scaling, and management of containerized applications. * No Vendor Lock-In * Large Community of support * Robust platform for container orchestration * Based on 15 years of experience of running production workloads at Google, combined with best-of-breed ideas and practices from the community ### Kubernetes is an Orchestration Platform * Scheduling: decide where containers run * Lifecycle and Health: keep containers running and restart them if they fail * Scaling: grow and shrink deployments as needed * Naming and Discovery: help containers find each other * LoadBalancing: distribute traffic across containers ...and a whole lot more ### Why Do You Need Container Orchestration? * Deploy applications to servers without worrying about specific servers * Scale the application horizontally up and dow * This is called container auto-healing or Restore the application if the server on which it worked fails rescheduling ### Kubernetes has a Declarative API Kubernetes is a Declarative Model You express the desired state Kubernetes maintains it What could be simpler? ## Kubernetes Architecture * There can be one or more Master Nodes (HA) * There can be zero or more Worker Nodes * Everyone communicates via the API Server * Kubelet on each Worker Node acting as an agent * Everything can be on one node for development use ### Kubernetes All-In-One * You can run Kubernetes all in one VM for development work (not for production!) * MiniKube is great for setting this up * MiniShift will deploy a development version of RedHat OpenShift 3.x which uses Kubernetes * CRC (Code Ready Container) will deploy OpenShift 4.x ### Kubernetes is the new "Cloud OS" Managing Containers with VMs: * SysAdmins must decide where to place container * Workload balancing is manual Managing Containers with Kubernetes: * Kubernetes schedules and optimizes workloads automatically ## Kubernetes Pods * Containers run in Pods * The Pod is the smallest deployment possible * Containers are deployed from a container registry (public or private) ## Kubernetes ReplicaSets * ReplicaSets allow multiple copies of containers to be deployed * Each one in it's own Pod * If a container dies, the ReplicaSet will spawn a new one ## Kubernetes Volume Mounts Volumes * **ConfigMaps** hold configuration parameters * **Secrets** hold credentials and other secrets * **Persistent Volume Claims** are used to ask for persistent storage for data/state ## Kubernetes Deployments Deployment * Sets up the ReplicaSets for you * Also specified the Secrets, ConfigMaps, and Volume Mounts * Provides features for rolling out updates and handling their rollbacks ## Kubernetes Service Service exposes Pods to the outside as: * ClusterIP * NodePort * Load Balancer ### Types of Services * **LoadBalancer**: Only available via cloud providers. Front end for service that balances the load across multiple backends from a single IP address * **NodePort**: Exposes the service as an arbitrary port on every worker node in the cluster * **ClusterIP**: Service is only accessible from other services within the cluster (no external exposure) ## Kubernetes Ingress Controller Ingress * Exposes Service outside of Kubernetes * Maps URL paths to services ## Services Map to Pods via Labels ![Services Map to Pods via Labels](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-c948eb090b48fbf184adbbf5ec3656795d71eff3%2Fservices-map-to-pods-via-labels.png?alt=media) ### Use Case for Multiple Containers in a Pod Pods can be used to host vertically integrated application stacks (e.g. LAMP), but their primary motivation is to support co-located, co-managed helper programs, such as: * Content management systems, file and data loaders, local cache managers, etc. * Log and checkpoint backup, compression, rotation, snapshotting, etc. * Data change watchers, log tailers, logging and monitoring adapters, event publishers, etc. * Proxies, bridges, and adapters * Controllers, managers, configurators, and updaters ### Linking Service to Pods Service: ```yaml apiVersion: v1 kind: Service metadata: name: hitcounter-service spec: type: NodePort selector: app: hitcounter # label ports: - name: primary protocol: TCP port: 8080 ``` Deployment: ```yaml apiVersion: apps/v1 kind: Deployment metadata: name: hitcounter spec: replicas: 3 selector: matchLabels: app: hitcounter # <-- should match this label template: metadata: labels: app: hitcounter spec: containers: - image: hitcounter:1.0 imagePullPolicy: IfNotPresent name: hitcounter ports: - containerPort: 8080 - protocol: TCP restartPolicy: Always ``` ## Service Discovery Kubernetes provides internal routing so services can find each other ![Internal Service Discovery](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-c106cfb27adcf7a361d1a4877ca3197102bdc4ea%2Fkubernetes-internal-routing.png?alt=media) ## External Service Access LoadBalancers provide external access for a single service ![LoadBalancer](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-8590c86cd939a382e6d4ef01e7b8a33b8217d586%2Fkubernetes-external-service-access.png?alt=media) ## External Routing Kubernetes provides an **Ingress Controller** to allow external network access or you can use NodePorts. ![External Routing](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-a54542d4ebcde1c9b28fdaefb7d7cf8d17b7398b%2Fkubernetes-external-routing.png?alt=media) ### Ingress Example ```yaml apiVersion: extensions/v1beta1 kind: Ingress metadata: name: ecommerce spec: rules: - host: ecommerce.containers.mybluemix.net http: paths: - path: /shopcarts backend: serviceName: shopcart-service servicePort: 5000 - path: /catalog backend: serviceName: catalog-service servicePort: 5000 - path: /orders backend: serviceName: order-service servicePort: 5000 - path: /recommendations backend: serviceName: recommendation-service servicePort: 5000 ``` ### Ingress Controller Single entry point into multiple kubernetes services ![Ingress Controller](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-f6f5e91ef30a9e13eb5e3ef9c9ced6186f57a3a5%2Fkubernetes-ingress-controller.png?alt=media) ## Persistent Volumes * Kubernetes loosely couples physical storage devices with containers by introducing an intermediate resource called persistent volume claims (PVCs). * A PVC defines the disk size, disk type (ReadWriteOnce, ReadOnlyMany, ReadWriteMany) and dynamically links a storage device to a volume defined against a pod * The binding process can either be done in a static way using PVs or dynamically be using a persistent storage provider ### Example Volume Mount There is a volume named `redis-storage` and that is connected to the `redis` container via the VolumeMount: `/data/redis` ```yaml apiVersion: v1 kind: Pod metadata: name: redis spec: containers: - name: redis image: redis volumeMounts: - name: redis-storage mountPath: /data/redis volumes: - name: redis-storage emptyDir: {} ``` ## Configurations Management: ConfigMaps * Containers generally use environment variables for parameterizing their runtime configurations * Kubernetes provides a way of managing more complex configuration files using a simple resource called ConfigMaps * ConfigMaps can be created using directories, files or literal values using following CLI command: ```bash $ kubectl create configmap # map-name: name of the config map # data-source: directory, file or literal value ``` ## Credentials Management: Secrets * Similar to ConfigMaps, Kubernetes provides another valuable resource called Secrets for managing sensitive information such as passwords, OAuth tokens, and ssh keys. * A secret can be created for managing basic auth credentials using the following way: ```bash # write credentials to two files $ echo -n 'admin' > ./username.txt $ echo -n '1f2d1e2e67df' > ./password.txt # create a secret $ kubectl create secret generic app-credentials --from-file=./ username.txt --from-file=./password.txt ``` ### Credentials From Environment Variables ```bash $ export DATABASE_URI='postgres://admin:s3cr3t@postgres:5432/postgres' $ kubectl create secret generic db-creds --from-literal=databaseuri=$DATABASE_URI ``` Creates the following ```yaml apiVersion: v1 kind: Secret data: database-uri: cG9zdGdyZXM6Ly9hZG1pbjpzM2NyM3RAcG9zdGdyZXM6NTQzMi9wb3N0Z3Jlcw== ``` ### Create Secrets from Literals ```bash kubectl create secret generic dev-db-secret \ --from-literal=username=devuser \ --from-literal=password='s3cr3t' \ --dry-run=client -o yaml ``` Output from create command: ```yaml apiVersion: v1 kind: Secret metadata: name: dev-db-secret type: Opaque data: username: ZGV2dXNlcgo= password: czNjcjN0Cg== ``` ### Secret Yaml Example ```yaml apiVersion: v1 kind: Secret metadata: name: ecommerce-apikey namespace: default data: secret: ``` ### Using Secrets ```yaml apiVersion: apps/v1 kind: Deployment --- spec: containers: - name: pet-demo image: pet-demo:v1 imagePullPolicy: IfNotPresent ports: - containerPort: 5000 protocol: TCP env: - name: DATABASE_URI valueFrom: secretKeyRef: name: pet-creds key: binding ``` ## Kubernetes Rolling Updates (Zero Downtime Deployments) ```bash $ kubectl set image deployment/ =: ``` ## Kubernetes Autoscaling Kubernetes allows pods to be manually scaled either using ReplicaSets or Deployments. This can be achieved using the following CLI command: ```bash $ kubectl scale --replicas= deployment/ ``` # Infrastructure as Code Describe your infrastructure in textual format and configure them using that description * Never perform system and software configurations manually * Use templates / scripts describing how to install / configure systems /devices /software / users * Configuration Management Systems make this possible ## Convergence * Rather than describing the steps needed to make a change, the language describes the final state in which one wants to end up * The agent then ensures that the necessary steps are taken to end up in this "policy compliant state" * Thus, configuration can be run again and again, whatever the initial state of a system, and it will end up with a predictable result ## Agent vs Agent-less Advantages of **Agent** based * Rich client can do more and run on a schedule * Low volume of network traffic Advantages of **Agent-less** based * Small memory footprint and support of rare systems * No need to run an agent all the time on each server ## Ansible ### Ansible Design Principles * Have a dead simple setup process and a minimal learning curve * Manage machines very quickly and in parallel * Avoid custom-agents and additional open ports, be agentless by leveraging the existing SSH daemon * Describe infrastructure in a language that is both machine and human friendly * Focus on security and easy auditability/review/rewriting of content * Manage new remote machines instantly, without bootstrapping any software * Allow module development in any dynamic language, not just Python * Be usable as non-root * Be the easiest IT automation system to use, ever ### Ansible Terminology The following list contains a quick overview of the most relevant terms used by Ansible: * **Control Node**: the machine where Ansible is installed, responsible for running the provisioning on the servers you are managing. * **Inventory**: an INI file that contains information about the servers you are managing. * **Playbook**: a YAML file containing a series of procedures that should be automated. * **Task**: a block that defines a single procedure to be executed, e.g.: install a package. * **Module**: a module typically abstracts a system task, like dealing with packages or creating and changing files. * **Role**: a set of related playbooks, templates and other files, organized in a pre-defined way to facilitate reuse and share. * **Play**: a provisioning executed from start to finish is called a play. * **Facts**: global variables containing information about the system, like network interfaces or operating system. * **Handlers**: used to trigger service status changes, like restarting or reloading a service. ### Ansible Components **Inventory**: The list of servers and optionally variables to operate on **Playbook**: The collection of "plays" in YAML format to operate on the servers **Plays**: A list of tasks and handlers to execute on each targeted server **Tasks**: Instructions to cary out the configuration ### Inventory File * The inventory files tells Ansible what servers to act on * Ansible allow you to place servers into groups (e.g., webservers, dbservers) and then make changes on entire groups of servers at the same time instead of changing them one-by-one * Groups allow you to specify servers of the same type ``` web1 ansible_ssh_host=192.168.56.20 db1 ansible_ssh_host=192.168.56.30 [webservers] web1 [dbservers] db1 [datacenter:children] webservers dbservers ``` ### Hierarchy of Groups ![Hierarchy of Groups](https://3437490578-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FIHriSm1GS8HhlboZIaAd%2Fuploads%2Fgit-blob-3d4ace88397f1b05d4f5f384c24fbc38d1c4ba5c%2Fansible-hierarchy-of-groups.png?alt=media) ## Playbooks * Ansible stores it’s instructions in files called "Playbooks" * Expressed in YAML language * Composed of one or more "plays" in a list * Allows for multi-machine deployment orchestration ## Playbook — Tasks * Are executed in the order they are specified against all machines that match the host pattern * May be included from other files * If a task fails, the remaining playbook are not executed for that host * Each task executes a module with specific options * Modules are idempotent in order to bring the system to a desired state ## Playbook — Handlers * Notifications may be triggered at the end of each block of tasks that modify the remote system * Handlers are referred to by name and can perform operations like restarting services that have had their configuration changed ```yaml tasks: - name: Create template configuration file template: src=template.j2 dest=/etc/httpd/httpd.conf notify: - restart apache handlers: - name: restart apache service: name=apache state=restarted ``` ### Example Playbook `python.yaml`: ```yaml --- - name: Performing Package Maintenance on All nodes hosts: all become: yes tasks: - name: Update and upgrade local packages apt: upgrade=full update_cache=yes - name: Installing Python development environment hosts: all become: yes tasks: - name: install required packages for Python using the apt module apt: package={{ item }} update_cache=yes with_items: - git - python-pip - python-dev - build-essential ``` ### Roles Based on a know file structure ``` site.yaml webservers.yaml roles/ webservers/ files/ templates/ tasks/ handlers/ vars/ defaults/ ``` `webservers.yaml`: ```yaml --- - hosts: webservers roles: - webservers ``` ### Vagrant Integration Ansible is supported by Vagrant so that you can use the same Ansible Playbooks to configure your local VM and remote servers ```ruby # # Run Ansible using the guest plugin # config.vm.provision :guest_ansible do |guest_ansible| guest_ansible.playbook = "python.yaml" guest_ansible.extra_vars = { user: "vagrant" } guest_ansible.sudo = true end ``` ### Example 1: LAMP STACK This will install Apache, MySQL, & PHP on Linux (LAMP) ```yaml ###################################################################### # LAMP Stack Example #1 ###################################################################### --- - hosts: webserver become: yes tasks: - name: Install MySQL server apt: name=mysql-server state=latest - name: Install Apache module for MySQL authentication apt: name=libapache2-mod-auth-mysql state=latest - name: Install MySQL module for PHP apt: name=php5-mysql state=latest ``` ### Example 2: Same LAMP STACK but better A better way would be to use the iteration of with\_items ```yaml ###################################################################### # LAMP Stack Example #2 ###################################################################### --- - hosts: webservers become: yes tasks: - name: install packages apt: name={{item}} state=latest update_cache=yes with_items: - mysql-server - libapache2-mod-auth-mysql - php5-mysql ``` # Overview | Course Code | CSCI-GA.2250-001 | | ----------- | -------------------- | | Professor | Hubertus Franke | | Email | | ## Grading A midterm and a final. 4 lab assignments. | Component | Weight | | -------------- | ------ | | Lab Assignment | 60% | | Midterm | 15% | | Final | 25% | # Introduction Kernel Structures and System Calls Operating systems turn ugly hardware into beautiful abstractions (arguable). ## The Operating System as a Resource Manager * Top down view: Provide abstractions to application programs * Bottom up view: Manage pieces of complex systems (hardware and events) * Alternative view: Provide orderly, controlled allocation of resources ## Two Main Tasks of OS * Provide programmers (and programs) a clean set of abstract resources and services to manipulate these resources * Manage the hardware resources ## Resources and Services Resources: Allocation, Protection, Reclamation and Virtualization Services: Abstraction, Simplification, Convenience and Standardization ### Operating System Short Explanation OS (kernel) is really just a program that runs with special privileges to implement the features of allocation, protection, reclamation and virtualization and the services that are structured on top of it. ## Booting Sequence * BIOS starts: checks how much RAM, keyboard, other basic devices * BIOS determines boot Device * The first sector in boot device is read into memory and executed to determine active partition * Secondary boot loader is loaded from that partition * This loaders loads the OS from the active partition and starts it. ## OS Services * Program development * Program execution * Access I/O devices * Controlled access to files * System access * Error detection and response * Accounting ## Operating System Jungle / Zoo * Mainframe operating systems * Server operating systems * Multiprocessor operating systems * Personal computer operating systems * Real-time operating systems * Embedded operating systems * Smart card operating systems * Cellphone/tablet operating systems * Sensor operating systems ## Processors Each CPU has a specific set of instructions, ISA (Instruction Set Architecture) largely epitomized in the assembler * RISC: Sparc, MIPS, PowerPC * CISC: x86, zSeries All CPUs contain: * **General registers**: inside to hold key variables and temporary results * **Special registers**: visible to the programmer * Program counter contains the memory address of the next instruction to be fetched * Stack pointer points to the top of the current stack in memory * PSW (Program Status Word) contains the condition code bits which are set by comparison instructions, the CPU priority, the mode (user or kernel) and various other control bits ### How Processors Work Execute instructions in CPU cycles. * Fetch(from mem) → decode → execute * Program counter (PC) * Pipeline: fetch n+2 while decode n+1 while execute n ### CPU Caches Principle: * Data/Instruction that were recently used are “likely” used again in short period * Caching is principle used in “many” subsystems ( I/O, filesystems, … ) \[ hardware and software] Cache hit: no need to access memory Cache miss: data obtained from mem, possibly update cache Issues: * Operation MUST be correct * Cache management for Memory done in hardware * Data can be in read state in multiple caches but only in one cache when in write state ## OS Major Components * Process and thread management * Resource management * CPU * Memory * Device (I/O) * File system * Bootstrapping ## Process: a running program A process includes: * Address space * Process table entries (state, registers): Open files, thread(s) state, resources field A process tree: * A created two child processes, B and C * B created three child processes, D, E and F ``` A / \ B C / | \ D E F ``` ## Address Space * Defines where sections of data and code are located in 32 or 64 address space. * Defines protection of such sections: ReadOnly, ReadWrite, Execute * Confined "private" addressing concept: requires form of address virtualization ![Address Space Example](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-2b2d5da10bfde542f15ecc2f66e8058c61f52aaa%2Faddress-space.png?alt=media) ## CPU Execution Modes Two modes of CPU: * **Kernel mode** (all instructions) aka privileged / supervisor mode * **User mode** (a subset of instructions) aka unprivileged / problem mode: limits (\~excludes) user from accessing critical resources How to switch between the two modes: * UserMode → KernelMode * Trap * Interrupt (also Kernel2Kernel) * Exception (also Kernel2Kernel) * KernelMode → UserMode * rfi (return from interrupt, also Kernel2Kernel) ### Interrupt / Exception / Trap * Interrupts: **asynchronously** triggered by an event from a "device" (device needs attention) * Exceptions: **synchronously** triggered by a "fault condition" of an instruction condition * Traps (instruction, aka sc \[system call], special kind of exception): **synchronously** triggered by "trap instruction" for syscall They all end up in the so called "interrupt handler": > `__entry` is the **ONLY** means to enter into the operating system kernel. Either by > > * hw-interrupt > * exception > * trap * assembler code aka `__entry` in the kernel * from there the assembler identifies whether an interrupt, exception, or trap and jumps to their respective handlers. * Protected Hardware register is initialized in OS bootstrap with the address of `__entry` so the hardware knows where to jump to when an Interrupt or Trap or Exception is raised. ## System Calls * Invoked via non-privileged instruction (trap / sc): Treated often like an interrupt, but its "somewhat" different * Synchronous transfer control from user to kernel * Side-effect of executing a trap in userspace is that an “exception” is raised and program execution continues at a prescribed instruction in the kernel see `__entry` -> syscall\_handler ### Service Requests from user to kernel (OS) = System Calls * Basic means to request services from the operating system kernel is to make **system calls** (which end up in a “trap / sc” event) * It’s a well architected and “secure” API between kernel and userspace ### How are syscalls implemented * First one has to understand how arguments in any regular function call are passed. * For this a **calling code convention** is defined. * Typically arguments are passed through registers (sometimes as offsets on the stack) * Those registers can be modified by the function called, any other registers most be saved and restored by the callee function: Volatile register (args,stackptr) and non-volative registers (callee must save and restore) * Generally referred to as ABI: **Application Binary Interface** * Syscalls are simply an extension on this. All compilers need to agree on this or code will no cooperate/work. #### User Side syscall is implemented as assembler largely taking the arguments already in the right registers and TRAP-ing into the kernel. #### Kernel Side * Kernel defines a table (using the compiler help) * On system trap, architecture automatically and immediately enters kernel mode and runs a small piece of assembler code that is stored at a machine register address set by the OS at boot time. * Said trap assembler code (aka interrupt handler) does the following: * Checks the syscall number in well known register (see ABI) to be in range * Assembler equivalent: * Change stack to kernel (more on this in a bit) * All arguments are already in right place thanks to the ABI and the compiler’s help - * `call/jmp` to `syscall_table[registers.syscall_number]; // see ABI definition` * After return from ^^^^, switch back from kernel stack to user stack and RFI (return from kernel mode). ## Other Implicit/Explicit OS Services Examples Services that can be provided at user level (because they only read unprotected data): * Read time of the day Services that need to be provided at kernel level: * System calls: file open, close, read and write * Control the CPU so that users won’t stuck by running `while ( 1 );` * Protection: * Keep user programs from crashing OS * Keep user programs from crashing each other ## Criteria to Evaluate OS * Portability * Security * Fairness * Robustness * Efficiency * Interfaces Not all of these can be satisfied at the same time. # Processes and Threads A "processor" can only run one unit of execution (process/thread) at a time. The processor is switched (context switch) among multiple applications so all will appear to be progressing (albeit potentially at reduced speed). The processor and I/O devices can be used efficiently: When application performs I/O, the processor can be used for a different application. ## What is a process? An abstraction of a running program. ### The Process Model * A process has a program, input, output, and state (data). * A process is an instance of an executing program and includes * Variables ( memory ) * Code * Program counter ( really hardware resource) * Registers * ... ### Process: a running program A process includes: * Address space * Process table entries (state, registers): Open files, thread(s) state, resources field A process tree: * A created two child processes, B and C * B created three child processes, D, E and F ``` A / \ B C / | \ D E F ``` ### Address Space * Defines where sections of data and code are located in 32 or 64 address space. * Defines protection of such sections: ReadOnly, ReadWrite, Execute * Confined "private" addressing concept: requires form of address virtualization ![Address Space Example](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-2b2d5da10bfde542f15ecc2f66e8058c61f52aaa%2Faddress-space.png?alt=media) ### Process Creation * System initialization * At boot time * Foreground * Background (daemons) * Execution of a process creation system call by a running process * A user request * A batch job * Created by OS to provide a service * Interactive login ### Process Termination * Normal exit (voluntary) * Error exit (voluntary) * Fatal error (involuntary) * Killed by another process (involuntary) ## Implementation of Processes * OS maintains a process table `Process procs[];` * An array (or a hash table) of structures * One entry per process (pid is the uniq id) ## Implementation of Processes: Process Control Block (PCB) * Contains the process elements * It is possible to interrupt a running process and later resume execution as if the interrupt had not occurred → state * Created and managed by the operating system * Key tool that allows support for multiple processes Includes: Identifier, state, priority, program counter, memory pointers, context data, I/O status information and accounting information. ## Fork Creation of a new process by `fork()`. Executing a program in that new process. Signal notifications. The kernel boot manually creates ONE process (the init process, pid=0) and all other processes are created by `fork()`. ### `fork()` ```c #include #include int main(int argc, char **argv) { pid_t pid = fork(); // syscall that creates new PCB and duplicates Address Space if (pid == 0) { // child process } else if (pid > 0) { // parent process } else { // fork failed printf("fork() failed!\n"); return 1; } } ``` ### `execv()` The `exec()` family of functions replaces the current process image with a new process image. ## Process State Model: Five-State Model ![Process Five State Model](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-1958a911d841e18f61f39829e0fa2a63b3ac799e%2Fprocess-five-state-model.png?alt=media) ### Using Queues to Manage Processes ![Single blocked queue](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-af7a11128949d7a4911722fb2cbe85ab7b05853c%2Fusing-queues-to-manage-processes.png?alt=media) ![Multiple blocked queues](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-611b89c2852039603ab78a20608aeae64d7f0074%2Fusing-queues-to-manage-processes-multiple.png?alt=media) ## Multiprogramming * One CPU and several processes * CPU switches from process to process quickly Running the same program several times will not result in the same execution times due to: * interrupts * multi-programming ## Concurrency vs. Parallelism * Concurrency is when two or more tasks can start, run, and complete in overlapping time periods. It doesn't necessarily mean they'll ever both be running at the same instant. For example, multitasking on a single-core machine. * Parallelism is when tasks literally run at the same time, e.g., on a multicore processor. ## Threads * Multiple threads of control within a process: unique execution * All threads of a process share the same address space and resources (with exception of stack) ### Why Threads? * For some applications many activities can happen at once: * With threads, programming becomes easier * Otherwise application needs to actively manage different logical executions in the process * This requires significant state management * Benefit applications with I/O and processing that can overlap * Lighter weight than processes * Can be used to implement concurrency * Faster to create and restore: we just really need a stack and an execution unit, but don't have to create new address space etc. ### Processes vs. Threads * Process groups resources: Address Space, files * Threads are entities scheduled for execution on CPU * Threads can be in any of several states: running, blocked, ready, and terminated (remember the process state model?) * No protections among threads (unlike processes) \[Why?] → this is important * The unit of dispatching is referred to as a thread or lightweight process (lwp) * The unit of resource ownership is referred to as a process or task (unfortunately in linux struct task represents both a process and thread) * Multithreading: The ability of an OS to support multiple, concurrent paths of execution within a single process * Process is the unit for resource allocation and a unit of protection. * Process has its own (one) address space. * A thread has: * an execution state (Running, Ready, etc.) * saved thread context when not running * an execution stack * some per-thread static storage for local variables * access to the memory and resources of its process (all threads of a process share this) ## Kernel-Level Threads (KLTs) Thread management is done by the kernel. No thread management is done by the application. Advantages: * The kernel can simultaneously schedule multiple threads from the same process on multiple processors * If one thread in a process is blocked, the kernel can schedule another thread of the same process * Kernel routines can be multithreaded Disadvantages: * The transfer of control from one thread to another within the same process requires a mode switch to the kernel ## Implementing Threads in Kernel Space * Kernel knows about and manages the threads * No runtime is needed in each process * Creating/destroying/(other thread related operations) a thread involves a system call Advantages: * When a thread blocks (due to page fault or blocking system calls) the OS can execute another thread from the same process Disadvantages: * Scalability (operating systems had limited memory dedicated to them) * ~~Cost of system call is very high~~ (Disagree because if you want to implement interruption to do thread scheduling you have to use `signal(SIGVTALARM)` which is much more expensive.) ## User-Level Threads (ULTs) * All thread management is done by the application * Initially developed to run on kernels that are not multithreading capable * The kernel is not aware of the existence of threads ### Implementing Threads in User Space * Threads are implemented by a library * Kernel knows nothing about threads * Each process needs its own private thread table in userspace * Thread table is managed by the runtime system ### Advantages * Thread switch does not require kernel-mode * Scheduling (of threads) can be application specific * Can run on any OS * Scales better ### Disadvantages * A system-call by one thread can block all threads of that process * Page fault blocks the whole process * In pure ULT, multithreading cannot take advantage of multiprocessing ## PCB vs. TCB Process Control Block handles global process resources. Thread Control Block handles thread execution resources. | Per process items | Per thread items | | --------------------------- | ---------------- | | Address space | Program counter | | Global variables | Registers | | Open files | Stack | | Child processes | State | | Pending alarms | | | Signals and signal handlers | | | Accounting information | | ## 1:1, M:1, M:N Thread Models are also knows as general ratio of user threads over kernels threads * 1:1: each user thread == kernel thread * M:1: user level thread mode * M:N: hybrid model ## Context Switch Scenarios: * Current process (or thread) blocks *OR* * Preemption Operations to be done: * Must release CPU resources (registers) * Requires storing "all" non provileged registers to the PCB or TCB save area * Tricky as you need registers to do this * All written in assembler * Typically an architecture has a few privileged registers so the kernel can accomplish this # Scheduling Whether scheduling is based on processes or threads depends on whether the OS is multi-threading capable: Given a group of ready processes or threads, which process/thread to run? ## When to schedule? * When a process is created * When a process exits * When a process blocks * When an I/O interrupt occurs ## Categories of Scheduling Algorithms * Interactive: preemption is essential, preemption is a means ofr the OS to take away the CPU from a currently running process/thread * Batch: * No user impatiently waiting * mostly non-preemptive, or preemptive with long period for each process * Real-time: deadlines ### Scheduling Algorithms: Goals and Measures * Turn Around Time (Batch) * Throughput (e.g. Jobs per second) * Response Time (Interactive) * Average wait times (how long waiting in ready queue) ## CPU / IO Burst **CPU Burst**: a sequence of instructions a process runs without requesting I/O. Mostly dependent on the program behavior. **IO "Burst"**: time required to satisfy an IO request while the Process can not run any code. Mostly dependent on system behavior (how many other IOs, speed of device, etc.) ## Scheduling Algorithms Goals All systems * Fairness: giving each process a fair share of the CPU * Policy enforcement: seeing that stated policy is carried out * Balance: keeping all parts of the system busy Batch systems * Throughput: maximize jobs per hour * Turnaround time: minimize time between submission and termination * CPU utilization: keep the CPU busy all the time Interactive systems * Response time: respond to requests quickly * Proportionality: meet users'expectations Real-time systems * Meeting deadlines: avoid losing data * Predictability: avoid quality degradation in multimedia systems ## Process State Transition Almost ALL scheduling algorithms can be described by the following process state transition diagram or a derivative of it (we covered some more sophisticated one in prior lecture) ![Process State Transition](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-76f5e3252a6108cdb4069f044169f8f4b58acdc3%2Fprocess-state-transition.png?alt=media) ## Scheduling Algorithms ### First Come First Serve (FIFO / FCFS) Non-preemptive (run till I/O or exit). Processes ordered as queue: A new process is added to the end of the queue. A blocked process that becomes ready added to the end of the queue Main disadvantage: Can hurt I/O bound processes or processes with frequent I/O ### Shortest Job First Non-preemptive. Assumes runtime is known in advance. Is only optimal when all the jobs are available simultaneously. ### Shortest Remaining Time First/Next (SRTF) Scheduler always chooses the process whose remaining time is the shortest. Runtime has to be known in advance. Preemptive or non-preemptive (wait till block or done) This typically reduces average turnaround time. ### Round Robin Each process is assigned a time interval referred to as quantum. After the quantum, the CPU is given to another process (i.e. CPU is removed from the process/thread aka preemption). RR = FIFO + preemption/quantum Length of the quantum * If too short, too many context switches will result in lower CPU efficiency * If too long, will cause poor response to short interactive * quantum longer than CPU burst is good ### Priority Scheduling Each process is assigned a priority. Runnable process with the highest priority is allowed to run. Priorities are assigned statically or dynamically. Must not allow a process to run forever: * Can decrease the priority of the currently running process * Use time quantum for each process ### Multiple Level Queuing (MLQ) Multiple levels of priority (MLQ) plus each level is run round-robin. Issue: starvation if higher priorities have ALWAYS something to run ### Multi-Level Feedback Queueing (MLFQ) Aka priority decay scheduler. If process has to be preempted, moves to (`dynamic_priority--`). When it reaches "-1", dynamic priority is reset to (`static_priority-1`): This creates some issues when high prio is reset before low prio is executing. When a process is made ready (from blocked): its dynamic priority is reset to (`static_priority-1`). What kind of process should be in bottom queue? * Higher priority for IO-Bound tasks * Lower priority for CPU-Bound tasks ### Comparisons | Algorithm | Advantages | Disadvantages | | ----------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | First Come First Serve (FCFS) |
  • FCFS algorithm doesn't include any complex logic, it just puts the process requests in a queue and executes it one by one.
  • Hence, FCFS is pretty simple and easy to implement.
  • Eventually, every process will get a chance to run, so starvation doesn't occur.
|
  • There is no option for pre-emption of a process. If a process is started, then CPU executes the process until it ends.
  • Because there is no pre-emption, if a process executes for a long time, the processes in the back of the queue will have to wait for a long time before they get a chance to be executed.
| | Shortest Job First (SJF) |
  • Each process is served by the CPU for a fixed time quantum, so all processes are given the same priority.
  • Starvation doesn't occur because for each round robin cycle, every process is given a fixed time to execute. No process is left behind.
|
  • The throughput in RR largely depends on the choice of the length of the time quantum. If time quantum is longer than needed, it tends to exhibit the same behavior as FCFS.
  • If time quantum is shorter than needed, the number of times that CPU switches from one process to another process, increases. This leads to decrease in CPU efficiency.
| | Priority based Scheduling |
  • The priority of a process can be selected based on memory requirement, time requirement or user preference. For example, a high end game will have better graphics, that means the process which updates the screen in a game will have higher priority so as to achieve better graphics performance.
|
  • A second scheduling algorithm is required to schedule the processes which have same priority.
  • In preemptive priority scheduling, a higher priority process can execute ahead of an already executing lower priority process. If lower priority process keeps waiting for higher priority processes, starvation occurs.
| ### Usage of Scheduling Algorithms in Different Situations #### Situation 1: The incoming processes are short and there is no need for the processes to execute in a specific order. In this case, FCFS works best when compared to SJF and RR because the processes are short which means that no process will wait for a longer time. When each process is executed one by one, every process will be executed eventually. #### Situation 2: The processes are a mix of long and short processes and the task will only be completed if all the processes are executed successfully in a given time. Round Robin scheduling works efficiently here because it does not cause starvation and also gives equal time quantum for each process. #### Situation 3: The processes are a mix of user based and kernel based processes. Priority based scheduling works efficiently in this case because generally kernel based processes have higher priority when compared to user based processes. For example, the scheduler itself is a kernel based process, it should run first so that it can schedule other processes. ## Load Balancing (LB) Occasionally or when no process is runnable, scheduler\[i] looks to steal work elsewhere. Each scheduler maintains a load average and history to determine stability of its load. LB typically done in a hierarchy. Frequency of neighbor check: * Level in hierarchy: cost to migrate * Make "small" changes by pulling work from other cpu # Concurrency Concurrency & Deadlocks ## Inter-Process Communication (IPC) Processes often need to work together or at the very least share resources. ### Issues * Send information * Mitigate contentions(disagreements) over resources * Synchronize dependencies ### Race Condition Race condition is a condition where the behavior(result) of the system depends on exact order of processes running. E.g. Two processes want to access shared memory at the same time: Read is typically not an issue but write or conditional execution IS. ## Intra-Process Communication Threads often need to work together and access resources (e.g. memory) in the common address space. ### Same Issues * Send information * Mitigate contentions(disagreements) over resources * Synchronize dependencies Example: Multi-threaded Webserver * Dispatcher thread deposits work into queue of requests to be processed * Worker threads will pick work from the queue ## Read-Modify-Write Cycles Read-Modify-Write cycles are typically an issue. For instance, you read a variable, make a decision and modify the variable. Examples: ```c if (var == 0) { /* do something */ var = 1; } ``` ```c if (var == 0) { var = 1; /* do something */ } ``` ``` ldw r3, @var cmpwi r3, 0 bne L1 stwi @var, 1 /* some code */ ``` These examples will have problems if the same code is executed by two threads concurrently. Consider the race and preemption case with 2 threads. So, expectation is that code has "consistent view" at data. ## Critical Region / Section Critical section / region is a protected section that accesses a shared resource, which can only executed by at most one process at a time. **Mutual Exclusion**: Only one process (thread) at a time can access any shared variables, memory or resources. ### Four conditions to prevent errors 1. No two processes simultaneously in critical region 2. No assumptions made about speeds or numbers of CPUs 3. No process running outside its critical region may block another process 4. No process must wait forever to enter its critical region ### Mutual Exclusion with Busy Waiting #### Simple solution: Disable interrupt Problems: * Disabling interrupt for user program would be too much privilege * Won't work in SMP (multi-core systems) #### Solution: Use lock variable If the value of the lock variable is 0, then process sets it to 1 and enters. Other processes have to wait. Problem: [Read-Modify-Write cycles](#read-modify-write-cycles) ### Peterson's Solution Mathematically correct but not practical, cannot be efficiently implemented. ```cpp #define FALSE 0 #define TRUE 1 #define N 2 // number of processes int turn = 0; // whose turn is it? int interested[N]; // all values initially 0 void enter_region(int process) { // process is 0 or 1 int other = 1 - process; // the other process interested[process] = TRUE; // show that you are interested turn = process; // set flag while (turn == process && interested[other] == TRUE) { /* busy wait */ } } void leave_region(int process) { // process: who is leaving interested[process] = FALSE; // indicate departure from critical region } ``` ### The TSL Instruction (Test and Set Lock) With a "little help" from hardware: the test and set instruction is used to write(set) 1 to a memory location and return its old value as a single atomic (non-interruptible) operation. This is implemented by locking the bus. ``` enter_region: TSL REGISTER, LOCK | copy lock to register and set lock to 1 CMP REGISTER, #0 | was lock 0? JNE enter_region | if not, loop RET | return to caller; critical region entered leave_region: MOVE LOCK, #0 | set lock to 0 RET | return to caller ``` ### The XCHG Instruction (cmp\_and\_swap) This is also implemented by locking the bus. ``` enter_region: MOVE REGISTER, #1 | put a 1 in the register XCHG REGISTER, LOCK | swap the contents of the register and lock variable CMP REGISTER, #0 | was lock 0? JNE enter_region | if not, loop RET | return to caller; critical region entered leave_region: MOVE LOCK, #0 | set lock to 0 RET | return to caller ``` ### Load / Store Conditional Modern processors resolve cmp\_and\_swap through the cache coherency mechanism. Reservation (`ldwx`) remembers ONE address on a CPU and verifies on (`stwx`) whether still held otherwise store will fail. ``` L1: ldwx r3, @lockvar // load r3 and set reservation register on CPU with &lockvar add r3, r3, #1 // increment r3 stwx r3, @lockvar // store r3 back to lockvar only if reservation still held bcond L1 // if store conditionally failed, loop ``` Reservation is lost on: 1. interrupts 2. if another CPU steals cacheline holding `lockvar` 3. if another `lwdx` is issued. ### Comparisons Both TSL (xchg/cmpswp) and Peterson's solution are correct, but they: * rely on busy-waiting during "contention" * waste CPU cycles (one way to circumvent this is by calling thread\_yield to voluntarily give up the CPU and upon rescheduling it will attempt again) * [Priority Inversion problem](#priority-inversion-problem) ### Priority Inversion Problem Higher priority process can be prevented from entering a critical section (CS) because the lock variable is dependent on a lower priority process. ## Lock Contention **Lock Contention** arises when a process/thread attempts to acquire a lock and the lock is not available. This is a function of (is related to): * frequency of attempts to acquire the lock * lock hold time (time between acquisition and release) * number of threads/processes acquiring a lock If lock contention is low, [TSL](#the-tsl-instruction-test-and-set-lock) is an OK solution. The linux kernel uses it extensively for many locking scenarios. ## Concurrency vs Parallelism **Concurrency** is having multiple contexts of execution not necessarily running at the exact same time. **Parallelism** is having multiple contexts of execution running at the exact same time. ## Producer-Consumer Problem ### Example: Piping `ls -ls | grep "yooh" | awk '{print $1}'` #### Responsibility of a Pipe * Provide Buffer to store data from stdout of Producer and release it to stdin of Consumer * Block Producer when the buffer is full (because consumer has not consumed data) * Block Consumer if no data in buffer when the consumer wants to read (stdin) * Unblock Producer when buffer space becomes free * Unblock Consumer when buffer data becomes available #### Pipes Pipes are not just for stdin and stdout. They can be created by applications used for all kinds of things. PipeBuffer typically has 16 write slots. 4KB guaranteed to be atomic. #### Race Condition ```cpp #define N 100 int count = 0; void producer() { int item = produce_item(); // generate next item if (count == N) sleep(); // if buffer is full, go to sleep insert_item(item); // put item in buffer count = count + 1; // increment count of items in buffer if (count == 1) wakeup(consumer); // was buffer empty? } void consumer() { if (count == 0) sleep(); // if buffer is empty, go to sleep int item = remove_item(); // take item out of buffer count = count - 1; // decrement count of items in buffer if (count == N - 1) wakeup(producer); // was buffer full? consume_item(item); // consume/print item } ``` Fatal race condition in this example: 1. Let count = 1 2. Consumer begins loop, decrements count == 0 3. COnsumer returns to loop beginning and executes: `if (count == 0)`, then preemption happens 4. Producer gets to run, executes `count = count + 1; if (count == 1)` and calls `wakeup(consumer)` 5. Preemption Consumer calls `sleep(consumer)` #### Requirements * Need a mechanism that allows synchronization between processes/threads on the base of shared resources. * Synchronization implies interaction with scheduling subsystem. * Let to the innovation of semaphores. ## Semaphore ### Semaphore Data Structure ```cpp class Semaphore { int value; // counter Queue waiting; // queue of threads waiting on semaphore void Init(int v); // initialization void P(); // acquiring the semaphore: down(), wait() void V(); // release the semaphore: up(), signal() } ``` Implementation: ```cpp void Semaphore::Init(int v) { value = v; waiting = Queue.init(); // initialize empty queue } void Semaphore::P() { value = value - 1; if (value < 0) { waiting.add(current_thread); current_thread.status = BLOCKED; schedule(); // forces wait, thread blocked } } void Semaphore::V() { value = value + 1; if (value <= 0) { Thread *thd = waiting.getNextThread(); scheduler->add(thd); // make it schedulable } } ``` ### How do P and V avoid race condition? `P()` and `V()` must be **atomic**. #### Solution: By disabling interruptions First line of `P()` and `V()` can disable interrupts. Last line of `P()` and `V()` re-enables interrupts. However, disabling interrupts only works on **single CPU systems**. #### Solution: Use atomic lock variable ```cpp class Semaphore { int lockvar; // to guarantee atomicity int value; // counter Queue waiting; // queue of threads waiting on semaphore void Init(int v); // initialization void P(); // acquiring the semaphore: down(), wait() void V(); // release the semaphore: up(), signal() } ``` New implementation: ```cpp void Semaphore::P() { lock(&lockvar); // + value = value - 1; if (value < 0) { waiting.add(current_thread); current_thread.status = BLOCKED; unlock(&lockvar); // + schedule(); // forces wait, thread blocked } else { unlock(&lockvar); // + } } void Semaphore::V() { lock(&lockvar); // + value = value + 1; if (value <= 0) { Thread *thd = waiting.getNextThread(); scheduler->add(thd); // make it schedulable } unlock(&lockvar); // + } ``` ### Two kinds of semaphores: Mutex and Counting **Mutex semaphores** or **binary semaphores** or simply LOCK is for mutual exclusion problems: value initialized to 1. **Counting semaphores** is for synchronization problems: value initialized to any value 0..N. Value shows available tokens to enter or number of processes waiting when negative. They are of same implementation, just different initial values. ### Semaphore Solution to the Producer-Consumer Problem 3 semaphores (minimal) example: ```cpp #define N Semaphore empty = N; Semaphore full = 0; Semaphore mutex = 1; T buffer[N]; int widx = 0, ridx = 0; Producer(T item) { P(&empty); P(&mutex); // Lock buffer[widx] = item; widx = (widx + 1) % N; V(&mutex); // Unlock V(&full); } Consumer(T &item) { P(&full); P(&mutex); // Lock item = buffer[ridx]; ridx = (ridx + 1) % N; V(&mutex); // Unlock V(&empty); } ``` 4 semaphores for lower lock contention: ```cpp #define N Semaphore empty = N; Semaphore full = 0; Semaphore mutex_w = 1; Semaphore mutex_r = 1; T buffer[N]; int widx = 0, ridx = 0; Producer(T item) { P(&empty); P(&mutex_w); // Lock buffer[widx] = item; widx = (widx + 1) % N; V(&mutex_w); // Unlock V(&full); } Consumer(T &item) { P(&full); P(&mutex_r); // Lock item = buffer[ridx]; ridx = (ridx + 1) % N; V(&mutex_r); // Unlock V(&empty); } ``` Using two mutexes for read and write makes it possible for producer and consumer to be more concurrent (they should not be competing), thus less lock contention. ## Mutexes in Pthreads Some of the Pthreads calls relating to mutexes are: | Thread call | Description | | ----------------------- | ------------------------- | | Pthread\_mutex\_init | Create a mutex | | Pthread\_mutex\_destroy | Destroy an existing mutex | | Pthread\_mutex\_lock | Acquire a lock or block | | Pthread\_mutex\_trylock | Acquire a lock or fail | | Pthread\_mutex\_unlock | Release a lock | Some of the Pthreads calls relating to condition variables are: | Thread call | Description | | ------------------------ | -------------------------------------------- | | Pthread\_cond\_init | Create a condition variable | | Pthread\_cond\_destroy | Destroy a condition variable | | Pthread\_cond\_wait | Block waiting for a signal | | Pthread\_cond\_signal | Signal another thread and wake it up | | Pthread\_cond\_broadcast | Signal multiple threads and wake all of them | P: wait, V: signal ### Using threads to solve the producer-consumer problem ```cpp #include #include #define MAX 1000000000 // how many numbers to product pthread_mutex_t the_mutex; pthread_cond_t condc, condp; int buffer = 0; // buffer used between producer and consumer void *producer(void *ptr) // produce data { int i; for (i = 0; i < MAX; i++) { pthread_mutex_lock(&the_mutex); // get exclusive access to buffer while (buffer != 0) { pthread_cond_wait(&condp, &the_mutex); } buffer = i; // put item in buffer pthread_cond_signal(&condc); // wake up consumer pthread_mutex_unlock(&the_mutex); // release access to buffer } pthread_exit(0); } void *consumer(void *ptr) // consume data { int i; for (i = 0; i < MAX; i++) { pthread_mutex_lock(&the_mutex); // get exclusive access to buffer while (buffer == 0) { pthread_cond_wait(&condc, &the_mutex); } printf("%d\n", buffer); // consume item from buffer buffer = 0; // take item out of buffer pthread_cond_signal(&condp); // wake up producer pthread_mutex_unlock(&the_mutex); // release access to buffer } pthread_exit(0); } int main(int argc, char **argv) { pthread_t pro, con; pthread_mutex_init(&the_mutex, 0); pthread_cond_init(&condc, 0); pthread_cond_init(&condp, 0); pthread_create(&con, 0, consumer, 0); pthread_create(&pro, 0, producer, 0); pthread_join(pro, 0); pthread_join(con, 0); pthread_cond_destroy(&condc); pthread_cond_destroy(&condp); pthread_mutex_destroy(&the_mutex); } ``` ## Problems with Semaphores * It can be difficult to write semaphores code (arguably) * One has to be careful with the code construction * If a thread dies and it holds a semaphore, the implicit token is lost ## Some Advice for Locks * **Always** acquire multiple locks in the same order * Preferably release in reverse order as acquired: not required but good hygiene (Lots of discussion on this, there are scenarios where that is not desired but highly optimized implementation) * Example: SMP CPU scheduler where load balancing is required. ### Example: SMP Scheduler #### Deadlock example ```cpp Schedule(int i) { lock(rqlock[i]); { // load balance with j lock(rqlock[j]); // pull some threads from j to i unlock(rqlock[j]); } unlock(rqlock[i]); } ``` Consider situation: `cpu0 (i=0, j=1)` and `cpu1 (i=1, j=0)`, this can lead to deadlocks -> must use same order instead #### Force order solution We force the correct order. If necessary, we release owned lock first and re-acquire. ```cpp Schedule(int i) { lock(rqlock[i]); { // load balance with j add_lock(i, j); // pull some threads from j to i unlock(rqlock[j]); } unlock(rqlock[i]); } void add_lock(int hlv, int alv) // hlv: holding lock, alv: acquiring lock { if (hlv > alv) { // could be "<" or based on addresses, doesn't matter // first unlock hlv unlock(rqlock[hlv]); lock(rqlock[alv]); // then lock hlv lock(rqlock[hlv]); } else { lock(rqlock[alv]); } } ``` ## Busy Lock vs Semaphore If lock hold time is short and/or code is uninterruptible, then lock variables and busy waiting is OK (linux kernel uses it all the time). Otherwise, use semaphores. ## Other Unix/Linux Mechanisms * File based: flock() * System V semaphores: heavy weight as each call is a system call going into the kernel. semget(), semop() \[P and V] * Futexes: lighter weight as uncontested cases are resolved done using cmpxchg in userspace and if race condition is recognized it goes into kernel. futex() * Message queues mq\_open(), mq\_close(), mq\_send(), mq\_receive() ## Monitors Hoare and Brinch Hansen proposed a higher-level synchronization primitive: monitor. * Only ONE thread allowed inside the Monitor * Compiler achieves Mutual Exclusion * Monitor is a programming language construct like a class or a for-loop We still need a way to synchronize on events: * Condition variables: wait & signal * Not counters: signaling with no one waiting -> event lost * Waiting on signal releases the monitor and wakeup reacquires it ### Monitor Example ``` monitor example integer i; condition c; procedure producer(); (* ... *) end; procedure consumer(); (* ... *) end; end monitor; ``` ### Producer-Consumer Problem with Monitor ``` monitor ProducerConsumer condition full, empty; integer count; procedure insert(item: integer); begin if count = N then wait(full); insert_item(item); count := count + 1; if count = 1 then signal(empty); end; function remove: integer; begin if count = 0 then wait(empty); remove:= remove_item(); count := count - 1; if count = N-1 then signal(full); end; count := 0; end monitor; ``` ## Message Passing When there's no shared memory (e.g. on distributed systems), we can send LAN messages instead. `send(destination, &message);` `send(destination, &message);` ### Producer-Consumer Problem with Message Passing ```cpp #define N 100 // number of slots in the buffer void producer(void) { int item; message m; // message buffer while(TRUE) { item = produce_item(); // generate something to put in buffer receive(consumer, &m); // wait for an empty to arrive build_message(&m, item); // construct a message to send send(consumer, &m); // send item to consumer } } void consumer(void) { int item, i; message m; for (i = 0; i < N; i++) send(producer, &m); // send N empty messages while(TRUE) { receive(producer, &m); // get message containing item item = extract_item(&m); // extract item from message send(producer, &m); // send back empty reply consume_item(item); // consume item } } ``` ### Message Passing Issues * Guard against lost messages (acknowledgement) * Authentication (guard against imposters) Addressing: * To processes * Via Mailbox (place to buffer messages) * Send to a full mailbox means block * Receive from an empty mailbox means block ### What about buffer-less messages? Send and Receive wait (block) for each other to be ready to talk: rendezvous (meet at an agreed time and place) ## Barriers A barrier for a group of threads or processes means any thread/process must stop at this point and cannot proceed until all other threads/processes reach this barrier. Three possible states: 1. Processes approaching a barrier 2. All processes but one blocked at the barrier 3. When the last process arrives at the barrier, all of them are let through ## Deadlocks A deadlock is a state in which each member of a group waits for another member, including itself, to take action. It occurs among processes/threads who need to acquire resources in order to progress. A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Assumptions: * If a process is denied a resource, it is put to sleep * Only single-threaded processes * No interrupts possible to wake up a blocked process ### Deadlock vs Starvation **Deadlock**: Process(es) waiting on events (resources) that will never happen. Can be system wide or just one process. **Starvation**: Process(es) waiting for its turn but never comes. Process could move forward, the resource or event might become available but this process may not be able to get access to it. Such starvation is usually caused by certain policy. For example, a printing policy may always choose to print the smallest file available. Then now one process shows up with HUGE file. This process will not likely get to run if there's steady stream of smaller file jobs coming in. ### Resources Resources are anything that must be acquired, used and released over the course of time. Could be hardware or software resources. #### Preemptable and non-preemptable resources * **Preemptable**: can be taken away from the process with no ill-effect * **Non-preemptable**: cannot be taken away from the process without causing the computation to fail #### Reusable and Consumable resources * **Reusable**: can be safely used by only one process at a time and is not depleted by that use. e.g. processors, I/O devices, main and secondary memory, devices, and data structures such as files, databases and semaphores. * **Consumable**: one that can be created (produced) and destroyed (consumed). e.g. interrupts, signals, messages and information in I/O buffers. ### Conditions for Resource Deadlocks 1. Each resource is either currently assigned to exactly one process or is available 2. Processes currently holding resources that were granted earlier can request new resources 3. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them. 4. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain. ### Resource Allocation Graph ![Resource Allocation Graph](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-a1302da5e7d6d1c1ff8afc1b21e85738212144fc%2Fresource-allocation-graph.png?alt=media) ## How to Deal with Deadlocks 1. Just ignore the problem. 2. Let deadlocks occur, detect them, and take action. 3. Dynamic avoidance by careful resource allocation. 4. Prevention, by structurally negating one of the [four required conditions](#conditions-for-resource-deadlocks). ### The Ostrich Algorithm The ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare. It is used when it is more cost-effective to allow the problem to occur than to attempt its prevention. ## Deadlock Detection The system does not attempt to prevent deadlocks. It tries to detect it when it happens. Then it takes some actions to recover. Several issues here: * Deadlock detection with one resource of each type * Deadlock detection with multiple resources of each type * Recovery from deadlock ### Deadlock Detection: One Resource of Each Type Construct a resource graph. If it contains one ore more cycles, a deadlock exists. ### Formal Algorithm to Detect Cycles in the Allocation Graph For each node N in the graph do: 1. Initialize L to empty list and designate all arcs as unmarked 2. Add the current node to end of L. If the node appears in L twice then we have a cycle and the algorithm terminates 3. From the given node, pick any unmarked outgoing arc. If none is available, go to 5. 4. Pick an outgoing arc at random and mark it. Then follow it to the new current node and go to 2. 5. If the node is the initial node, then no cycles found and the algorithm terminates; Otherwise, we are in dead end. Remove that node and go back to the previous one. Go to 2. ### When to check for deadlocks? * Check every time a resource request is made * Check every k minutes * When CPU utilization has dropped below a threshold ## Recovery from Deadlock We have detected a deadlock, what next? We have some options: Recovery through preemption, recovery through rollback and recovery through killing process. ### Recovery Through Preemption Temporary take a resource away from its owner and give it to another process. Manual intervention may be required (e.g. in case of printer) Highly dependent on the nature of the resource. Recovering this way is frequently impossible. ### Recovery Through Rollback Have processes **checkpointed** periodically. **Checkpoint** of a process: its state is written to a file so that it can be restarted later. In case of deadlock, a process that owns a needed resource is rolled back to the point before it acquired that resource. ### Recovery Through Killing Process Kill a process in the cycle. Can be repeated (i.e. kill other processes) until deadlock is resolved. The victim can also be a process NOT in the cycle. ## Deadlock Avoidance In most systems, resources are requested one at a time. Resource is granted only if it is **safe** to do so. ### Safe and Unsafe States A **state** is said to be **safe** if there is one scheduling order in which every process can run to completion even if all of theme suddenly request their maximum number of resources immediately. An **unsafe** state is NOT a deadlock state. For example, assume a total of 10 instances of the resources available: ![Safe states example](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-0613a0c87c934e6fea399610cccfc6e48e257c30%2Fsafe-and-unsafe-states-example.png?alt=media) ### The Banker's Algorithm The algorithm checks if granting the request leads to an unsafe state. If it does, the request is denied. #### The main idea The algorithm checks to see if it has enough resources to satisfy some customers. If so, the process closest to the limit is assumed to be done and resources are back, and so on. If all loans (resources) can eventually be repaid, the state is safe. ### Example ![Banker's Algorithm Example](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-b1f8e8564edcd550956ddefdf78acd843bffabf6%2Fbankers-algorithm-example.png?alt=media) ### Problems Very nice theoretically, but practically useless. * Processes rarely know in advance what their maximum resource needs will be. * The number of processes is not fixed. * Resources can suddenly vanish. ## Deadlock Prevention Deadlock avoidance is essentially impossible. If we can ensure that at least one of the four conditions of the deadlock is never satisfied, then deadlocks will be structurally impossible. ### Deadlock Prevention: Attacking the Mutual Exclusion Can be done for some resources (e.g. the printer) but not all. E.g. For printer, use spooling (Spooling is a process in which data is temporarily held to be used and executed by a device, program or the system.). Words of wisdom: * Avoid assigning a resource when that is not absolutely necessary. * Try to make sure that as few processes as possible may actually claim the resource. ### Deadlock Prevention: Attacking the Hold and Wait Condition Prevent processes holding resources from waiting for more resources. This requires all processes to request all their resources before starting execution. A different strategy: require a process requesting a resource to first temporarily release all the resources it currently holds. Then tries to get everything it needs all at once. ### Deadlock Prevention: Attacking No Preemption Condition Virtualizing some resources can be a good strategy. (e.g. virtualize a printer). Not all resources can be virtualized. (e.g. records in a database) ### Deadlock Prevention: Attacking the Circular Wait Condition Method 1: Have a rule saying that a process is entitled only to a single resource at a moment. Method 2: * Provide a global numbering of all resources. * A process can request resources whenever they want to, but all requests must be done in numerical order. * With this rule, resource allocation graph can never have cycles. ### Summary | Condition | Approach | | ---------------- | ------------------------------------- | | Mutual exclusion | Spool everything | | Hold and wait | Request all resources initially | | No preemption | Take resources away / virtualize them | | Circular wait | Order resources numerically | ## Conclusions Deadlocks can occur on hardware/software resources. OS needs to be able to: * Try to avoid them if possible * Detect deadlocks * Deal with them when detected # Memory Management ## What if there's no memory abstraction? Processes access physical memory directly, so they need to be relocated in order to not overlap in physical memory. Can be done at program load time, but it is a bad idea: * very slow * Require extra info from program ## Memory Abstraction To allow several programs to co-exist in memory we need: * Protection * Relocation * Sharing * Logical organization * Physical organization For that, we have a new abstraction for memory: Address Space ## Address Space Address Space: set of addresses that a process can use to address memory * Defines where sections of data and code are located in 32 or 64 address space. * Defines protection of such sections: ReadOnly, ReadWrite, Execute. * Confined "private" addressing concept: requires form of address virtualization. ![Address Space Example](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-2b2d5da10bfde542f15ecc2f66e8058c61f52aaa%2Faddress-space.png?alt=media) ### Base and Limit Map each process address space onto a different part of physical memory. Two registers: Base and Limit. * Base: start address of a program in physical memory. * Limit: length of the program Only OS can modify Base and Limit. #### Add and Compare For every memory access: * Base is added to the address. * Result is compared to Limit. This can be done in hardware. So it doesn't significantly add to latency. ## Swapping * Programs move in and out of memory * **Holes** are created * Holes can be combined → **memory compaction** * What if a process needs more memory? * If a hole is adjacent to the process, it is allocated to it * Process has to be moved to a bigger hole * Process suspended till enough memory is there ## Managing Free Memory **Bitmap** and **Linked List** are universal methods used in OS and applications. Other methods employ Heaps. Bitmap is slow to find k-consecutive 0s for a new process. Linked List method consists of allocated and free memory segments. It is more convenient to use **double-linked** lists. ## Buddy Algorithm Considers blocks of memory only as 2^N. Potential for fragmentation (drawback). If no block of a size is available, it splits higher blocks into smaller blocks. Easy to implement and fast: `O(log2(MaxBlockSz/MinBlockSz))` e.g. 4K .. 128B = 2^(12-7) = 2^(5 steps) ### Examples ![Allocation at level 0](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-7390d5b58d9e35e31e6f150c94d19664678068df%2Fbuddy-algorithm.png?alt=media) ![Free "X" at level 2 leading to coalescing](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-4e9ca0a66da81cd6870e63b7b249dcf31dd4023d%2Fbuddy-algorithm-2.png?alt=media) ## What are really the problems? * Memory requirement unknown for most apps. * Not enough memory: Having enough memory is not possible with current technology. How do you determine “enough”? * Exploit and enforce one condition: Processor does not execute or access anything that is not in the memory (how would that even be possible ?) Enforce transparently (user is not involved) ## Memory Management Techniques Memory management brings processes into main memory for execution by the processor * involves virtual memory * based on paging and segmentation But we can see that... * All memory references are **logical addresses** in a process’s **address space** that are dynamically translated into physical addresses at run time * An address space may be broken up into a number of pieces that don’t need to be contiguously located in main memory during execution. So it is not necessary that all of the pieces of an address space be in main memory during execution. Only the ones that I am “currently” accessing ## Virtual Memory * Each program has its own **address space** * This address space is divided into **pages** (e.g 4kB) * Pages are mapped into physical memory chunks (called **frames**) * By definition then `sizeof(page) == sizeof(frame)` (the size is determined by the hardware manufacturer) ### Secondary Storage Main memory can act as a cache for the secondary storage (disk) Advantages: * illusion of having more physical memory * program relocation * protection ### Page Table Entry ![Structure of a Page Table Entry](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-19a2c245d6d8eb4faf4528cc64259d1d13ee2a12%2Fpage-table-entry.png?alt=media) **Present bit**: '1' if the values in this entry is valid, otherwise translation is invalid and an pagefault exception will be raised **Frame Number**: this is the physical frame that is accessed based on the translation. **Protection bits**: 'kernel' + 'w' specifies who and what can be done on this page if kernel bit is set then only the kernel can translate this page. If user accesses the page a 'privilege exception' will be raised. If *writeprotect* bit is set the page can only be read (load instruction). If attempted write (store instruction), a write protection exception is raised. **Reference bit**: every time the page is accessed (load or store), the reference bit is set. **Modified bit**: every time the page is written to (store), the modified bit is set. **Caching Disabled**: required to access I/O devices, otherwise their content is in cpu cache ### Multi-Level Page Table / RadixTree / Hierarchical Page Table To reduce storage overhead in case of large memories. For sparse address spaces (most processes) only few 2nd tables required #### 4 Level PageTable for 64-bit arch OS has to make sure no segment is allocated into high range of address space (63-48 bits). If bits are set, the MMU will raise an exception (this is really an OS bug then). ![4 Level PageTable for 64-bit arch](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-eb732650db4881c62e45daa28c1dd68e45acf4de%2F4-level-page-table.png?alt=media) ### General Formula of PageTable Management The OS must create its page table and VMM management following the hardware definition. * Hardware defines the frame size as 2^N * (virtual) page size is typically equal frame size (otherwise it's a power-of-two multiple, but that is rare and we shall not base on this exception) * Everything the OS manages is based on pagesize (hence framesize) * You can compute all the semantics with some basic variables defined by the hardware: * Virtual address range (e.g. 48-bit virtual address, means that the hardware only considers the 48-LSB bits from an virtual address for ld/st, all others raise a SEGV error) * Frame size * PTE size (e.g. 4byte or 8byte) * From there you can determine the number of page table hierarchies, offsets * Examples: * `Framesize = 4KB` → 12bit offset to index into frame (12bits) * `PTE size = 8Bytes` → 512 entries in each page table hierarchy (9bits/hierarchy) * `Virtual address range = 48bits` → `12 + N*9 = 48` (N=4) * The hardware does all the indexing as described before ## Speeding Up Paging Challenges: * Mapping virtual to physical address must be fast: we can not always traverse the page table to get the VA -> PA mapping\ **Solution**: Translation Lookaside Buffer(TLB) * If address space is large, page table will be large (but remember the sparsity, not fully populated)\ **Solution**: Multi-level page table ## TLB > Observation: most programs tend to make a large number of references to a small number of pages over a period of time -> only fraction of the page table is heavily used ( data and instruction locality !!!) TLB is the hardware cache inside the MMU. It caches PageTable translations (VA -> PA) and maps virtual to physical address without going to the page table (unless there’s a miss). In case of TLB miss -> MMU accesses page table and load entry from pagetable to TLB. TLB misses occur more frequently than page faults. ### TLB Management * TLB entries are not written back on access, just record the R and M bits in the PTE (it is a cache after all) upon access * On TLB capacity miss, if the entry is dirty, write it back to its associated PageTableEntry (PTE) * On changes to the PageTable, potential entries in the TLB need to be flushed or invalidated * "TLB invalidate" e.g. when mmap area disappears * "TLB flush" write back when changes in TLB to PageTable (either global or per address) must be recorded, think when a “TLB invalidate” might be insufficient ### TLB based translation ![Paging hardware with TLB](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-87595c078378c9116a5543fbc6eb3d6770d18dc9%2Ftlb-based-translation.png?alt=media) ### Shared Pages (efficient usage of memory) Shared code: * One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems) * Similar to multiple threads sharing the same process space * Also useful for inter-process communication if sharing of read-write pages is allowed Private code and data: * Each process keeps a separate copy of the code and data * The pages for the private code and data can appear anywhere in the logical address space ### Copy on Write (COW) **Copy-on-Write (COW)** allows both parent and child processes to initially **share** the same pages in memory. If either process modifies a shared page, only then is the page copied COW allows more efficient process creation as only modified pages are copied * In general, free pages are allocated from a pool of zero-fill-on-demand pages * Pool should always have free frames for fast demand page execution: Don’t want to have to free a frame when one is needed for processing on page fault * Why zero-out a page before allocating it? -> so we get a known state of a page. * `vfork()` variation on `fork()` system call has parent suspend and child using copy-on-write address space of parent * Designed to have child call `exec()` * Very efficient ## Page Replacement Algorithms ### Optimal Page Replacement Algorithm Each page labeled with the number of instructions that will be executed before this page is referenced. Page with the highest label should be removed. Impossible to implement (just used for theoretical evaluations) ### The FIFO Replacement Algorithm * OS maintains a list of the pages currently in memory \[that would be for instance frame table] * The most recent arrival at the tail * On a page fault, the page at the head is removed * In lab3: for simplicity you implement FIFO with a simple round robin using a `HAND == pointer` to the frametable ### The Second-Chance Page Replacement Algorithm * Modification to FIFO * Inspect the R bit of the oldest page * If R=0 page is old and unused -> replace * If R=1 then * bit is cleared * page is put at the end of the list * the search continues * If all pages have R=1, the algorithm degenerates to FIFO ### The Clock Page Replacement Policy Keep page frames on a circular list in the form of a clock The hand points to the oldest uninspected page When page fault occurs * The page pointed to by the hand is inspected * If R=0 * page evicted * new page inserted into its place * hand is advanced * If R=1 * R is set to 0 * hand is advanced This is essentially an implementation of 2nd-Chance ### The Clock Page Replacement Policy (an optimization) When a page fault occurs, the page the hand is pointing to is inspected. The action taken depends on the R bit: * `R = 0`: Evict the page * `R = 1`: Clear R and advance hand Tail moves in front and “processes” candidates, writing optimistically modified pages back to swap and clear “M” bit and R bit ### The Not Recently Used (NRU) Replacement Algorithm / Enhanced Second Chance Algorithm Two status bits with each page * R: Set whenever the page is referenced (used) * M: Set when the page is written / dirty R and M bits are available in most computers implementing virtual memory Those bits are updated with each memory reference * Must be updated by hardware * Reset only by the OS Periodically (e.g. on each clock interrupt) the R bit is cleared * To distinguish pages that have been referenced recently | Class | R | M | | ----- | - | - | | 0 | 0 | 0 | | 1 | 0 | 1 | | 2 | 1 | 0 | | 3 | 1 | 1 | ### The Least Recently Used (LRU) Page Replacement Algorithm Good approximation to optimal. When page fault occurs, replace the page that has been unused for the longest time. Realizable but **not cheap**. Slow + Few machines (if any) have required hardware. #### Hardware Implementation 1 * 64-bit counter increment after each instruction * Each page table entry has a field large enough to include the value of the counter * After each memory reference, the value of the counter is stored in the corresponding page entry * At page fault, the page with lowest value is discarded Too expensive! Too slow! #### Hardware Implementation 2 * Machine with n page frames * Hardware maintains a matrix of n x n bits * Matrix initialized to all 0s * Whenever page frame k is referenced: * Set all bits of row k to 1 * Set all bits of column k to 0 * The row with lowest value is the LRU ![LRU hardware implementation 2](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-79362ac91c39095789feaf8636ddba8a8fbd095f%2Flru-hardware-implementation-2.png?alt=media) #### Hardware Implementation 3 Maintain the LRU order of accesses in frame list by hardware ``` Head: 4 <-> 2 <-> ... <-> 7 <-> 3 <-> 5 ``` After accessing page 3: ``` Head: 3 <-> 4 <-> 2 <-> ... <-> 7 <-> 5 ``` #### Approximating LRU in Software * Not Frequently Used (NFU) algorithm * Software counter associated with each page, initially zero * At some periodicity (e.g. a second), the OS scans all page table entries and adds the R bit to the counter of that PTE * At page fault: the page with lowest counter is replaced Still a lot of overhead ( not really practical either) ### Aging Algorithm NRU never forgets anything -> high inertia Modifications: * shift counter right by 1 * add R bit as the leftmost bit * reset R bit This modified algorithm is called aging. Each bit in vector represents a period. The page whose counter is lowest is replaced at page replacement ![Aging algorithm](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-e898c0ffa201d8e5ec37c5fa87e01c469cee490e%2Faging-algorithm.png?alt=media) ### The Working Set Model **Working set**: the set of pages that a process is currently using **Thrashing**: a program causing page faults at high rates (e.g. pagefaults/instructions metric) * OS must keep track of which pages are in the working set * Replacement algorithm: evict pages not in the working set * Possible implementation (but expensive): working set = set of pages accessed in the last k memory references * Approximations: working set = pages used in the last 100 msec or 1 sec (etc.) #### Working Set Page Replacement Algorithm ![Working set algorithm](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-3c14fc1b08b3da2489798a79bc71bf6fbf326890%2Fworking-set-temp.png?alt=media) #### WSClock Page Replacement Algorithm (specific implementation of Working Set Replacement) Based on the clock algorithm and uses working set * data structure: circular list of page frames (clock) * Each entry contains: time of last use, R bit * At page fault: page pointed by hand is examined * If R = 1: * Record current time, reset R * Advance hand to next page * If R = 0: * If age > threshold and page is clean -> it is reclaimed * If page is dirty -> write to disk is scheduled and hand advances (note in lab3, we skip this step for simplicity reasons, but think why this is advantageous?) * Advance hand to next page ![WSClock algorithm](https://1131120285-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkHa2lHxqa0pWCOMxKmtW%2Fuploads%2Fgit-blob-9af1742140fa7c947a0a373d1d3645f95afc8783%2Fwsclock-temp.png?alt=media) ## OS Involvement With Paging ### When a new process is created * Determine how large the program and data will be (initially) * Create page table * Allocate space in memory for page table * Record info about page table and swap area in process table ### When a process is scheduled for execution * TLB flushed for current process * MMU reset for the process * Process table of next process made current ### When process exits * OS releases the process page table * Frees its pages and disk space ### When page fault occurs: Page Fault Exception Handling 1. The hardware: * Saves program counter * Exception leads to kernel entry 2. An assembly routine saves general registers and calls OS. 3. OS tried to discover which virtual page is needed 4. OS checks address validation and protection and assign a page frame (page replacement may be needed) 5. If page frame selected is dirty * Page scheduled to transfer to disk * Frame marked as busy * OS suspends the current process * Context switch takes place 6. Once the page frame is clean * OS looks up disk address where needed page is * OS schedules a disk operation * Faulting process still suspended 7. When disk interrupts indicates page has arrived * OS updates page table 8. Faulting instruction is backed up to its original state before page fault and PC is reset to point to it. 9. Process is scheduled for execution and OS returns to the assembly routine. 10. The routine reloads registers and other state information and returns to user space. ### Virtual Memory & I/O Interaction (Interesting Scenario) Process issues a `syscall()` to read a file into a buffer, the process suspended while waiting for I/O. New process starts executing, this other process gets a page fault. If paging algorithm is global there is a chance the page containing the buffer could be removed from memory, the I/O operation of the first process will write some data into the buffer and some other on the just-loaded page ! One solution: **Locking** (**pinning**) pages engaged in I/O so that they will not be removed by replacement algo ### Backing Store Swap area: not a normal file system on it. Associates with each process the disk address of its swap area; store in the process table Before process starts swap area must be initialized * One way: copy all process image into swap area \[static swap area] * Another way: don’t copy anything and let the process swap out \[dynamic] Instead of disk partition, one or more preallocated files within the normal file system can be used \[Windows uses this approach.] ### Memory Mappings Each process consists of many memory areas, aka: * segments * regions * VMAs virtual memory areas. * Examples: Heap, stack, code, data, ronly-data, etc. Each has different characteristics * Protection (executable, rw, rdonly) * Fixed, can grow (up or down) \[heap, stack] Each process can have 10s-100s of these. ### Memory Mapped Files Maps a VMA -> file segment (see `mmap()`'s `fd` argument ) * It’s contiguous * On PageFault, it fetches the content from file at the appropriate offset into a virtual page of the address space * On "swapout", writes back to file (different versions though) Benifits: Can perform load/store operations vs input/output ## Organization of Memory Regions * Cells are by default non-overlapping. Called VMA (Virtual Memory Areas) * Organized as AVL trees * Identify in O(logN) time during pgfault: `Pgfault(vaddr)` → VMA * Rebalanced when VMA is added or deleted ## VMA organization * Organized as balanced tree * Node \[start - end] * On add/delete: rebalance * Lookup in `O(log(n))` time # Overview | Course Code | CSCI-GA.2110-001 | | ----------- | ------------------ | | Professor | Cory Plock | | Email | | ## Useful links * [RegEx Online Validation Tool](http://tool.chinaz.com/regex/) (Chinese) * [Yet Another Scheme Tutorial](https://www.kancloud.cn/kancloud/yast-cn/64461) (Chinese) * [Syntax in SML](http://rigaux.org/language-study/syntax-across-languages-per-language/SML.html): SML syntax fast loop-up book * [SML Help](https://smlhelp.github.io/book/index.html): SML tutorial written by TAs at CMU. ## Grading A midterm and a final. 4 homework assignments. Weights: | Item | Weight | | ------------------------ | ------ | | Midterm | 25% | | Final | 35% | | Homework assignments (4) | 40% | # Introduction > Lecture slide: [click here](https://www.kdocs.cn/p/104545603342) History, standards, syntax, semantics, grammars, parsing.\ Readings: Scott, ch 1 - 2\ See [resources folder](https://newclasses.nyu.edu/portal/site/dd700183-e7c5-4095-b7c7-84d4f34b722f/tool/77e1f123-557e-4781-8580-6713673dc39e?panel=Main) for language standards documents: C11, C++17, ECMA-262, ECMA-334, and JLS15. ## Programming paradigms ### Imperative (von Neumann) Such as: Fortran, Pascal, C, Ada * programs have mutable storage (state) modified by assignments * the most common and familiar paradigm ### Functional (applicative) Such as: Scheme, Lisp, ML, Haskell * functions are first-class values * side effects (e.g., assignments) discouraged ### Logical (declarative) Such as: Prolog, Mercury * programs are sets of assertions and rules ### Object-Oriented Such as: Simula 67, Smalltalk, C++, Ada95, Java, C# * data structures and their operations are bundled together * inheritance ### Quantum Such as: QCL, Q, Q#, qGCL * performs operations on data using quantum bits (“qubits”) * utilizes quantum properties such as superposition and entanglement ## BNF (Backus-Naur Form) Does not add expressiveness to the language—for convenience only. * alernation: ` ::= | ` * sequencing: ` ::= ` ### BNF Building blocks 1. Numbers of a and b are equal (in any order): ``` :== a b | b a | ε ``` 1. a is more: ``` :== a | a ``` ## EBNF (Extended Backus-Naur Form) Encompasses everything BNF has, plus: * repetition: * * zero or more: `{}` or `*` * * one or more: `+` * option: `[]` * grouping: `('+'|'-')` ## The Chomsky hierarchy ### Regular grammars (Type 3) * all productions can be written in the form: N ::= TN * one non-terminal on left side; at most one on right * generally used for scanners ### Context-free grammars (Type 2) * all productions can be written in the form:N ::= XYZ * one non-terminal on the left-hand side; mixture on right * most major programming languages ### Context-sensitive grammars (Type 1): * number of symbols on the left is no greater than on the right * no production shrinks the size of the sentential form * used for parts of C++, but otherwise rarely used ### Type-0 grammars no restrictions ## Regular expressions > **Regular grammars** can be used to generate regular languages.\ > **Regular expressions** can be used to accept regular languages. * `ε` denotes `∅` * a character `x`, where `x ∈ Σ`, denotes `{x}` * sequencing: a sequence of two regular expressions `RS` denotes `{αβ | α ∈ [R], β ∈ [S]}` * alternation: `R|S` denotes `[R] ∪ [S]` * Kleene star: `R*` denotes the set of strings which are concatenations of zero or more strings from `[R]` * grouping: parentheses `(A|B)` **Shorthands** ``` R? ≡ ε|R R+ ≡ RR* ``` **Conventions** ``` . ≡ any α ∈ Σ (“any character”) [abc] ≡ (a|b|c) [^abc] ≡ Σ \ {a, b, c} [0-9] ≡ (0|1|2|3|4|5|6|7|8|9) a-z and A-Z ``` ## Parse tree A parse tree describes the grammatical structure of a sentence * leaf nodes are terminal symbols * internal nodes are non-terminal symbols * construction of tree from sentence is called *parsing* **Example:** Input string: `52.316` Grammar: ``` ::= | '.' ::= | ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' ``` Parse tree: ## Grammar ambiguity If the parse tree for a sentence is not unique, the grammar is ambiguous. > From recitation: A CFG is ambiguous if it has more than one parse tree for some strings. i.e. there is more than 1 derivation for a string. ### "Dangling if" rewrite solution ``` ::= | ::= ‘=’ | ‘;’ ::= ‘if’ ‘then’ ‘else’ | ::= ‘if’ ‘then’ | ‘if’ ‘then’ ‘else’ ::= ‘===’ ::= ‘x’ | ‘y’ | ‘z’ ::= | ‘0’ | ‘1’ | ‘2’ | ‘3’ ``` ### Precedence If we say operator `*` has precedence over operator `+`. This means expression `5 + 2 * 3` should be evaluated as: `5 + (2 * 3)`, not `(5 + 2) * 3`. **Precedence can be specified in two ways:** * Write precedence directly into the rules: higher precedence appear in deeper rules. * Write an ambiguous grammar first, then specify operator precedence separately. ### Associativity Associativity tells the parser what to do with operators at the same level of precedence. For example, `5 - (2 - 3)` verses `(5 - 2) - 3`. Two `-` operators have the same precedence. However, how you associate them will yield different mathematical results. Usually, you can specify using *left* associativity or *right* associativity. ## Scanners and parsers Scanners (or tokenizers) read in text and extract tokens. Parsers read in tokens and construct a parse tree. ### LL parsers LL (Left-to-right, Leftmost derivation) parsers are also called top-down, recursive descent or predictive parsers. It begins at the root symbol. `LL(k)`: means `k` look ahead. **Problems with LL parsing:** * Left recursion: a grammar is left-recursive if there exists non-terminal `A` such that ` ::= α` for some `α`. * Common prefixes: if there exists a non-terminal `A` and terminal `b` such that there exists rule R1 ` ::= b ...` and R2 ` ::= b ...`. **How to eliminate left-recursive problem:** Original: ``` A → Aα1| Aα2 | … | Aαm | β1 | β2 | … | βn ``` Convert to: ``` A → β1A' | β2 A' | … | βnA' A' → α1A' | α2A' | … | αmA' | ε ``` # Imperative Languages > Lecture slide: [click here](https://www.kdocs.cn/p/105166936239) Names, binding, scope, lifetime, nesting, control structures.\ Readings: Scott, ch 3 ## Names Mutable variables, values, functions, types, type constructors, classes, modules/packages, execution points (labels), execution points with environment (continuation). ## Bindings A binding is an association of two things. The first is usually a name. **Binding time** is the time at which the association is made. It can be at: language design time (semantics of most language constructs), language implementation time (implementation dependent semantics), compile time, link time or run time. **Static binding** means before run time, **dynamic binding** means during run time. For example, virtual methods in C++ are dynamically bound. ## Scope and lifetime **Scope** is the region of program text where a binding is active, thus a space.\ **Lifetime** is the period of time between the creation of an entity and its destruction, thus a time span. ### Lifetimes Three different objects in memory: * **static** objects: lifetime of entire program execution. e.g., global and static variables. * **stack** objects: from the time the function or block is entered until the time it is exited. e.g., local variables. * **heap** objects: arbitrary lifetimes. e.g., dynamically allocated objects like those created using `new`. ### Scoping Two major scoping disciplines: * **static scoping**: binding of a name is given by its declaration in the innermost enclosing block. * **dynamic scoping**: binding of a name is given by the most recent declaration encountered at runtime. ### Memory allocation * **Static**: allocated once at compile time (usually in protected memory). Usually include: Strings, constants, static variables. * **Stacks**: allocated in frames on a first-in last-out basis. Frames usually store: actual parameters, temporaries, local variables, bookkeeping information and return address. * **Heap**: allocated from main memory according to an allocation policy like first-fit, best-fit, etc. ## Control flows Basic topics are in the slides. ### Serial copy Copy a chuck of memory from one place to another. A trivial inefficient implementation in C: ```c void send(int *to, int *from, int count){ do { /* precondition: count > 0 */ *to++ = *from++; } while (--count > 0); } ``` Solution (unstructured flow, Duff’s device): > Lecture recording at `1:35:00` ```c void send(int *to ,int * from, int count){ register n = (count + 7) / 8; switch (count % 8) { case 0: do { *to++ = *from++; case 7: *to++ = *from++; case 6: *to++ = *from++; case 5: *to++ = *from++; case 4: *to++ = *from++; case 3: *to++ = *from++; case 2: *to++ = *from++; case 1: *to++ = *from++; } while (--n > 0); } } ``` Why `8`? Because that was the size of the cache back then. Being bigger than that would cause cache overflow thus cache miss. # Subprograms > Lecture slide: [click here](https://www.kdocs.cn/p/104545603342) Functions and procedures. Parameter passing. Nested procedures. First-class and higher-order functions. Implementation issues.\ Readings: Scott, ch 6, 8.1 - 8.3 ## Parameter passing When defining functions, the names of variables we give are called (formal) parameters. ```js function f(a, b, c) ... // parameters: a, b, c ``` When calling function, the values or variables we feed are called (actual) arguments. ```js f(i, 2 / i, g(i, j)); // arguments: i, 2/i, g(i, j) ``` ### Methods of passing * **by value**: formal is bound to value of actual. * **by reference**: formal is bound to location of actual. * **by copy-return**: formal is bound to value of actual; upon return from routine, actual gets copy of formal. * **by name**: formal is bound to expression for actual; expression evaluated whenever needed; writes to parameter are allowed (and can affect other parameters!) * **by need**: formal is bound to expression for actual; expression evaluated the first time its value is needed; cannot write to parameters. ### Passing in practical languages * Ada: semantic intent is separated from passing implementation. Parameter modes: `in`(default, read-only in subprogram), `out`(write in subprogram) and `in out`(read-write in subprogram). * C: parameter passing by value, no semantic checks. Assignment to formal is assignment to local copy. * C++: default is by-value. Can explicitly pass parameter by reference: `void incr (int& y)`. * Java: by value only. Just different semantics for primitive types and objects. ## Runtime organizations Each subprogram invocation creates an activation record.\ Recursion imposes stack allocation. * **activation record**: hold actuals, linkage information, saved registers, local entities. * **caller**: place actuals on stack, return address, linkage information, then transfer control to callee. * **prologue**: (before) save registers, allocate space for locals. * **epilogue**: (after) place return value in register or stack position, update actuals, restore registers, then transfer control to caller. * **binding of locations**: actuals and locals are at fixed offsets from frame pointers. * **complications**: variable # of actuals, dynamic objects. ## Activation record Layout:
**Frame pointer**: pointing to the head/base of the stack frame/activation record\ **Stack pointer**: pointing to the top of the stack ### Variable number of parameters Consider C function `printf`: ```c printf("this is %d a format %d string", x, y); ``` `printf` can have variable length of parameters. Within body of printf, we need to locate as many actuals as placeholders in the format string. Solution: place parameters on stack in reverse order (actuals at positive offset from the frame pointer, locals at negative offset from the frame pointer) ### Call conventions Subprogram callers and callees must completely agree on who does what, how, and when. These details are encompassed in a protocol known as the *calling convention*. * C (`cdecl`): Parameters placed on the stack in right-to-left order. Caller required to clear the stack parameters. * Microsoft Standard (`stdcall`): called function required to clear the stack parameters. * Fast Call (`fastcall`): up to two parameters placed in hardware registers. Rest on the stack. * Microsoft C++ (`thiscall`): the "this" pointer passed through the CX register (x86) ### Objects of dynamic size Two solutions to handle objects of dynamic size on activation record: * Solution 1: use indirection: activation record holds pointers simpler implementation, costly dynamic allocation/deallocation. * Solution 2: local indirection: activation record holds offset into stack faster allocation/deallocation, complex implementation. ## Global linkage **Static chain/link** is a pointer to activation record of statically enclosing scope.\ **Display** is an array of pointers to activation records. > Functional languages, however, do not use global linkage because they allocate activation records on heap. ### Static links Set up as part of call prologue. To retrieve entity n scopes out, need n dereference operations. ### Display O(1) display lookup: one entry per scoping level (known at compile time), plus dereference. ## First-class & higher-order functions Allowing functions as first-class values forces heap allocation of activation records. Also, environment of function definition must be preserved until the point of call: activation record cannot be reclaimed if it creates functions. As a result, functional languages require more complex run-time management. ### Higher-order functions Higher-order functions are the functions that take (other) functions as arguments and/or return functions. (A function that takes/returns pointers to functions can also be considered a higher-order function.) How they are restricted in different languages: * C: no nested definitions, so environment is always global. * C++: ditto, except for nested classes. * Ada: static checks to reject possible dangling references. * Modula: pointer to function illegal if function not declared at top-level. * ML, Haskell: no restrictions. For example, compose function: `fun compose f g x = f (g x)` # Functional Programming Overview of the lambda calculus and Scheme. > Lecture slide: [click here](https://www.kdocs.cn/p/105324573301) Readings: Scott, ch. 10 (including 10.6.1 on the CD), Dybvig ch. 1,2 (optional) ## λ-Calculus A Turing complete model of computation that has its syntax and reduction rules. It is the basis for functional languages. ### Syntax ç-calculus has variables, abstraction and application. **Variables**: lower-case letters. Such as `x`.\ **Abstraction**: (definition of function) `λx.M`, `x` being the function parameter, `M` being the function body.\ **Application**: (invocation of function) `M N`. Call function `M` with the argument `N`. Abstraction is *right-associative*, application is *left-associative*. And application has precedence over abstraction. (For example,`λx. y λx. z` means `λx.(y (λx.z))`) ### Free and bound variables In term `λx.M`, the scope of `x` is `M`. So, we call `x` bound in `M`. The variables that are not bound are *free*. ### α-conversion Renaming bound variables. Usually used to avoid name collision. ``` λy.(...y...) → λw.(...w...) ``` ### β-reduction Applying the argument and calling the function. ``` (λx.M) N → [x→N]M ``` `[x→N]M` means `M` with all bound occurences of `x` replaced by `N`.\ **Restriction**: `N` should not have any free variables which are bound in `N`. ### Normal form An expression that cannot be β-reduced any further is a normal form. Not everything has a normal form. For example, `(λz.z z)(λz.z z)` reduces to itself which will result in infinite application. ### Evaluation strategies > Slide page 7 For example, `(λx.λy.yxx)((λx.x)(λy.z))` 1. normal-order: reduct the outermost "redex" first. ``` [x→(λx.x)(λy.z)](λy.yxx) → λy.y((λx.x)(λy.z))((λx.x)(λy.z) ``` 2.applicative-order: arguments to a function evaluated first, from left to right. ``` (λx.λy.yxx)([x→(λy.z)]x) → (λx.λy.yxx)((λy.z)) ``` **Some observations:** * If a lambda reduction terminates, it terminates to the same reduced expression regardless of reduction order. * If a terminating lambda reduction exists, normal order evaluation will terminate. ### η-reduction η(eta)-reduction is used to eliminate useless variables. ``` (λx.M x) → M ``` ### Computational power The untyped λ-calculus is Turing complete. **Numbers and numerals**: number is an abstract idea, numeral is the representation of a number. **Booleans**: ``` TRUE ≡ λa.λb.a FALSE ≡ λa.λb.b IF ≡ λc.λt.λe.(cte) AND ≡ λm.λn.λa.λb.m(nab)b OR ≡ λm.λn.λa.λb.ma(nab) NOT ≡ λm.λa.λb.mba ``` **Arithmetic**: Some numerals ``` ⌜0⌝ ≡ λfx.x ⌜1⌝ ≡ λfx.fx ⌜2⌝ ≡ λfx.f(fx) ⌜3⌝ ≡ λfx.f(f(fx)) ``` Some operations ``` ISZERO ≡ λn.n(λx.FALSE)TRUE SUCC ≡ λnfx.f(nfx) // n+1 PRED ≡ λn.n(λgk.(g⌜1⌝)(λu.PLUS(gk)⌜1⌝)k)(λv.⌜0⌝)⌜0⌝ // n-1 PLUS ≡ λmnfx.mf(nfx) // m+n MULT ≡ λmnf.m(nf) // m*n EXP ≡ λmn.nm // n^m ``` Iteration ``` MUL = λmn.m (ADD n) 0 EXP = λmn.m (MUL n) 1 ``` ## Scheme overview * [Yet Another Scheme Tutorial](https://www.kancloud.cn/kancloud/yast-cn/64461) (Chinese) `symbol?`\ `number?`\ `pair?`\ `list?`\ `null?`\ `zero?` ### List `(cons 'a '(b))` => list `(a b)`\ `(cons 'a 'b)` => dotted pair `(a . b)` `car`: get head of list.\ `cdr`: get rest of list.\ `cons`: perpend an element to a list.\ `'()`: null list. #### List decomposition
```scheme (car '(this is a list of symbols)) => this (cdr '(this is a list of symbols)) => (is a list of symbols) (cdr '(this that)) => (that) ; a list (cdr '(singleton)) => () ; the empty list (car '()) => Error: car expects argument of type; given() ``` `(cadr xs)` is `(car (cdr xs))`\ `(cdddr xs)` is `(cdr (cdr (cdr xs)))` #### List building
```scheme (cons 'this '(that and the other)) => (this that and the other) (cons 'a '()) => (a) ``` shortcut: `(list 'a 'b 'c 'd 'e)` ### Quoting data (`'...`) `quote` or `'` to describe data. ```scheme (quote (1 2 3 4)) (quote (Baby needs a new pair of shoes)) '(this also works) ``` ### Booleans `#t`: true.\ `#f`: false. Any value not equal to `#f` is considered to be true. ### Simple control structures #### Conditional
```scheme (if condition expr1 expr2) ``` #### Generalized form
```scheme (cond (pred1 expr1) (pred2 expr2) ... (else exprn)) ``` ### Global definitions `define` is a special function that only can be used at the top level to create global variables. ```scheme ; (define name value) (define x 15) (define sqr (lambda (n) (* n n)) ; (define (name ...parameters) body) (define (sqr n) (* n n)) ``` ### Locals: `let`, `let*` and `letrec` Basic `let` skeleton: ```scheme (let ((v1 init1) (v2 init2) ... (vn initn)) body) ``` # Data Types > Lecture slide: [click here](https://www.kdocs.cn/p/106175368491) Typing: strong vs. weak, static vs. dynamic. Type declarations, type equivalence, type inference. Subtypes and derived types. Scalar and composite types (arrays, records, variant records). Pointers and References Readings: Scott, ch. 7 ## Static vs dynamic type system A language can have a mixture of both, like C#, Visual Basic, Alore. Java has a mostly static type system with some runtime checks. ### Static typing Languages like Ada, C++, Java, ML. * Variables have types. * Compilers ensures (at **compile time**) that type rules are obeyed. ### Dynamic typing Languages like JavaScript, PHP, Lisp, Ruby. * Variables do not have types, values do. * Compilers ensures (at **run time**) that type rules are obeyed. ### Pros and cons * Static is faster. Dynamic typing requires run-time checks. * Dynamic is more flexible. * Static is easier to refactor code. ## Strong vs weak typing A **strongly typed** language does not allow variables to be used in a way inconsistent with their types (no loopholes).\ A **weakly typed** language allows many ways to bypass the type system (e.g., pointer arithmetic). There's no fine line between them. Most languages are neither strictly strongly or weakly typed. Usually a mixture with a bias toward one or the other. ## Pointers and references Both refer to an object in memory. **Pointers** tend to make this notion more explicit: * Dereferencing. * Pointer arithmetic (raises issues of allocation, alignment). * Low level operations often supported (e.g. `memcpy`). **References** tend to behave more like ordinary variables: * Dereferencing still occurs, just under the hood. * No notion of pointer arithmetic. * Restrictions on reference variable bindings (C++). ## Records A record consists of a set of typed fields. ### Name equivalence or structural equivalence **Name equivalence**: two types are the same if they have the same name. (e.g. Ada)\ **Structural equivalence**: two types are equivalent if they have the same structure. (e.g. ML) Most statically typed languages choose name equivalence. ML and Haskell are exceptions. ### Variant records / discriminated union A **variant record** is a record that provides multiple alternative sets of fields, only one of which is valid at any given time. Also known as a **discriminated union**. ## Polymorphisms ### Subclass polymorphism The ability to treat a class as one of its superclasses, which is the basis of OOP. ### Subtype polymorphism The ability to treat a value of a subtype as a value of a supertype. Related to subclass polymorphism. ### Parametric polymorphism The ability to treat any type uniformly. Found in ML, Haskell, and, in a very different form, in C++ templates and Java generics. ### Ad hoc polymorphism Multiple definitions of a function with the same name, each for a different set of argument types (known as *overloading*). ## Subtyping A relation between types. Similar to but not the same as subclassing. Can be used in two different ways: **subtype polymorphism** and **coercion**. Examples: 1. `{a, b, c}` is a subtype of `{a, c}`. 2. `a|c` is a subtype of `a|b|c`. 3. Range `1..100` is a subtype of `1..500`. ### Subtype/Supertype conversions **Typecasting** is an *explicit* conversion of one type to another. Source type is known or can be inferred, destination type must be specified by the programmer. Two variations: * **Type widening (lifting)**: converting subtype to supertype (coercion can also be used). * **Type narrowing**: converting supertype to subtype. Involves information loss. ### Subtype polymorphism vs coercion **Subtype polymorphism**: ability to *treat* a value of a subtype as a value of a supertype.\ **Coercion**: ability to *convert* a value of a subtype to a value of a supertype. # SML/NJ Lecture slide: [click here](https://www.kdocs.cn/p/107488041032) Pattern matching, type inference, data types, pattern matching, continuations.\ Readings: Ullman, ch 1-4, 5 (optional) [Syntax in SML](http://rigaux.org/language-study/syntax-across-languages-per-language/SML.html): SML syntax fast loop-up book\ [SML Help](https://smlhelp.github.io/book/index.html): SML tutorial written by TAs at CMU. ### Overview * Functional: functions as first-class values * Garbage collected * Strict evaluation (applicative order) * No coercion * Strong and static typing * parametric polymorphism * structural equivalence * all with type inference * Advanced module system * Exceptions * Miscellaneous features * datatypes (merge of enumerated literals and variant records) * pattern matching * `ref` type constructor (like const pointers) ```smlnj (* Comments *)val k = 5; List operations ``` ```smlnj 1::[2,3]; => val it = [1, 2, 3] : int list (* whether empty or not *) null [1, 2]; => val it = false : bool hd [1, 2, 3]; => val it = 1 : int tl [1, 2, 3]; => val it = [2,3] : int list (* concatenation of lists *) [1, 2, 3] @ [2, 3, 4]; => val it = [1,2,3,2,3,4] : int list ``` ### Functions ```sml (* named *) fun abs x = if x >= 0.0 then x else ~x; (* anonymous *) fn x => if x >= 0.0 then x else ~x; (* pattern-matching style *) fun length [] = 0 | length (x::xs) = 1 + length xs; (* multiple arguments *) fun add (a, b) = a + b; (* pass a tuple *) fun add a b = a + b; (* currying *) ``` Type notation `α → β → δ` means `α → (β → δ)` ### `let` local scope ```sml fun findroot (a, x, acc) = let val nextx = (a / x + x) / 2.0 in if abs (x - nextx) < acc * x then nextx else findroot (a, nextx, acc) end ``` ### Records Type declaration ```sml type vec = {x: real, y: real}; ``` Variable declaration ```sml val v = {x=2.3, y=4.1}; ``` Field selection: `#x v` Pattern matching in a function: ```sml fun dist {x, y} = sqrt (pow (x, 2.0) + pow (y, 2.0)); ``` ### Tuples Tuples are actually records: ```sml ("I", "Love", "Programming", "Languages"); ``` is actually: ```sml {1="I", 2="Love", 3="Programming", 4="Languages"} ``` Index starting from `1`. ### Datatypes For example: ```sml datatype tree = Leaf of int | Node of tree * tree; ``` `tree` is a type constructor. `Leaf` and `Node` are data constructors: * `Leaf : int → tree` * `Node : tree * tree → tree` #### Pattern matching for datatypes We can define functions by pattern matching: ```sml fun sum (Leaf t) = t | sum (Node (t1, t2)) = sum t1 + sum t2; ``` or ```sml fun sum x = case x of Leaf t => t | Node (t1, t2) => sum t1 + sum t2; ``` Functions accepting data constructors as arguments must provide an exhaustive definition(cover every data constructor for the datatype). #### Parameterized datatypes (with type variables) ```sml datatype 'a gentree = Leaf of 'a | Node of 'a gentree * 'a gentree; val names = Node (Leaf "this", Leaf "that"); ``` ### Common idiom: option `option` is a built-in datatype: ```sml datatype 'a option = NONE | SOME of 'a; ``` A lookup function using option: ```sml fun lookup eq key [] = NONE | lookup eq key ((k,v)::kvs) = if eq (key, k) then SOME v else lookup eq key kvs; ``` Type of `lookup` is `(α1*α2→bool) → α1 → (α2*β)list → βoption`. ### Signature and structures An ML signature specifies an interface for a module. ```sml signature STACKS = sig type stack exception Underflow val empty : stack val push : char*stack->stack val pop : stack->char*stack val isEmpty : stack->bool end ``` A structure implementing it would be: ```sml structure Stacks : STACKS = struct type stack = char list exception Underflow val empty=[] val push=op:: fun pop (c::cs) = (c, cs) | pop [] = raise Underflow fun isEmpty [] = true | isEmpty _ = false end ``` #### Signature ascription **Opaque ascription** (`:>`) hides the identity of types beyond that which is conveyed in the signature. That is, additional type information provided by the structure will be considered abstract.\ **Transparent ascription** (`:`) exposes the identity of types beyond that conveyed in the signature. That is, additional type information provided by the structure will augment the signature. * both prohibit the introduction of identifiers not already present in the signature. This is *component hiding*. * both permit types (in structures) which are broader than the signature. Examples: ```sml signature SetSignature = sig type ’a set val empty : ’’a set val singleton : ’’a -> ’’a set end; structure Set = struct type ’a set = ’a list; val empty = []; fun singleton a = [a] val aux = []; end; (* Opaque ascription *) structure Set2 :> SetSignature = Set; Set2.aux ; (* error - component hiding *) Set2.singleton (2) = [2]; (* error - list representation hidden *) (* Transparent ascription *) structure Set2 : SetSignature = Set; Set2.aux ; (* error - component hiding *) Set2.singleton (2) = [2]; (* okay *) ``` ### Functor A functor creates a structure from a structure. ```sml signature TOTALORDER = sig type element; val lt : element * element -> bool; end ; functor MakeBST (Lt : TOTALORDER): sig type ’label btree; exception EmptyTree; val create : Lt.element btree; val lookup : Lt.element * Lt.element btree -> bool ; val insert : Lt.element * Lt.element btree -> Lt.element btree; val deletemin : Lt.element btree -> Lt.element * Lt.element btree; val delete : Lt.element * Lt.element btree -> Lt.element btree; end = struct open Lt ; datatype ’label btree = Empty | Node of ’label * ’label btree * ’label btr... val create = Empty; fun lookup (x, Empty) = ...; fun insert (x, Empty) = ...; exception EmptyTree; fun deletemin (Empty) = ...; fun delete (x , Empty) = ...; end; ``` Invoke the functor: ```sml structure String : TOTALORDER = struct type element = string ; fun lt (x, y) = let fun lower (nil) = nil | lower (c::cs ) = (Char.toLower c)::lower(cs); in implode(lower(explode(x))) < implode(lower(explode(y))) end ; end ; structure StringBST = MakeBST (String); ``` # GC > Lecture slide: [click here](https://www.kdocs.cn/p/110422566840) Garbage collection, allocation/deallocation, reference counting, concurrent programming.\ Readings: Scott, ch. 7 ## Types of allocation * **Static**: absolute address retained throughout program’s execution. Such as: static variables, global variables, certain fixed data like string literals, constants. * **Stack**: last-in, first-out ordering. Such as subroutine arguments, local variables, and runtime system data structures like displays. * **Heap**: general storage, foe allocation at arbitrary times. It's explicitly or automatically allocated, things like resizable types (e.g. String), Java class instances, all objects and data structures in Python. ### Heap deallocation methods * Manual deallocation, `free`, `delete` * Automatic deallocation via GC * Semi-automatic deallocation, using destructors (C++, Ada) ## Allocation methods Two basic methods: *free list* and *heap pointer*. ### Kinds of fragmentation that happen when allocating **Internal fragmentation**: memory allocated but not used. Typical for fixed block allocation.\ **External fragmentation**: available memory blocks too small to be used. ### Free list A linked list of unused blocks of memory is maintained (the free list). **Allocation**: a search is done to find a free block of adequate size, then remove the found block from the list.\ **Deallocation**: the freed block is placed back on the free list. Problems: may take some time to find a free block of the right size; memory eventually becomes fragmented. #### First fit Select the first block large enough to satisfy the request. #### Best fit Select the smallest block large enough to satisfy the request. #### Worst fit Always select the largest available block. ### Heap pointer Initially, the heap pointer is set to bottom of heap. **Allocation**: the heap pointer is incremented an appropriate amount\ **Deallocation**: defragmentation eventually required. Problem: requires moving live objects in memory. ## Automatic deallocation Basic garbage collection algorithms: mark/sweep, copying, hybrid(combination of copy and mark & sweep) and reference counting. ### Mark / sweep Works for free list. Algorithm at slide P16. ### Copying GC Works for heap pointer. Algorithm at slide P18. ### Generational GC Slide P19. ### Reference counting Slide P22. # OOP > Lecture slide: [click here](https://www.kdocs.cn/p/111952867211) Objects, classes, data and function members, constructors/destructors. OOP in C++ and Java, objects vs closures, classes vs datatypes, OO pitfalls.\ Readings: Scott ch 3.3.4-3.3.5, 3.7, Stroustrup ch. 8-9 (optional), Arnold ch. 13 (optional). ## Styles of OOLs (object oriented languages) ### Class-based In a class-based OOP language, each object is an instance of a class. ### Prototype-based In a prototype-based OOP language, each object is a clone of another object, possibly, with modifications and/or additions. Example: ```js var original = {a: 'A', b: 'B'}; var clone = owl.util.clone(original); // clone.a == 'A' // clone.b == 'B' clone.a = 'Apple'; // clone.a == 'Apple' // original.a == 'A' // unchanged original.b = 'Banana'; // clone.b == 'Banana' // change shows through clone.c = 'Car'; // original.c is undefined original.a = 'Blah'; // clone.a == 'Apple' // clone's new val hides original delete clone.a; // clone.a == 'Blah' // original value visible again // repeating "delete clone.a" won 't delete orig.value ``` ## Classes in C++ Example: ```cpp class Point { double m_x, m_y; // private data members public: Point (double x, double y) // constructor : m_x (x), m_y (y) {} virtual ~Point () {} virtual void move (double dx, double dy) { m_x += dx; m_y += dy; } virtual double distance (const Point & p) { double xdist = m_x - p.m_x, ydist = m_y - p.m_y; return sqrt (xdist * xdist + ydist * ydist); } virtual void display () { ... } }; ``` ### Extending a class Example: ```cpp class ColoredPoint : public Point { Color color; public: ColoredPoint (double x ,double y, Color c) : Point (x ,y), color ( c ) {} ColoredPoint (Color c) : Point (0.0, 0.0), color (c) { } virtual Color getColor () {return color;} virtual void display () { ... } // now in color! }; ``` ### Dynamic despatching by vtable **vtable** is used to determine which class' method to invoke.\ `virtual` method means: "use the subclass version" (including all descendant subclasses). Virtual methods are placed in the *vtable*. * `Point` class vtable example: * `ColoredPoint`: ## OOP pitfalls # Overview | Course Code | CSCI-GA.2590-001 | | ----------- | ------------------- | | Professor | Adam Meyers | | Email | | ## Useful Links * [Personal Tools](https://colab.research.google.com/drive/1aG8gwgp260bK_zomp_3ce68NdZgQzg8Y) ## Grading 5 long homework assignments and 3 short ones. A midterm exam and a final project. | Component | Weight | | ------------------------- | ------ | | Long Homework Assignments | 30% | | Midterm | 30% | | Short Homework | 5% | | Final Project | 35% | # Introduction ## Computational Linguistics AKA, Natural Language Processing (NLP), Language Engineering, ... **Domain:** The set of problems involving the interpretation and generation of human language text and speech **Poperties:** * As with applied science: the proof is in the pudding * Sometimes at odds with theoretical linguistics * Need not model human abilities and human methods * Need not correspond to published linguistic theories * Sometimes draws on linguistic theories and/or studies of human processing * Broad and changing domain influenced by available funding ### Computational Linguistics Applications * **Machine translation:** Methods are not at all based on how humans translate; Effective for gisting text, generating 1st draft translations, but not for high-level translation; Works better for “controlled languages” – technical manuals (Microsoft, Catterpiller, etc.); [Systran](https://translate.systran.net/?lang=en); [Google](http://www.google.com/language_tools?hl=en); * **Spoken Language:** dictation (IBM ViaVoice, Dragon Naturally Speaking), Telephone-based customer support (phone mazes) * **Information Retrieval:** Finding documents based on a query, e.g., Web Searches * **Information Extraction:** Dealtime, Google Products, Monster.com (job search); Some open source tools: [OpenNLP](https://opennlp.apache.org), [AliasI](http://alias-i.com/lingpipe/); Tools on NYU website include: [NYU NLP Products](http://nlp.cs.nyu.edu/projects/index.shtml#t-r-i), [NYU Grishman Jet](http://cs.nyu.edu/grishman/jet/jet.html), [NYU NLP ICE](http://nlp.cs.nyu.edu/ice/), [NYU NLP Termolator](http://nlp.cs.nyu.edu/termolator/). * **Question Answering:** ask.com, Wolfram Alpha, MIT start: * **Summarization:** * **Spelling/Grammar Checking**, etc. * Other NLP demos: ## Lowest Level Syntactic Processing (text) * **Tokenization and Segmentation:** Given a sentence, determine the words or word-like units that it consists of. NLTK command: `nltk.word_tokenize('this is a sentence')` * **Part of Speech Tagging** (modified PTB): Apply a set of part of speech tags to a set of tokens. NLTK command: `nltk.pos_tag(tokens)` * **Named Entity Tagging** (with a little semantics): Mark boundaries of names of type `PERSON`, `ORGANIZATION`, `FACILITY`, `GPE`, `LOCATION`, … NLTK command: `nltk.chunk.ne_chunk(nltk.pos_tag(nltk.word_tokenize(test_sentence)` * Chunking: mark verb groups and/or noun groups, convenient approximations of syntactic units. NLTK see following lines of code. ```python sentence = 'The book with the blue cover will end up on the shelf.' chunks = r""" NG: {()*()} VG: {*?} """ chunks_grammar = nltk.RegexpParser(chunks) chunks_grammar.parse(nltk.pos_tag(nltk.word_tokenize(sentence))) ``` ## Parsing: High Level Syntactic Processing ``` (S (NP (DT the) (NN book) (PP (IN with) (NP (DT the) (JJ blue) (NN cover)))) (VP (VBZ is) (PP (IN on) (NP (DT the) (NN shelf))))) ``` ## Semantics A wide range of topics loosely referring to "meaning". Some Example Topics which may be part of Semantics: * Word Sense Disambiguation * Predicate Argument Structure * Anaphora * Discourse Argument Structure * "Semantic Parsing" ### Word Sense Disambiguation For interesting characterizations of word senses (and relation between senses), use WordNet (online or download it): wordnet.princeton.edu. Difficult sense disambiguation: Example: senses 2, 6 and 9 for word "bank" are arguably not distinct. Lexicographers are acutely aware of the merging vs. splitting problem of enumerating senses. CL systems usually collapse some WordNet distinctions. ### Predicate / Argument Structure For thousands of years, linguists have employed systems to characterize predictable paraphrases, e.g., Pāṇini, a Sanskrit linguist from the 4rth Century BC In 21st Century CL, semantic role labeling is popular ![Semantic Role Labeling](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-f7f8bd2a7a194d1e00a7467a9b794436904dc6b1%2Fimage.png?alt=media) ### Anaphora Coreference * Though **Big Blue** won the contract, this official is suspicious of **IBM**. * **Mary** could not believe what **she** heard. Other Varieties * John ate **a sandwich** and Mary ate **one** also. \[type coref] * **The amusement park** is very dangerous. **The gate** has sharp edges. **The rides** have not been inspected for years. \[Bridging Anaphora] * **This book** is valuable, but **the other book** is not. \[Other coref] ### Discourse Argument Structure Adverbs, Subordinate/Coordinate, Conjunctions, among other words link clauses ![Discourse Argument Structure](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-692412d81777762148726d80eaf43f0c2ad70fa2%2Fimage.png?alt=media) ### Semantic Parsing (e.g. GLARF) Means different things to different researchers, but my version of semantic parsing is called [GLARF](http://nlp.cs.nyu.edu/meyers/GLARF.html). One representation of the sentence that includes as much information as possible: lexical categories, predicate argument structure, discourse annotation, etc. #### Example A representation of the sentence: * `Afterwards, she decided to perform the operation.` * When it occurs after the sentence: `The doctor ran some tests` ![GLARF Example](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-8d5b6b0cb62a3c83a6e527f0ecfa17cab129118b%2Fimage.png?alt=media) ## Role of Manual Annotation Used to create, test and fine-tune task definitions/guidelines. * For a task to be well-defined, several annotators must agree on classification most of the time. * If humans cannot agree, it is unlikely that a computer can do the task at all * Popular, but imperfect measurement of agreement: $$ Kappa={{Percent(Actual\_Agreement) - Prob(Chance\_Agreement)}\over{1 - Prob(Chance\_Agreement)}} $$ Used to create answer keys to score system output. * One set of measures are: recall, precision and f-score: $$Recall={{\lvert Correct \rvert}\over{\lvert Answer\_Key \rvert}}$$ $$Precision={{\lvert Correct \rvert}\over{\lvert System\_Output \rvert}}$$ $$ F\_Score={1\over{{1\over2}*({1\over{Precision}}+{1\over{Recall}})}}={2{{Precision}*{Recall}\over{Precision+Recall}}} $$ ### Manual Annotation in Supervised Statistical ML Divide the corpus into sub-corpora * A training corpus is used to acquire statistical patterns * A test corpus is used to measure system performance * A development corpus is similar to a test corpus * Systems are “tuned” to get better results on the dev corpus * Test corpora are only used infrequently to insure accuracy/fairness: The system should not be tuned to get better results * More annotated text often yield better results * Different genres may have different properties * Systems can “train” separately on different genres * Systems can “train” on one diverse corpus # Regular Expressions Formal Languages, Regular Expressions, Automata and Transducers Useful links: * [RegEx online validation tool](https://tool.chinaz.com/regex/) (Chinese) ## Formal Language = Set of Strings of Symbols A Formal Language can model a phenomenon, e.g. written English Examples: All combinations of the letters, any number of As, followed by any number of Bs, mathematical equations, all the sentences of a simplified version of written English, a sequence of musical notation (e.g., the notes in Beethoven's 9th Symphony), etc. ### What is a Formal Grammar for? A formal grammar: a set of rules that match all and only instances of a formal language. A formal grammar defines a formal language. In Computer Science, Formal grammars are used to **generate** and **recognize** formal languages (e.g., programming languages) * Parsing a string of a language involves: * Recognizing the string and * Recording the analysis showing it is part of the language * A compiler translates from language X to language Y, e.g.,This may include parsing language X and generating language Y * If all natural languages were formal languages, then Machine Translation systems would just be compilers ### A Formal Grammar Consists of #### N: a Finite set of non-terminal symbols Symbols that can be replaced by other symbols #### T: a Finite set of terminal symbols Symbols that cannot be replaced by other symbols #### R: a set of rewrite rules Replace the symbol sequence XYZ with abXzY: `XYZ → abXzY` #### S: A special non-terminal that is the start symbol Marks the start of the language ## The Chomsky Hierarchy Type0 ⊇ Type1 ⊇ Type2 ⊇ Type3 ### Type 0: No restrictions on rules Equivalent to Turing Machine, general system capable of simulating any algorithm. ### Type 1: Context-sensitive rules `αAβ → αγβ` * Greek letters = 0 or more non-terms/terms. * A = non-terminal * Rule means: replace A with γ, when A is between α and β ### Type 2: Context-free rules `A → αγβ` * Like context-sensitive, except left-hand side can only contain exactly one non-terminal Example Rule from linguistics: ![Context-free Rules](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-79597f2ff3b14500034a36eb90a70dfc639cd927%2Fchomsky-hierarchy-type-2.png?alt=media) ### Type 3: Context-free rules with restrictions Regular (finite state) grammars * `A → βa` or `A → ϵ` (left regular) * `A → aβ`, or `A → ϵ` (right regular) Like Type 2, except: * Non-terminals can precede terminals in left regular grammar * Non-terminals can follow terminals in right regular grammar * Null string is allowed Type-3 grammars generate the regular languages #### Further Simplifications Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal. The productions must be in the form `X → a` or `X → aY` where X, Y ∈ N (Non terminal) and a ∈ T (Terminal) The rule S → ε is allowed if S does not appear on the right side of any rule. ### Comparisons Type 3 grammars: Least expressive, Most efficient processors Type 0 grammars: Most expressive, Least efficient processors Complexity of recognizer for languages: * Type 0: exponential * Type 1: polynomial * Type 2: $$O(n^3)$$ * Type 3: $$O(n logn)$$ ### CL mainly features Type 2 & 3 Grammars Type 3 grammars: * Include regular expressions and finite state automata (aka, finite state machines) * The focal point of the rest of this talk * Also see [Nooj platform for NLP](http://www.nooj-association.org) Type 2 grammars: * Commonly used for natural language parsers * Used to model syntactic structure in many linguistics theories (often supplemented by other mechanisms) * Important for later talks on constituent structure & parsing ### Type 1.5 Grammars Human Language believed to be “mildly context sensitive” * Less expressive than type 1 (context sensitive) * More expressive than type 2 (context-free) Some complex dependencies cannot be expressed in context free rules, e.g. see [this](https://dash.harvard.edu/bitstream/handle/1/2026618/Shieber_EvidenceAgainst.pdf?sequence=2) Three Adjoining Grammars * * * Formalism by A. Joshi & others * May be able to handle these cases ## Regular Expressions Concatenation * If X is a regexp and Y is a regexp, then XY is a regexp * Examples: * If `ABC` and `DEF` are regexps, then `ABCDEF` is a regexp * If `AB*` and `BC*` are regexps, then `AB*BC*` is a regexp Note: Kleene \_ is explained below Disjunction * If X is a regexp and Y is a regexp, then `X | Y` is a regexp * Example: `ABC|DEF` will match either `ABC` or `DEF` Repetition * If X is a regexp then a repetition of X will also be a regexp * The Kleene Star: `A*` means 0 or more instances of A * Regexp{number}: `A{2}` means exactly 2 instances of A Disjunction of characters * `[ABC]` – means the same thing as `A | B | C` * `[a-zA-Z0-9]` – character ranges are equivalent to lists: `a|b|c|...|A|B|...|0|1|...|9` Negation of character lists/sequences * `^` inside bracket means complement of disjunction, e.g., `[^a-z]` means a character that is neither a nor b nor c … nor z Parentheses * Disambiguate scope of operators * `A(BC)|(DEF)` means `ABC` or `ADEF` * Otherwise defaults apply, e.g., `ABC|D` means `ABC` or `ABD` `?` signifies optionality * `ABC?` is equivalent to `(ABC)|(AB)` `*` indiates 1 or more * `A(BC)*` is equivalent to `A|(A(BC)+)` Special Symbols: * Period means any character, e.g., `A.*B` – matches A and B and any characters between * Carrot (`^`) means the beginning of a line, e.g., ^ABC matches ABC at the beginning of a line \[\*Note dual usage of ^ as negation operator] * Dollar sign (`$`) means the end of a line, .e.g., `[\.?!] *$` matches final punctuation, zero or more spaces and the end of a line Sets of characters: * `\w` = `[A-Za-z0-9_]` * `\W` = `[^A-Za-z0-9_]` ### Generator {% embed url="" %} RegEx Generator {% endembed %} ## Finite State Automata Devices for recognizing finite state grammars (include regexps) Two types * Deterministic Finite State Automata (DFSA): Rules are unambiguous * NonDeterministic FSA (NDFSA): Rules are ambiguous. Sometimes more than one sequence of rules must be attempted to determine if a string matches the grammar. Ways to solve this: Backtracking, Parallel Processing and Look Ahead. Any NDFSA can be mapped into an equivalent (but larger) DFSA ### DFSA ![DFSA Example for RegEx A(ab)\*ABB](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-1d27b1fb568484a37900296f7d94eda7cbe7a419%2Fdfsa-example.png?alt=media) Algorithm: ``` D-Recognize(tape, machine) pointer ← beginning of tape current state ← initial state Q0 repeat until the end of the input is reached look up (current state,input symbol) in transition table if found: set current state as per table look up advance pointer to next position on tape else: reject string and exit function if current state is a final state: accept the string else: reject the string ``` ### NDFSA ![NDFSA Example for RegEx A(ab)\*ABB](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-bd257b8412c8cf325181a40aea58f7d7eed5d227%2Fndfsa-example.png?alt=media) Algorithm: ``` ND-Recognize(tape, machine) agenda ← {(initial state, start of tape)} current state ← next(agenda) repeat until accept(current state) or agenda is empty agenda ← Union(agenda,look_up_in_table(current state,next_symbol)) current state ← next(agenda) if accept(current state): return(True) else: false ``` Accept if at the end of the tape and current state is a final state Next defined differently for different types of search * Choose most recently added state first (depth first) * Chose least recently added state first (breadth first) * Etc. # HMM POS Tagging HMM and Part of Speech Tagging. Viterbi Algorithm. Limits of Sequence Labeling. ## POS Tagger Tool {% embed url="" %} POS Tagger Tool {% endembed %} ## Penn Treebank POS Tag Set | Tag | Description | Examples | Tag | Description | Examples | | -------- | ------------------------------- | -------------- | ------- | ---------------------------- | ---------------- | | **CC** | Coordinating conjunction 并列连词 | and, or | **RB** | Adverb 副词 | very | | **CD** | Cardinal number 数 | one, 2 | **RBR** | Adverb, comparative 副词比较级 | better | | **DT** | Determiner 限定词 | the, a | **RBS** | Adverb, superlative 副词最高级 | best | | **FW** | Foreign word 外来词 | 单词 | **SYM** | Symbol 符号 | % | | **IN** | Preposition or subord. 介词或从属连词 | of, in, with | **TO** | Infinitival marker 不定式标记 | to | | **JJ** | Adjective 形容词 | big, nice | **UH** | Interjection 感叹词 | um, ah, oh, oops | | **JJR** | Adjective, comparative 形容词比较级 | bigger, better | **VB** | Verb, base form 动词原形 | go | | **JJS** | Adjective, superlative 形容词最高级 | biggest, best | **VBD** | Verb, past form 动词过去式 ed | went | | **LS** | List item marker 列表头标 | 1, 2, 3 | **VBG** | Verb, gerund form 动词现在分词 ing | running | | **MD** | Modal 情景动词 | can, should | **VBN** | Verb, past part 动词过去分词 | ran | | **NN** | Noun, singular or mass 名词单数或不可数 | book, car | **VBP** | Verb, present 动词现在时 | eat | | **NNS** | Noun, plural 名次复数 | books, cars | **VBZ** | Verb, 3rd person 动词三单 | eats | | **NNP** | Proper noun, singular 专有名词单数 | Edinburgh | **WDT** | Wh-determiner Wh-限定词 | which | | **NNPS** | Proper noun, plural 专有名次复数 | Smiths | **WP** | Wh-pronoun Wh-代词 | who | | **PDT** | Predeterminer 前置限定词 | all, both | **WP$** | Possessive wh-pron. Wh-物主代词 | whose | | **POS** | Possessive ending 所有格后缀 | 's | **WRB** | Wh-adverb Wh-副词 | how | | **PRP** | Personal pronoun 人称代词 | I, you, he | **PU** | Punctuation 标点 | ",", "." | | **PRP$** | Possessive pronoun 物主代词 | my, your, his | | | | ![Penn Treebank POS Tags](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-9821b5782c4d4250042fbf442ab8963cc242bab9%2Fpenn-treebank-tags.png?alt=media) #### SBAR Clause introduced by a (possibly empty) subordinating conjunction. Examples: 1. \[**S** I can't believe \[**SBAR** that John went without me.]] 2. \[**S** I can't believe \[**SBAR** \_\_ John went without me.]] ## HMM Viterbi Algorithm ### Training States **Transition Probability / Prior Probability** $$Trans\_Prob(TagA \rightarrow TagB) = {{Count(TagB\_following\_TagA)}\over{Count(TagA)}}$$ **Emission Probability / Likelihood** $$Emis\_Prob(TokenA, TagA) = {{Count(TokenA\_being\_TagA)}\over{Count(TagA)}}$$ ### Viterbi Algorithm Each step: $$Step\_Prob(TokenA, TagA) = max\[Step\_Prob(Last\_Token, TagX) \* Trans\_Prob(TagX, TagA)] \* Emis\_Prob(TokenA, TagA)$$ ### Example: Fish sleep. #### Transition Probability ![Transition Probability for "Fish sleep."](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fjgg2BWt98NBb9clgK2AM%2Fimage.png?alt=media\&token=0cc5a236-950a-4ef0-a91e-c27dee877b7e) #### Emission Probability $$Emis\_Prob(fish, noun)={8\over{8+2}}=0.8$$ $$Emis\_Prob(fish, verb)={5\over{5+5}}=0.5$$ $$Emis\_Prob(sleep, noun)={2\over{8+2}}=0.2$$ $$Emis\_Prob(sleep, verb)={5\over{5+5}}=0.5$$ #### Steps ![Steps result for "Fish sleep."](https://1251386145-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FhlVpDn7SdvOjFjiV7ezN%2Fuploads%2Fgit-blob-281bcb253e8c8ae66ac5e5b879fecda713135643%2Fhmm-viterbi-example-steps.png?alt=media) # Information Retrieval Information Retrieval and Related Applications. TF/IDF, Cosine Similarity. ## TF/IDF ### Term Frequency (TF) TF: number of times term t occurs in document (or alternative: number of terms divided by length of document) $$TF(t, d)=Count(times\ of\ term\ t\ appearing\ in\ d)$$ ### Inverse Document Frequency (IDF) IDF: logarithm of number of documents (in corpus) divided by number of documents containing term t $$IDF(t)=\log{{Count(documents\ in\ total)}\over{Count(documents\ containing\ term\ t)}}$$ ### TF-IDF $$TF\_IDF(t, d)=TF(t, d) \* IDF(t)$$ ## Cosine Similarity Cosine of the Angle Between the Vectors. Range is \[0, 1]. The higher the value, the more similar the vectors. $$Cosine(v1, v2) = \frac{v\_1 \cdot v\_2}{\sqrt{{v\_1}^2} \cdot \sqrt{{v\_2}^2}}$$ ### Example $$v1 = \[0, 5, 0, 5, 0]$$ $$v2 = \[0, 7, 0, 9, 0]$$ $$Cosine(v1, v2) = {{0*0+5*7+0*0+5*9+0\*0}\over{\sqrt{0^2+5^2+0^2+5^2+0^2}+\sqrt{0^2+7^2+0^2+9^2+0^2}}} = 0.992$$ # Constituent Structure Distribution of Words in Sentences: N-grams, Phrase Structure Syntax and Parsing ## unigram Probability of each token chosen randomly (and independently of other tokens) $$unigram(t) = {Count(times\ t\ appearing)\over{Count(total\ word\ appearings)}}$$ ### Markov Assumption Probability of each token chosen randomly (and independently of other tokens) ## bigram Probability of a token given the previous token $$bigram(t, t\_{previous}) = {{Count({t\_{previous}}\rightarrow{t})}\over{Count(t\_{previous})}}$$ ### Example ```python Count(the) = 69_971 Count(the -> same) = 628 bigram(same, the) = count(the -> same) / count(the) = 628 / 69_971 = 0.0898 ``` ### Additional Steps 1. Include probability that a word occurs at the beginning of a sentence, i.e. bigram(the, START) 2. Include probability that a token occurs at the end of a sentence, e.g. bigram(END, .) 3. Include non-zero probability for case when an unknown word follows a known one. ### Backoff Model If a bigram has a zero count, "backoff" (use) the unigram of the word. That is to replace `bigram(current_word, previous_word)` with `unigram(current_word)`. ### Markov Assumption Probability of a word depends only on the previous word. ## Trigrams, 4-grams, N-grams ### Trigram Probability $$trigram(t, t\_{-1}, t\_{-2})={Count({t\_{-2}}\rightarrow{t\_{-1}}\rightarrow{t})\over{Count({t\_{-2}}\rightarrow{t\_{-1}})}}$$ Example: `count(the -> same -> as) / count(the -> same)` ### 4-gram Probability $$fourgram(t, t\_{-1}, t\_{-2}, t\_{-3})={Count({t\_{-3}}\rightarrow{t\_{-2}}\rightarrow{t\_{-1}}\rightarrow{t})\over{Count({t\_{-3}}\rightarrow{t\_{-2}}\rightarrow{t\_{-1}})}}$$ Example: `count(the -> same -> as -> an) / count(the -> same -> as)` ### N-gram Probability $$ngram(t, t\_{-1}, ..., t\_{-n+1})={Count({t\_{-n+1}}\rightarrow{...}\rightarrow{t\_{-1}}\rightarrow{t})\over{Count({t\_{-n+1}}\rightarrow{...}\rightarrow{t\_{-1}})}}$$ ### Markov Assumptions Trigram Model: probability of a word depends only on the previous two words. N-gram Model: probability of a word depends only on the previous N-1 words. Probability of a sentence = Product of probabilities of each word. ## Noun Phrases and Noun Groups Both can have left modifiers. Only noun phrases can have right modifiers. * A noun group consists of: left modifiers of the head noun and the head noun * We will assume that all punctuation and coordinate conjunctions are outside of a noun group # Named Entities Shallow Parsing, Named Entities and Machine Learning # Overview ## Overview | Course Code | CSCI-GA.1170-001 | | ----------- | ---------------- | | Professor | Chee Yap | | Email | | ## Useful links * [Symbolab Online Math Solver](https://www.symbolab.com/) * [Online basic master theorem solver](https://www.nayuki.io/page/master-theorem-solver-javascript) ### Grading 10 Homework assignments (1 per week). A midterm exam and a final project. | Component | Weight | | -------------------------------- | ------ | | In-class Quizzes/Attendence/Misc | 5% | | Homework | 30% | | Midterm | 25% | | Final Exam | 40% | # Introduction Outline of Algorithmics ## Exponent rule $$ \begin{gather\*} (a^b)^c = a^{bc} \end{gather\*} $$ ## Log rule $$ \begin{gather\*} c^{\log\_a(n)} = n^{\log\_a(c)} \end{gather\*} $$ ## Asymptotics | Name | Notation | Rough Meaning | Definition | In-fix Notation | | ----------- | --------------- | ------------- | ----------------------------------------------- | --------------- | | big-Oh | $$g=O(f)$$ | $$g \le f$$ | $$(\exists C > 0)\[C f \ge g \ge 0(e.v.)]$$ | $$g \preceq f$$ | | big-Omega | $$g=\Omega(f)$$ | $$g \ge f$$ | $$(\exists C > 0)\[C g \ge f \ge 0(e.v.)]$$ | $$g \succeq f$$ | | Theta | $$g=\Theta(f)$$ | $$g = f$$ | $$(\exists C > 1)\[C^2 f \ge C g \ge 0(e.v.)]$$ | $$g \asymp f$$ | | small-oh | $$g=o(f)$$ | $$g \ll f$$ | $$(\forall C > 0)\[C f \ge g \ge 0(e.v.)]$$ | $$g \ll f$$ | | small-omega | $$g=\omega(f)$$ | $$g \gg f$$ | $$(\forall C > 0)\[C g \ge f \ge 0(e.v.)]$$ | $$g \gg f$$ | ![Asymptotics Notations](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-d59da137de1682022596b9baf00e99cd5c95e64a%2Faymptotics-table.png?alt=media) ## Stirling's Approximation Original: $$\sqrt{2\pi n}({n \over e})^n e^{1\over{12n + 1}} < n! < \sqrt{2\pi n}({n \over e})^n e^{1\over{12n}}$$ $$log(n!) = n \log(n) - n + \Theta(\log(n))$$ Further simplification: $$log(n!) = \Theta(n \log(n))$$ A possible transformation: $$n! = \Theta(e^{n \log(n)})$$ ## Comparison Tree Example: Merge $$x\_1 < x\_2$$ and $$y\_1 < y\_2 < y\_3 < y\_4$$. ![Decision Tree Example](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-81a9506e4b2cee4fa4eba32a58d1f17b300efe63%2Fdecision-tree.png?alt=media) ### Hasse Diagram The lower the smaller, circle(o) for x, cross(×) for y. ![Hasse Diagram Example](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-f9a48203bb5bd8e9794818ac7b58f2f0bd54e56c%2Fhasse-diagram.png?alt=media) # Recurrences Separable form for recurrence relation: $$ \begin{gather\*} T(n) = G(n, T(n\_1), ..., T(n\_k)) \end{gather\*} $$ where $$G(x\_0, x\_1, ..., x\_k)$$ is a function in $$k+1$$ variables and each $$n\_i (i=1,...,k)$$ is a function of $$n$$ that is strictly less than $$n$$. **Fibonacci sequence** is defined by the recurrence relation: $$ \begin{gather\*} F(n) = F(n-1) + F(n-2) \end{gather\*} $$ For this, we have $$k=2, n\_1=n-1, n\_2=n-2$$ $$ \begin{gather\*} G(n, x, y) = x + y \end{gather\*} $$ **Merge sort** complexity: $$ \begin{gather\*} T(n) = n + 2T(n/2) \end{gather\*} $$ For this, we have $$k=1, n\_1=n/2$$ $$ \begin{gather\*} G(n, x) = n + 2x \end{gather\*} $$ ## Rote Method {% hint style="info" %} Related homework questions: h2-Q7 {% endhint %} ### EGVS method 4 stages: **E**xpand, **G**uess, **V**erify and **S**top-and-Sum. **Example:** $$T(n) = 2T(n/2) + n$$ 1. Expand: $$ \begin{align\*} T(n) &= 2T(n/2) + n \ &= 2 (2 T(n/4) + (n/2)) + n \ &= 4 T(n/4) + 2n \ &= 4 (2T(n/8) + (n/4)) + 2n \ &= 8T(n/8) + 3n \ &= \dots \end{align\*} $$ 2. Guess: $$ \begin{gather\*} T(n) = 2^i T({n\over{2^i}}) + i n \end{gather\*} $$ 3. Verify: (use natural induction) Base case: $$T(n)\_{i=1} = 2T(n/2) + n$$ holds Inductive step: Assume $$T(n)*{i=k}$$ holds, the goal is to prove $$T(n)*{i=k+1}$$ also holds. $$ \begin{align\*} T(n) &= 2^k T({n\over{2^k}}) + k n \ &= 2^k (2 T({n\over{2^{k+1}}}) + {n\over{2^k}}) + k n \ &= 2^{k+1} T(n/2^{k+1}) + （k+1) n \end{align\*} $$ Therefore, this proves $$T(n)\_{i=k+1}$$ also holds. Combining the base case and the inductive step we verified that $$T(n) = 2^i T({n\over{2^i}}) + i n$$. 4. Stop: We can pick $$i = \lfloor {\lg n} \rfloor$$ for stopping, then $$0 < {n\over{2^i}} \le 2$$. By DIC, choose $$T(n) = 0$$ for all $$n \le 2$$. Therefore, for $$n > 1$$, $$ \begin{gather\*} T(n) = \lfloor {\lg n} \rfloor n \end{gather\*} $$ ### Basic Sums Other kinds of sums are often reduces to the following forms. #### Arithmetic Sums $$ \begin{gather\*} S^k\_n := \sum^n\_{i=1}{i^k} \end{gather\*} $$ Solution: $$S^k\_n = \Theta(n^{k+1})$$ #### Geometric Sums When $$x \ne 1$$, $$ \begin{gather\*} S\_n(x) := \sum^{n-1}\_{i=0}{x^i} \end{gather\*} $$ Solution: $$S\_\infty = {{x^n - 1}\over{x - 1}}$$ #### Infinite Geometric Series When $$\lvert{x}\rvert < 1$$, $$ \begin{gather\*} S\_{\infty}(x) := \sum^{\infty}\_{i=0}{x^i} \end{gather\*} $$ Solution: $$S\_{\infty}={1\over{1 - x}}$$ #### Harmonic Series $$ \begin{gather\*} H\_n := 1 + {1\over{2}} + {1\over{3}} + \dots + {1\over{n}} \end{gather\*} $$ Solution: $$H\_n = ln(n) + g(n)$$ where $$0 < g(n) < 1$$. ## Summation Techniques ### Growth Types {% hint style="info" %} Related homework questions: h3-Q1 {% endhint %} #### Polynomial Type A real function $$f$$ is **polynomial-type** if $$f$$ is non-decreasing (ev.) and there is some $$C > 1$$ such that: $$ \begin{gather\*} f(x) \le C f(x/2)\ (ev.) \end{gather\*} $$ #### Increasing Exponential Type $$f$$ increases exponentially if there exists real numbers $$C > 1$$ and $$k > 0$$ such that: $$ \begin{gather\*} f(x) \ge C f(x - k)\ (ev.) \end{gather\*} $$ #### Decreasing Exponential Type $$f$$ decreases exponentially if there exists real numbers $$C > 1$$ and $$k > 0$$ such that: $$ \begin{gather\*} f(x) \le f(x - k) / C\ (ev.) \end{gather\*} $$ #### Lemma 8: Closed Properties (a) **Polynomial-type** functions are closed under addition, multiplication, and raising to any positive power $$a > 0$$. (b) **Exponential-type** functions $$f$$ are closed under addition, multiplication, and raising to any power $$a$$. In case $$a > 0$$, the function $$f^a$$ will not change its subtype (increasing or decreasing). In case $$a < 0$$, the function $$f^a$$ will change its subtype. (c) If $$f$$ is polynomial-type and $$\lg f$$ is non-decreasing then $$\lg f$$ is also polynomial-type. If $$f$$ is exponential-type and $$a > 1$$ then so is $$a ^ f$$. ### Summation Rules by Growth Type {% hint style="info" %} Related homework questions: h3-Q2 {% endhint %} Theorem 6: Summation Rules $$ S\_f(n) = \Theta \begin{cases} n f(n) & \text{if f is polynomial-type,} \ f(n) & \text{if f is increasing exponentially,} \ 1 & \text{if f is decreasing exponentially.} \end{cases} $$ Examples: * Polynomial Sums: $$ \sum^n\_{i\ge{1}}{i \log(i)} = \Theta(n^2 \log(n)), \sum^n\_{i\ge{1}}{\log(i)} = \Theta(n \log(n)), \sum^n\_{i\ge{1}}{i^a} = \Theta(n^{a+1})(a\ge{0}). $$ * Exponentially Increasing Sums: $$ \sum^n\_{i\ge{1}}{b^i} = \Theta(b^n)(b\ge{0}), \sum^n\_{i\ge{1}}{i^{-5}2^{2^i}} = \Theta(n^{-5}2^{2^n}), \sum^n\_{i\ge{1}}{i!} = \Theta(n!). $$ * Exponentially Decreasing Sums: $$ \sum^n\_{i\ge{1}}{b^{-i}} = \Theta(1)(b\ge{0}), \sum^n\_{i\ge{1}}{i^2 i^{-i}} = \Theta(1), \sum^n\_{i\ge{1}}{i^{-i}} = \Theta(1). $$ ![More Examples](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-ef58671ba26829f81559fa116a4d34de5998a7e9%2Fsummation-rules-examples.png?alt=media) ## Transformation Techniques ### Domain Transformation {% hint style="info" %} Related homework questions: h3-Q3 and h3-Q4(combining range transformation) {% endhint %} Example: Consider: $$ \begin{gather\*} T(N) = T(N/2) + N \end{gather\*} $$ We define $$t(n) := T(2^n) \text{or} N = 2^n$$. This transforms the original N-domain into the n-domain: $$ \begin{align\*} T(2^n) &= T(2^n/2) + 2^n \ T(2^n) &= T(2^{n-1}) + 2^n \ t(n) &= t(n-1) + 2^n \end{align\*} $$ We get this standard form. By DIC, we choose the boundary condition $$t(n) = 0$$ for all $$n \le 0$$. We get sum: $$ \begin{gather\*} t(n) = \sum^n\_{i\ge{0}}{2^n}=\Theta(2^n) \end{gather\*} $$ Because we have $$n = \lg N$$, $$ \begin{gather\*} T(N) = \Theta(N) \end{gather\*} $$ {% hint style="info" %} On Lecture II Page 46, L1120, we get the exact sum by transforming the descending sum to the ascending sum. {% endhint %} ### Range Transformation {% hint style="info" %} Related homework questions: h3-Q4(combining domain transformation) {% endhint %} Example: $$ \begin{gather\*} T(n) = 2T(n-1) + n \end{gather\*} $$ We define $$t(n) := {T(n)\over{2^n}}$$, then divide the both sides of the original equation by $$2^n$$. $$ \begin{align\*} {T(n)\over{2^n}} &= 2{T(n-1)\over{2^n}} + {n\over{2^n}} \ {T(n)\over{2^n}} &= {T(n-1)\over{2^{n-1}}} + {n\over{2^n}} \ t(n) &= t(n-1) + {n\over{2^n}} \end{align\*} $$ We get this standard form. By DIC, we choose the boundary condition $$t(n) = 0$$ for all $$n \le 0$$. We get sum: ($$\sum^n\_{i\ge{0}}{n\over{2^n}}$$ is exponentially decreasing) $$ \begin{gather\*} t(n) = \sum^n\_{i\ge{0}}{n\over{2^n}}=\Theta(1) \end{gather\*} $$ Because $$t(n) = {T(n)\over{2^n}}$$, $$ \begin{gather\*} T(n) = \Theta(2^n) \end{gather\*} $$ ## Master Theorem {% hint style="info" %} Related homework questions: h2-Q8 {% endhint %} **Master recurrence:** $$ \begin{gather\*} T(n) = a T(n/b) + d(n) \end{gather\*} $$ where $$a > 0$$, $$b > 0$$ are real constants and $$d(n)$$ the driving/forcing function. **Watershed constant** $$w = \log\_b(a)$$ **Watershed function** $$W(n) = n^w = n^{\log\_b(a)}$$ > Useful link: [Online basic master theorem solver](https://www.nayuki.io/page/master-theorem-solver-javascript) ### Master Theorem Theorem 10: Master Theorem on Lecture II Page 51, L1207 $$ \begin{gather\*} T(n) = \Theta \begin{cases} n^w, & \text{if } d(n) = O(n^{w-\epsilon}) \text{ for some } \epsilon > 0, & CASE(-) \ n^w \log(n), & \text{if } d(n) = \Theta(n^w), & CASE(0) \ d(n), & \text{if } a\cdot d(n/b) \le c\cdot d(n) \text{ for some } 0 < c < 1. & CASE(+) \ \end{cases} \end{gather\*} $$ ### Extended Master Theorem Theorem 12: Extended Master Theorem on Lecture II Page 54, L1282 $$ \begin{gather\*} T(n) = \Theta \begin{cases} d(n), & \text{if } a\cdot d(n/b) \le c\cdot d(n) \text{ for some } 0 < c < 1. & CASE(+) \ W(n)\log\log n, & \text{if } d(n) = \Theta(W(n)\log^c(n)) \text{ for } c = -1, & CASE(1) \ W(n)\log^{c+1}(n), & \text{if } d(n) = \Theta(W(n)\log^c(n)) \text{ for } c > -1, & CASE(0) \ W(n), & \text{if } d(n) = O(W(n)\log^c(n)) \text{ for } c < -1. & CASE(-) \ \end{cases} \end{gather\*} $$ ## Multi-term Master Recurrences {% hint style="info" %} Related homework questions: h3-Q5 {% endhint %} $$ \begin{gather\*} T(n) = d(n) + \sum\_{i=1}^{k}{a\_i T(n/b\_i)} \end{gather\*} $$ where $$a\_i > 0$$ and $$b\_1 > b\_2 > \cdots > b\_k > 1$$ are real constants. **Watershed constant** It is the real number $$\alpha$$ such that: $$ \begin{align\*} 1 = \sum\_{i=1}^{k}{a\_i\over{b\_i^{\alpha}}} \end{align\*} $$ It clearly exists and is unique. ### Multi-term Master Theorem Theorem 15: Multi-term Master Theorem on Lecture II Page 62, L1483 $$ \begin{gather\*} T(n) = \Theta \begin{cases} n^{\alpha}, & \text{if } d(n) = O(n^{w-\epsilon}) \text{ for some } \epsilon > 0, & CASE(-) \ n^w, & \text{if } d(n) = \Theta(n^w), & CASE(0) \ d(n), & \text{if } \sum^k\_{i=1}{a\_i\cdot d(n/{b\_i})} \le c\cdot d(n), & CASE(+) \ \end{cases} \end{gather\*} $$ ## Real Induction {% hint style="info" %} Related homework questions: h2-Q9 {% endhint %} # Search Trees ## Binary Search Trees (BST) {% hint style="info" %} Related homework questions: h3-6 {% endhint %} ### Binary Tree A binary tree $$T$$ is a set $$N$$ of nodes where each node $$u\_0$$ has two pointers, $$u\_0$$.left and $$u\_0$$.right. The size of $$T$$ is $$|N|$$. **Complete Binary Tree** Every level of the tree is completely filled, except possibly the last level. Moreover, the last level has to be filled from left to right. If a complete binary tree is also complete on the last level, then it is called a **perfect** binary tree. **Height of binary trees** Minimum number of nodes in a binary tree of height $$h$$: $$ \begin{gather\*} \mu(h) = h + 1 \end{gather\*} $$ Maximum number of nodes in a binary tree of height $$h$$: $$ \begin{gather\*} M(h) = 2^{h+1} - 1 \end{gather\*} $$ The minimum height of binary trees with $$n$$ nodes: $$ \begin{gather\*} h \ge \lg(n + 1) - 1 \end{gather\*} $$ ### Binary Search Tree A binary tree is a binary search tree if each node $$u \in T$$ has a field $$u$$.key that satisfies the BST property: $$ \begin{gather\*} u\_L.key < u.key \le u\_R.key \end{gather\*} $$ ## AVL Trees {% hint style="info" %} Related homework questions: h3-7, h3-8 {% endhint %} An AVL tree is a binary search tree where the left subtree and right subtree at each node differ by at most 1 in height. ### Balance Factor More generally, define the **balance** of any node $$u$$ of a binary tree to be the height of the left subtree minus the height of the right subtree: $$ \begin{gather\*} b(u) = h(u.left) - h(u.right) \end{gather\*} $$ ### Insertion and Deletion Algorithms **UPDATE PHASE**: Insert or delete as we would in a binary search tree. **REBALANCE PHASE**: Let $$x$$ be parent of the node that was just inserted, or just cut during deletion, in the UPDATE PHASE. THe path from $$x$$ to the root will be called the **rebalance path**. We now move up this path, rebalancing nodes along this path as necessary. Let $$u$$ be the first unbalanced node we encounter along the rebalance path from bottom to top. It is clear that $$u$$ has a balance of $$\pm 2$$. The situation is illustrated below: ![Figure 16: Node u is unbalanced after insertion or deletion](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-bb72491fcc2c2519b6d01515ee83e90724281c9a%2Favl-situation.png?alt=media) #### Insertion Rebalancing CASE (I.a): $$h\_L = h$$ and $$h\_R = h - 1$$. This means that the inserted node is in the left subtree of $$v$$. In this case, we rotate $$v$$, the result would be balanced. Moreover, the height of $$u$$ is now $$h+1$$. We call this the "single-rotation" case. ![Figure 17: AVL Insertion: CASE (I.a)](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-14cdc7cc847d9986ef9bb35a4bb1a19ae2396200%2Favl-insertion-case-i-a.png?alt=media) CASE (I.b): $$h\_L = h - 1$$ and $$h\_R = h$$. This means that the inserted node is in the right subtree of $$v$$. In this case, let us expand the subtree $$D$$ and let $$w$$ be its root. The two children of $$w$$ will have heights $$h - \delta$$ and $$h - \delta'$$ where $$\delta, \delta' \in {1, 2}$$. Now a double-rotation at $$w$$ results in a balanced tree of height $$h+1$$ rooted at $$w$$. ![Figure 17: AVL Insertion: CASE (I.b)](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-aebf6ae404298e5e5e7c0f3fe260e697916043de%2Favl-insertion-case-i-b.png?alt=media) #### Deletion Rebalancing CASE (D.a): $$h\_L = h$$ and $$h\_R = h - 1$$. This is like case (I.a) and treated in the same way, namely a single rotation at $$v$$. Now $$u$$ is replaced by $$v$$ after this rotation, and the new height of $$v$$ is $$h+1$$. Now $$u$$ is AVL balanced. However, since the original height is $$h + 2$$, there may beb unbalanced node further up the rebalance path. Thus, this is a non-terminal case. CASE (D.b): $$h\_L = h - 1$$ and $$h\_R = h$$. This is like case (I.b) and treated in the same way, namely a double rotation at $$w$$. Again, this is a non-terminal case. CASE (D.c): $$h\_L = h\_R = h$$. This case is new, we simply rotate at $$v$$. We check that $$v$$ is balanced and has height $$h+2$$. Since $$v$$ is in the place of $$u$$ which has height $$h+2$$ originally, we can safely terminate the rebalancing process. ![Figure 20: AVL Deletion: CASE (D.c) rotate(v)](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-f509594936bc209b9a3b30c60c9de9f04f07a549%2Favl-deletion-case-d-c.png?alt=media) ## Ratio/Weight Balanced Trees {% hint style="info" %} Related homework questions: h4-3 {% endhint %} **Extended size**: $$ \begin{gather\*} esize(u) = \begin{cases} 1 & \text{if } u = nil \ esize(u.left) + esize(u.right) & \text{if } u \neq nil \end{cases} \end{gather\*} $$ **Ratio**: $$ \begin{gather\*} ratio(u) := {esize(u.left) \over {esize(u.right)}} \end{gather\*} $$ ### ρ-ratio $$ \begin{gather\*} \rho < ratio(u) < 1/\rho \end{gather\*} $$ ### Insertion and Deletion Algorithms Example: $$ho = 1/3$$ **UPDATE PHASE**: Insert or delete as we would in a binary search tree. In insertion, this results in a new leaf $$x$$ in $$T$$. If deletion, we will physically "cut" the leaf $$x$$ from $$T$$. **REBALANCE PHASE**: Let $$u$$ be the parent of $$x$$. Clearly, every node that is not RB balanced must lie on the root-path of $$u$$. We therefore move up this path, rebalancing any such node. ``` Rebalance(u) While (u != u.parent) u <- Rebalance-Step(u) u <- u.parent ``` ``` Rebalance-Step(u) If (ratio(u) >= 3) v <- u.left If (ratio(v) >= 3/5) Return(rotate(v)) Else \\ ratio(v) < 3/5 Return(double-rotate(v.right)) elif (ratio(u) <= 1/3) v <- u.right If (ratio(v) <= 3/5) Return(rotate(v)) Else \\ ratio(v) > 3/5 Return(double-rotate(v.left)) else Return(u) ``` ## Generalized B-Trees: (2,3)-trees {% hint style="info" %} Related homework questions: h4-1, h4-2 {% endhint %} An (a,b)-tree is a rooted, ordered tree with the following structural constraints: * Depth property: All leaves are at the same depth. * Degree bound: Let $$m$$ be the number of children of an internal node $$u$$. This is also known as the **degree** of $$u$$. In general, we have the bounds $$a \le m \le b$$. The root is an exception, with the bound $$2 \le m \le b$$. ### (a,b)-search trees > Lecture Note 3, Page 80. An (a,b)-search tree is an (a,b)-tree whose nodes are organized as an **external search tree**, which means items are only stored in leaves. Leaves are also called **external nodes**. ![Figure 35: Organization of external and internal nodes in (a,b)-search trees](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-f1e33b0d697cde0589e73e402f17847a16698ee6%2Fa-b-search-tree-organization.png?alt=media) Leaves: $$(a', b')$$ where $$1 \le a' \le b'$$. Default assumption for leaves: $$a' = b' = 1$$. #### Reorganization of nodes For an internal node $$u$$, * $$u$$ is **overfull** if its degree is $$b+1$$. * $$u$$ is **underfull** if its degree is $$a-1$$. **Simple Remedy**: borrow or donate children ![Figure 36: Borrowing or donating as simple remedy](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-624ff315e3a3378b77cf334231538ec2056ecbe1%2Fa-b-search-tree-borrow-and-donate.png?alt=media) **Strong Remedy**: when simple remedy fails. * Split an overfull node Figure 35: Splitting an overfull node * Merge an underfull node Figure 37: Merging an underfull node #### Split-Merge Inequality $$ \begin{gather\*} a \le {{b + 1} \over {2}} \end{gather\*} $$ This is a combination of split inequality ($$a \le \lfloor{{b+1}\over{2}}\rfloor$$) and merge inequality ($$a \le {{b + 1} \over {2}}$$). Since $$a$$ and $$b$$ are integers, these two are equivalent. # Dynamic Programming ## LCS [Visualization](https://www.cs.usfca.edu/~galles/visualization/DPLCS.html) # Shortest Paths ## Dijkastra Shortest path between two certain vertices. ![Dijkastra Example](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-2fcb6f1469a69f511d2422ae305cc31fe53c319a%2Fdijkastra.png?alt=media) Number of decreaseKeys is 14. All updates except Stage 0 and the circled ones. # NP Complete ## Polynomial Reducibility When A is polynomial-reducible to B, we denote this relationship as: $$ A \leqslant^P B $$ To prove this relationship, we need: * Construct an input $$I\_B$$ for B according to input $$I\_A$$ of A (be creative, your goal is the next bullet point). Get the result of B: $$O\_B$$. * Show that we can get the desired output $$O\_A$$ from $$O\_B$$. # Overview ## Grading | Component | Weight | | ----------------------- | ------ | | Homework assignments | 15% | | Project | 30% | | Programming assignments | 30% | | Final Exam (take home) | 25% | # CUDA ## Allocating Device Memory `cudaMalloc(LOCATION, SIZE)` * LOCATION: Memory location on Device to allocate memory, an address in the GPU's memory * SIZE: number of bytes to allocate De-Allocate: `cudaFree()` ## Copy Data between Host and Device `cudaMemory(DST, SRC, NUM_BYTES, DIRECTION)` * DST: An address of the memory to copy into * SRC: An address of the memory to copy from * NUM\_BYTES: N \* sizeof(type) * DIRECTION: * cudaMemcpyHostToDevice * cudaMemcpyDeviceToHost ## Define the Kernel ```cpp __global__ void kernel(int *d_out, int *d_in) { d_out[0] = d_in[0]; } ``` ### Thread Index In kernel definition, built-in variable `threadIdx` is accessible to get thread index within the thread block for each thread. It has 3 dimensions: `threadIdx.x`, `threadIdx.y` and `threadIdx.z`. ### Block Index Index of a block: `blockIdx.x`, `blockIdx.y` and `blockIdx.z`. ### Indexing within Grid ```cpp i = threadIdx.x + blockIdx.x * blockDim.x; ``` ### \_\_syncthreads To explicitly synchronize all threads (adding barriers), use `__syncthreads.` ```cpp int temp = a[i + 1]; __syncthreads; a[i] = temp; __syncthreads; ``` ## Launch the Kernel ```cpp int *h_c, *d_c; // Allocate memeory on the device cudaMalloc((void**)&d_c, sizeof(int)); // Copy content from host to device cudaMemcpy(d_c, h_c, sizeof(int), cudaMemcpyHostToDevice); // Launch the kernel dim3 grid_size(1); dim3 block_size(1); kernel<<>>(...); // Force host to wait on the completion of the kernel cudaDeviceSynchronize(); // Copy data back to host cudaMemcpy(h_c, d_c, sizeof(int), cudaMemcpyDeviceToHost); // Clean up memory cudaFree(d_c); free(h_c); ``` # Final Exam Prep: Concepts #### S22.1a: **All the threads in a warp share the same front-end (i.e. fetch, decode, etc). State two reasons as to why did GPU designers decide to do so instead of having a front end for each thread. That is, one front-end for each SP?** * This will save room in the chip for more SPs and hence more potential parallelism. * This will reduce the cost of the hardware as we will need fewer front ends which are expensive. * All threads are executing the same code. So, it makes sense to reduce the front-end hardware. #### S22.1b: **Why did NVIDIA GPU designers decide to group several SPs in an SM?** * It is useful, in many applications, for threads executing on SPs to exchange data in a fast way and to synchronize. * It is prohibitively expensive to have a full connection among all the SPs in the chip (we have hundreds of SPs) * Also, it leads to poor performance if we let the SPs communicate through the global memory * Therefore, a middle ground is to group SPs in clusters called SMs and have fast communication among SPs in the same SM. #### S22.1c: **If the warp concept did not exist, what will be the implications on GPU programming? State three implications and, for each one, explain in 1-2 lines.** * The programmer will need to know the number of SPs per SM because the number of threads per block cannot exceed that number. * Without warps, we will need front-end for each SP. So, no need to have number of threads per block to be multiple of warp-size. * No need to worry about thread-divergence. #### S22.1d: **Suppose we want to implement vector additions on multi-GPU systems because the two vectors we want to add are huge. Each thread will be responsible for few hundred elements. Which is more beneficial: using the traditional `cudaMalloc()` and `cudaMemcpy()`? or using unified memory? And why?** Unified memory is better here \[4], for several reasons\[6, 2 reasons are enough with 3 points each]: * Data will not need to move several times among different GPUs because each thread will be working, exclusively, on subset of elements. * Programming is easier. * Since the vectors are huge. There is a chance we run out of memory. With unified memory, you can exceed the capacity of the device’s memory and use the system virtual memory. #### S22.2c: Can more than one grid exist in the same GPU at the same time? Explain in 1-2 sentences. Yes, it can happen \[3]. A grid is a kernel in execution. There may be more than one kernel (belonging to the same process or different processes) in execution at the GPU at the same time \[2]. #### S22.2d: Even though registers are much faster than shared memory, it is sometimes more beneficial to put data in shared memory. When does this happen? If the data will be shared among threads of the same block, then using shared memory is better \[3] because it reduces the trips to global memory and hence may enhance the performance \[2]. #### F21.2a: **If the total number of threads in the whole grid is t, is it always the case that the total number of warps created in the whole grid is ceil(t/32)? Assume warp size = 32 threads. Explain in no more than 2-3 lines.** No, 32 threads can be divided into two blocks (hence two warps) vs being assigned to one block (hence one warp). #warps = #blocks \* #warps per block = #blocks \* ceil(t/#blocks/32). #### F21.2b: **State two advantages of warps.** * Reduces the cost of GPU hardware. * Decouples the number of threads per block from number of SPs per SM. **F21.2c: What is needed for GPUs to be standalone machines and not just co-processors to CPUs?** Nothing, the GPU can be a standalone chip if we write an OS that runs on GPU. The performance will be bad though because an OS is not a GPU friendly code. #### F21.2d: **Do you think there is any kind of virtual memory in GPUs? Justify your answer in 1-2 lines.** Yes, there is. Example: Two blocks assigned to the same SM cannot see each other’s memory. Also, local memories for different threads are isolated from each other. #### F20.3 The GPU global memory is connected to the device itself (i.e. the GPU) and to the system memory (i.e. the one connected to the CPU). #### F20.3a: **Which connection is slower? And why do you think it is slower?** * The one connecting the global memory to system memory is slower. * The main reason for that is that GPU companies have to follow the industry standard (e.g. PCIe) in order for their GPUs to work with other vendors of CPUs and motherboards. Otherwise, GPU vendors could have built faster buses (e.g. NVLINK). #### F20.3b: **The GPU global memory and the system memory are both built from the same technology, yet, they are different. State two main differences between the GPU global memory and the system memory.** * System memory is designed for latency while GPU memory is designed for bandwidth. * GPU memory is, on average, smaller in size than system memory. * The bus connecting system memory to CPU follows the machine architecture (64-bit for the majority of machines nowadays) which GPU memory has much wider buses. #### F19.1: **Can some threads of a warp finish before other threads of that same warp? Explain.** Yes, if, for example, there is an if-else and there is nothing after the else-part. So, the threads in the if-part will finish before those of the else-part. There must be branch divergence. #### F19.2: **If we take a snapshot of a warp during execution we may not always find 32 threads executing. State three scenarios that may cause this to happen.** * Number of threads in a block is not multiple of 32 * Branch-divergence * Threads finished earlier in the warp. #### F19.3: **State one reason you will use unified memory in a multi-GPU system. And state another reason you will use the traditional \`cudaMemcpy()\` instead.** * Use unified memory: Easier programming and data are not shared among different GPUs. So, unified memory will automatically move the data to the needed GPU. * Use traditional `cudaMemcpy()`: Some data may need to be shared among multiple GPUs. So, unified memory may move the data back and forth. But, if done by hand, you can duplicate the data and/or use streams to overlap data movement and computation. #### F19.5: a. Two blocks corresponding to kernels from different processes can simultaneously exist in the same SM: ✅ b. Two blocks corresponding to kernels from different threads can simultaneously exist in the same SM: ✅ c. An L1 cache miss always results in coalesced global memory access: ❌ d. The concept of streams is important for performance only but has nothing to do with correctness of execution: ❌ e. If a thread in a grid has two local variables: int x; and int a\[100]; * Access to x is faster than access to a. f. In a multi-GPU system, you can have two blocks corresponding to the same kernel but executing on two different GPUs: ❌ g. A computation intensive application with mostly independent computations is for sure a GPU friendly application: ❌ e. In multi-GPU system, if there is a small piece of data that is needed by all the GPUs: Traditional cudaMemcpy() is better than unified memory. #### F18.1: **GPUs support virtual memory. State, in no more than one sentence each, two evidences of this.** * Two blocks assigned to the same SM cannot see each other’s shared memory. * The existence of unified virtual address and unified memory. #### F18.2: We have seen that using array of structure(`struct`) in a kernel execution is not a good idea. #### F18.2a: **Why?** Because if two threads access two consecutive elements of the array, they cannot be coalesced because they are separated by the other members of the structure. #### F18.2b: How can we fix that? To have several arrays, one for each structure member. #### F18.2c: Can you find a scenario where using an array of structure is indeed a good idea in CUDA kernel execution? \[Use your imagination but be brief and no code is necessary]. If structure members consist of large arrays and threads in a warp are accessing those elements. #### F18.4: Does each block of the same kernel get the same amount shared memory? Justify. Yes, because there is no dynamic shared memory allocation as soon as the kernel is launched. #### F18.5: Does each block of the same kernel get the same number of registers? Justify. In general yes. #### F18.6: In any cuda program, we have computations, communication, and memory access. For each one of them, state one technique to deal with it to get the best overall performance. * **Computation:** Maximizing the number of threads in the system to ensure higher utilization. * **Communication:** Hide it using streams to overall communication and computation. * **Memory access:** Ensure memory access can be coalesced. #### F18.7 a. Having several command queues between the host and a device is needed in OpenCL in order to get as good performance as multiple streams in CUDA. This statement is: ❌ b. Which one of the following is NOT an advantage of streams in CUDA: Allows dynamic parallelism (i.e. kernel calls another kernel). > Advantages of streams in CUDA: > > * Allows parallel kernel execution > * Overlaps communication and computation > * Overlaps simultaneous communications c. An L2 cache miss always results in coalesced memory access: ✅ d. Coalescing is as important for shared memory as it is important for global memory: ✅ e. If large number of threads need to update the same data item. Which technique do we use to ensure correctness: Atomic instructions. #### F17.1: We have seen many issues that can affect the performance of a kernel. State three issues that can affect the performance of a kernel, in no more than one sentence each. * Branch divergence * Non-coalesced memory access * Too much resources per block, reducing number of blocks executed in parallel per SM. #### F17.2: State three useful usages of streams. * Execute multiple kernels at the same time * Overlap communication and computation * Ensure ordered execution for commands in the same stream #### F17.5: In class, we have seen tiling as a useful technique in matrix multiplication. State two scenarios where tiling is useful at: * To allow more usage of shared memory to reduce global memory access * To allow dealing with very large matrices that cannot fit in global memory #### F17.6: We know that CUDA does not allow synchronization among threads in different blocks. Suppose CUDA allows this. State one potential problem that may arise. Not all blocks of the grid are executing at the same time. Some are waiting to be scheduled. This can be a cause of deadlock. #### F17.7: We have seen many type of memories in the GPU. One of them is the local memory. Given that registers are used on per thread basis, what is the point of having a local memory? For local variables that do not fit in a register, like arrays, structures, etc. #### F16.1: State three reasons why a GPU version of a code can be slower than a sequential code even though the code has data parallelism. * Problem size not big enough to produce a lot of parallelism * Communication overhead is to high * There is not enough data parallelism #### F16.3: State one advantage and one disadvantage of warps. Advantages: * Amortize the hardware cost of instruction fetch and decode phases * Simplifies the scheduling Disadvantages: * Lockstep execution can cause branch divergence * Introduces some restrictions on block sizes #### F16.7a: State advantages of CUDA over OpenCL: * More mature → more libraries and APIs * Supports GPU to GPU communication * Gives the programmer more control #### F16.7b: State one advantage of OpenCL over CUDA: * Can be used with other accelerators than GPUs. #### F15.1: We know in CUDA that commands in a stream (e.g. kernel launch, data movement between host and device, etc) are executed in order. Why is this restriction, given that it may lead to some performance loss? Because commands in a stream usually depend on each other (moving data from device to host need to wait till the kernel is done, etc …) so they need to be in-order to ensure correctness. If they are independent, then they can be issues in different streams for parallelism. #### F15.2: We have seen that if-else may lead to branch divergence in a warp due to lockstep execution of instructions. Now, suppose there is a thread that has an \`if\` without \`else\`. Can this also lead to performance loss in some cases? If yes, explain a scenario where there is performance loss. If no, explain why not. No need to write full code, just explain. Yes, it can lead to some performance loss if some threads in the warp have a true condition and others do not. In that case, those who have false, must wait till the others finish the ifpart, leading to performance loss. However, it is not as severe as the if-else. #### F15.3: In OpenCL there is only one queue between the host and each device. So we cannot have several queues between the host and device like streams in CUDA. #### F15.3a: Does this restrict the performance of OpenCL? Justify. No, because the task queue can be configured to be out-of-order, hence ensuring some parallelism. #### F15.3b: Will we gain any performance in OpenCL if we allow multiple queues between the host and the device? If yes, give a scenario where multiple queues give better performance. If no, explain why not. No, we will not. Actually we can lose some performance due to the extra work in managing several task queues instead of one. #### F15.4: Beside overlapping data-transfer and computation, state two other scenarios where streams are useful. * Executing two different kernels in parallel * Streams ensure correctness when commands of a single stream are executed in order #### F15.5: State two characteristics of a problem that makes GPU a good candidate instead of CPU * Massive data parallelism * Compute bound #### F15.6: State three reasons you may want to have several kernels instead of one big kernel. * If you need to synchronize among threads of different blocks * If the different kernels require different geometry * If you want smaller threads with smaller resources to ensure parallelism among blocks in the same SM #### F15.7: Suppose NVIDIA decides to have larger warps in their future GPUs. Give advantages and disadvantages of doing so. Advantages: * More opportunities for memory coalescing * Potentially more parallelism Disadvantages: * Higher probability of thread divergence * Putting more restrictions on the programmer in choosing block size to be a multiple of bigger number #### F15.8: We have discussed a lot the importance of memory coalescing. Also we said that having an L2 cache (servicing all the SMs) helps in global memory coalescing. #### F15.8a: How does L2 helps in memory coalescing? In an L2 miss, a cache block is fetched from the global memory. A cache block is coalesced as it consists of continuous bytes from memory. #### F15.8b: Does the existence of L2 mean that the programmer does not need to pay attention to global memory access to be coalesced? Explain. No, still the program needs to be aware of memory access pattern because accessing separated memory locations means the L2 cache may need to fetch several blocks to satisfy the requirements, which is not coalesced. #### F14.1: A block is not assigned to an SM before it is given all the resources it needs beforehand. #### F14.1a: What are these resources? * registers * shared memory * slots in SM scheduler #### F14.1b: What is the advantage of doing so? zero-time scheduling #### F14.2: What is wrong with that piece of kernel code? How to deal with it if we need to syncthreads both in the if-body and else-body (i.e. ho to change that code yet preserve the semantic)? 
if {
 // ...
 __syncthreads();
} else {
 // ...
 __syncthreads();
}
May result in deadlock if some threads in the warp go to the if-part and others in the else-part. Solution: Move `_syncthreads()` outside the if-else part. #### F14.3: Briefly explain why CUDA code optimized for one GPU might run inefficiently when executed on another model of GPU (assuming warp size is the same). * Different number and sizes of SMs * Different size and architecture of shared memory (e.g. separate or with L1 cache) * Existence and non-existence of L2 cache #### F14.4: A kenel launch is non-blocking from the host perspective. If we have two kernels: kernelA and kernelB. The first kernel produces some results and leave them in the device global memory. The second kernel uses these results to do more calculations. Given the following piece of code at the host: 
// ...
kernelA<<<a, b>>>(arg1);
kernelB<<<a, b>>>(arg1);
**Does kernelB face a problem of starting execution before the results generated by kernelA are ready? Justify.** No, both are assigned to the default stream and stream commands are executed in order. #### F14.5: The fact that instructions in the warp are executed in lockstep makes branch divergence a big performance-loss problem. Then why GPU designers insist on this lockstep design? To amortize the cost of fetching/decoding instructions, and reduce hardware needed for non-computational purposes. #### F14.6: Suppose that your code needs to deal with large amount of data that does not fit in the device memory, explain briefly what you can do to overcome this problem. Assume that applications are usually NOT embarrassingly parallel (i.e. there may be dependencies that may need to be taken into account). * Tiling * Using streams to move data back-and-forth between CPU and GPU to get new data * Make the best use of shared memory #### F13.1: As a CUDA programmer, how does knowing about the concept of warps help you, especially that warps are transparent to the programmer? * In the kernel invocation, chose a number of threads that divides evenly with the **number of threads in a warp**. Otherwise, you will not make the best use of underlying hardware. * Knowing about warps helps writing your code in a way to reduce **branch-divergence** as much as you can. * Knowing about warps helps you access the memory in a way to increase the opportunities of **memory coalescing**. #### F13.2: Suppose we have a compute bound application with enough parallelism. Discuss the pros and cons of each the following two strategies: (i) more blocks per gird and less threads per block (ii) more threads per block but less blocks per grid. Assume the total number of threads is fixed. (i) More Blocks, Less Threads per Block pros: * smaller blocks can make better use of SM resources: when several blocks are assigned to the same SM. cons: * less opportunities to synchronize among threads: because synchronization is done among threads of the same block and here block size is small * If block size turned out to be less than a warp-size then there is a performance loss here. (ii) Less Blocks, More Threads per Block pros: * more opportunities for sharing among threads cons: * Large blocks may not make the best use of resources in an SM because the granularity of assignments to SM is a block granularity. #### F13.5: The line of code below checks for a special case to avoid calling an expensive square root. Describe a situation in which it makes sense for CUDA to do that, and a different situation when it makes no sense (meaning it would be faster to do the square root all the time). Assume that 50% of the time d is equal to 1. ```c if ( d == 1 ) s = 1; else s = sqrt(d); ``` It makes sense if there is no branch divergence, meaning that for all warps the branch is either always taken or always not taken. If there is branch divergence then the code will run more slowly than code always performing the square root since within a warp the execution time will be the sum of both paths through the if. #### S12.4: In FERMI memory hierarchy we have 64KB that can be configured as 48K shared memory and 16KB L1 cache or 48KB L1 cache and 16KB shared memory. Indicate when will you use the first configuration and when will you use the second configuration. If there is a lot of locality in your code regarding data access, then a cache is needed more than shared memory because a cache is very successful to benefit from spatial and temporal locality. But if you want full control of what needs to be close to the SM and do not want it to be evicted, then shared memory is better. #### S12.5: Assume we have M total threads, each of which need some data from the global memory of the GPU. Those threads can be grouped into X blocks with Y threads each (i.e. X*Y=M). Keeping the total number of threads fixed, discuss the effect of increasing X (and decreasing Y to keep M fixed) or increasing Y on bandwidth requirement. Assume the GPU can accommodate M total threads per SM and only 1 block per SM, and the total number of SMs is M (i.e. a maximum of M*M threads can exist in the whole GPU at the same time). Justify your answer. In one hand, more threads per block means more warps. This means more opportunities for coalescing and hence potential reduction in bandwidth. On the other hand, more blocks means they will be spread over several SMs and hence will have access to more L1 caches, which can positively reduce L2 access and hence bandwidth requirement. # Final Exam Prep: Code ## CGMA Calculation Compute to Global Memory Access (CGMA) ratio: The number of FP calculations performed for each access to the global memory within a region in a CUDA program. A good CGMA is in the order of 20 or 30 to overcome slow global memory access. ### 2 Elements per Thread: C\[i] = A\[i] + B\[i] Index of the first element: ```c i = threadIdx.x + (blockIdx.x * blockdim.x)*2; ``` Index of the second element: ```c i + blockDim.x ```